``` Subject: Re: macros vs HOFs (was: O'Caml) From: rpw3@rpw3.org (Rob Warnock) Date: Wed, 11 Sep 2002 04:07:46 -0000 Newsgroups: comp.lang.lisp Message-ID: <untgci2bjh9rd1@corp.supernews.com> ```
```Nils Goesche  <cartan@cartan.de> wrote:
+---------------
| Christopher Browne <cbbrowne@acm.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
> (fact 5)
120
> (fact 50)
30414093201713378043612608166064768844377641568960512000000000000
>

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
be mixed.

In short, one might not ever actually use the formal Y-combinator
in practical coding, but having studied it might have some positive
spinoffs (maybe).

+---------------
| 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

-----
Rob Warnock, PP-ASEL-IA		<rpw3@rpw3.org>
627 26th Avenue			<URL:http://www.rpw3.org/>
San Mateo, CA 94403		(650)572-2607

```