The FLIP System

A Functional Logic Inductive Programming System

Copyright 1999-2001 The MIP Group: Ferri-Ramírez, Cèsar; Hernandez-Orallo, José; Ramirez-Quintana, M.José


Presentation:

The FLIP system is an application that implements a framework for the Induction of Functional Logic Programs (IFLP) from facts. This can be seen as an extension to the now consolidated field of Inductive Logic Programming (ILP). Inspired in the inverse resolution operator of ILP, the system is based on the reversal of narrowing, the more usual operational mechanism for Functional Logic Programming.

The main advantages of FLIP system over the most used ILP systems are a natural handling of functions, without the use of mode or determinism declarations, and many others inherited from the power of narrowing wrt resolution.

The System:

You can download the whole system package (FLIP v.0.7) for academic use only here. It includes the C++ sources and many example datasets. Once downloaded and decompressed the software, follow the readme file and run the shell-script for installation on Unix-like machines.
DISCLAIMER & COPYRIGHT: The software has been checked on a Pentium machine under Linux version 2.2.12-20. It 'should' compile on any other system with an ANSI C compiler possibly under slight modifications. In this regard, you can make any modification to the software, provided you always make the changes explicit and refer to its original authors. Obviously, we are not responsible for any damage caused by the use or misuse of this software. If you find any bug please contact the authors. For commercial use do contact the authors.
If the installation is successful, you can directly type:

flip -?

and you will have the following usage information:

######################### FLIP System (v0.7) ##########################

usage: ./flip [-t] [-b background_file] [-u] [-e] [-n] [-f] [-p depth]
[-s steps] positive_examples_file [negative_examples_file]
    -t          Switches off the equation termination filter.
    -b file     Uses the specified file as the background knowledge.
    -u          Uses the union operator in the first step.
    -e          Introduces the Background functions in the examples.
    -n          Inverse narrowing with full program clauses combination.
    -f          Stops immediately when a program is found that covers all the examples.
    -p depth    Depth limit of the narrowing solver(default 19).
    -s steps    Maximum number of steps of the main induction loop(default 10).

For more information please download the user manual and enjoy FLIP . Let you be surprised by FLIP's learning abilities.

DataSets:

The FLIP system accepts both positive and negative examples, from two files .pex and .nex respectively.
The generated program has extension .ple.
Examples consist of sets of equations, with its rhs. normalised wrt. the program to be induced.
Background can also be used as a conditional functional logic program. Note that any logic program can be expressed as a conditional functional logic program. Therefore, virtually any logic program can be used as background knowledge as well as functional definitions.  FLIP must be given the function symbols from the background knowledge that should be used in the definition of the function to be learned.

As you can see in the following results, The FLIP system induces the 'correct' programs from very few examples.
There is no need for good examples (in the sense of  Ling), nor Basic Representative Sets (BRS) such as FOIL, GOLEM, Progol, amongst others, require.
A random generator of both ILP & IFLP datasets is under construction.
You can download the complete zipped dataset and the intended programs from here. These datasets are also included in the whole package
 

Results:

Simple non-recursive programs without background knowledge:

Program
Description
Data Sample
Src
Steps
Time
(sec.)
top(push(X,Y)) = Y  Top element of a stack. top.pex (4 eqs.)
top.nex (3 eqs.)
  0  1.10
if(true,X) = X  if function   0  
ifthenelse(true,X,Y) = X 
ifthenelse(false,X,Y) = Y
 if-then-else function (-u option 
 with union option).
  0  1.40
not(true) = false 
not(false) = true
 logical negation (-u option 
 with union option).
  0  0.04
or(true,X) = true 
or(false, X) = X
  ( -u option 
 with union option).
   0.06 
and(false,X) = false 
and(true, X) = X
  (-u option 
 with union option)
  0  0.05 
enjoysport(sunny, X1, X2, X3, X4, X5) = yes, 
enjoysport(cloudy, X1, X2, X3, X4, X5) = yes
The EnjoySport learning task where the arguments represent: 
(Sky, AirTemp, Humidity, Wind, Water, Forecast)
enjoy.pex
enjoy.nex
 with union option.
Mitchell97 
pp. 21,40
0  1.18
playtennis(overcast, X1, X2, X3) = yes 
playtennis(sunny, X1, normal, X3) = yes 
playtennis(rain, X1, X2, weak) = yes
The playtennis learning task (a decision tree) 
where the arguments represent: 
(Outlook, Temperature, Humidity, Wind)
playtennis.pex
playtennis.nex
 with union option.
