To Y or not to Y? That is the question! (Was: Efficiency of Y)

[zodiac!DUCHAMPS.ADS.COM!rar@ames.arpa (Bob Riemenschneider)]

Apparently, I should have been more explicit about the point I was making
in my previous posting.  Let me take another shot at it.

When Joe Weening wrote that use of the Y combinator for definition of 
recursive functions "would be fairly inefficient", I took him to be making
a general claim that you shouldn't use Y.  (Maybe I was wrong about this.)
I decided to test this claim.  Like most Lisp programmers, the first recursive
function test I try when testing is factorial.  It turned out that bignum 
arithmetic performance dominated everything else in the computation.  
*That was the point I was trying to make.*  My conclusion was not that you 
can *always* use Y without performance penalty--I knew that was false based 
on the second experiment I tried (see below)--but that you can *sometimes* 
use Y without *significant* performance penalty.  For all I knew a priori,
(factorial-lfp N) would run [[N]] times as slowly as (factorial-rec N), so 
this seemed significant enough to post.  Given that Y makes for more
elegant code than letrec--it's nice for the same reasons that lambda is nice--
the experiment shows that there may be a role for Y in your Scheme toolkit.  
In particular, if you need to compute factorials (or Fibonacci numbers, or 
...), but you don't need to compute them often, feel free to use Y.  My 
statement that 

	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.

would have been less misleading if I'd added "completely" at the end.  
But, based on the performance figures I've seen and my second experiment, 
I'm now willing to go a bit farther.

Here's the second experiment.

   1.	Build a moderately complicated test list.

		(define l '())

		(do ((i 0 (+ i 1))) 
		    ((> i 15) i) 
                    (set l (cons l l)))

	(15 was determined by trial and error using T on a Sun--I wanted
	the largest value that wouldn't cause a garbage collection during
	a test run.)

   2.	Define three procedures for computing the function flatten, one
	iterative:

		(define flatten-trec-aux 
		   (lambda (l l-aux l-acc)
		      (cond ((null? l-aux) 
		                (cond ((null? l) l-acc)
		                      ((atom? l) (cons l l-acc))
		                      (else      
                                         (flatten-trec-aux 
		                            (car l) (cdr l) l-acc))))
		            ((atom? l-aux) 
                                (flatten-trec-aux l '() (cons l-aux l-acc))) 
		            (else          
		                (flatten-trec-aux 
		                   (cons l (car l-aux)) 
		                   (cdr l-aux) 
		                   l-acc)))))
		
		(define flatten-trec 
		   (lambda (l) 
		      (flatten-trec-aux l '() '())))


	one recursive:

		(define flatten-rec 
		   (lambda (l)
                      (cond ((null? l) '())
                            ((atom? l) (list l))
                            (else      (append 
                                          (flatten-rec (car l)) 
                                          (flatten-rec (cdr l)))))))

	and one using Y:

		(define flatten-lfp 
		   (Y (lambda (f)
                         (lambda (l)
                            (cond ((null? l) '())
                                  ((atom? l) (list l))
                                  (else      (append 
                                                (f (car l)) 
                                                (f (cdr l)))))))))

   3.	Compute flatten of l using each of the three procedures, garbage 
	collecting between computations.

No bignums here, just basic list manipulation.  I found flatten-lfp to be
about half as fast as flatten-rec, and flatten-rec to be about half as fast
as flatten-trec.  (And I have a funny feeling flatten-trec-aux wasn't the
best choice of an auxiliary function for flatten-trec; it's just the first
thing that occurred to me.)

I'm still not sure I have a good handle on the efficiency of Y.  But, based 
on my two experiments and the other figures I've seen posted, I'll stick my
neck out and claim: 

	Y is *efficient enough* that using, say, 

		((Y (lambda (f) ... f ...)) --- )

	in place of 

		     (letrec ((f ...f...))
		         (f ---))

	where ...f... won't give you tail-recursion, is *never* bad
	programming; if efficiency is enough of a concern that Y
	shouldn't be used, you should come up with an iterative
	algorithm.
	
(Unlike my original claim, this *ought* to create some controversy!)


							-- rar