[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

The wonders of partial evaluation

From: Ludovic Courtès
Subject: The wonders of partial evaluation
Date: Fri, 09 Sep 2011 00:32:09 +0200
User-agent: Gnus/5.110018 (No Gnus v0.18) Emacs/24.0.50 (gnu/linux)


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:

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)
                       (+ (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 (_)
              (((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

Feedback welcome!



reply via email to

[Prev in Thread] Current Thread [Next in Thread]