Automatisches Programmieren/Automatic Programming

Ute Schmid und Jens Waltermann (Tutor)

Institut für Informatik, FB Mathematik-Informatik, Universität Osnabrück

Praktikum und Seminar im Sommersemester 2002
(programming lab and seminar course, summer term 02)

Kategorie: KI, Vertiefung/Category: AI, advanced

Course language: English

Einführung in Automatisches Programmieren als Teilgebiet des wissensbasierten Software-Engineering (KBSE). Schwerpunkt: deduktive und induktive Programmsynthese. Programmtransformation, das System KIDS; Programmkonstruktion mittels konstruktivem Theorembeweis; Induktion rekursiver funktionaler Programme aus Ein-Ausgabe-Beispielen und Berechnungsspuren; Induktive logische Programmierung und Programmsynthese; Programmieren durch Vormachen für die Endbenutzerprogrammierung; Beziehungen zum Lernen von Strategien und Kontrollregeln.
Im Rahmen des Praktikums werden spezielle Themen aus dem Bereich der Programmsynthese in Zweier-Gruppen bearbeitet: von der Präzisierung der Aufgabenstellung, über die Rezeption der notwendigen Literatur, zur Formalisierung, Implementierung und Evaluation. Programmiersprache je nach Thema ML, Lisp oder Java.
Empf. Semester: 4. Sem. und höher (erwünscht: Vorlesung Funktionale Programmierung)

