Publications | Emanuel Kitzelmann

Journal Articles

A Combined Analytical and Search-Based Approach for the Inductive Synthesis of Functional Programs.
Emanuel Kitzelmann (2011).
Künstliche Intelligenz, 25(2):179–182. Extended abstract of my PhD thesis.
[link] [pdf]

Inductive program synthesis addresses the problem of automatically generating (declarative) recursive programs from ambiguous specifications such as input/output examples. Potential applications range from software development to intelligent agents that learn in recursive domains. Current systems suffer from either strong restrictions regarding the form of inducible programs or from blind search in vast program spaces. The main contribution of my dissertation (Kitzelmann, Ph.D. thesis, 2010 ) is the algorithm Igor2 for the induction of functional programs. It is based on search in program spaces but derives candidate programs directly from examples, rather than using them as test cases, and thereby prunes many programs. Experiments show promising results.
Inductive Rule Learning on the Knowledge Level.
Ute Schmid, Emanuel Kitzelmann (2011).
Cognitive Systems Research, 12(3-4):237–248.
[link] [pdf]

We present an application of the analytical inductive programming system Igor to learning sets of recursive rules from positive experience. We propose that this approach can be used within cognitive architectures to model regularity detection and generalization learning. Induced recursive rule sets represent the knowledge which can produce systematic and productive behavior in complex situations – that is, control knowledge for chaining actions in different, but structural similar situations. We argue, that an analytical approach which is governed by regularity detection in example experience is more plausible than generate-and-test approaches.
After introducing analytical inductive programming with Igor we will give a variety of example applications from different problem solving domains. Furthermore, we demonstrate that the same generalization mechanism can be applied to rule acquisition for reasoning and natural language processing.
Inductive Programming: Example-driven construction of functional programs.
Ute Schmid, Martin Hofmann, Emanuel Kitzelmann (2009).
Künstliche Intelligenz, 23(2):38–41.
[link]

We developed an efficient, analytical approach for learning recursive functional programs from examples. Igor2 is a realization of this approach as constructor term rewriting system. We can show that our approach compares very well to other systems of inductive programming and we will discuss applications in the domains of cognitive modelling, end-user programming and automated software engineering.
Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities.
Emanuel Kitzelmann, Ute Schmid (2007).
Electronic Notes in Theoretical Computer Science, 174(1):49–63.
[link] [pdf]

We present a technique for inducing functional programs from few, well chosen input/output-examples (I/O-examples). Potential applications for automatic program or algorithm induction are to enable end users to create their own simple programs, to assist professional programmers, or to automatically invent completely new and efficient algorithms. In our approach, functional programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples for a target function to be implemented are a set of pairs of terms (F(i_i),o_i) meaning that F(i_i)—denoting application of function F to input i_i—is rewritten to o_i by a CS implementing the function F. Induction is based on detecting syntactic regularities between example terms. In this paper we present theoretical results and describe an algorithm for inducing CSs over arbitrary signatures/data types which consist of one function defined by an arbitrary number of rules with an arbitrary number of non-nested recursive calls in each rule. Moreover, we present empirical results based on a prototypical implementation.
Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach.
Emanuel Kitzelmann, Ute Schmid (2006).
Journal of Machine Learning Research, 7:429–454. Revised and extended version of KitzelmannSchmid2005.
[link] [pdf]

We describe an approach to the inductive synthesis of recursive equations from input/output-examples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/O-examples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. These traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term. Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.
Cost Optimality And Predictability Of Parallel Programming with Skeletons.
Holger Bischof, Sergei Gorlatch, Emanuel Kitzelmann (2003).
Parallel Processing Letters, 13(4):575–587.
[link]

