[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: scheme@mc.lcs.mit.edu*Subject*: Efficiency of Y (Was: Limitation with lambda)*From*: zodiac!DUCHAMPS.ADS.COM!rar@ames.arpa (Bob Riemenschneider)*Date*: Mon ,14 Nov 88 18:29:54 EDT*Sender*: scheme-request@mc.lcs.mit.edu

[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

**Follow-Ups**:**Re: Efficiency of Y (Was: Limitation with lambda)***From:*edward@ucbarpa.berkeley.edu (Edward Wang)

**Re: Efficiency of Y (Was: Limitation with lambda)***From:*mike@arizona.edu (Mike Coffin)

- Prev by Date:
**self duplicating code summary** - Next by Date:
**Re: Efficiency of Y (Was: Limitation with lambda)** - Previous by thread:
**self duplicating code summary** - Next by thread:
**Re: Efficiency of Y (Was: Limitation with lambda)** - Index(es):