Re: Scheme Digest #8, Efficiency of Y

[zodiac!DUCHAMPS.ADS.COM!rar@ames.arpa (Bob Riemenschneider)]

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