[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> firstname.lastname@example.org 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?