Re: Scheme Digest #8, Efficiency of Y

=>   In article <8811161012.AA13091@kleph.ai.mit.edu>, cph@KLEPH (Chris Hanson)
=>   writes:
=>   >Bill Rozas has expended no small effort in the MIT Scheme compiler to
=>   >make the Y combinator produce good results, and these timings are
=>   >evidence of that.  Still not perfect, but I believe Bill claims that
=>   >he can make the output code identical given a bit more work.
=>
=>   Is there a particular reason why its worth a lot of effort to make Y
=>   compile efficiently??  More the the point, does anyone have examples
=>   of code that is more elegant (or better in some other way) than, say,
=>   a simple recursive implementation??
=>
=>
=>   Bruce

Rather than present particular examples, let me make three general points.

1.  Y is elegant for the same reason lambda is elegant: you can define
and use a procedure without having to give it a name.

2.  The treatment of procedures in Scheme, while better than Lisp, is still
not entirely first-class.  Here's an example.

Suppose n ==> 2.  After

(define n (* n n))

n ==> 4: (* n n) gets evaluated, and the result gets stored in the
location n is bound to.  Now suppose f computes the successor function.
If procedure values were treated like numeric values, after

(define f
(lambda (n)
(if (= n 0)
1
(+ n (f (- n 1))))))

f would compute the function that returns 1 when applied to 0,
and 2n when applied to any n > 0: the lambda would be evaluated in
an environment where f computes successor and the resulting procedure
would be stored in the location f is bound to.  Of course, that's
not what happens in Scheme.  The definition is interpreted as: let
f be a solution (in fact, the least solution) to

f = (lambda (n) ...f...)

Having Y allows you to convert the implicit definition into an
explicit definition

(define f (Y (lambda (g) (lambda (n) ...g...))))

and pretend that procedures are treated just like other values by define.
This certainly seems more elegant to me.

3. Having Y around makes Scheme seem more like "an interpreter for
extended lambda calculus".

-- rar