Content
News
Dagstuhl Seminar on Inductive Programming
The 7th AAIP Workshop on Approaches and Applications of Inductive Programming is accepted as Dagstuhl Seminar 17382 and will take place September 17 to 20, 2017. The workshop is jointly organized by Ute Schmid (University of Bamberg), Stephen Muggleton (Imperial College London), and Rishabh Singh (MIT and Microsoft Research).
For more information, see the Dagstuhl Seminar Page.
RuleML Blog Report about Dagstuhl Seminar AAIP'16
AAIP'16 in the RuleML Blog
http://via.aayo.ws/YmI4J
CACM on Inductive Programming
The review article “Inductive programming meets the real world” by
Gulwani,
Hernández-Orallo,
Kitzelmann,
Muggleton,
Schmid, and
Zorn
has been published in the Communications of the ACM, Vol. 58 No. 11, Pages 90-99. 10.1145/2736282
see fulltext
Wikipedia Page on Inductive Programming
José Hernández-Orallo and Ute Schmid created Wikipedia articles for Inductive Programming and Inductive Functional Programming.
Dagstuhl Seminar "Approaches and Applications of Inductive Programming"
José Hernández-Orallo (Polytechnic University of Valencia, ES), Stephen H. Muggleton (Imperial College London, GB), Ute Schmid (Universität Bamberg, DE) and Benjamin Zorn (Microsoft Research - Redmond, US) organize Dagstuhl Seminar 15442 "Approaches and Applications of Inductive Programming" scheduled for October 25 to 30, 2015.
The seminar is a continuation of the AAIP workshop series.
Please visit the AAIP 15 Homepage.
Report of Dagstuhl Seminar
We're pleased to inform you that the report of Dagstuhl Seminar 13502 is now published as part of the periodical Dagstuhl Reports.
The report is available online at the DROPS Server.
Dagstuhl Seminar "Approaches and Applications of Inductive Programming"
Ute Schmid (University of Bamberg), Emanuel Kitzelmann (University of Duisburg-Essen), Sumit Gulwani (Microsoft Research) and Marcus Hutter (Austrian National University) organize Dagstuhl Seminar 13502 "Approaches and Applications of Inductive Programming" scheduled for Monday, December 09 to December 11, 2013. The seminar is a continuation of the AAIP workshop series.
Please visit the AAIP 13 Homepage.
4th Workshop AAIP 2011
Ute Schmid and Emanuel Kitzelmann organize the 4th Workshop on Approaches and Applications of Inductive Programming. It will take place on July 19, 2011, in Odense, Denmark. Co-located events are the 13th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2011) and the 21st International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2011).
Details can be found on the AAIP 2011 Homepage.
Repository
A repository of benchmark problems is the starting point for a competitive environment in which state-of-the-art inductive programming systems can match with each other. Based on a set of commonly known example problems, the most up-to-date IP systems ADATA, MagicHaskeller, Igor, Igor2.2, and Igor2.3 have been evaluated in a common framework. This initial repository is based on a student project by Thomas Hieber in winter term 2008/2009.
Everybody who is missing a/his/her system is highly encouraged to contribute!
Classification
The systems' classification is based on the following two papers:
-
Hofmann, Martin ; Kitzelmann, Emanuel ; Schmid, Ute: A unifying framework for analysis and evaluation of inductive programming systems. In: Hitzler, Pascal ; Hutter, Marcus (Hrsg.) : Proceedings of the Second Conference on Artificial General Intelligence(Second Conference on Artificial General Intelligence (AGI-09) Arlington, Virginia March 6-9 2009). . : ., 2009.
-
Hofmann, Martin ; Kitzelmann, Emanuel ; Schmid, Ute: Analysis and Evaluation of Inductive Programming Systems in a Higher-Order Framework. In: Dengel, A. ; Berns, K. ; Breuel, T. M. ; Bomarius, F. ; Roth-Berghofer, T. R. (Hrsg.) : KI 2008: Advances in Artificial Intelligence (31th Annual German Conference on AI (KI 2008) Kaiserslauten September 2008). Berlin : Springer, 2008, p. 78-86. (LNAI vol. 5243)
Symbol Table
Symbol | Description | Symbol | Description |
---|---|---|---|
C | Constructors | rhs | Right Hand Side |
FT | Function symbols of the functions to be synthesized | {·} | Singleton Set |
FB | Symbols of predefined functions | º | Restricted/Unconditional Rules |
FI | Function variables (function invention) | • | Unrestricted/Conditional Rules |
E+ | Positive Examples | ∅ | Empty Set |
E- | Negative Examples | ilc | If-Let-Case |
BK | Background Knowledge | ∞ | Timeout (after 10 Minutes) |
χM | High-Order-Functions | ⊥ | False Result |
lhs | Left Hand Side | --- | Not Tested |
Characteristics
This is a short comparison of the system features in respect to their power and limits by comparing the quantity of constructors, synthesisable functions, predefined functions, function variables, examples (+/-), background knowledge and if they are capable of dealing with high-order-functions.
C | FT | FB | FI | E+ | E- | BK | χM | |
---|---|---|---|---|---|---|---|---|
ADATE | • | {·} | • | • | • | • | • | ∅ |
IGOR I | • | {·} | ∅ | • | º | ∅ | ∅ | ∅ |
IGOR II | • | • | • | • | º | ∅ | º | ∅ |
Magic Haskeller | • | {·} | • | ∅ | • | • | • | º |
Restriction Bias
The focus here is on the function term's left-hand-side, right-hand-side and on the constructs employed along the synthesis (if-let-case).
F(i1,...,in)/lhs | rhs | vi/ui | |
---|---|---|---|
ADATE | ii ∈ χT | TC(χT) | ilc |
IGOR I | ii ∈ TC(χT) | TC(χT) | - |
IGOR II | ii ∈ TC(χT) | TC(χT) | i |
Magic Haskeller | composition of functions from BK, higher-order via paramorphisms |
Programming Tasks
None of the problems were specially built to fit the needs of the system in order to be most efficient. Some problems were not tested on all of the systems (clearblock, hanoi...) - in this case "---" is used. MagicHaskeller for instance was used in a customized version, which is available for download in the download section. As there is a big difference in the usage of library vs. standalone MagicHaskeller both were tested since it might be interesting to see them in comparison. Igor1 is having trouble with natural numbers/peano numbers so problems consisting of those were skipped.
The generation of suitable input/output examples was basically aimed to keep them as easy and small as possible. It is not intended to fiddle around in order to make one system shine - but there are some problems where certain assumptions were to be made (especially with igor). But the most basic principle creating the inputs was to start with a small and easy set. As some systems demanded more/less examples along the way - some customizing was necessary in order to get any results. This may have led to a slightly incoherent approach on the large scale - but the intention was to create this repository to begin with, elaboration and tweaking intended and strongly encouraged. This is why every example specification used can be accessed, improved and re-evaluated.
All the Problems were executed on a Pentium 4 3.0GHz machine with 1024 MB RAM.
Problem Descriptions:
Both Igor2 and ADATE sometimes had to be eqipped with background knowledge in order to get some results. The functions provided are listed along with a short description of the problems in the repository. Note that MagicHaskeller's Library file always includes background knowledge.
Problem | Description | BK |
---|---|---|
ack | Ackermann-Function | |
add | Addition | |
append | Append two lists | |
car | Head of a list | |
cdr | Tail of a list | |
clearblock | Clear a Specific Block From a Blocksworld-Tower | |
drop | Drop the first n elements from a list starting at the front | |
eq | Equality of numbers | |
even | Even numbers | |
evenlist | List of even numbers | |
evenodd | Even < Odd simultaneously | |
evenpos | Filter even field positions from a list | |
evenslist (alleven) | Only even numbers in a list | |
fib | Fibonacci numbers | |
geq | Greater than or equal | |
hanoi | Towers of Hanoi | |
insert | Insert into list | lt (lower than) |
last | Last element of a list | |
lasts | Combine the last elements of a list of lists to a new list | |
length | Lenght of a list | |
member | Test if element is member of a list | |
mult | Multiplication | |
multadd | Multiplication < Addition simultaneously | |
multfirst | Replace every list element with the head | |
multlast | Replave every list element with the last element | |
odd | Odd numbers | |
oddpos | Filter odd positions from a list | |
oddslist (allodds) | Only odd numbers in a list | |
reverse | Reverse list | |
shiftl | Shift all list elements to the left | |
shiftr | Shift all list elements to the right | |
sort | Sort a list | insert, lt (lower than) |
sum | Sum over all list elements | |
swap | Swap first and last list element | |
switch | Switch elemnts in a list pair-wise starting up front | |
take-n | Take the n first elements from a list | |
weave | Sew two lists together |
Further problems to be tested in the future:
- AND
- Binary Search
- Tree Deletion
- Binomial Coefficient
- Cartesian Product
- Check for Duplicates (lists)
- Count
- Factorial
- "Go East" (Michalsky Trains)
- >
- Halves (lists)
- Insert Last (lists)
- Intersect (lists)
- Locate Substring
- <
- Max
- Max Delete
- Merge (sorted lists)
- Min
- Min Delete
- Modulo
- OR
- Pack (lists)
- Partition (lists)
- Path Finding
- Permute
- Powerset (lists)
- Split (lists)
- Square Root
- String Comparison
- Transpose a Matrix
- Zip/Unzip (lists)
- DNF/CNF/NNF (logic)
- ...
Downloads:
- igor1 problems
- igor2 problems
- igor2 benchmark tool
- customized MagicHaskeller library
- MagicHaskeller problems