Zeitschriftenartikel
Schema-Guided Inductive Functional Programming
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Text/Journal Article
Zusatzinformation
Datum
2012
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Springer
Zusammenfassung
Inductive Program Synthesis or Inductive Programming (IP) is the task of generating (recursive) programs from an incomplete specification, such as input/output (I/O) examples. All known IP algorithms can be described as search in the space of all candidate programs, with consequently exponential complexity. To constrain the search space and guide the search traditionally program schemes are used, usually given a priori by an expert user. Consequently, all further given data is interpreted w.r.t. this schema which now almost exclusively decides on success and failure, depending on whether it fits the data or not. Instead of trying to fit the data to a given schema indiscriminately, in my thesis (Schema-guided inductive functional programmin through automatic detection of type morphisms, 2010) I proposed to utilise knowledge about data types to choose and fit a suitable schema to the data! Recursion operators associated with data type definitions are well known in functional programming, but less in IP. I showed how to exploit universal properties of type morphisms which may be detected in the given I/O examples. This technique allows to introduce generic recursion schemes, such as catamorphisms or paramorphisms, on arbitrary inductive data types in the analytical inductive functional programming system Igor II which was already presented here in a previous issue (Kitzelmann in Künstl. Intell. 25:179–182, 2011).