#|
In article <······················@wuecl.wustl.edu>, ····@cec2.wustl.edu
(Peter Pui Tak Chiu) writes:
> does anyone have a version of y-combinator that works for multiple
> recursions?
I thought it would be fun to write one, so here it is:
A short explanation: the Y-combinator is a function such that
Yf = fYf
Solving for Y (he says, non-chalantly):
Y = \f.\x.(\r.f(rr)x)(\r.f(rr)x)
In Common Lisp, using the factorial function as an example:
|#
(defun Y (f)
(let ((g #'(lambda (g)
#'(lambda (x)
(funcall (funcall f (funcall g g)) x)))))
(funcall g g)))
(setq Y-! (Y #'(lambda (f)
#'(lambda (n)
(if (= n 0) 1 (* n (funcall f (1- n))))))))
#|
(And who was it that opined just recently, that Scheme's function call
syntax was 'a minor detail' -- How much clearer that would be in Scheme!)
(If your head aches just looking at Y, I recommend the article 'The Why
of Y' in Lisp Pointers a couple of years ago -- I'm sorry I can't
provide a more precise reference but I'm separated from my reference
library.)
Now a combinator Y' that does the same thing for two mutually recursive
functions would be:
Y'fg = f(Y'fg)(Y'gf)
And in open form, by analogy with Y (and if I could program that 'by
analogy' into a computer, we could all retire):
Y' = \f.\g.\x.(\r.\s.f(rrs)(srs)x)
(\r.\s.f(rrs)(srs)x)
(\r.\s.g(rrs)(srs)x)
And in CL, with reverse and append as examples:
|#
(defun YY (f g)
(let ((r #'(lambda (r s)
#'(lambda (&rest x)
(apply (funcall f (funcall r r s) (funcall s r s))
x))))
(s #'(lambda (r s)
#'(lambda (&rest x)
(apply (funcall g (funcall r r s) (funcall s r s))
x)))))
(funcall r r s)))
(setq reverse
#'(lambda (reverse append)
#'(lambda (x)
(if (null x)
x
(funcall append (funcall reverse (rest x))
(list (first x)))))))
(setq append
#'(lambda (reverse append)
#'(lambda (x y)
(if (null x)
y
(funcall append
(funcall reverse (rest (funcall reverse x)))
(cons (first (funcall reverse x)) y))))))
(setq Y-reverse (YY reverse append))
#|
That was undoubtedly the slowest reverse I've ever written: reversing a
seven-element list took almost 10 s CPU time on a VAX 6000-420!
Pekka P. Pirinen ·············@helsinki.fi
University of Helsinki, soon Harlequin Ltd.
|#
From: Ken Dickey
Subject: Y not? (was Re^2: lambda calculus)
Date:
Message-ID: <729@data.rain.com>
·······@cc.helsinki.fi writes:
>(If your head aches just looking at Y, I recommend the article 'The Why
>of Y' in Lisp Pointers a couple of years ago -- I'm sorry I can't
>provide a more precise reference but I'm separated from my reference
>library.)
Richard Gabriel: "The Why of Y", LISP Pointers, vol 2, # 2,
Oct-Nov-Dec 1988.
Enjoy!
-Ken