Path: utzoo!attcan!uunet!husc6!think!ames!zodiac!DUCHAMPS.ADS.COM!rar
From: rar@DUCHAMPS.ADS.COM (Bob Riemenschneider)
Newsgroups: comp.lang.scheme
Subject: Efficiency of Y (Was: Limitation with lambda)
Message-ID: <8811142229.AA01756@duchamps.ads.com>
Date: 14 Nov 88 22:29:54 GMT
Sender: daemon@zodiac.UUCP
Lines: 56

[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