Re: Scheme Digest #8, Efficiency of Y

[polya!max@labrea.stanford.edu (Max Hailperin)]

In article <8811170243.AA00199@duchamps.ads.com> rar@DUCHAMPS.ADS.COM
(Bob Riemenschneider) writes in response to a question of why Y is useful:

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

If you write
  (Y (lambda (f)
      (lambda (x)
        ... f ...)))
then you have given the procedure a name, namely f, within itself,
just not externally.  The same can be accomplished with named-lambda
or with letrec.  For example, (letrec ((f (lambda (x) ... f ...))) f).
So Riemenshneider's argument isn't much of an argument, if this is
all he has in mind.

What you can do with Y and not easily with letrec or some such is
write something like (Y f) or (Y (f x)).  Of course, Rozas's optimized
implementation may not be quite as much help here.  Does anyone have a
good use for Y in any context other than surrounding a lambda
expression?


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

Riemenshneider seems to be confused here about the store vs. the
environment.  This has nothing to do with the firstclassness of
procedures.  Incidentally, the numeric definition he gives only works
as he states at the top level: as an internal definition it is an
error.