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.

[more]
15.03.2017
RuleML Blog Report about Dagstuhl Seminar AAIP'16

AAIP'16 in the RuleML Blog
http://via.aayo.ws/YmI4J

[more]
24.03.2016
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

[more]
1.11.2015
Wikipedia Page on Inductive Programming

José Hernández-Orallo and Ute Schmid created Wikipedia articles for Inductive Programming and Inductive Functional Programming.

[more]
15.01.2015
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.

[more]
07.10.2014
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.

[more]
31.03.2014
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.

[more]
15.12.2012
4th Workshop AAIP 2011

AAIP 2011 Homepage

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.

[more]
12.01.2011

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:

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 ADATE IGOR I IGOR 2.2 IGOR 2.3 Magic Haskeller (standalone/library 0.8.4) IGOR H IGOR H extended
ack 2.47 ⊥ --- ∞ ∞ 9.982/∞ ∞ ∞
add 0.3 --- ∞ ∞ 0.038/0.02 0.372 0.428
append 0.75 Ω 0.494 0.252 0.011/0.05 5.6884 5.5763
car 0.054 < 0.001 0.002 0.004 0.003/0.01 0.0001 0.0001
cdr 0.044 < 0.001 0.002 0.004 0.004/0.01 0.0001 0.0001
clearblock --- --- 0.056 0.058 --- ∞ ---
drop 0.63 --- ∞ 206.99 to be reevaluated ∞ ∞
eq 0.86 --- 0.234 0.141 34.217/10.26 6.0924 6.1524
even 0.1 --- 0.005 0.005 0.183/1.49 0.004 0.0001
evenlist 0.088 --- 0.034 0.042 0.25/0.49 0.004 0.004
evenodd --- --- 0.036 0.405 --- ∞ ∞
evenpos 0.591 0.127 0.678 0.168 5.599/∞ 0.008 0.008
evenslist 206.54 --- ∞ ∞ ∞/∞ 0.02 12.4048
fib 161.53 --- 0.037 0.178 141.744/∞ 1.3161 1.3081
geq 1.24 --- ∞ 4.516 0.941/2.3 0.08 0.08
hanoi --- --- 0.126 0.583 --- 0.056 0.052
insert 2.03 ⊥ 0.007 ∞ ∞ to be reevaluated ∞ 0.052
last 0.407 0.004 0.014 0.021 0.06/0.06 0.0001 0.0001
lasts --- 0.02 14.877 0.829 9.129/∞ 0.02 0.004
length 0.57 0.02 0.016 0.031 0.008/0.01 0.004 0.0001
member 0.67 --- 0.016 0.035 to be reevaluated ∞ ∞
mult 303.93 --- ∞ ∞ 9.892/0.01 ∞ ∞
multadd --- --- ∞ ∞ --- ∞ ∞
multfirst 21.17 0.1 0.021 0.061 1.668/13.96 0.028 0.004
multlast 2.25 0.526 0.048 0.096 0.272/11.97 0.012 0.0001
odd 937.49 --- 0.006 0.006 0.074/0.1 0.004 0.004
oddpos 1.098 0.079 3.479 2.771 5.532/∞ 0.04 0.044
oddslist 209 --- ∞ ∞ ∞/∞ ∞ 1.6521
reverse 33.76 0.868 0.163 0.498 0.109/1.16 0.04 0.0001
shiftl 6.78 0.658 0.039 0.096 1.666/∞ 0.012 0.004
shiftr 6.68 0.13 0.248 0.481 6.376/∞ 0.032 0.008
sort 33.75 --- 0.004 0.006 ∞/0.06 ∞ ∞
sum 21.9 --- ∞ ∞ 0.636/0.1 ∞ 0.128
swap 162.21 1.08 2.201 0.972 ∞/∞ 0.028 0.192
switch 1.31 0.03 0.078 0.394 ∞/∞ 0.048 0.048
take-n ∞ --- ∞ 14.632 0.079/0.14 0.02 0.008
weave ∞ Ω ∞ 0.245 43.746/∞ 0.112 0.116

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:

 

This file was last modified on Thursday February 21, 2019