Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!pasteur!agate!labrea!polya!max
From: max@polya.Stanford.EDU (Max Hailperin)
Newsgroups: comp.lang.scheme
Subject: Re: Scheme Digest #8, Efficiency of Y
Summary: Y changes eqness (or at least eqvness) in scheme
Message-ID: <5084@polya.Stanford.EDU>
Date: 16 Nov 88 16:43:27 GMT
References: <8811161012.AA13091@kleph.ai.mit.edu>
Reply-To: mxh@ksl.Stanford.EDU (Max Hailperin)
Organization: Stanford University
Lines: 26

In article <8811161012.AA13091@kleph.ai.mit.edu> cph@zurich.ai.mit.edu 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.

As this remark points out, there is no reason from an efficiency
standpoint to not simply define letrec in terms of Y.  While Y may be
expensive in some general cases, as long as it only appears
surrounding an explicit lambda, there is no particular reason a
compiler can't catch on to what's going on. 

HOWEVER,

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?