Programmieren durch analoges Schließen

Abstract

Es wird ein Ansatz zum Programmieren durch analoges Schließen dargestellt, der auf dem Konzept rekursiver Programmschemata basiert. Ist kein hinreichend ähnliches Beispiel zu einem aktuellen Problem vorhanden, so werden solche Schemata induktiv aus Ein-Ausgabe-Beispielen aufgebaut. Das Gedächtnis ist hierarchisch organisiert, indem ausgehend von konkreten Programmschemata generalisierte Strukturen gebildet und gespeichert werden. Beim analogen Schließen werden folgende Teilprozesse modelliert: Die Ähnlichkeit zwischen einem aktuellen Problem und bereits gelösten Beispielen wird über ein strukturelles Distanzmaß auf (Term-)Bäumen bestimmt. Dieses Ähnlichkeitsmaß definiert gleichzeitig die Modifikationen, die notwendig sind, um ein Beispielprogramm an die neuen Anforderungen anzupassen. Bei erfolgreichem analogem Transfer wird das neu inferierte Schema sowie eine über Beispiel und aktuelles Problem generalisierende Struktur in das Gedächtnis eingefügt. Das Problem des analogen Transfers bei nicht-isomorphen Strukturen wird diskutiert und es werden Lösungsideen aufgezeigt. Der Ansatz ist als erster Prototyp in Lisp implementiert. We propose an approach to programming by analogy which is based on the notion of recursive program schemes. If there are no examples with sufficient structural similarity to a new problem, the program scheme is inferred from the scratch using induction over input-output examples. Program schemes are stored in a hierarchically organized knowledge structure by constructing generalized schemes from concrete programs. Our approach handles the following processes of analogical reasoning: Similarity between new problems and example solutions are calculated by a structural measure defined on trees. In addition, this similarity measure defines which modifications have to be performed to adapt the example solution to the new problem. In case of succesful transfer the new solution together with a generalized structure are stored in memory. The problem of handling non-isomorphic structures is discussed and possibilities for handling transfer in such cases are proposed. Our approach is implemented as a first prototype in Lisp.