It's ok now. The problem was in the let of the optimize function... initially I had: (let [reduced (reverse (into nil (eval-deep exprs)))] because exprs was a lazy sequence and I wanted to turn it into a list. I replaced the "(reverse (into nil ..." part with "(apply list ..." and it works just fine :)
The problem is that this implementation doesn't account for variable scoping, I need to fix that. For example if I have (def n 10) (let [ n 5 ] (+ (+ n 6) something)) If i try to optimize the let it will return (let [ n 5 ] (+ 16 something)) Because it uses the global n defined outside the let. Andru Gheorghiu On Apr 6, 10:56 am, Sanel Zukan <[email protected]> wrote: > This looks really nice; good work! > > To force evaluation of lazy constructs, you can use 'doall' and 'dorun'. > Can you show the snippet with this problem? > > Sanel > > > > > > > > On Thursday, April 5, 2012 1:19:32 AM UTC+2, Andru Gheorghiu wrote: > > > 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 > > ... > > read more » -- 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
