[racket] Y-combinator perfomance

I think you're comparing apples and oranges here. 
The use of _apply_ should make things a lost slower
for comb-sum than for sum. Also, you should collect
garbage before you run timed microbenchmarks. Otherwise
you might have bad interactions. With that done, I
get the following results: 

> [:~/Desktop] matthias% racket y.rkt
> cpu time: 5127 real time: 5427 gc time: 1834
> 10000000
> cpu time: 4289 real time: 4557 gc time: 1369
> 10000000
> [:~/Desktop] matthias% !!
> racket y.rkt
> cpu time: 5129 real time: 5523 gc time: 1840
> 10000000
> cpu time: 4313 real time: 4658 gc time: 1373
> 10000000
> [:~/Desktop] matthias% !!
> racket y.rkt
> cpu time: 5113 real time: 5404 gc time: 1835
> 10000000
> cpu time: 4308 real time: 4622 gc time: 1376
> 10000000

As you can see, three runs produce a rough average
of a 20% overhead. I think that's a fair price for
an applicative vs an imperative recursion. 

-- Matthias

CODE: 

#lang racket

(define-syntax U
  (syntax-rules ()
    [(_ f) (f f)]))

(define-syntax define/comb
  (syntax-rules ()
    [(_ comb name (arg1 arg2) body)
     (define name 
       (comb (λ (name) (λ (arg1 arg2) body))))]))

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

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

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

(collect-garbage)(collect-garbage)
(time (comb-sum (make-list 10000000 1) 0))

(collect-garbage)(collect-garbage)
(time (sum (make-list 10000000 1) 0))




On Jun 25, 2010, at 2:07 PM, Groshev Dmitry wrote:

> I've mistyped. In fact things are even worse.
> #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 (comb-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))
> Result:
> cpu time: 9922 real time: 10007 gc time: 3323
> 10000000
> cpu time: 2762 real time: 2783 gc time: 469
> 10000000
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users