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