O que são funções faseadas (conceitualmente)?

Em um artigo recente do CACM [1], os autores apresentam uma implementação para funções em etapas . Eles usam o termo como se fosse bem conhecido, e nenhuma das referências parece uma introdução óbvia.

Eles dão uma breve explicação (os meus enfatizam e o número de referência mudou; são 22 no original)

No contexto da geração de programas, a programação em vários estágios (MSP, estadiamento, abreviado), conforme estabelecido por Taha e Sheard [2], permite que os programadores adiem explicitamente a avaliação de uma expressão de programa para um estágio posterior (portanto, preparem uma expressão). O estágio atual atua efetivamente como um gerador de código que compõe (e possivelmente executa) o programa do próximo estágio.

No entanto, Taha e Sheard escrevem (ênfase minha):

Um programa de vários estágios envolve a geração, compilação e execução de código, tudo dentro do mesmo processo. Linguagens de vários estágios expressam programas de vários estágios. A preparação e, consequentemente, a programação em vários estágios, atendem à necessidade de soluções de uso geral que não pagam custos indiretos interpretativos em tempo de execução.

Eles então fazem várias referências a trabalhos mais antigos, alegadamente mostrando que a preparação é eficaz, o que sugere que o conceito é ainda mais antigo. Eles não dão uma referência para o próprio termo.

Essas afirmações parecem ortogonais, se não contraditórias; talvez o que Rompf e Odersky escrevam seja uma aplicação do que Taha e Sheard propõem, mas talvez seja outra perspectiva sobre a mesma coisa. Eles parecem concordar que um ponto importante é que os programas (re) escrevem partes de si mesmos em tempo de execução, mas não sei se essa é uma capacidade necessária e / ou suficiente.

Então, o que é encenação, respectivamente, são interpretações de encenação neste contexto? De onde vem o termo?

1. Estadiamento Modular Leve: Uma Abordagem Pragmática à Geração de Código em Tempo de Execução e DSLs Compiladas por T. Rompf e M. Odersky (2012)
2. Programação MetaML e multiestágio com anotações explícitas de W. Taha e T. Sheard (2000)

Que eu saiba, o termo computação faseada foi usado pela primeira vez por Bill Scherlis neste artigo . Antes disso, o termo " avaliação parcial " era usado praticamente para o mesmo conceito, mas a idéia de computação faseada é sutilmente diferente. Ambas as idéias estão relacionadas ao teorema Smn de Kleene .

