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/