Krzysztof is a professor in the Institute of Computing Science, Poznan University of Technology, and co-founder of the Center for Artificial Intelligence and Machine Learning (CAMIL), https://camil-research.pl His main research areas are program synthesis and improvement using metaheuristics, exact algorithms (SMT/SAT-solver based), and more recently deep neural networks. He's been applying these and other techniques to synthesize general-purpose functions, mathematical models, image analysis programs, and game-playing agents.
Synthesis of recursive functions from examples has historically proved difficult, not least due to issues of non-termination and the often ad hoc methods for addressing this. In this talk, after discussing those challenges and sketching a broader context of program synthesis, I will present a general synthesis method of implicit recursion which operates via an automatically-derivable decomposition of datatype structure by cases, thereby ensuring well-foundedness. The method is applied to recursive functions of long-standing interest and the results outperform recent work which combines two leading approaches and employs `human in the loop' to define the recursion structure. We show that synthesis with the proposed method on benchmark functions is effective not only with metaheuristic algorithms, but even with random search.