The wonders of partial evaluation

The wonders of partial evaluation

[Ludovic Courtès]

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/

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

Re: The wonders of partial evaluation

[Ludovic Courtès]

Hi Noah!

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> 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.)

I’m not sure if it does what you want, but you’re welcome to try and
report back—best way to test is to run:

  (peval (compile exp #:to 'tree-il))

Next step will be to have peval consider local module-private bindings,
which should have more visible effects.

Thanks,
Ludo’.

Re: The wonders of partial evaluation

[dsmich]

---- "Ludovic Courtès" <ludo@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

Bravo!

-Dale