GODDEN@gmr.COM (08/04/88)
Date: Wed, 3 Aug 88 09:16 EDT
From: GODDEN%gmr.com@RELAY.CS.NET
To: ailist@mc.lcs.mit.edu
Subject: Church's Y-operator
X-VMS-To: NET%"ailist@ai.ai.mit.edu"
In the new >Lisp and Symbolic Computation< vol.1, no.1 Gabriel and Pitman
make reference to "the Y operator" (p.85). There is also a reference
to it in a footnote in "The Art of the Interpreter" by Steele and Sussman
where they supply a pointer to McCarthy "History of LISP", ACM SIGPLAN
Notices, Aug. 78. McCarthy refers to "Church's Y-operator". I've been
scanning through Church's >The Calculi of Lambda-Conversion< but have
been unable to find any mention of it (alas, Church has no index). Can
anyone help direct me to where this is originally discussed by Church?
Perhaps it appears in some other work of Church? FYI: The Y operator,
defined in a Scheme-like language is:
(defun y (f)
((lambda (g) (lambda (h) ((f (g g)) h)))
(lambda (g) (lambda (h) ((f (g g)) h)))))
Interesting, huh? You can use it to implement recursive procedures
even when your interpreter does not explicitly support recursion.
Thus, to calculate 6! recursively, it could be invoked as
((y (lambda (fn)
(lambda (x)
(if (zerop x) 1 (* x (fn (- x 1)))))))
6)
-Kurt Godden
godden@gmr.com