This is excellent! Congratulations! An interesting note from my current project: a partial evaluator means you don't have to use macros to define the PEG parser (while keeping exactly the same efficiency as now): instead of having (define-peg pattern) be a macro that analyzes pattern and outputs code, you have, (interpret-peg pattern string) be a program that parses string with peg. Then to generate code, you just partially apply interpret-peg to pattern, leaving string undetermined. (I'm not sure if the partial evaluator currently does this, but it would be an interesting approach.)
Noah On Thu, Sep 8, 2011 at 6:32 PM, Ludovic Courtès <l...@gnu.org> wrote: > 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/ > > >
