Improving Evolutionary Program Synthesis through Types, Recursion Schemes, Equality Saturation, and Diversity

Abstract : Program synthesis seeks to automatically generate programs that satisfy a specification, commonly expressed through input-output examples. Despite the progress achieved by genetic programming approaches, synthesizing correct, expressive, and generalizable programs remains challenging due to the vastness of the search space, the difficulty of handling recursion, the occurrence of code bloat, and the tendency of evolutionary populations to converge prematurely. These challenges motivate a synthesis framework that progressively incorporates structural information into the search process. This presentation examines a unified approach to evolutionary program synthesis based on the principle that program search can be made more effective by embedding structural information directly into the synthesis process. Rather than relying solely on evolutionary operators to discover both program structure and behavior, the framework introduces constraints and abstractions that encode relevant properties of valid solutions, reducing the burden placed on the search process and enabling more effective exploration of the space of candidate programs. Taken together, these ideas form a coherent strategy in which different forms of structural guidance are incorporated throughout the synthesis process: types ensure validity, Recursion Schemes guide recursive program construction, Equality Saturation manages equivalent representations, and diversity mechanisms promote sustained exploration. Our experimental results demonstrate that progressively incorporating structural information into the synthesis process substantially improves the effectiveness of genetic programming for the automatic synthesis of functional programs.