srlm@ukc.UUCP (S.R.L.Meira) (08/16/83)
I'd like to talk about some points that I feel have not been
touched at, in "recursion is difficult" et coetera. First, as P. Curtis
has pointed out, recursion is NOT difficult, given that you are told
about it properly, by the right people, using the right language!!!
Second, if instead of LISP, you think of a PURE applicative language
like KRC [Turner82a], besides of recursion you'll have referential tran-
sparency, higher order functions, infinite data structures, (parameter)
pattern matching, partial parametrization, which will make your life a LOT
better.
In order to give a short presentation of the language I'll make use
of some examples. The (not that original) definition of factorial goes
like:
fact 0 = 1 ;
fact n = n * fact (n - 1) ;
As you can see, we don't need parenthesis or def's and lambda's! In a
more original example, the Towers of Hanoi are solved by:
hanoi 0 x y z = [] ;
hanoi n x y z = hanoi (n - 1) x z y:" move from peg ":x:" to peg ":y:nl:
hanoi (n - 1) z y x ;
The Cyclic Towers of Hanoi, defined by Atkinson in [Atkins81a], where
the rings can move only in the clockwise direction (try a non-recursive
solution for this one) is:
clock 0 x y z = [] ;
clock n x y z = anti (n - 1) x z y:" move a ring from peg ":x:nl:
anti (n - 1) z y x ;
anti 0 x y z = [] ;
anti n x y z = anti (n - 1) x y z:" move a ring from peg ":x:nl:
clock (n - 1) y x z:" move a ring from peg ":z:nl:
anti (n - 1) x y z ;
In both cases, n is the number of rings, and x,y and z the pegs' names
--as the language is weakly typed, they may be either numbers or strings
or a mix of them. [] is the null list, : is CONS and nl is the library
function <newline>.
Now, let's talk about "hidden" recursion, i. e., the use of
Zermelo-Fraenkel equations in KRC to, say, implement Hoare's quicksort
algorithm:
quick [] = [] ;
quick (a:x) = quick {y | y <- x; y <= a} ++
a:quick {z | z <- x; z > a} ;
where ++ is APPEND, and the first curly-bracketed equation is to be read
as "'set' of all y such that y is drawn from x and y is less than or
equal to a". Actually instead of 'set' we have LIST. Note the use of
"(a:x)" as argument, in order to avoid the LISPy use of CAR and CDR.
Some "real" programs have been written in KRC, as an em-like editor
which has +-400 equations, a lambda calculus interpreter, etc. If you
are interested, first have a look at [Turner82a], then mail me so that I
could try to give additional information about KRC. A UN*X (4.1BSD)
implementation of KRC using Turner's COMBINATORS method [Turner79a] is
being done by UKC's Simon Croft. We'll mail more details of that soon.
Just before I leave, that's how one would define insertion sort:
insort [] = [] ;
insort (a:x) = insert a (sort x) ;
insert a [] = [a] ;
insert a (b:x) = a:b:x, a <= b ;
= b:insert a x ;
==========================================
Silvio Meira - Univ. of Kent at Canterbury
============ ...!mcvax!ukc!srlm ==========
Atkins81a.
M. D. Atkinson, "The Cyclic Towers of Hanoi," Inf. Proc. Lett.,
Vol. 13, (3), pp. 118-119, (Dec. 1981).
Turner79a.
D. A. Turner, "A New Implementation Technique for Applicative
Languages," Soft. Pract. and Exp., Vol. 9, pp. 31-49, (1979).
Turner82a.
D. A. Turner, "Recursion Equations as a Programming Language," in
Functional Programming and its Applications, An Advanced Course, C.
U. P., Cambridge, UK (1982).