Thank you for the clarifications and the resources, I understand now
what tree shaking is. In fact, I had a project last year at our
college to implement (in Scheme) a constant folding optimizer for
Scheme programs, I now see the resemblance with what you described.
The program would optimize functions like:
(define some-function
(lambda (x)
(if (> x (+ 2 4))
(- 7 (car ‘(1 2 3)))
(cons x 4)))
Turning it into
(define some-function
(lambda (x)
(if (> x 6)
6
(cons x 4))))
Also, when finding conditional statements in which the test condition
is known (can be evaluated) to replace it with the code which runs on
the appropriate branch. For example, replacing:
(if (or #f #t)
then-code
else-code)
With
then-code
Same thing for cond.
Another part of the project was to classify recursive functions into
stack recursive, tree recursive or iterations. I was thinking that a
similar program for Clojure could detect stack recursive functions and
replace them with their iterative counterparts, though this can be
somewhat difficult as various loop-holes can arise that would "fool"
the program.
I suppose an approach can be found which makes the best out of both
worlds: a tree shaker and constant folding implementation + an
automated program which detects recursions and replaces them with more
efficient versions and a rule-based system to cover some cases which
the first approach misses.
Andru Gheorghiu
On Mar 20, 1:31 am, Sanel Zukan <san...@gmail.com> wrote:
> Hi Andru and thank you for expressing interest in this proposal.
>
> > Could you please give more details (or examples) on the types of
> > optimizations the optimizer should be able to do? Also, what is a tree
> > shaker implementation?
>
> As David wrote, this is dead code elimination and in LISP world is also
> known as tree shaking. Contrary to pattern matching (for which you
> expressed desire), dead code elimination is usually more advanced approach,
> sometimes requiring passing through the code multiple times, inspecting
> compiler facilities or simply doing a bunch of tricks to remove obvious and
> not so obvious unused code.
>
> Take this example:
>
> (defonce *always-true* true)
> (if *always-true*
> (println "Always executed")
> (println "Never executed"))
>
> Matching this case could be hard for pattern matching tools; they often do
> not understand the content outside given pattern. True optimizer would pick
> up *always-true* and notice it will never be changed for this block.
> However, if I do some weird magic inside some function and globally change
> the value of *always-true* at some point, optimizer should recognize this
> case or would remove valid code.
>
> Also, often case for optimizers is to precompute simple expressions in
> compilation phase yielding static values, like:
>
> (let [a 0
> b (+ a 1)]
> (if something
> b))
>
> here it could rewrite whole block as:
>
> (if something
> 1)
>
> or even can recognize Clojure patterns like:
>
> (apply + (range 1 10))
>
> where the pattern matching approach could rewrite expression to (+ 1 2 3 4
> 5 6 ... 9) and optimizer would simply produce 45. Using this case you can
> see how pattern matching can be a part of optimizer.
>
> I'm hoping I manage to fully describe you an idea behind this proposal. Of
> course, taking some expert system approach and doing Kibit-style matching
> can be a good starting point too :)
>
> Also, if you are interested to take tree shaking way, a good starting point
> can be SBCL alpha shaker athttp://jsnell.iki.fi/tmp/shake.lisp.
> Unfortunately without documentation, but the code is quite easy to follow.
>
> Sanel
>
>
>
>
>
>
>
> On Saturday, March 17, 2012 10:59:44 PM UTC+1, Andru Gheorghiu wrote:
>
> > Hello,
>
> > I am a third year student majoring in computer science and I am
> > interested in the Clojure code optimizer project proposed for GSoC
> > 2012. Could you please give more details (or examples) on the types of
> > optimizations the optimizer should be able to do? Also, what is a tree
> > shaker implementation?
> > I was thinking that an optimizer could be implemented as a rule engine
> > similar to Jess or CLIPS in which rules contains patterns which need
> > to be replaced and the code to replace them with. For example one
> > could write patterns for generic linear recursive functions that
> > should be replaced with linear iterative functions. Similarly patterns
> > can be written for functions which replicate the behavior of an
> > already existing function (such as reverse, map, apply etc) and a rule
> > to replace those functions with the predefined ones.
>
> > Thank you,
> > Andru Gheorghiu
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
