Banca de DEFESA: MATHEUS CAMPOS FERNANDES

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
STUDENT : MATHEUS CAMPOS FERNANDES
Date: 31/10/2025
TIME: 12:30
LOCAL: https://meet.google.com/qwr-agud-qcu
TITLE:

Functional Program Synthesis with Higher-Order Functions and Recursion Schemes

PAGES: 128
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUMMARY:

Program synthesis is the process of generating a computer program following a set of specifications, which can be a high-level description of the problem and/or a set of input-output examples.
The synthesis can be modeled as a search problem in which the search space is the set of all the programs valid under a grammar.
As the search space is vast, brute force is usually not viable, and search heuristics, such as genetic programming, also have difficulty navigating it without guidance.
This text presents two novel genetic programming algorithms that synthesize pure, typed, and functional programs: HOTGP and Origami.
HOTGP leverages the knowledge provided by the rich data types associated with the specification and the built-in grammar to constrain the search space and improve the performance of the synthesis.
Its grammar is based on Haskell's standard base library (the synthesized code can be directly compiled using any standard Haskell compiler) and includes support for higher-order functions, $\lambda$-functions, and parametric polymorphism.
Experimental results show that HOTGP is competitive with the state of the art.
Additionally, Origami is an algorithm that tackles the challenge of effectively handling loops and recursion by exploring Recursion Schemes.
The main advantage of writing a program using Recursion Schemes is that the programs are composed of well-defined templates with only a few parts that need to be synthesized.
Preliminary results on a prototype implementation show that, once the choice of which recursion scheme is made, the synthesis process can be simplified.
The first implementation of Origami is able to synthesize solutions in several Recursion Schemes and data-structures when evaluated in $3$ different benchmarks, achieving a considerable improvement over its prototype.
Results also show that it is competitive with other GP methods in the literature, as well as LLMs.
The latest version of Origami employs AC/DC, a novel procedure designed to improve the search-space exploration.
Experimental results show that it achieves considerable improvement over its previous version by raising success rates on every problem.
Compared to similar methods in the literature, it has the highest count of problems solved with success rates of $100\%$, $\geq75\%$, and $\geq25\%$ across all benchmarks.
In $18\%$ of all benchmark problems it stands as the only method to reach $100\%$ success rate, being the first known approach to achieve it on any problem in PSB2.
It also demonstrates competitive performance to large language models, achieving the highest overall win-rate against Copilot among all GP methods.

 

COMMITTEE MEMBERS:
Presidente - Interno ao Programa - 1932365 - FABRICIO OLIVETTI DE FRANCA
Membro Titular - Examinador(a) Externo ao Programa - 3277486 - MARIO LESTON REY
Membro Titular - Examinador(a) Externo ao Programa - 1604131 - JERONIMO PELLEGRINI
Membro Titular - Examinador(a) Externo à Instituição - MARCIO BASGALUPP - UNIFESP
Membro Titular - Examinador(a) Externo à Instituição - ALCIDES FOSENCA - Univ Lisboa
Membro Suplente - Examinador(a) Interno ao Programa - 1722875 - DAVID CORREA MARTINS JUNIOR
Membro Suplente - Examinador(a) Externo à Instituição - GISELE LOBO PAPPA - UFMG
Membro Suplente - Examinador(a) Externo à Instituição - ADOLFO GUSTAVO SERRA SECA NETO - UTFPR