- author = "Alberto Moraglio and James McDermott",
- title = "Evolving Programs in the Lambda Calculus using Program Trace Optimisation",
- booktitle = "Genetic Programming Theory and Practice XXII",
- year = "2025",
- editor = "Bogdan Burlacu and Fabricio {Olivetti de Franca} and Alexander Lalejini and Stephen Kelly and Wolfgang Banzhaf",
- series = "Genetic and Evolutionary Computation",
- pages = "233--253",
- address = "Michigan State University, USA",
- month = jun # " 5-7",
- publisher = "Springer",
- keywords = "genetic algorithms, genetic programming, PTO",
- isbn13 = "978-981-95-6397-5",
-
DOI = "
10.1007/978-981-95-6398-2_12",
- abstract = "Program Trace Optimization (PTO) is a framework that provides automatic representation design by separating problem specification from search algorithms. PTO requires 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 PTO ability to work with unrestricted programs as generators. While previously applied with simple random generators, we now explore PTOs 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 context-dependent nature. Additionally, non-trivial LC programs require recursive expressions, which are notoriously difficult to evolve. We demonstrate that PTO naturally captures LC context-dependent aspects and efficiently searches the space of valid LC expressions, with its automatically designed operators proving well suited for evolving recursive expressions.",
-
notes = "lightning talk.
published in 2026 after the workshop",
