[racket] Y-combinator perfomance

From: Groshev Dmitry (a2alt at ya.ru)
Date: Fri Jun 25 13:59:51 EDT 2010

Here is the code:
#lang racket
(define-syntax U
  (syntax-rules ()
    [(_ f) (f f)]))
(define-syntax define/comb
  (syntax-rules ()
    [(_ comb name (arg . args) f)
     (define name 
       (comb (λ (name) (λ (arg . args) f))))]))

(define (Z f)
  (U (λ (g) (λ x
              (apply (f (U g)) x)))))

(define/comb Z comb-sum (l t) 
  (if (empty? l) t (sum (rest l) (+ t (first l)))))

(define (sum l t)
  (if (empty? l) t (sum (rest l) (+ t (first l)))))

(time (comb-sum (make-list 10000000 1) 0))
(time (sum (make-list 10000000 1) 0))
Here is the result:
cpu time: 4664 real time: 4656 gc time: 2278
10000000
cpu time: 3276 real time: 3326 gc time: 1014
10000000
Why so much overhead? Is there any way to avoid it without missing the combinator's power?


Posted on the users mailing list.