rar@DUCHAMPS.ADS.COM (Bob Riemenschneider) (11/15/88)
[Sorry this is so late; I'm behind on my correspondence.]
Awhile ago, Joe Weening asserted (in response to an article posted by
Jonathan Dubman) that use of the Y combinator for definition of recursive
functions "would be fairly inefficient". Mark VandeWettering then questioned
this assertion in his response to Joe, saying that looking at the
efficiency of Y was an element of his thesis work.
Here's a simple experiment you can perform using your favorite Scheme.
1. Define a fixed point combinator:
(define Y
(lambda (g)
((lambda (h) (g (lambda (x) ((h h) x))))
(lambda (h) (g (lambda (x) ((h h) x)))))))
2. Define three procedures for computing the factorial function,
one iterative:
(define factorial-loop
(lambda (n)
(do ((i 1 (+ i 1))
(a 1 (* i a)))
((> i n) a))))
one recursive (but not tail-recursive, so introduction of an
accumulator is left up to the compiler):
(define factorial-rec
(lambda (n)
(if (= n 0)
1
(* n (factorial-rec (- n 1))))))
and one using the combinator:
(define factorial-lfp
(Y (lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1))))))))
3. Compute the factorial of a number using each of the three procedures,
timing the results. Make the number large enough so that you can get
a reasonably accurate timing. (I found 100 worked well for MacScheme,
and 1000 for T on my Sun 3.)
I found performance of the three to be identical, leading me to believe that,
given current Scheme compiler technology, there's no reason to avoid using Y.
-- raredward@ucbarpa.Berkeley.EDU (Edward Wang) (11/15/88)
In article <8811142229.AA01756@duchamps.ads.com> you write: > 3. Compute the factorial of a number using each of the three procedures, > timing the results. Make the number large enough so that you can get > a reasonably accurate timing. (I found 100 worked well for MacScheme, > and 1000 for T on my Sun 3.) > >I found performance of the three to be identical, leading me to believe that, >given current Scheme compiler technology, there's no reason to avoid using Y. Wouldn't the time be dominated by bignum arithmetic? A better test would be to go through the iterations without actually computing the factorial.
mike@arizona.edu (Mike Coffin) (11/16/88)
From article <8811142229.AA01756@duchamps.ads.com> (Bob Riemenschneider): > Here's a simple experiment you can perform using your favorite Scheme. [three definitions of a factorial function omitted: one iterative, one recursive, and one using the Y combinator] > 3. Compute the factorial of a number using each of the three procedures, > timing the results. Make the number large enough so that you can get > a reasonably accurate timing. (I found 100 worked well for MacScheme, > and 1000 for T on my Sun 3.) > > I found performance of the three to be identical, leading me to believe that, > given current Scheme compiler technology, there's no reason to avoid using Y. I tried this using T. When I performed the experiment as stated, I indeed got identical times for the three definitions: > (time (factorial-loop 100)) virtual time = 0.36 seconds > (time (factorial-rec 100)) virtual time = 0.36 seconds > (time (factorial-lfp 100)) virtual time = 0.36 seconds However, when I instead calculated the factorial of a small number many times, there was a huge difference --- more than a factor of 10 --- between the times: > (time (factorial-loop 10) 1000) virtual time = 0.18 seconds > (time (factorial-rec 10) 1000) virtual time = 0.2 seconds > (time (factorial-lfp 10) 1000) virtual time = 2.58 seconds I think the benchmark, as originally stated, mostly measures the speed of longnum arithmetic, and not the efficiency of the various contol constructs. -- Mike Coffin mike@arizona.edu Univ. of Ariz. Dept. of Comp. Sci. {allegra,cmcl2}!arizona!mike Tucson, AZ 85721 (602)621-2858