News

CfP: PEPM'10 at POPL'10

ACM SIGPLAN 2010 Workshop on Partial Evaluation and Program Manipulation (PEPM'10) co-located with POPL'10 in Madrd Spain - January 18-19 2010 - welcomes contributions on techniques for program synthesis and inductive programming. See the Call for Papers at http://www.program-transformation.org/PEPM10.

[more]
19.06.2009
AAIP 09 deadline extension

The submission deadline for AAIP 09 has been extended to May 25th, 2009.

[more]
12.05.2009
Mailing List problems fixed

Due to an Apache bug our mailing list didn't work properly. This should be fixed now. If you still encounter problems, please let us know (contact the admin).

[more]
12.03.2009
Repository Online

Thanks to our project student Thomas Hieber we are glad to announce further progress iat one of our construction sites. He as updated the systems' section and started to build up a repository of example problems. A first set of systems is already compared in a uniform framework. Everybody who is missing a/his/her system is highly encouraged to contribute.

[more]
19.02.2009
AAIP '09 accepted

The next workshop on Approaches and Applications of Inductive Programming 2009 (AAIP'09) will be held in conjunction with the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009). Detailed information can be found at the workshop homepage.

[more]
07.01.2009

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