Re: Scheme Digest #8, Efficiency of Y

[titan!dorai@rice.edu (Dorai Sitaram)]

In article <5145@polya.Stanford.EDU> mxh@ksl.Stanford.EDU (Max Hailperin) writes:
>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.

Last time, I didn't wait to see Hailperin's response to
Riemenschneider before I posted  m y  own response, which turned out
to be almost a clone. Sorry. Now that H has answered the 2nd half of
R's claim #1, let's consider the 1st half:

Using whatever metric for elegance, Y  c a n n o t  be elegant for the
same [or similar] reason that lambda is. They are not in the same
league. Lambda is a core form; Y, on the other hand, is something
defined  u s i n g  lambda. Y can be compared to [let]rec, though. It
is strictly less powerful than the latter, for [let]rec can define
cyclic data objects, including self-eq recursive procedures, whereas Y
can only define non-self-eq recursive procedures. Y can however claim
elegance on the following point: it requires only one* core form
[lambda] for its definition, whereas [let]rec require two [lambda +
set!]. 

I have used the "elegance" of a construct to mean a combination of 2
factors, the economy of core forms needed to get it going, and the
profusion of other constructs this construct itself produces. The
latter, when applied to {a set of} core form(s) is better known as
"expressiveness".

--dorai

*if you consider  a p p l i c a t i o n  to be a core form, add one to
both contestants.