On Fri, Jun 25, 2010 at 11:50 AM, Matthew Flatt <mfl...@cs.utah.edu> wrote: > > Compilers can't easily see through a Y combinator, and a factor of 8 or > so difference is probably typical for Lisp compilers. (I tried Ikarus > and Gambit to double check, and performance was about the same as with > Racket.)
See @INPROCEEDINGS{Juan92tamingthe, author = {Guillermo Juan and Guillermo Juan Rozas}, title = {Taming the Y operator}, booktitle = {In ACM Conference on LISP and Functional Programming}, year = {1992}, pages = {226--234}, publisher = {ACM Press} } ``In this paper I present a set of conceptually simple but involved techniques used by Liar 1 , the MIT Scheme compiler, to generate good code when recursive procedures are specified in terms of suitable versions of the Y operator. The techniques presented are general-purpose analysis and optimization tools, similar to well-known techniques used in the analysis and optimization of applicative languages, that combine synergistically to enable Liar to generate identical machine code for ordinary recursive definitions written using letrec and those written using suitable forms of Y.'' ;; Allow compiler to inline standard procedures. (declare (usual-integrations)) (define-syntax U (syntax-rules () ((_ f) (f f)))) (define-syntax define/comb (syntax-rules () ((_ comb name (arg1 arg2) body) (define name (comb (lambda (name) (lambda (arg1 arg2) body))))))) ;; Allow compiler to inline Z (define-integrable (Z f) (U (lambda (g) (lambda (x y) ((f (U g)) x y))))) (define/comb Z comb-sum (l t) (if (null? l) t (comb-sum (cdr l) (+ t (car l))))) (define (sum l t) (if (null? l) t (sum (cdr l) (+ t (car l))))) (define (test1) (let ((start-time (runtime)) (l (make-list 10000000 1))) (let ((answer (comb-sum l 0))) (- (runtime) start-time)))) (define (test2) (let ((start-time (runtime)) (l (make-list 10000000 1))) (let ((answer (sum l 0))) (- (runtime) start-time)))) (test1) => .11 seconds (test2) => .11 seconds -- ~jrm _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users