* The wonders of partial evaluation
@ 2011-09-08 22:32 Ludovic Courtès
2011-09-08 22:59 ` Noah Lavine
2011-09-08 23:31 ` dsmich
0 siblings, 2 replies; 4+ messages in thread
From: Ludovic Courtès @ 2011-09-08 22:32 UTC (permalink / raw)
To: guile-devel
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/
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: The wonders of partial evaluation
2011-09-08 22:32 The wonders of partial evaluation Ludovic Courtès
@ 2011-09-08 22:59 ` Noah Lavine
2011-09-09 8:38 ` Ludovic Courtès
2011-09-08 23:31 ` dsmich
1 sibling, 1 reply; 4+ messages in thread
From: Noah Lavine @ 2011-09-08 22:59 UTC (permalink / raw)
To: Ludovic Courtès; +Cc: guile-devel
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/
>
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: The wonders of partial evaluation
2011-09-08 22:32 The wonders of partial evaluation Ludovic Courtès
2011-09-08 22:59 ` Noah Lavine
@ 2011-09-08 23:31 ` dsmich
1 sibling, 0 replies; 4+ messages in thread
From: dsmich @ 2011-09-08 23:31 UTC (permalink / raw)
To: guile-devel, Ludovic Courtès
---- "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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: The wonders of partial evaluation
2011-09-08 22:59 ` Noah Lavine
@ 2011-09-09 8:38 ` Ludovic Courtès
0 siblings, 0 replies; 4+ messages in thread
From: Ludovic Courtès @ 2011-09-09 8:38 UTC (permalink / raw)
To: guile-devel
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’.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2011-09-09 8:38 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-09-08 22:32 The wonders of partial evaluation Ludovic Courtès
2011-09-08 22:59 ` Noah Lavine
2011-09-09 8:38 ` Ludovic Courtès
2011-09-08 23:31 ` dsmich
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).