Síntese de Programas Funcionais
Síntese de programas é o processo de geração de um programa de computador seguindo um conjunto de especificações, que pode ser uma descrição de alto nível do problema e/ou um conjunto de exemplos de entrada-saída.
A síntese pode ser modelada como um problema de busca, em que o espaço de busca é o conjunto de todos os programas válidos sob uma gramática.
Como o espaço de busca é amplo, força bruta geralmente não é viável, e heurísticas de busca, como a programação genética, também têm dificuldade de navegar sem orientação.
Este texto apresenta dois novos algoritmos de programação genética que sintetizam programas puros, tipados e funcionais: HOTGP e Origami.
HOTGP faz uso do conhecimento fornecido pelos tipos de dados associados à especificação e à gramática interna para restringir o espaço de busca e melhorar o desempenho da síntese.
Sua gramática é baseada na biblioteca padrão da linguagem Haskell (o código sintetizado pode ser compilado diretamente usando qualquer compilador Haskell) e inclui suporte para funções de alta ordem, funções $\lambda$ e polimorfismo paramétrico.
Os resultados experimentais mostram que o HOTGP é competitivo com o estado da arte.
Adicionalmente, Origami é um algoritmo que aborda o desafio de lidar com laços e recursão de maneira eficaz, explorando esquemas de recursão.
A principal vantagem de se escrever um programa utilizando Esquemas de Recursão é que os programas são compostos por modelos bem definidos com apenas algumas partes que precisam ser sintetizadas.
Para destacar as vantagens e desvantagens desta abordagem, resolvemos manualmente todo o benchmark PSB1 usando esquemas de recursão, destacando as partes que deveriam ser evoluídas em comparação com implementações alternativas.
Apresentamos resultados preliminares de uma implementação protótipo, que mostram que, uma vez feita a escolha de qual esquema de recursão usar, o processo de síntese pode ser simplificado, pois cada uma das partes faltantes do modelo é reduzida a funções mais simples, que são ainda mais limitadas por suas próprios tipos de entrada e saída.