Quinlan, 
Mitchell97 
pag. 59
0  0.55
cup(y, up, X1, X2, n, y, X3) = true, 
cup(y, up, X1, X2, side, y, X3) = true
The cup learning task 
where the arguments represent: 
BottomIsFlat, Concavity (up, not-up, no), 
Expensive, Fragile, Handle (n, top, side), 
Light, MadeOf(ceramic, paper, styrofoam)
cup3.pex
cup3.nex
 with union option.
Mitchell97 
pag. 342
0  11.55
lens(X0,no,normal) = soft 
lens(X0,X1,reduced) = no 
lens(X0,yes,normal) = hard
The lenses fitting problem without the age attribute. lenses.pex 
lenses.nex
Chend. 2  0.19
lens(X0,hymyope,no,X1) = soft 
lens(young,myope,no,normal) = soft 
lens(X0,myope,yes,X1) = hard 
lens(young,hymyope,yes,normal) = hard 
lens(prepresby,myope,no,normal) = soft 
lens(prepresby,hymyope,yes,normal) = no 
lens(presby,myope,no,normal) = no 
lens(X0,X1,X2,reduced) = no 
lens(presby,hymyope,yes,normal) = no
The complete lenses fitting problem.  lenses.pex 
lenses.nex
Chendr.    6.26
  The monks1 problem        

 

Simple recursive programs without background knowledge:

Non-Boolean functions are also learnt from positive data only.
 
Program
Description
Data Sample
Src
Steps
Time
(sec.)
sum(s(X),Y) = s(sum(X,Y)) 
sum(0,Y)=Y
 Sum of two natural numbers. sum.pex (10 eqs.)
sum.nex (5 eqs.)
  1  0.99
length(p(X,Y)) = s(length(X)) 
length(v)=0
 Length of a list.  length.pex (8 eqs.)
length.nex (4 eqs.)
   0.72
consec(p(X,Y)) = consec(X) 
consec(p(p(X,Y),Y)) = true
 Returns true if there exist two consecutive equal members. cons.pex (11 eqs.)
cons.nex (6 eqs.)
   7.45
drop(0,X0) = X0 
drop(s(X),p(Y,Z)) = drop(X,Y)
 Drops from a list the N last elements. drop.pex (6 eqs.)
drop.nex (7 eqs.)
  1  2.85
app(p(X,Y),Z) = p(app(X,Z),Y) 
app(v,X) = X
 Appends two lists. app.pex (5 eqs.)
app.nex (8 eqs.)
Mgn 
0.199
1  12.86
prefix(p(X0,X1),p(X2,X1)) = prefix(X0,X2) 
prefix(v,X0) = true
 Checks whether the left argument is a prefix of the second argument     1  15.6
suffix(X0,p(X1,X2)) = suffix(X0,X1) 
suffix(X0,X0) = true
 Checks whether the left argument is a suffix of the second argument     1  26.2
member(p(X,Y),Z) = member(X,Z) 
member(p(X,Y),Y) = true
 Returns true if Z is in the list. member.pex (12 eqs.)
member.nex (9 eqs.)
Mgn 1  7.77
last(p(X,Y)) = last(X) 
last(p(v,X)) = X
 Last element of a list. last.pex (7 eqs.)
last.nex (5 eqs.)
Mgn 
0.066
1  1.60
geq(s(X),s(Y)) = geq(X,Y) 
geq(X,0) = true
 Returns true if the first element is equal or greater 
 than the second one.
geq.pex (8 eqs.)
geq.nex (8 eqs.)
  1  0.29
lt(X0,s(X1)) = lt(X0,X1) 
lt(X0,s(X0)) = true
 Returns true if the first element is less 
 than the second one.
    1  1.21
max(0,X) = X 
max(s(X),s(Y)) = s(max(X,Y)) 
max(X,Y) = max(Y,X)
 Maximum between two natural numbers. 
 (with commutativity) (-t option)
max.pex (11 eqs.)
max.nex (11 eqs.)
(with nonterm. option)
  2  13.35
max(0,X) = X 
max(s(X),s(Y)) = s(max(X,Y)) 
max(X,0) = X
 Maximum between two natural numbers. 
 (without commutativity)
max.pex (11 eqs.)
max.nex (11 eqs.)
  2  4.88
mod2(s(s(X))) = mod2(X) 
mod2(s(0)) = s(0) 
mod2(0)=0
 The mod 2 operation. mod2.pex (7 eqs.)
