I'm happy to see you are familiar with the subject :) 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. >
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 allow Clojure to 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's code [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-optimizerscm [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 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
