Hello! Three days ago I had the chance to attend William Cook’s excellent tutorial on partial evaluation at DSL 2011, called “Build your own partial evaluator in 90 minutes” [0].
A few times 90 minutes later, I am pleased to announce a new partial evaluator for Tree-IL: http://git.sv.gnu.org/cgit/guile.git/commit/?h=stable-2.0&id=11671bbacbdd52039c77978bfe7f24a3316f6019 Partial evaluation is “the mother of all optimizations”, and in particular that of constant propagation and inlining. So that’s what the partial evaluator is here for. A few examples, showing code before and after partial evaluation: (let ((x 1) (y 2)) (+ x y)) => (const 3) (letrec ((even? (lambda (x) (or (= 0 x) (odd? (- x 1))))) (odd? (lambda (x) (not (even? (- x 1)))))) (and (even? 4) (odd? 7))) => (const #t) (letrec ((fibo (lambda (n) (if (<= n 1) n (+ (fibo (- n 1)) (fibo (- n 2))))))) (fibo 7)) => (const 13) Here all the values are known at compile-time, so the partial evaluator does basically the same job as ‘eval’. (let ((f (lambda (x y) (if (> x 0) y x)))) (+ (f -1 x) (f 2 y) (f z y))) => (let (f) (_) ((lambda (_) (lambda-case (((x y) #f #f #f () (_ _)) (if (apply (primitive >) (lexical x _) (const 0)) (lexical y _) (lexical x _)))))) (apply (primitive +) (const -1) ; (f -1 x) (toplevel y) ; (f 2 y) (apply (lexical f _) ; (f z y) (toplevel z) (toplevel y)))) Here calls to ‘f’ have been inlined 3 times and specialized twice. Isn’t it great? :-) Note that currently this only works with lexical bindings, not across top-level bindings–i.e., a top-level binding never gets inlined. Of course the main difficulty is to make sure it behaves correctly in the presence of effects. Please let me know if you suspect a compilation problem (partial evaluation can be turned off, see ‘optimize.scm’.) Feedback welcome! Ludo’. [0] http://www.cs.utexas.edu/~wcook/tutorial/