mod2.nex (5 eqs)
  2  0.21
mod3(0) = 0 
mod3(s(0)) = s(0) 
mod3(s(s(0))) = s(s(0)) 
mod3(s(s(s(X0)))) = mod3(X0)
 The mod 3 operation. mod3.pex (7 eqs.)
mod3.nex (8 eqs.)
  3  0.37
even(s(s(X)) = even(X) 
even(0) = true
 Returns true if the natural number is even. even.pex (3 eqs.) 
even.nex (2 eqs.)
Mgn 
0.216
1  0.06
odd(s(0))=true 
odd(s(s(X)))=odd(X)
 Returns true if the natural number is odd. odd.pex (3 eqs.)
odd.nex (2 eqs.)
  1  0.16
minus(X,Y)) = m(minus(Y,X)) 
minus(X,0) = X 
minus(s(X), s(Y)) =minus(X,Y)
 Subtraction of two natural numbers. 
(-t option)
minus.pex
minus.nex
(with nonterm. option)
  2  34.08
minus1(0,s(X)) = m(X) 
minus1(X,0) = X 
minus1(s(X), s(Y)) = minus1(X,Y)
 Subtraction of two natural numbers. minus.pex
minus.nex
  2  2.29
sum(s(X),Y) = s(sum(X,Y)) 
sum(0,Y)=Y 
prod(s(X0),X1) = sum(prod(X0,X1),X1) 
prod(0,X0) = 0
 Addition and Product at the same time (-n option 
with full program 
clauses combination)
  3 3.40 
or(true,X) = or(false, true) 
or(false, X) = X
      1 0.07
and(false,X) = and(true, false) 
and(true, X) = X
      1  0.07
ifthenelse(false,X0,X1) = ifthenelse(true,X1,X0) 
ifthenelse(true,X0,X1) = X0
 if-then-else function     1  1.47
 customer(p(X0,X1)) = customer(X0) 
 customer(p(X0,has_children)) = true 
 customer(p(X0,woman)) = true 
 customer(p(X0,teacher)) = true
The good customer function where attributes are non-structured and appear in a list. customer.pex
customer.nex
  5  8.69

More complex algorithmic programs with background knowledge:

Non-Boolean functions are also learnt from positive data only.
 
Program
Description
Data Sample
Background
Src
Steps
Time 
(sec.)
suml(p(X0,X1)) = sum(suml(X0),X1) 
suml(p(v,X0)) = X0
 Sum of a list of natural numbers. suml.pex (10 eqs.)
suml.nex (10 eqs.)
Definition of sum.   1  6.52
suml(p(X0,X1)) = sum(suml(X0),X1) 
suml(p(v,X0)) = X0
 Sum of a list of natural numbers. suml.pex (10 eqs.)
suml.nex (10 eqs.)
Definition of sum.
(with -f option)
  1  5.40
maxl(p(X0,X1)) = max(X1,maxl(X0)) 
maxl(p(v,X0)) = X0
 Maximum of a list.  maxl.pex (7 eqs.)
maxl.nex (6 eqs.)
Definition of max.   1  8.91
maxl(p(X0,X1)) = max(X1,maxl(X0)) 
maxl(p(v,X0)) = X0
 Maximum of a list.  maxl.pex (7 eqs.)
maxl.nex (6 eqs.)
Definition of max.
(with -f option)
  1  8.13
prod(s(X0),X1) = sum(prod(X0,X1),X1) 
prod(0,X0) = 0
 Product of two natural numbers. prod.pex (5 eqs.)
prod.nex (5 eqs.)
Definition of sum.   1  0.83
rev(p(X0,X1)) = app(rev(X0),p(v,X1)) 
rev(v) = v
 Reverse of a list. rev.pex (5 eqs.)
rev.nex (4 eqs.)
Definition of append.   2  1.40
fact(s(X0)) = prod(fact(X0),s(X0)) 
fact(0) = s(0)
 Factorial of a natural number   Definition of sum and.
Definition of prod
(with -f option) 
(with -e option)
   2.90 
sort(p(X0,X1)) = inssort(X1,sort(X0)) 
sort(v) = v
 Inefficient Sort of a List   Definition of inssort, gt and if.   1  9.17

Times are recorded on a Pentium III processor (450 Mhz) with 64 MBytes of RAM under Linux version 2.2.12-20.


Future Extensions:


Prospective Applications:



© 1999-2001 José Hernández Orallo, Cèsar Ferri Ramírez.