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

24

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)
Rafael
fonte
Que contradição você vê entre as duas declarações? Para mim, eles parecem estar falando da mesma coisa, com ênfase diferente.
Gilles 'SO- stop be evil'
@ Gilles Não preciso de geração / compilação de código de tempo de execução para atrasar a avaliação de algo (veja continuáveis). Pode muito bem ser que seja apenas outra ênfase (admito essa opção na pergunta), mas não sei dizer.
Raphael
Você poderia verificar a Julia programação implementação da linguagem e documentação metaprogramming em @generated functions: julia.readthedocs.org/en/latest/manual/metaprogramming/...
salchipapa

Respostas:

21

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 )ϕ(m,n)mϕ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 nϕm(n) ϕmnϕmϕmn

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 φ mϕmϕmϕ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:ϕ ϕϕ

  • 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.

Uday Reddy
fonte
Tanto quanto posso ver, então a diferença entre computação faseada e avaliação parcial é a forma de ? (há alguns que podem ser obtidos a partir da computação em etapas, mas não da avaliação parcial). ϕ ϕϕ
Ta Thanh Dinh
Portanto, o que você quer dizer com avaliação parcial é uma abstração sobre programação de vários estágios, o que significa avaliação parcial não implica programação de vários estágios, mas a programação com vários estágios implica avaliação parcial. Em que a avaliação parcial pode ser feita em um ou vários estágios, já que o currying em linguagens funcionais não envolve necessariamente vários estágios e gera código em tempo de execução, certo?
Denis631
1
Não exatamente. Um avaliador parcial compila um programa comum em um programa de 2 estágios e depois executa seu primeiro estágio. Na programação faseada, você mesmo escreve o programa de vários estágios.
Uday Reddy
9

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).

ex0du5
fonte
@ Rafael: Aqui está o capítulo três, com o básico sobre domínios e reutilização. Veja até a otimização que você mencionou. A FFT não é realizada por teste para torná-la mais rápida. Isso é feito para que o programador não precise calcular a tabela de valores todas as vezes manualmente, copiá-los para o programa e criar uma grande lista. É para minimizar o trabalho realizado e reutilizar as etapas básicas. Mesmo com desenrolamento de loop. Fazer isso manualmente repete as informações e não pode ser reutilizado.
Ex0du5
Esse ponto de vista DSL parece limitar a preparação para um nível (um compilador DSL dentro do programa), certo?
Raphael
1
@Raphael: Depende realmente do seu ponto de vista. Obviamente, o conceito não adiciona poder computacional quando visto simplesmente como a fonte -> tradução executável. Nós poderíamos simplesmente construir um compilador para a linguagem DS e pronto. De onde vem a força está na iteração. Ao criar bibliotecas que serão usadas e expandidas por projetos no futuro, os estágios naturais aparecem dentro dos limites da biblioteca. Você pode ter uma biblioteca que transforma objeto especificações em fonte para serialização completa, e depois outra biblioteca que constrói a camada de transporte construído sobre alguns especificação expedição ...
ex0du5
1
@ Rafael: A encenação pode mais naturalmente ser feita com vários estágios. Se um pedaço de código tiver seus requisitos alterados muito ao longo do tempo, enquanto outros são muito mais estáveis, pode ser apropriado, devido à "camada de cisalhamento", separar o teste em camadas com interfaces mais estáveis. Você pode afetar menos o sistema com alterações e respeitar uma forma de preparação do princípio de aberto-fechado. Essas são preocupações práticas que não têm necessidade matemática, mas tudo é baseado na praticidade. Não queremos uma única linguagem de compilador, queremos permitir a evolução.
Ex0du5
5

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)
Rafael
fonte