Sorry for dropping off the radar, I was caught up in some homework for
college.
I've written a very simple program for a limited form of constant
folding:
; Forces evaluation of an expression or returns the expression if
; it can be evaluated
(defn force-eval [exprs]
(try (eval exprs)
(catch Exception e exprs)))
; Recursively evaluates expressions and subexpressions achieving
; constant folding
(defn eval-deep [exprs]
(if (not (list? exprs))
exprs
(let [evaled (force-eval exprs)]
(if (list? evaled)
(map eval-deep evaled)
evaled))))
; Checks if the given argument is a boolean type
(defn boolean? [x]
(or (true? x) (false? x)))
; Replaces an if for which the test condition is known with the
; corresponding branch (then for true, else for false)
(defn replace-if [exprs]
(cond (or (not (list? exprs)) (empty? exprs)) exprs
(= (first exprs) 'if)
(if (boolean? (nth exprs 1))
(if (nth exprs 1)
(first (replace-if (drop 2 exprs)))
(first (replace-if (drop 3 exprs))))
(map replace-if exprs))
:else (map replace-if exprs)))
; Combines eval-deep and replace-if
(defn optimize [exprs]
(let [reduced (reverse (into nil (eval-deep exprs)))]
(replace-if reduced)))
The basic idea was to use exception handlers to try to evaluate and
expression if it can be evaluated and if so, replace it with it's
evaluated form. Then recursively apply this function to an expression
and, if necessary, all subexpressions.
I've also added a function to reduce if statements. Similar functions
can be written for cond, condp, case.
I did have a problem: for some reason my eval-deep function returns a
lazy sequence for the expressions that can't be evaluated. This was an
inconvenient when I was trying to apply another function (namely
replace-if) on the result of eval-deep. To get around this I converted
the lazy sequence into a persistent list, but this lead to that ugly
application of functions in the let in optimize. How could I have
avoided this?
Andru Gheorghiu
On Mar 22, 1:41 pm, Andru Gheorghiu <[email protected]> wrote:
> Thank you for the responses. I'm looking into the resources you gave
> me.
>
> Andru Gheorghiu
>
> On Mar 21, 1:16 pm, Sanel Zukan <[email protected]> wrote:
>
>
>
>
>
>
>
> > I'm happy to see you are familiar with the subject :)
>
> > I was thinking that a
>
> > > similar program forClojurecould 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.
>
> > This isn't a big issue, as recursive functions aren't much advised in
> >Clojure. However, ideal solution would be to detect tail calls and rewrite
> > block in loop/recur combo. This would allowClojureto fully reuse TCO
> > without waiting for JVM to implement it (which will probably never happen).
>
> > 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.
>
> > Using all this tasks would impose a bit of work to complete them all. I
> > would advise taking smaller steps in form of real tasks, followed with
> > rigorous tests. It can look like this:
>
> > * constant folding
> > * empty let removal
> > * lambda reduction
> > * TCO
> > * simplification (using Kibit or directly core.logic)
> > * ...
>
> > If you decide to work on this, for the starting point you can look at
> > "optimizer.scm" (from CHICKEN source) which is nicely summarized at [1] and
> > Egi'scode[2]. Both of them applies common techniques in quite readable
> > manner. Of course, if someone else have additional resource, please share
> > it :)
>
> > Sanel
>
> > [1]http://wiki.call-cc.org/chicken-internal-structure#the-optimizer-opti...
> > [2]https://bitbucket.org/egi/compiler/src
>
> > On Tuesday, March 20, 2012 7:30:41 PM UTC+1, Andru Gheorghiu wrote:
>
> > > 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 foldingoptimizerfor
> > > 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 thecodewhich 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 forClojurecould 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 <[email protected]> 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 theoptimizershould be able to do? Also, what is a tree
> > > > > shaker implementation?
>
> > > > As David wrote, this is deadcodeelimination and in LISP world is also
> > > > known as tree shaking. Contrary to pattern matching (for which you
> > > > expressed desire), deadcodeelimination is usually more advanced
> > > approach,
> > > > sometimes requiring passing through thecodemultiple times, inspecting
> > > > compiler facilities or simply doing a bunch of tricks to remove obvious
> > > and
> > > > not so obvious unusedcode.
>
> > > > 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. Trueoptimizerwould
> > > 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,optimizershould recognize
> > > this
> > > > case or would remove validcode.
>
> > > > 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 recognizeClojurepatterns like:
>
> > > > (apply + (range 1 10))
>
> > > > where the pattern matching approach could rewrite expression to (+ 1 2 3
> > > 4
> > > > 5 6 ... 9) andoptimizerwould simply produce 45. Using this case you
> > > can
> > > > see how pattern matching can be a part ofoptimizer.
>
> > > > 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 thecodeis 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 theClojurecodeoptimizerproject proposed for GSoC
> > > > > 2012. Could you please give more details (or examples) on the types of
> > > > > optimizations theoptimizershould be able to do? Also, what is a tree
> > > > > shaker implementation?
> > > > > I was thinking that anoptimizercould be implemented as a rule engine
> > > > > similar to Jess or CLIPS in which rules contains patterns which need
> > > > > to be replaced and thecodeto 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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
