Nils Goesche <email@example.com> wrote:
| Christopher Browne <firstname.lastname@example.org> writes:
| > I obviously need to read the Little Schemer and successor again. I
| > still don't "get" why one would really _care_ about the Y-combinator.
| Just for the heck of it.
Well, it's a *little* bit more than *that*! ;-} ;-}
Basically, it provides (one way of showing) a solid theoretical basis
for recursive functions, even in a *purely* functional (non-mutational)
world. That is, it gives you a way to talk about what CL DEFUN & LABELS
and Scheme "define" & "letrec" do [w.r.t. recursive functions, that is]
*without* assuming that they're primitive in the language(s).
But beyond that, there are actually a few somewhat-useful things
you can learn from studying it, at least once. First, having done
something like define the factorial "the hard way", with Y, most
people see that there is a *less* general but simpler way to write
*specific* recursive functions without using Y [or the built-in
recursion of DEFUN or LABELS], e.g., for factorial:
> (defun fact (n)
(flet ((aux (f n)
(if (< n 2) 1 (* n (funcall f f (1- n))))))
(aux #'aux n)))
> (fact 5)
> (fact 50)
Then from that one might get the notion of a tree-walker that
passes *itself* down as one of the arguments to recursive calls.
Why? Because if you pass down the function to recurse with instead
of hard-coding it into the algorithm, you can *change* that function
at some point in the walk and the rest of the walk of that sub-tree
will automatically use the new function as the default.
Note that this is similar to but subtly different from doing the
tree walk with a CLOS generic function that dispatches based on
node type, and in fact two approaches are complimentary and can
In short, one might not ever actually use the formal Y-combinator
in practical coding, but having studied it might have some positive
| The point is, it is /trivial/ to write it in Lisp.
Yup, once you've seen it and walk through it enough to really grok it.
But the *first* time's sure a bitch, i'n'it... ;-} ;-}
Rob Warnock, PP-ASEL-IA <email@example.com>
627 26th Avenue <URL:http://www.rpw3.org/>
San Mateo, CA 94403 (650)572-2607