INDUCTIVE FUNCTIONAL PROGRAMMING USING INCREMENTAL PROGRAM TRANSFORMATION

The paper presents a system, ADATE, for automatic functional programming. ADATE uses specifications that contain few constraints on the programs to be synthesized and that allow a wide range of correct programs, ADATE can generate novel and unexpected recursive programs with automatic invention of recursive auxiliary functions. Successively better programs are developed using incremental program transformations. A key to the success of ADATE is the exact design of these transformations, and how to systematically search for appropriate transformation sequences.