Evolving Programs in the Lambda Calculus Using Program Trace Optimisation

Program TraceProgram TraceOptimization (PTOPTO) is a framework that provides automatic representation design by separating problem specification from search algorithms. PTOPTOrequires only a generator creating candidate solutions and a fitness function, enabling any search algorithm to address any problem through a universal solution representation. A key strength is PTOPTO’s ability to work with unrestricted programs as generators. While previously applied with simple random generators, we now explore PTOPTO’s use with sophisticated generators to search the space of Lambda calculus (LC) expressions. LC serves as an ideal test case: a Turing-complete minimal language underlying all functional programming. Despite its simplicity, traditional Genetic Programming and Grammatical Evolution struggle with LC’s context-dependent nature. Additionally, non-trivial LC programs require recursive expressions, which are notoriously difficult to evolve. We demonstrate that PTOPTOnaturally captures LC’s context-dependent aspects and efficiently searches the space of valid LC expressions, with its automatically designed operators proving well suited for evolving recursive expressions.