Skeletons are reusable, parameterized program components with well-defined semantics and pre-packaged efficient parallel implementation. This paper develops a new, provably cost-optimal implementation of the DS (double-scan) skeleton for programming divide-and-conquer algorithms. Our implementation is based on a novel data structure called plist (pointed list); implementation’s performance is estimated using an analytical model. We demonstrate the use of the DS skeleton for parallelizing a tridiagonal system solver and report experimental results for its MPI implementation on a Cray T3E and a Linux cluster: they confirm the performance improvement achieved by the cost-optimal implementation and demonstrate its good predictability by our performance model.

Conference and Workshop Papers (peer-reviewed)

Two New Operators for IGOR2 to Increase Synthesis Efficiency.
Emanuel Kitzelmann (2011).
In Proceedings of AAIP 2011, 4th International Workshop on Approaches and Applications of Inductive Programming, pages 49–61. University of Southern Denmark.
[pdf]

Inductive program synthesis addresses the problem of automatically generating computer programs from incomplete specifications such as input/output examples. Potential applications range from automated software development to end-user programming to autonomous intelligent agents that learn from experience or observation.We present a recent version of the domain-independent algorithm Igor2 for the inductive synthesis of recursive functional programs, represented as rewriting rules. Igor2 combines classical analytical methods, that detect recursion by matching I/O examples, with search in program spaces as applied by recent generate-and-test methods; thereby widening the class of programs that are synthesizable in reasonable time. In particular, we present two recent improvements over an earlier Igor2 version which significantly increase the efficiency of the synthesis. Functions that were not inducible in several minutes are now induced in several seconds. It has already been shown that an earlier version of Igor2 outperforms other recent systems on several problems. In the empirical evaluation here, we show the significance of the improved synthesis operators by means of more complex problems, most of which were not tractable for Igor2 until now.
From Sensorimotor Graphs to Rules: An Agent Learns from a Stream of Experience.
Marius Raab, Mark Wernsdorfer, Emanuel Kitzelmann, Ute Schmid (2011).
In Artificial General Intelligence, 4th International Conference, AGI 2011, Proceedings, Volume 6830 of LNCS/LNAI, pages 333–339. Springer-Verlag.
[link] [pdf]

In this paper we argue that a philosophically and psychologically grounded autonomous agent is able to learn recursive rules from basic sensorimotor input. A sensorimotor graph of the agent’s environment is generated that stores and optimises beneficial motor activations in evaluated sensor space by employing temporal Hebbian learning. This results in a categorized stream of experience that feeds in a Minerva memory model which is enriched by a time line approach and integrated in the cognitive architecture Psi—including motivation and emotion. These memory traces feed seamlessly into the inductive rule acquisition device Igor2 and the resulting recursive rules are made accessible in the same memory store. A combination of cognitive theories from the 1980ies and state-of-the-art computer science thus is a plausible approach to the still prevailing symbol grounding problem.
I/O Guided Detection of List Catamorphisms: Towards Problem Specific Use of Program Templates in IP.
Martin Hofmann, Emanuel Kitzelmann (2010).
In Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM ’10, pages 93–100. ACM.
[link]

Inductive programming (IP), usually defined as a search in a space of candidate programs, is an inherent exponentially complex problem. To constrain the search space, program templates have ever been one of the first choices. In previous approaches to incorporate program schemes, either an (often very well) informed expert user has to provide a template in advance, or templates are used simply on suspicion, regardless whether they are target-aiming or not. Instead of rather fit the data to the template, we present an approach to fit a template to the data. We propose to utilise universal properties of higher-order functions to detect the appropriateness of a certain template in the input/output examples. We use this technique to introduce catamorphisms on lists in our IP system Igor2.
Porting IgorII from Maude to Haskell.
Martin Hofmann, Emanuel Kitzelmann, Ute Schmid (2010).
In Approaches and Applications of Inductive Programming, 3rd International Workshop, AAIP 2009, Revised Papers, Volume 5812 of LNCS, pages 140–158. Springer-Verlag.
[link]

