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 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-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 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
