[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: The wonders of partial evaluation
From: |
Noah Lavine |
Subject: |
Re: The wonders of partial evaluation |
Date: |
Thu, 8 Sep 2011 18:59:09 -0400 |
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 <address@hidden> 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/
>
>
>