This paper describes our efforts and solutions in porting our IP system Igor 2 from the termrewriting language Maude to Haskell . We describe how, for our purpose necessary features of the homoiconic language Maude , especially the treatment of code as data and vice versa, can be simulated in Haskell using a stateful monad transformer which makes type and class information available. With our new implementation we are now able to use higher-order context during our synthesis and extract information from type classes useable as background knowledge. Keeping our new implementation as close as possible to our old, we could keep all features of our system.
Inductive Programming: A Survey of Program Synthesis Techniques.
Emanuel Kitzelmann (2010).
In Approaches and Applications of Inductive Programming, 3rd International Workshop, AAIP 2009, Revised Papers, Volume 5812 of LNCS, pages 50–73. Springer-Verlag.
[link] [pdf]

Inductive programming (IP)—the use of inductive reasoning methods for programming, algorithm design, and software development—is a currently emerging research field. A major subfield is inductive program synthesis, the (semi-)automatic construction of programs from exemplary behavior. Inductive program synthesis is not a unified research field until today but scattered over several different established research fields such as machine learning, inductive logic programming, genetic programming, and functional programming. This impedes an exchange of theory and techniques and, as a consequence, a progress of inductive programming. In this paper we survey theoretical results and methods of inductive program synthesis that have been developed in different research fields until today.
Combining Analytical and Evolutionary Inductive Programming.
Neil Crossley, Emanuel Kitzelmann, Martin Hofmann, Ute Schmid (2009).
In Artificial General Intelligence, 2nd Conference, AGI 2009, Proceedings, pages 19–24. Atlantis Press. Best Paper Prize at AGI 2009.
[link] [pdf]

Analytical inductive programming and evolutionary inductive programming are two opposing strategies for learning recursive programs from incomplete specifications such as input/output examples. Analytical inductive programming is data-driven, namely, the minimal recursive generalization over the positive input/output examples is generated by recurrence detection. Evolutionary inductive programming, on the other hand, is based on searching through hypothesis space for a (recursive) program which performs sufficiently well on the given input/output examples with respect to some measure of fitness. While analytical approaches are fast and guarantee some characteristics of the induced program by construction (such as minimality and termination) the class of inducable programs is restricted to problems which can be specified by few positive examples. The scope of programs which can be generated by evolutionary approaches is, in principle, unrestricted, but generation times are typically high and there is no guarantee that such a program is found for which the fitness is optimal. We present a first study exploring possible benefits from combining analytical and evolutionary inductive programming. We use the analytical system Igor2 to generate skeleton programs which are used as initial hypotheses for the evolutionary system Adate. We can show that providing such constraints can reduce the induction time of Adate.
Evolutionary Programming Guided by Analytically Generated Seeds.
Neil Crossley, Emanuel Kitzelmann, Martin Hofmann, Ute Schmid (2009).
In IJCCI 2009 – Proceedings of the International Joint Conference on Computational Intelligence, pages 198–203. INSTICC Press.

Evolutionary programming is the most powerful method for inducing recursive functional programs from input/output examples while taking into account efficiency and complexity constraints for the target program. However, synthesis time can be considerably high. A strategy which is complementary to the generate-and-test based approaches of evolutionary programming is inductive analytical programming where program construction is example-driven, that is, target programs are constructed as minimal generalization over the given input/output examples. Synthesis with analytical approaches is fast, but the scope of synthesizable programs is restricted. We propose to combine both approaches in such a way that the power of evolutionary programming is preserved and synthesis becomes more efficient. We use the analytical system I GOR 2 to generate seeds in form of program skeletons to guide the evolutionary system A DATE when searching for target programs. In an evaluations with several examples we can show that using such seeds indeed can speed up evolutionary programming considerably.
A Unifying Framework for Analysis and Evaluation of Inductive Programming Systems.
Martin Hofmann, Emanuel Kitzelmann, Ute Schmid (2009).
In Artificial General Intelligence, 2nd Conference, AGI 2009, Proceedings, pages 55–60. Atlantis Press.
[link] [pdf]