Se você possui uma função de dois argumentos, mas conhece um argumento, digamos , pode executar parte da computação da função imediatamente usando o conhecimento do primeiro argumento. O que resta a você é uma função cujos cálculos dependem apenas do segundo argumento desconhecido.m ϕ m ( n $\phi(m,n)$$m$$\phi_m(n)$

A ideia da avaliação parcial é calcular a função especializada automaticamente . Dado o código da função original , a avaliação parcial faz uma análise estática para determinar quais bits do código dependem de e quais bits dependem de , e o transforma em uma função que, dada , constrói . O segundo argumento pode então ser alimentado para essa função especializada.φ m n φ ' m φ m$\phi_m(n)$ $\phi$$m$$n$$\phi'$$m$$\phi_m$$n$

A idéia da computação faseada é pensar primeiro na função . É chamada de função "faseada" porque funciona em vários estágios. Depois que o primeiro argumento , ele constrói o código da função especializada . Este é o "primeiro estágio". No segundo estágio, o segundo argumento é fornecido para que faz o resto do trabalho. m φ m φ $\phi'$$m$$\phi_m$$\phi_m$

Portanto, o trabalho da avaliação parcial é transformar o código de uma função comum em uma função faseada . Scherlis previu que essa transformação poderia ser feita por mecanismos mais gerais do que os métodos de avaliação parcial anteriores. O assunto "computação faseada" agora lida com questões como:ϕ $\phi$$\phi'$

• Como definir funções em etapas?
• Quais linguagens de programação e sistemas de tipos devem ser usados ​​para definir funções em etapas?
• Qual é a semântica de tais linguagens?
• Como garantimos a coerência e a correção das funções em etapas?
• Quais técnicas são úteis para a construção automática ou semi-automática de funções em etapas?
• Como provamos a correção de tais técnicas?

A computação em etapas pode ser muito importante na prática. De fato, todo compilador é, de fato, uma computação faseada. Dado um programa de origem, ele constrói um programa de destino traduzido e otimizado, que pode receber a entrada real e calcular o resultado. É difícil escrever programas de computação em etapas na prática, porque precisamos manipular os vários estágios e garantir que as coisas certas sejam feitas no momento certo. Todo mundo que escreveu um compilador teve problemas com esses problemas. Também é difícil escrever programas que escrevem outros programas, sejam eles programas de linguagem de máquina (compiladores), consultas SQL (manipulações de banco de dados) ou código HTML / Server Pages / Javascript (aplicativos da Web) e uma infinidade de outros aplicativos.

Embora as outras respostas sejam tecnicamente corretas, acho que elas não entendem por que os cientistas da computação estão interessados ​​em funções encenadas.

Ao criar funções em etapas, você define programas que geram programas. Um dos grandes objetivos da teoria prática moderna da linguagem é maximizar a reutilização potencial. Queremos tornar possível escrever bibliotecas que não são apenas funções e objetos úteis, mas que ajudam os programadores ao fornecer construções arquitetônicas de ordem superior.

Seria ótimo se pudéssemos nos livrar de todo o código clichê. Deveríamos ser capazes de minimizar a linguagem de especificação. Se quisermos que um despachante orientado a eventos, por exemplo, se comunique com outros despachantes com um determinado design de encadeamento, poderemos especificar isso compactamente, e todos os ouvintes de IO e as conexões de objetos e encadeamentos de E / S deverão poder ser construídos a partir dessa especificação.

As linguagens de domínio tendem a ser as representações compactas que procuramos. Quando as pessoas trabalham em um domínio por um tempo, o idioma usado costuma diminuir a maior parte da duplicação de informações e se tornar uma especificação enxuta. Portanto, essa teoria do estadiamento tende a se tornar um sistema de tradução de idiomas de domínio para o idioma de execução.

Compiladores são tecnicamente estágios, mas erra o objetivo. O objetivo do estadiamento moderno é permitir a criação de programas que criem programas para maximizar a reutilização e automatizar a construção do programa sempre que possível. Seria ótimo se um dia os requisitos funcionais de um programa fossem o programa.

Veja "Programação Generativa" de Czarnecki e Eisenecker (ISBN-13: 978-0201309775).

A resposta é dada na peça da perspectiva técnica do artigo em questão [1]. O problema em consideração é a área de tensão entre código geral e específico:

Os programas podem ser escritos para fins gerais ou especiais. O código de uso geral tem a vantagem de ser utilizável em várias situações, enquanto o código de uso especial pode ser escrito de uma maneira que aproveite as características exclusivas do ambiente de execução e, assim, obtenha eficiência com o custo de reutilização.

É claro que queremos resolver essa tensão, que é obter código geral e implementação específica:

Podemos fazer a pergunta: É possível escrever um código para que seja de uso geral, mas depois se especialize automaticamente na situação em questão durante a execução?

Isso deu origem à idéia de que programas (gerais) (re) se escrevessem em tempo de execução para acomodar uma situação específica:

Como resultado, uma direção importante da pesquisa envolveu a busca por tecnologias de linguagem e compilador que permitam aos programadores escrever código de uso geral que é então correta e eficientemente transformado em código especializado de alto desempenho em tempo de execução.

Eu acho que o JIT de Java é um bom exemplo. Uma ideia em particular é a programação em vários estágios, que Lee explica assim:

Nesta linha de pesquisa, uma das idéias centrais é o conceito de estadiamento. Imaginamos a execução de um programa em uma série de estágios, cada um calculando valores que são usados ​​por estágios posteriores. O que procuramos, então, é escrever o código do programa para que, de alguma maneira, esses estágios sejam aparentes. Se isso for feito, podemos providenciar para que o código do estágio posterior seja compilado em geradores de código que otimizem com os resultados dos cálculos do estágio anterior.

Ou seja, "estadiamento" é uma maneira de observar funções / códigos adequados que identificam fases na computação / execução que podem ser simplificadas, sabendo os resultados das fases anteriores. O atraso no cálculo, como na primeira citação da pergunta, pode ser um efeito colateral necessário para separar os estágios corretamente, mas não é esse o ponto.

Rompf e Odersky mencionam a transformação rápida de Fourier como um exemplo que pode ser instrutivo.

1. A raposa e o porco-espinho: perspectiva técnica de Peter Lee (2012)