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

*To*: scheme@mc.lcs.mit.edu*Subject*: Re: Scheme Digest #8, Efficiency of Y*From*: zodiac!DUCHAMPS.ADS.COM!rar@ames.arpa (Bob Riemenschneider)*Date*: Wed ,16 Nov 88 22:43:28 EDT*Sender*: scheme-request@mc.lcs.mit.edu

=> In article <8811161012.AA13091@kleph.ai.mit.edu>, cph@KLEPH (Chris Hanson) => 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. => => 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?? => => => Bruce 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 (define f (lambda (n) (if (= n 0) 1 (+ 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 explicit definition (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". -- rar

**Follow-Ups**:**Re: Scheme Digest #8, Efficiency of Y***From:*polya!max@labrea.stanford.edu (Max Hailperin)

- Prev by Date:
**Re: Scheme Digest #9** - Next by Date:
**AmigaScheme** - Previous by thread:
**Re: Scheme Digest #8, Efficiency of Y** - Next by thread:
**Re: Scheme Digest #8, Efficiency of Y** - Index(es):