[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@KLEPH (Chris Hanson)
=> >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.
=> Is there a particular reason why its worth a lot of effort to make Y
=> compile efficiently?? More the the point, does anyone have examples
=> of code that is more elegant (or better in some other way) than, say,
=> a simple recursive implementation??
Rather than present particular examples, let me make three general points.
1. Y is elegant for the same reason lambda is elegant: you can define
and use a procedure without having to give it a name.
2. The treatment of procedures in Scheme, while better than Lisp, is still
not entirely first-class. Here's an example.
Suppose n ==> 2. After
(define n (* n n))
n ==> 4: (* n n) gets evaluated, and the result gets stored in the
location n is bound to. Now suppose f computes the successor function.
If procedure values were treated like numeric values, after
(if (= n 0)
(+ n (f (- n 1))))))
f would compute the function that returns 1 when applied to 0,
and 2n when applied to any n > 0: the lambda would be evaluated in
an environment where f computes successor and the resulting procedure
would be stored in the location f is bound to. Of course, that's
not what happens in Scheme. The definition is interpreted as: let
f be a solution (in fact, the least solution) to
f = (lambda (n) ...f...)
Having Y allows you to convert the implicit definition into an
(define f (Y (lambda (g) (lambda (n) ...g...))))
and pretend that procedures are treated just like other values by define.
This certainly seems more elegant to me.
3. Having Y around makes Scheme seem more like "an interpreter for
extended lambda calculus".