kranz@WHEATIES.AI.MIT.EDU (David Kranz) (11/15/88)
Edward Wang is correct that the time in the example is dominated by bignum arithmetic. I changed the * in factorial to + and got the following result in T3.1: (factorial-loop 20000) -> .1 sec (factorial-rec 20000) -> .22 sec (factorial-lfp 20000) -> 1.32 sec With *: (factorial-rec 100) -> .42 sec (factorial-rec 1000) -> 57.78 sec
cph@KLEPH.AI.MIT.EDU (Chris Hanson) (11/16/88)
Date: Tue, 15 Nov 88 10:26:46 EST
From: kranz@wheaties.ai.mit.edu (David Kranz)
Edward Wang is correct that the time in the example is dominated by
bignum arithmetic. I changed the * in factorial to + and got the
following result in T3.1:
I tried a similar experiment in MIT Scheme (using + instead of *,
except a smaller loop to account for smaller fixnums), with the
following results:
(factorial-loop 100) -> 1.03 msec
(factorial-rec 100) -> 1.0 msec
(factorial-lfp 100) -> 2.74 msec
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.max@polya.Stanford.EDU (Max Hailperin) (11/17/88)
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?
Krulwich-Bruce@cs.yale.edu (Bruce Krulwich) (11/17/88)
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
rar@DUCHAMPS.ADS.COM (Bob Riemenschneider) (11/17/88)
=> 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".
-- rarmax@polya.Stanford.EDU (Max Hailperin) (11/18/88)
In article <8811170243.AA00199@duchamps.ads.com> rar@DUCHAMPS.ADS.COM (Bob Riemenschneider) writes in response to a question of why Y is useful: >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. If you write (Y (lambda (f) (lambda (x) ... f ...))) then you have given the procedure a name, namely f, within itself, just not externally. The same can be accomplished with named-lambda or with letrec. For example, (letrec ((f (lambda (x) ... f ...))) f). So Riemenshneider's argument isn't much of an argument, if this is all he has in mind. What you can do with Y and not easily with letrec or some such is write something like (Y f) or (Y (f x)). Of course, Rozas's optimized implementation may not be quite as much help here. Does anyone have a good use for Y in any context other than surrounding a lambda expression? >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. Riemenshneider seems to be confused here about the store vs. the environment. This has nothing to do with the firstclassness of procedures. Incidentally, the numeric definition he gives only works as he states at the top level: as an internal definition it is an error.
dorai@titan.rice.edu (Dorai Sitaram) (11/19/88)
In article <5145@polya.Stanford.EDU> mxh@ksl.Stanford.EDU (Max Hailperin) writes: >In article <8811170243.AA00199@duchamps.ads.com> rar@DUCHAMPS.ADS.COM >(Bob Riemenschneider) writes in response to a question of why Y is useful: > >>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. > >If you write > (Y (lambda (f) > (lambda (x) > ... f ...))) >then you have given the procedure a name, namely f, within itself, >just not externally. The same can be accomplished with named-lambda >or with letrec. For example, (letrec ((f (lambda (x) ... f ...))) f). >So Riemenshneider's argument isn't much of an argument, if this is >all he has in mind. Last time, I didn't wait to see Hailperin's response to Riemenschneider before I posted m y own response, which turned out to be almost a clone. Sorry. Now that H has answered the 2nd half of R's claim #1, let's consider the 1st half: Using whatever metric for elegance, Y c a n n o t be elegant for the same [or similar] reason that lambda is. They are not in the same league. Lambda is a core form; Y, on the other hand, is something defined u s i n g lambda. Y can be compared to [let]rec, though. It is strictly less powerful than the latter, for [let]rec can define cyclic data objects, including self-eq recursive procedures, whereas Y can only define non-self-eq recursive procedures. Y can however claim elegance on the following point: it requires only one* core form [lambda] for its definition, whereas [let]rec require two [lambda + set!]. I have used the "elegance" of a construct to mean a combination of 2 factors, the economy of core forms needed to get it going, and the profusion of other constructs this construct itself produces. The latter, when applied to {a set of} core form(s) is better known as "expressiveness". --dorai *if you consider a p p l i c a t i o n to be a core form, add one to both contestants.