In this paper we present a comparison of several inductive programming (IP) systems. IP addresses the problem of learning (recursive) programs from incomplete specifications, such as input/output examples. First, we introduce conditional higher-order term rewriting as a common framework for inductive logic and inductive functional program synthesis. Then we characterise the several ILP systems which belong either to the most recently researched or currently to the most powerful IP systems within this framework. In consequence, we propose the inductive functional system IGOR II as a powerful and efficient approach to IP. Performance of all systems on a representative set of sample problems is evaluated and shows the strength of IGOR II.
Analytical Inductive Functional Programming.
Emanuel Kitzelmann (2009).
In Logic-Based Program Synthesis and Transformation, 18th International Symposium, LOPSTR 2008, Revised Selected Papers, Volume 5438 of LNCS, pages 87–102. Springer-Verlag.
[link] [pdf]

We describe a new method to induce functional programs from small sets of non-recursive equations representing a subset of their input-output behaviour. Classical attempts to construct functional Lisp programs from input/output-examples are analytical, i.e., a Lisp program belonging to a strongly restricted program class is algorithmically derived from examples. More recent approaches enumerate candidate programs and only test them against the examples until a program which correctly computes the examples is found. Theoretically, large
program classes can be induced generate-and-test based, yet this approach suffers from combinatorial explosion. We propose a combination of search and analytical techniques. The method described in this paper is search based in order to avoid strong a-priori restrictions as imposed by the classical analytical approach. Yet candidate programs are computed based on analytical techniques from the examples instead of being generated independently from the examples. A prototypical implementation shows first that programs are inducible which are not in scope of classical purely analytical techniques and second that the induction times are shorter than in recent generate-and-test based methods.
Analytical Inductive Programming as a Cognitive Rule Acquisition Device.
Ute Schmid, Martin Hofmann, Emanuel Kitzelmann (2009).
In Artificial General Intelligence, 2nd Conference, AGI 2009, Proceedings, pages 162–167. Atlantis Press.
[link] [pdf]

One of the most admirable characteristic of the human cognitive system is its ability to extract generalized rules covering regularities from example experience presented by or experienced from the environment. Humans’ problem solving, reasoning and verbal behavior often shows a high degree of systematicity and productivity which can best be characterized by a competence level reflected by a set of recursive rules. While we assume that such rules are different for different domains, we believe that there exists a general mechanism to extract such rules from only positive examples from the environment. Our system Igor2 is an analytical approach to inductive programming which induces recursive rules by generalizing over regularities in a small set of positive input/output examples. We applied Igor2 to typical examples from cognitive do- mains and can show that the Igor2 mechanism is able to learn the rules which can best describe systematic and productive behavior in such domains.
Analysis and Evaluation of Inductive Programming Systems in a Higher-Order Framework.
Martin Hofmann, Emanuel Kitzelmann, Ute Schmid (2008).
In KI 2008: Advances in Artificial Intelligence, 31st Annual German Conference on AI, Proceedings, Volume 5243 of LNCS/LNAI, pages 78–86. Springer-Verlag.
[link]

In this paper we present a comparison of several inductive programming (IP) systems. IP addresses the problem of learning (recursive) programs from incomplete specifications, such as input/output examples. First, we introduce conditional higher-order term rewriting as a common framework for inductive program synthesis. Then we characterise the ILP system Golem and the inductive functional system MagicHaskeller within this framework. In consequence, we propose the inductive functional system Igor II as a powerful and efficient approach to IP.
Performance of all systems on a representative set of sample problems is evaluated and shows the strength of Igor II.
Data-driven Induction of Functional Programs.
Emanuel Kitzelmann (2008).
In ECAI 2008 – 18th European Conference on Artificial Intelligence, Proceedings, Volume 178 of Frontiers in Artificial Intelligence and Applications, pages 781–782. IOS Press.

