rar@DUCHAMPS.ADS.COM (Bob Riemenschneider) (11/16/88)
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