http://www.dagstuhl.de/13502

December 8 – 11, 2013, Dagstuhl Seminar 13502

Approaches and Applications of Inductive Programming

Organizers

Sumit Gulwani (Microsoft Research – Redmond, US)
Emanuel Kitzelmann (Universität Duisburg – Essen, DE)
Ute Schmid (Universität Bamberg, DE)


1 / 2 >

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 3, Issue 12 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents

Summary

Inductive programming (IP) research addresses the problem of learning programs from incomplete specifications, such as input/output examples, traces, or constraints. In general, program synthesis is a topic of interest to researchers in artificial intelligence as well as in programming research since the 1960s [2]. On the one hand, this research aims at relieving programmers from the tedious task of explicit coding on the other hand it helps to uncover the complex cognitive processes involved in programming as a special domain of complex problem solving. From the beginning, there were two main directions of research -- deductive knowledge based approaches and inductive machine learning based approaches. Due to the progress in machine learning, over the last decades the inductive approach currently seems to be the more promising.

Researchers working on the topic of IP are distributed over different communities, especially inductive logic programming (ILP) [12,6], evolutionary programming [13], functional programming [15,5,10], grammar inference [1], and programming languages and verification [7]. Furthermore, domain specific IP techniques are developed for end-user programming [4,9] and in the context of intelligent tutoring in the domain of programming [8]. In cognitive science, researchers concerned with general principles of human inductive reasoning have constructed computer models for inductive generalization which also have some relation to IP [3,16].

In general, approaches can be classified by (1) the strategy of program construction which can be example-driven or generate-and-test driven; (2) the implicit or explicit restriction bias which can be Horn clauses, functional programs, or domain specific languages possibly with further constraints given as meta-interpreters, templates or program schemes; (3) the possibility to consider background knowledge.

IP research had its first boost in the 1970s in the context of learning Lisp programs from examples. Due to only limited progress, this direction of research decayed and in the 1990s was newly addressed in the context of ILP and evolutionary programming. Again, after first promising results, disappointment set in [14,11]. However, over the last years, a new revival in IP research can be observed in different communities and promising results, for example in the domain of enduser programming, give rise to new expectations.

Therefore, in the Dagstuhl Seminar AAIP we brought together researchers from these different communities as well as researchers of related fields. The possibility to discuss and evaluate approaches from different perspectives helped to (a) gaining better insights in general mechanisms underlying inductive programming algorithms, (b) identifying commonalities between induction algorithms and empirical knowledge about cognitive characteristics of the induction of complex rules, and (c) open up new areas for applications for inductive programming in enduser programming, support tools for example driven programming, and architectures for cognitive systems.

The presentations covered several aspects of inductive programming and were grouped in the topic sessions

  • Inductive Programming Systems and Algorithms (with an introductory talk by Stephen Muggleton),
  • Enduser Programming (with an introductory talk by Sumit Gulwani),
  • Intelligent Tutoring and Grading,
  • Cognitive Aspects of Induction (with an introductory talk by José Hernández-Orallo),
  • Combining Inductive Programming with Declarative Programming and with Other Approaches to Program Synthesis (with an introductory talk by Luc de Raedt).

In an initial discussion round three focus topics were identified and further discussed in working groups

  • Comparing Inductive Logic and Inductive Functional Programming as well as other Approaches to Program Synthesis,
  • Potential New Areas of Applications and Challenges for Inductive Programming,
  • Benchmarks and Metrics.

Concluding Remarks and Future Plans

In the final panel discussion the results of the seminar as well as future plans were identified. Participants stated that they learned a lot about different inductive programming techniques and tools to try. The general opinion was that it was very inspiring to have researchers from different backgrounds. To facilitate mutual understanding it was proposed to give introductory lectures, define the vocabulary of the different groups, collect a reading list, and identify common benchmark problems.

To progress in establishing inductive programming as a specific area of research it was proposed to write a Wikipedia page, and to collect introductory literature from the different areas covered in the seminar. Furthermore, plans for joint publications and joint grant proposals were made.

This seminar was highly productive and everybody hoped that there will be a follow-up in the near future.

References

  1. D. Angluin and C. H. Smith. Inductive inference: theory and methods. Computing Surveys, 15(3):237–269, September 1983.
  2. A. W. Biermann, G. Guiho, and Y. Kodratoff, editors. Automatic Program Construction Techniques. Macmillan, New York, 1984.
  3. P. A. Carpenter, M. A. Just, and P. Shell. What one intelligence test measures: A theoretical account of the processing in the Raven Progressive Matrices test. Psychological Review, 97:404–431, 1990.
  4. A. Cypher. EAGER: Programming repetitive tasks by example. In Human Factors in Computing Systems, Proc. of CHI’91, pages 33–39. ACM Press, 1991.
  5. C. Ferri-Ramírez, José Hernández-Orallo, and M. José Ramírez-Quintana. Incremental learning of functional logic programs. In FLOPS ’01: Proceedings of the 5th International Symposium on Functional and Logic Programming, pages 233–247, London, UK, 2001. Springer-Verlag.
  6. P. Flener and S. Yilmaz. Inductive synthesis of recursive logic programs: Achievements and prospects. Journal of Logic Programming, 41(2–3):141–195, 1999.
  7. Sumit Gulwani. Synthesis from examples: Interaction models and algorithms. In SYNASC, pages 8–14, 2012.
  8. Sumit Gulwani. Example-based learning in computer-aided stem education. To appear in Commun. ACM, 2014.
  9. Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Commun. ACM, 55(8):97–105, 2012.
  10. E. Kitzelmann and U. Schmid. Inductive synthesis of functional programs: An explanation based generalization approach. Journal of Machine Learning Research, 7(Feb):429–454, 2006.
  11. Tessa Lau. Why programming-by-demonstration systems fail: Lessons learned for usable ai. AI Magazine, 30(4):65–67, 2009.
  12. S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, Special Issue on 10 Years of Logic Programming, 19-20:629–679, 1994.
  13. Roland Olsson. Inductive functional programming using incremental program transformation. Artificial Intelligence, 74(1):55–83, March 1995.
  14. J.R. Quinlan and R.M. Cameron-Jones. FOIL: A midterm report. In P. B. Brazdil, editor, Proceedings of the ECML’93, number 667 in LNCS, pages 3–20. Springer, 1993.
  15. U. Schmid and F. Wysotzki. Induction of recursive program schemes. In Proc. 10th European Conference on Machine Learning (ECML-98), volume 1398 of LNAI, pages 214–225. Springer, 1998.
  16. Ute Schmid and Emanuel Kitzelmann. Inductive rule learning on the knowledge level. Cognitive Systems Research, 12(3):237–248, 2011.

Classification

  • Artificial Intelligence / Robotics
  • Programming Languages / Compiler
  • Verification / Logic

Keywords

  • Inductive program synthesis
  • End-user programming
  • Universal artificial intelligence
  • Constraint programming
  • Probabilistic programming
  • Cognitive modeling

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.