News

4th Workshop AAIP 2011

AAIP 2011 Homepage

The 4th Workshop on Approaches and Applications of Inductive Programming 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).

Paper submissions are due on April 3, 2011.

Please visit the AAIP 2011 Homepage and the Call for Papers.

[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 July 08, 2010