[racket] Y-combinator perfomance

This version misses an explicit combinator passing. Z can be replaced by I, Z-memoize, Z-verbose or any other, this is the point.

25.06.10, 22:58, "Ryan Culpepper" <ryanc at ccs.neu.edu>:

> On 06/25/2010 12:59 PM, Groshev Dmitry wrote:
>  > Is there any way to avoid this overhead? I'm really interested in
>  > combinator style, but if it makes programs 8 times slower, it is
>  > useless. Maybe some compiler/macro optimizations is possible?
>  
>  You might find this version interesting:
>  
>  (define-syntax define/rec
>    (syntax-rules ()
>      [(define/rec (name arg ...) body)
>       (define name
>         (let ([actual
>                (λ (self arg ...)
>                  (let-syntax ([name
>                                (syntax-rules ()
>                                  [(name name-arg (... ...))
>                                   (self self name-arg (... ...))])])
>                    body))])
>           (lambda (arg ...) (actual actual arg ...))))]))
>  
>  The (... ...) escapes the ellipses, so they are interpreted as ellipses
>  for the local 'name' macro, not the 'define/rec' macro.
>  
>  (define/rec (rec-sum l t)
>    (if (empty? l) t (rec-sum (cdr l) (+ t (car l)))))
>  
>  Ryan
>  
>  
>  > 25.06.10, 22:50, "Matthew Flatt" :
>  > 
>  >> 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))
>  >>  
>  >>  
>  >>  
>  > _________________________________________________
>  >   For list-related administrative tasks:
>  >   http://lists.racket-lang.org/listinfo/users
>  
>