Going Bananas! - Unfolding Program Synthesis with Origami

Autor(es)

Fernandes, Matheus Campos ; de Franca, Fabricio Olivetti ; Francesquini, Emilio

• Tipo de documento: Artigo Científico
• Fonte: INTELLIGENT SYSTEMS, BRACIS 2024, PT II; v. 15413, p. 16-pg., 2025-01-01.

Resumo

Automatically creating a computer program using input-output examples can be a challenging task, especially when trying to synthesize computer programs that require loops or recursion. Even though the use of recursion can make the algorithmic description more succinct and declarative, this concept creates additional barriers to program synthesis algorithms such as the creation and the attempt to evaluate non-terminating programs. One reason is that the recursive function must define how to traverse (or generate) the data structure and, at the same time, how to process it. In functional programming, the concept of Recursion Schemes decouples these two tasks by putting a major focus on the data processing. This can also help to avoid some of the pitfalls of recursive functions during program synthesis, as argued in the paper that introduced the Origami technique. The authors showed how this technique can be effective in finding solutions for programs that require folding a list. In this work, we incorporate other Recursion Schemes into Origami, such as accumulated folding, unfolding, and the combination of unfolding and folding. We evaluated it on the 29 problems of the standard General Program Synthesis Benchmark Suite 1, obtaining favorable results against other well-known algorithms. Overall, Origami achieves the best results in 25% more problems than its predecessor (HOTGP) and an even higher increase when compared to other approaches. Not only that, but it can also consistently find a solution to problems for which other concurrent algorithms report a low success rate. (AU)

• Processo FAPESP: 23/00811-0 - EcoSustain: ciência de dados e computação para o meio ambiente
• Beneficiário: Antonio Jorge Gomes Abelém
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 19/26702-8 - Tendências em computação de alto desempenho, do gerenciamento de recursos a novas arquiteturas de computadores
• Beneficiário: Alfredo Goldman vel Lejbman
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 24/01115-0 - CCD-Cidades Carbono Neutro
• Beneficiário: Liedi Legi Bariani Bernucci
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Ciência para o Desenvolvimento
• Processo FAPESP: 21/06867-2 - Aplicações de teoria do escalonamento para otimizar o uso de energia verde em plataformas de nuvens computacionais
• Beneficiário: Daniel de Angelis Cordeiro
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 21/12706-1 - Regressão simbólica com restrição de forma da função
• Beneficiário: Fabricio Olivetti de França
• Modalidade de apoio: Bolsas no Exterior - Pesquisa