Re: Re^2: Scheme Digest #8, Efficiency of Y

Bob Riemenschneider writes:
\$Max Hailpern writes:
\$
\$=>   There is another reason, in Scheme, not to use Y: it breaks the fact
\$=>   that you can use procedures as objects.  While the R^3R says that a
\$=>   procedure created by a given lambda at a given time will be eqv to
\$=>   itself (and implies eq as well, though on looking I see that isn't in
\$=>   there -- is this a mistake?), the same does not necessarily hold for
\$=>   the various incarnations of a procedure that Y will churn out (or
\$=>   rather, that Y is entitled to churn out: presumably in Rozas's
\$=>   implementation there is indeed only one procedure).
\$=>
\$=>   Perhaps I'm wrong to mix together such disparate worlds as Y and
\$=>   eqvness of procedures belong to, but I do consider this to be
\$=>   something of an issue.  Does anyone else?
\$
\$Could you provide a specific example?  I don't see how Y makes the situation
\$any worse than lambda.  Just as you might decide to write
\$
\$		   (let ((p (lambda (n) ...n...)))
\$		       ===p===p===)
\$
\$rather than
\$
\$		===(lambda(n) ...n...)===(lambda (n) ...n...)===
\$
\$because Scheme doesn't guarantee that even syntactically identical lambda
\$terms will test equivalent---Does anyone know why 'operational equivalence'
\$for procedures was defined extensionally, making it uncomputable, rather
\$than intensionally (say, in terms of alpha-convertability)?--, you might
\$decide to write
\$
\$		    (let ((p (Y (lambda (q) ...q...))))
\$			===p===p===)
\$
\$rather than
\$
\$	  ===(Y (lambda(q) ...q...))===(Y (lambda (q) ...q...))===
\$
\$Arguments against Y that apply equally well to lambda don't count!
\$
\$  							-- rar

It is very useful that a procedure be eq to itself [and to nothing
else (not even to something alpha-convertible)]. For instance, we can
create abstract data objects using lambda and set!. Using the fact
that procedures are self-eq, we can determine whether these data
objects are self-eq.

Lambda and set! give the conventional Scheme way of getting recursive
functions with rec/letrec. Recursive procedures created thus  a r e
self-eq, like any other procedure. Eg,

(let ([h (rec h (lambda (dummy) h))])
(eq? h (h 'any)))

yields  t r u e.

However, if _h_ had been defined with _Y_, ie,

(let ([h (Y (lambda (h) (lambda (dummy) h)))])
(eq? h (h 'any)))

the result is  f a l s e,  owing of course to the different [read
non-eq] procedures created for _h_ at each time it shows up.
Self-eqness of ADOs is lost, and though it can retrieved with some
amount of hacking [like adding a separate field in the ADO  a n d
redefining the eq function (see Matthias Felleisen's thesis where he
describes a cons data object)] the result is anything but concise or
easily extendable.

--dorai