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 <androi...@gmail.com> 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 <san...@gmail.com> 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 <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 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 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