We present a new method and system, called \igorii, for the induction of recursive functional programs from few non-recursive, possibly non-ground example equations describing a subset of the input-output behaviour of a function to be implemented.
Inductive Synthesis of Recursive Functional Programs: A Comparison of Three Systems.
Martin Hofmann, Andreas Hirschberger, Emanuel Kitzelmann, Ute Schmid (2007).
In KI 2007: Advances in Artificial Intelligence, 30th Annual German Conference on AI, Proceedings, Volume 4667 of LNCS/LNAI, pages 468–472. Springer-Verlag.
[link]
Data-Driven Induction of Recursive Functions from Input/Output-Examples.
Emanuel Kitzelmann (2007).
In ECML/PKDD-2007 Workshop on Approaches and Applications of Inductive Programming, AAIP 2007, Proceedings, pages 15–26. Warsaw University.
[pdf]

We describe a technique for inducing recursive functional programs over algebraic datatypes from few non-recursive and only positive ground example-equations. Induction is data-driven and based on structural regularities between example terms. In our approach, functional programs are represented as constructor term rewriting systems containing recursive rewrite rules. In addition to the examples for the target functions, background knowledge functions that may be called by the induced functions can be given in form of ground equations. Our algorithm induces several dependent recursive target functions over arbitrary user-defined algebraic datatypes in one step and automatically introduces auxiliary subfunctions if needed. We have implemented a prototype of the described method and applied it to a number of problems.
An Explanation Based Generalization Approach to Inductive Synthesis of Functional Programs.
Emanuel Kitzelmann, Ute Schmid (2005).
In ICML-2005 Workshop on Approaches and Applications of Inductive Programming, AAIP 2005, Proceedings, pages 15–27. University of Bonn.
[pdf]

We describe an approach to the inductive synthesis of recursive equations from input/outputexamples which is based on the classical two-step approach to induction of functional Lisp programs of Summers (1977). In a first step, I/Oexamples are rewritten to traces which explain the outputs given the respective inputs based on a datatype theory. This traces can be integrated into one conditional expression which represents a non-recursive program. In a second step, this initial program term is generalized into recursive equations by searching for syntactical regularities in the term.
Our approach extends the classical work in several aspects. The most important extensions are that we are able to induce a set of recursive equations in one synthesizing step, the equations may contain more than one recursive call, and additionally needed parameters are automatically introduced.
Cost Optimality and Predictability of Parallel Programming with Skeletons.
Holger Bischof, Sergei Gorlatch, Emanuel Kitzelmann (2003).
In Euro-Par 2003: Parallel Processing, 9th International Euro-Par Conference, Proceedings, Volume 2790 of LNCS, pages 682–693. Springer-Verlag. Distinguished Paper at Euro-Par 2003.
[link]

Skeletons are reusable, parameterized components with well-defined semantics and pre-packaged efficient parallel implementation. This paper develops a new, provably cost-optimal implementation of the DS (double-scan) skeleton for the divide-and-conquer paradigm. Our implementation is based on a novel data structure called plist (pointed list); implementation’s performance is estimated using an analytical model. We demonstrate the use of the DS skeleton for parallelizing a tridiagonal system solver and report experimental results for its MPI implementation on a Cray T3E and a Linux cluster: they confirm the performance improvement achieved by the cost-optimal implementation and demonstrate its good predictability by our performance model.
Design and Implementation of a Cost-Optimal Parallel Tridiagonal System Solver Using Skeletons.
Holger Bischof, Sergei Gorlatch, Emanuel Kitzelmann (2003).
In Parallel Computing Technologies, 7th International Conference, PaCT 2003, Proceedings, Volume 2763 of LNCS, pages 415–428. Springer-Verlag.
[link]

