Re: Curry design

From: Harold Boley <boley_at_informatik.uni-kl.de>
Date: Thu, 3 Jul 97 17:54:25 MET DST

Dear John, Michael, Sergio, and Curritos,

The cute example given by Sergio is a good start. Below is the larger
one I often use for Relfun demos (www.dfki.uni-kl.de/~vega/relfun.html),
here, however, given in a different syntax. Johan Boye has written an
even more realistic typesetting program using similar techniques:
J. Boye. 'Avoiding dynamic delays in functional logic programs'.
Proceedings of PLILP'93, pp. 12-27, LNCS 714, Springer, 1993.

Cheers, Harold.
------------------------------------------------------------------------

The following pairlists (or zip) function definition stems from the
`ground functional programming' tradition:

pairlists([],[]) = []
pairlists([X|L],[Y|M]) = [[X,Y]|pairlists(L,M)]

Thus it's usually called with both arguments being ground lists:

>>>>>> pairlists([d,a,l,l,a,s],[2,1,3,3,1,4])
[[d,2],[a,1],[l,3],[l,3],[a,1],[s,4]]

However, employing a narrowing interpreter, it demonstrates a useful
`non-ground functional programming' technique: partial data structures
even for computations with ground-I/O.

For example, a non-ground pairlists call with a logic variable R in
the second argument position binds R to a list of variables that also
appear as the second elements of the pairs in the list returned:

>>>>>> pairlists([d,a,l,l,a,s],R)
[[d,Y1],[a,Y2],[l,Y3],[l,Y4],[a,Y5],[s,Y6]]
R=[Y1,Y2,Y3,Y4,Y5,Y6]

This is at the center of the following functional version of
David H. D. Warren's relational serialise definition:

serialise(L) = R if numbered(qsort[before](pairlists(L,R)),1)

Here, numbered is Warren's relation with an embedded "+" function:

numbered([],N).
numbered([[X,N]|R],N) :- numbered(R,+(N,1)).

Also, qsort[Cr] is a Cr-parameterized function for quicksort (without
duplicates), called here with a comparison relation Cr=before,
lexicographically comparing the first elements of pairs:

before([X1,Y1],[X2,Y2]) :- string<(X1,X2).

For the task of transforming a list of symbols into the list of their
lexicographic serial numbers, we can now use ground serialise calls,
which after the essential non-ground processing described above,
return a ground value:

>>>>>> serialise([d,a,l,l,a,s])
[2,1,3,3,1,4]
Received on Do Jul 03 1997 - 19:02:00 CEST