[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?