We address the problem of systematically designing correct parallel programs and developing their efficient implementations on parallel machines. The design process starts with an intuitive, sequential algorithm and proceeds by expressing it in terms of well-defined, pre-implemented parallel components called skeletons. We demonstrate the skeleton-based design process using the tridiagonal system solver as our example application. We develop step by step three provably correct, parallel versions of our application, and finally arrive at a cost-optimal implementation in MPI (Message Passing Interface). The performance of our solutions is demonstrated experimentally on a Cray T3E machine.
Inductive Synthesis of Functional Programs.
Emanuel Kitzelmann, Ute Schmid, Martin Mühlpfordt, Fritz Wysotzki (2002).
In Artificial Intelligence, Automated Reasoning, and Symbolic Computation, Joint International Conferences, AISC 2002, Proceedings, Volume 2385 of LNCS/LNAI, pages 337–354. Springer-Verlag.
[link]

We present an approach to folding of finite program terms based on the detection of recurrence relations in a single given term which is considered as the k-th unfolding of an unknown recursive program. Our approach goes beyond Summers’ classical approach in several aspects: It is language independent and works for terms belonging to an arbitrary term algebra; it allows induction of sets of recursive equations which are in some arbitrary ’calls’ relation; induced equations can be dependent on more than one input parameters and we can
detect interdependencies of variable substitutions in recursive calls; the given input terms can represent incomplete unfoldings of an hypothetical recursive program.

Proceedings (Editorship)

Proceedings of AAIP 2011, 4th International Workshop on Approaches and Applications of Inductive Programming.
Emanuel Kitzelmann, Ute Schmid (eds.) (2011).
University of Southern Denmark.
[link] [pdf]
Artificial General Intelligence, 3rd Conference, AGI 2010, Proceedings.
Marcus Hutter, Eric Baum, Emanuel Kitzelmann (eds.) (2010).
Atlantis Press.
[link] [pdf]
Approaches and Applications of Inductive Programming, 3rd International Workshop, AAIP 2009, Revised Papers.
Ute Schmid, Emanuel Kitzelmann, Rinus Plasmeijer (eds.) (2010).
Volume 5812 of LNCS. Springer-Verlag.
[link]
AAIP 2009, Proceedings of the 3rd Workshop on Approaches and Applications of Inductive Programming.
Ute Schmid, Emanuel Kitzelmann, Rinus Plasmeijer (eds.) (2009).
Number 81 of Bamberger Beiträge zur Wirtschaftsinformatik und Angewandten Informatik. University of Bamberg.
[link] [pdf]
ECML/PKDD-2007 Workshop on Approaches and Applications of Inductive Programming, AAIP 2007, Proceedings.
Emanuel Kitzelmann, Ute Schmid (eds.) (2007).
Warsaw University.
[link] [pdf]
ICML-2005 Workshop on Approaches and Applications of Inductive Programming, AAIP 2005, Proceedings.
Emanuel Kitzelmann, Roland Olsson, Ute Schmid (eds.) (2005).
University of Bonn.
[link] [pdf]

Technical Report

The Double-Scan Skeleton and its Parallelization.
Holger Bischof, Sergei Gorlatch, Emanuel Kitzelmann (2002).
Technische Universität Berlin.

Theses

A Combined Analytical and Search-Based Approach to the Inductive Synthesis of Functional Programs.
Emanuel Kitzelmann (2010).
Fakultät für Wirtschafts- und Angewandte Informatik, Universität Bamberg. PhD thesis.
[link] [pdf]

This thesis is concerned with the inductive synthesis of recursive declarative programs and in particular with the analytical inductive synthesis of functional programs. Program synthesis addresses the problem of (semi-)automatically generating computer programs from specifications. In inductive program synthesis, recursive programs are constructed by generalizing over incomplete specifications such as finite sets of input/output examples (I/O examples). Classical methods for induction of functional programs are analytical, that is, a recursive function definition is derived by detecting and generalizing recurrent patterns between the given I/O examples. Most recent methods, on the other side, are generate-and-test based, that is, they repeatedly generate programs independently from the provided I/O examples until a program is found that correctly computes the examples. Analytical methods are much faster than generate-and-test methods, because they do not rely on search in a program space. Therefore, however, the schemas that generatable programs conform to, must be much more restricted. This thesis at first provides a comprehensive overview of current approaches and methods to inductive program synthesis. Then we present a new algorithm to the inductive synthesis of functional programs that generalizes the analytical approach and combines it with search in a program space. Thereby, the strong restrictions of analytical methods can be resolved for the most part. At the same time, applying analytical techniques allows for pruning large parts of the problem space so that solutions can often be found faster than with generate-and-test methods. By means of several experiments with an implementation of the described algorithm, we demonstrate its capabilities.
Inductive Functional Program Synthesis: A Term-Construction and Folding Approach.
Emanuel Kitzelmann (2003).
Technische Universität Berlin. Master’s thesis.

