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]
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
Some
distinguised features of Toy
are
- 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?
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.