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" <ry...@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 > > _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
