# The Toy System

What can you expect from Toy?

The basic features of Toy are:
• 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]```
```
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
Some distinguised features of Toy are

• 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 ]```
```
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```
```
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 )
```

```
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?

As usual in functional logic languages, the operational mechanism of the language is bases on a lazy narrowing strategy, called demand driven narrowing . The Toy system implements demand driven narrowing by means of a translation of Toy into Prolog code.