[racket] Y-combinator perfomance

If you're interested in specially the overhead of combinator style,
then your example still understates the overhead compared to relatively
cheap operations.

In addition to Matthias's change to get rid of `apply', I've revised
your program (see below) to replace `first' and `rest' with `car' and
`cdr' (which don't have to check that they're given lists) and to lift
out the list creation (which becomes significant). With those changes,
I get

 cpu time: 1655 real time: 1668 gc time: 1546 ; list creation
 cpu time: 422 real time: 426 gc time: 41
 10000000
 cpu time: 60 real time: 60 gc time: 0
 10000000

The direct version is faster because the compiler can see the loop, so
it can produce code with fewer jumps and less allocation of
intermediate closures. I suppose that the general rule is that the
compiler is more effective when you can use constructs that say more
directly what you want.

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.)

----------------------------------------

#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 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 l (time (make-list 10000000 1)))
(time (comb-sum l 0))
(time (sum l 0))