The Toy System

• Toy is a (Constraint) Functional Logic Programming language which combines the capabilities of the Functional and (Constraint) Logic Programming Paradigms. For example, one can define functions like:

    append    []     Ys = Ys  
    append [ X | Xs ] Ys = [ X | append Xs Ys ]

and solve goals with logic variables, like:

   TOY> append Xs [ 2, 3 ] == [ 1 , 2 , 3]

which yields the answer:

    Xs == [ 1 ]

Expression evaluation in functional style is also possible. For example:

    TOY>  >append [ 1, 2, 3] [4, 5, 6 ] 

yields the result:

     [ 1, 2, 3, 4, 5, 6]

In general, rules may have conditions (constraints) as in the following example:

    prefix Xs Ys = true <== append Xs Zs == Ys

(Note the existential variable Zs in the conditions).

Predicates in Toy are particular cases of functions returning the value true . Toy provides clausal notation for defining predicates, as shown below:

    prefix Xs Ys :- append Xs Zs == Ys

Apart from clauses, Toy is syntactically similar to functional languages of the Haskell family.

Functional programming features available in Toy include:
 

• Inferred polymorphic types (optionally declared)
• Higher order functions
• Lazy evaluation and infinite data structures

• Strict equality and disequality constraints, which can be returned as computed answers.
   
  • Strict equalities can provide non-ground computed answers. For example:

  
  
      TOY> [ X, 3 | R ] == [ Y | S ]

  yields the answer:

  
      X == Y, S == [ 3 | R]

  • Disequality constraints allow compact and expressive computed answers.
    For instance, assuming the definitions

  
  

  
      size    []     = 0  
      size [ X | Xs ] = if (member X Xs) then size Xs else 1 + (size Xs) 
      member X    []     = false  
      member X [ Y | Ys ] = if X==Y then true else member X Ys

  the goal

  
      TOY> size [ X, Y ] == N

  has two computed answers:

  
      X == Y, N == 1

  and

  
      X /= Y, N==2

• Linear arithmetic constraints over the real numbers are allowed. For instance, one can define the product of vector in the plane

    product (U1, U2) (V1,V2) = (U1*V1-U2*V2,U1*V2+U2*V1)

and then solve the goal:

    TOY> product ( 1, 1 ) V = ( -1, 2 )

obtaining the answer:

    V == ( 0.5, 1.5)

• Toy also supports non-deterministic functions, which in many cases can be profitably used as an alternative to predicates.
  For example, a function which performs a non-deterministic choice between two given arguments can be defined as:

  
      choice X Y = X 
      choice X Y = Y

  Then, given the goal:

  
      TOY> choice 0 1 ==X

  Toy can successively compute two answers:

  
      X ==0

  and

      X ==1

• HO computations. Toy can solve goals involving HO logic variables, which become bound to intensional representations of functions. Therefore, the 'first class citizen' status of functions in functional computations is extended to logic computations.

How does it Works?