Introduction to automatic programming as research area of knowledge-based software-engineering (KBSE), focussing on deductive and inductive program synthesis. Programm transformation, the system KIDS; program construction as constructive theorem proving; inductive inference of recursive programs from I/O examples and traces; inductive logic programming; programming by demonstration for enduser programming; relations to learning of strategies and constrol rules/policies.
In the lab course, selected topics in program synthesis are worked on in groups of two students, covering task specification, literature studies, formalization, implementation, and evaluation. Programming language is ML, Lisp, or Java.
Recommended for 4th or higher semester (helpful background: lecture `Functional Programming')

Hours and Contact Credits Seminar Schedule and Syllabus Programming Lab Topics Students

Hours and Contact

MI 16:00-17:30 in 31/322
Contact: Ute Schmid, schmid@informatik.uni-osnabrueck.de
Office Hours: MO 15:00-16:00 Uhr u.n.V. in 31/318
Tutor (teaching assistant): Jens Waltermann

Credits

It is possible to participate at the seminar course only and obtain a "Seminarschein" (3 credit points): Consultations with the supervisor as scheduled, seminar talk (slides should be provided for online linking); regular participation in class (very necessary for discussions).
The lab course can only be taken together with the seminar to obtain a "Praktikumschein" (6 credit points).
For cognitive science students this seminar course is classified as "optional course in AI" (4/12 credit points).

Schedule and Syllabus

03.04. Introduction -- Topics in Automatic Programming
10.04. Selection of Topics
17.04. (14-16: Talk in IFC) Jens Waltermann: Inductive Program Synthesis for XSL
24.04. no class
08.05. Robert Mertens: Similarity of Programming Terms
15.05. no class
22.05. (Pfingstferien)
29.05. discussion
05.06. no class
12.06. Bernd Pachur: Function Application in Planning
19.06. Christopher Loerken: State-based Planning (10 a.m.)
26.06. Christopher Loerken: Planning in IPAL
03.07. no class
10.07. Martin Beckmann: Programming by Analogy in IPAL
------ programming lab work
15.08. report of lab work by Martin Beckmann and Christopher Loerken (and afterwards... a movie)

A selection of topics: Knowledge-based software engineering (KBSE) is an research area concerned with the application of AI technology to support development and evaluation of software systems. Active research is in the domains of specification acquisiton, program synthesis, program reuse, program verification and validation. Automatic programming as a part of KBSE is focussing on machine support for the programming process. Program synthesis, finally, is concerned with automatic (or interactive) generation of program code from specifications. In this course, we are focussing on inductive and deductive synthesis methods. Inductive synthesis is a special area of machine learning: the behavior of a desired (small) program is specified by some input/output examples and the synthesis algorithms generalizes over them, typically constructing a recursive program. Deductive synthesis means the derivation of a program from a complete and formal specification either by application of transformation rules or by a constructive proof.

General introductions
- Flener, P. (1995). Logic Program Synthesis from Incomplete Information. Kluwer. (chap. 1-3)
- Barr, A. and Feigenbaum, E. A. (Eds.) (1982). The Handbook of Artificial Intelligence, Vol. 2, chap. 10 "Automatic Programming".
- Lowry, M. and Duran, R. (1989). Knowledge-based software engineering. In A. Barr, P. R. Cohen and E. A. Feigenbaum (Eds.), Handbook of Artificial Intelligence, Vol. 4, pp. 241-322.
- Schmid, U. (2001, submitted habilitation thesis). Inductive Synthesis of Functional Programs -- Learning Domain-Specific Control Rules and Abstract Schemes. [GZipped Postscript, 447 pages] (chap. 6)
The classical approach
- Survey: D.R. Smith (1984) The synthesis of LISP programs from examples: A survey. In A.W. Biermann, G. Guiho, and Y. Kodratoff (Eds.), Automatic Program Construction Techniques (pp. 307-324). Macmillan.
- P.D. Summers (1977). A methodology for LISP program construction from examples. Journal ACM, 24(1), 162-175.
- G. Le Blanc (1994). BMWk revisited: Generalization and formalization of an algorithm for detecting recursive relations in term sequences. In F. Bergadano and L. de Raedt, Machine Learning, Proc. of ECML-94, pages 183-197, Springer.
- J.P. Jouannaud and Y.Kodratoff (1979). Characterization of a class of functions synthesized from examples by a Summers like method using a `B.M.W.' matching technique. In IJCAI-79, pages 440-447, Morgan Kaufmann.
- Y. Kodratoff and J.Fargues (1978). A sane algorithm for the synthesis of LISP functions from example problems: The Boyer and Moore algorithm. In Proc. of the AISE Meeting Hambourg, pages 169-175.
- Schmid, U. and Wysotzki, F. (1998). Induction of recursive program schemes. In Proceedings of the 10th European Conference on Machine Learning (ECML-98) (pages 214-225). Springer.
- Schmid, U. (2001, submitted habilitation thesis). Inductive Synthesis of Functional Programs -- Learning Domain-Specific Control Rules and Abstract Schemes. [GZipped Postscript, 447 pages] (chap. 7, Folding of Finite Program Terms)
Learning flow of control from traces
- Stefan Schrödl & Stefan Edelkamp (1999). Inferring Flow of Control in Program Synthesis by Example. KI, Bonn, pages 171-182, LNAI, Springer.
- Programming by Example
  esp.: Tinker, A Programming by Demonstration System for Lisp
  H. Lieberman (1993). Tinker: A Programming by Demonstration System for Beginning Programmers, in Allen Cypher (Ed.), Watch What I Do: Programming by Demonstration, MIT Press.
Theoretical background: Grammar inference
- Gold, E. (1967). Language identification in the limit. Information and Control, 10, 447-474.
- D. Angluin (1984). Inductive Inference: Efficient Algorithms. In A.W. Biermann, G. Guiho, and Y. Kodratoff (Eds.), Automatic Program Construction Techniques (pp. 503-515). Macmillan.
- Sakakibara, Y. (1997). Recent advances of grammatical inference. Theoretical Computer Science, 185, 15-45.
Inductive Logic Programming
- Mitchell, T. (1997). Machine Learning. McGraw-Hill. chap. 10.
- Lavrac, N., Dzeroski, S. (1994). Inductive Logic Programming. Techniques and Applications. New York.
- Muggleton, S., De Raedt, L. (1994). ILP: Theory and Methods. Journal of Logic Programming, 19,20. pp. 629.
Program Transformation
- Burstall, R.M. and Darlington, J. (1977). A transformation system for developing recursive programs. JACM, 24(1), 44-67.
- Broy, M. and Pepper, P. (1981). Program development as formal activity. IEEE Transactions on Software Engineering, SE-7(1), 14-22.
- Smith, D. R. (1990). KIDS: a semiautomatic program development system. IEEE Transactions on Software Engineering, 16(9), 1024-1043.
  (Publications of the Kestrel Institute)
  The System: KIDS
- Pepper P. and Smith, D. R. (1996). A High-Level Derivation of Global Search Algorithms (with Constraint Propagation). Science of Computer Programming.
- Giesl, J. (1999). Context-Moving Transformations for Function-Verification. Proc. of the 9th Int. Conf. on Logic-Based Program Synthesis and Transformation (LOPSTR-99), pp. 293-312. Springer LNCS 1817. [local copy, ps]
Deductive Synthesis and Verification
- Green, C. (1969). Application of theorem proving to problem solving. IJCAI 1.
- Manna, Z. and Waldinger, R. (1992). Fundamentals of deductive program synthesis. IEEE Transactions on Software Engineering, 18(8), 674--704.
- Kreitz, C. (1998). Program Synthesis. In W. Bibel and P. Schmitt (Eds.), Automated Deduction - A Basis for Applications (chap. III.2.5), 105-134. Kluwer.
- Program verification with [Isabelle] [Links to other verification/synthesis systems]
Programming by analogy
- Dershowitz, N. (1986). Programming by analogy. In J. C. R.S. Michalski and T. Mitchell (Eds.), Machine learning - an artificial intelligence approach (volume 2, pages 393-422). Los Altos, CA: Morgan Kaufmann.
- Hasker, R. W. (1994). The replay of program derivations. [thesis, 200+ pages, pdf]
Knowledge-based software-engineering (KBSE)
- see papers published by the automated software engineering group of the NASA [ASE Home]

Practical Links:

Programming Lab Topics

There are a variety of topics in relation to my IPAL project [IPAL home] -- universal planning and plan to term transformation for generation of traces, folding of finite terms, programming by analogy.
Further problem domains are: Applying automatic theorem provers for synthesis, integrating folding in transformational synthesis, comparing ILP and functional approaches, combining proof planning and inductive program synthesis, policy learning and inductive program synthesis.

Students

[mailto-allstudents]

Top of Page