[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) |
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/
- The wonders of partial evaluation,
Ludovic Courtès <=