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

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

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