A Knowledge-Based Approach to Program Synthesis from Examples

This paper proposes an approach to synthesize functional programs of Backus FP system from input/output instances.Based on a theory of orthogonal expansion of programs,the task of program synthesis is expressed in program equations,and fulfilled by solving them according to the knowledge about the equivalence between programs.Some general knowledge of solving program equations with a number of examples are given in the paper.