Synthesis of Recursive Functions with Interdependent Parameters.pdfVIP

Synthesis of Recursive Functions with Interdependent Parameters Martin M¨uhlpfordt and Ute Schmid  Methods of Artificial Intelligence, Computer Science Department, Sekr. Fr 5–8, Technical University Berlin, Franklinstr. 28/29, D-10587 Berlin, Germany, Email: schmid@cs.tu-berlin.de Abstract. We present a methodology for the inductive synthesis of recursive functions based on the theoretical framework of context-free tree grammars. The synthesis task is splitted into two parts: First, a small set of posi- tive input/output examples is transformed into an “initial program” by means of heuristic search; second, the initial program is generalized to a recursive function. In this paper we concentrate on the second part of the synthesis task. We will describe our theoretical framework and propose an in duction algorithm. The algorithm works without in- formation about the number of parameters which might occur in the initial program. Subterms which change in a regular way are identified as parameters together with a substitution. It is possible to deal with substitutions which are interdependent between the parameters. Thereby we can infer a greater class of recursive functions than standard generalization-to-n techniques. Keywords. inductive program synthesis, grammatical inference, context free tree grammers 1 Introduction small set of primitive functions (namely car and cdr). In [6] we show that a wider class of input/output ex- Inductive synthesis of recursive programs from ex- amples can be handled using a generic planning algo- amples was a major research topi