Learning functional programs with function invention and reuse
This work addresses the problem of synthesizing smaller, more modular functional programs for inductive functional programming researchers, representing an incremental improvement in program synthesis.
This paper explores the generation of modular functional programs to enable function reuse, aiming to reduce program size. The authors introduce two algorithms and type-based pruning techniques, demonstrating that reuse is important for various problems and identifying two classes of programs that benefit from it.
Inductive programming (IP) is a field whose main goal is synthesising programs that respect a set of examples, given some form of background knowledge. This paper is concerned with a subfield of IP, inductive functional programming (IFP). We explore the idea of generating modular functional programs, and how those allow for function reuse, with the aim to reduce the size of the programs. We introduce two algorithms that attempt to solve the problem and explore type based pruning techniques in the context of modular programs. By experimenting with the implementation of one of those algorithms, we show reuse is important (if not crucial) for a variety of problems and distinguished two broad classes of programs that will generally benefit from function reuse.