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