[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Scheme Digest #8, Efficiency of Y

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. 


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?