worley@compass.com (Dale R. Worley) (09/26/89)
In most discussions of graph reduction execution of the combinator
representation of the lambda calculus, recursive functions are
represented by introducing a circularity in the tree that represents
the function defintion. In theoretically pure lambda calculus,
recursion is expressed using the Y combinator, or some such, which can
be represented in terms of the simpler combinators. Has anyone
actually done this in graph reduction execution? Has anyone analyzed
the optimization which removes the Y and replaces it with the circular
edge? Is this a special case of a more general optimization?
Dale
worley@compass.com
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.chase@orc.olivetti.com (David Chase) (09/28/89)
[In reply to several questions from Dale Worley]
Background: in combinator rewriting/graph reduction, the application
of the fixed-point operator can either be rewritten like so
Y(F) ==> F(Y(F))
(That's the definition)
or it can be graph-reduced into a cycle
__
APP v \
/ \ ==> APP \
Y F / \_|
F
as observed by David Turner (and maybe other people).
> Has anyone actually done this in graph reduction execution?
Yes (I did it once in a toy interpreter for FP84, but the
interpreter was generally so slow that nothing terribly long
was ever run through it). Stoye (and others) don't mention
doing this in their paper on SKIM II (see the 1984 Conference
Lisp and Functional Programming), but I thought that they did.
>Has anyone analyzed the optimization which removes the Y and
>replaces it with the circular edge?
Not me. I think the consensus is that it replaces the creation
of lots of non-cyclic garbage with the creation of a little
cyclic garbage, but I could be wrong. Both supercombinator
optimizations and continuation-passing transformations might
change this, and I just don't know enough about the interaction
to say for sure what happens. Also, note that non-cyclic garbage
makes reference counting collection more useful, and reference
counting apparently refuses to die (I have seen it proposed for
some multiprocessor systems).
>Is this a special case of a more general optimization?
Yes. John Hughes has an interesting paper on "lazy memo functions"
in the 1985 Conference on Functional Programming Languages
and Computer Architecture (Springer-Verlag LNCS #201). A lazy
memo function is like an "ordinary" memo function, except that it
1. use an EQ test for equality on non-atomic objects.
This is necessary for practical use of memo functions
in a lazy language, because otherwise memoization
forces full evaluation.
2. evaluate functions lazily, and rely on overwriting
of old applications with the results of their evaluation.
The use of EQ to test functions and arguments for equality
forces one "level" of evaluation into a structure, so you don't
end up with the trivial result that F(X) = F(X).
Consider this example (taken from Hughes' paper):
ones = 1 : ones (a cyclic data structure)
twos = map double ones
map f [] = []
map f (a:x) = (f a):(map f x)
(: is list prepend, [] is empty list, and "f x" is "f applied to x")
Evaluation of "twos" yields:
map double ones = map double (1:ones)
= (double 1) : (map double ones)
= 2 : (map double ones)
However, the arguments to "map" in the last line are identical (EQ)
to the arguments at the start of the evaluation, so we use that result
and obtain a cycle. More interesting results can be obtained when
evaluating the function zip (another example from Hughes' paper)
zip [] [] = []
zip (a:x) (b:y) = [a,b] : (zip x y)
applied to the two lists "ab" and "abc" below:
ab = a : b : ab
abc = a : b : c : abc
We get (intermediate steps omitted, see the paper if you care)
zip ab abc = [a,a]:[b,b]:[a,c]:[b,a]:[a,b]:[b,c]:(zip ab abc)
Similarly,
Y F = F (Y F)
The paper is worth reading. It contains more interesting examples,
and a discussion of interactions with garbage collection and full
memo functions.
David
[From David Chase <chase@orc.olivetti.com>]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.augustss@cs.chalmers.se (Lennart Augustsson) (09/29/89)
worley@compass.com (Dale R. Worley) says > ... In theoretically pure lambda calculus, > recursion is expressed using the Y combinator, or some such, which can > be represented in terms of the simpler combinators. Has anyone > actually done this in graph reduction execution? Yes, I'm sure many have tried this. I know I have. > Has anyone analyzed the optimization which removes the Y and replaces > it with the circular edge? I haven't seen anything formal on this, but not using the "knot-tying" version of Y gives you horrible space leaks. Any recursion will unfold the definition of a function as deep as the recursion has ever been in that function. Most of the time it is not possible to garbage collect the unfolded part of the graph unless you use a very clever collector. As far as I know there is *no* reason to use the unfolding version except if you want to avoid cycles in the graph. > Is this a special case of a more general optimization? Yes and no. Y handles everything you write in a correct way (I've no formal proof of this, but I believe it to be true), but for each recursive definition you can tailor a special combinator that does it in a more efficient may. Check in "The Implementation of Functional Programming Languages" by Simon Peyton Jones (Prentice Hall, ISBN 0-13-453333-X or 0-13-453325-9) for suitable ways to do all this. This book is a *must* for anyone interested in implementation of lazy functional languages. -- Lennart Augustsson -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.