Miscellaneous

Ein kombinierter analytischer und suchbasierter Ansatz zur induktiven Synthese funktionaler Programme.
Emanuel Kitzelmann (2011).
In Ausgezeichnete Informatikdissertationen 2010, Volume D-11 of LNI, pages 141–150. Gesellschaft für Informatik (GI).
[pdf]
Code as Data: Creating Programs which Create Programs with Maude.
Emanuel Kitzelmann (2011).
Invited contribution to the discussion “What Language Do You Use to Create Your AI Programs and Why?”, special topic “Languages of AI” in Künstliche Intelligenz, 26(1):101–103.
[link] [pdf]
Programming Recursive Functions By Examples (Poster Abstract).
Thomas Hieber, Martin Hofmann, Emanuel Kitzelmann, Ute Schmid (2008).
In Proceedings der 9. Jahrestagung der Gesellschaft für Kognitionswissenschaft, KogWis 2008. Nominated (2nd place) for the “Brain Products Poster Preis” at KogWis 2008.
[pdf]

Writing computer programs can be performed in three principle ways: Generating code based on informal specifications of the desired behavior of the program, automated program construction from formal specifications, or constructing programs by generalization over small sets of input/output examples. Research in the artificial intelligence domain of inductive programming (IP) addresses the third approach. From a technical perspective, IP systems can relieve software developers from routine programming task by exploiting test cases
for automatic generation of code (for clear cut subproblems). From a cognitive perspective, IP research investigates the intellectual abilities and skills of human programmers who typically are highly successful in coding programs from input/output examples. Our IP system IGOR (Kitzelmann and Schmid, 2006; Kitzelmann, 2007) induces recursive functional programs from small sets of the first input/output examples with respect to the input data type. We conducted an empirical study to investigate whether inexperienced programmers can produce the examples necessary for IGOR and whether generating examples is less prone to errors than directly producing the program code. Participants were 30 first year computer science students who had participated in a course where recursive functional programming with Scheme was one of the major topics. Each student received a booklett with four programming tasks (“length” of a list, “reverse” a list, is a list of “oddlength”, and “flatten” a nested list). Each students had to give the smallest set of input/output examples for two of the tasks and to write the Scheme code for the other two tasks (sequence of tasks was balanced over subjects and giving examples vs coding was balanced over tasks). Nearly all students failed in giving examples as well as in producing correct program code for the most complex problem “flatten”. For the other three tasks we got clear evidence that while students are able to give the first input/output examples they mostly fail in producing correct code. Besides this general result, an analysis of typicall errors provided some insights in difficulties of recursive programming. The results show that IP systems cannot only support professional programmers but they also give more power to programming novices who are enabled to produce correct code by providing input/output examples.
Induction of Functional Programs based on Relations between I/O Examples.
Emanuel Kitzelmann, Ute Schmid (2006).
In KI 2006: Advances in Artificial Intelligence, 29th Annual German Conference on AI, Poster Abstracts. Extended Poster Abstract.
[pdf]
Inductive Program Synthesis: From Theory to Application.
Ute Schmid, Emanuel Kitzelmann, Fritz Wysotzki (2002).
In Beiträge zum Treffen der GI-Fachgruppe 1.1.3 Maschinelles Lernen (FGML 2002), pages 135–141.