I've recently been studying the lambda calculus. Just for the heck
of it I tried to define the Y combinator in lisp. The "obvious"
transcription:
(defun (Y f)
(funcall #'(lambda (x) (funcall f (funcall x x)))
#'(lambda (x) (funcall f (funcall x x)))))
does not work; it goes into an infinite loop. The best I've
been able to come up with is:
(defun Y (f)
(funcall #'(lambda (x)
#'(lambda (&rest args)
(apply (funcall f (funcall x x)) args)))
#'(lambda (x)
#'(lambda (&rest args)
(apply (funcall f (funcall x x)) args)))))
Does anybody know a cleaner way to do this?
--
Mike Haertel <····@ai.mit.edu>
"There are two ways of constructing a software design. One way is to make it
so simple that there are obviously no deficiencies, and the other is to make
it so complicated that there are no obvious deficiencies." -- C. A. R. Hoare
the first version is for a call-by-name environment and as observed
does diverge in a call-by-value environment.
one y written without the horrid explicit applies, funcalls and #'
of lisp is:
(defun y (f)
(let ((h (lambda (g) (lambda (x) ((f (g g)) x)))))
(h h)))
a cute article concerning y in lisp is
"the why of y" by dick gabriel in vol. 2 no. 2 lisp pointers. 1988.
-iam-
From: Jeff Dalton
Subject: Re: Y combinator in Common Lisp
Date:
Message-ID: <2338@skye.ed.ac.uk>
In article <······················@cs.umn.edu> ····@umn-cs.cs.umn.edu (Mike Haertel) writes:
>I've recently been studying the lambda calculus. Just for the heck
>of it I tried to define the Y combinator in lisp. The "obvious"
>transcription:
>
> (defun (Y f)
> (funcall #'(lambda (x) (funcall f (funcall x x)))
> #'(lambda (x) (funcall f (funcall x x)))))
>
>does not work; it goes into an infinite loop.
The initial call to x gets to (funcall f (funcall x x)), which does
(funcall x x) and starts another (funcall f (funcall x x)), which
starts another (funcall x x), and so on. So you need to put
#'(lambda (arg) (funcall ... arg)) around (funcall f (funcall x x))
to delay it.
So I get more or less your second version, which for the 1-arg case
looks like this:
(defun Y (f)
(funcall
#'(lambda (rec)
#'(lambda (arg) (funcall (funcall f (funcall rec rec)) arg)))
#'(lambda (rec)
#'(lambda (arg) (funcall (funcall f (funcall rec rec)) arg)))))
It can be made a little neater by rewriting:
(defun Y (f)
(let ((rec #'(lambda (rec)
#'(lambda (arg)
(funcall (funcall f (funcall rec rec))
arg)))))
(funcall rec rec)))
That's about as good as it gets in a call-by-value language,
though it doesn't look so bad in Scheme.