Re: The wonders of partial evaluation

[Noah Lavine]

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/
>
>
>