Efficiency of Y (Was: Limitation with lambda)

[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.

-- rar