Re: Clojure code optimizer
Very good solution :) To continue this discussion, feel free to mail me; we will also reduce some noise here on the list. Sanel On Friday, April 6, 2012 6:47:37 PM UTC+2, Andru Gheorghiu wrote: > > 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 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 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 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 sys
Re: Clojure code optimizer
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 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 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 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) wh
Re: Clojure code optimizer
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 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 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
Re: Clojure code optimizer
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 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 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, repl
Re: Clojure code optimizer
; > (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
Re: Clojure code optimizer
> > 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). > Not all tail calls are self-recursion. If you call a different function in tail position, there would be no TCO which if I remember correctly is why Rich added recur instead of optimizing self-recursion. He doesn't want to fool you into believing that Clojure supports TCO when it doesn't. -- 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
Re: Clojure code optimizer
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
Re: Clojure code optimizer
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 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 re
Re: Clojure code optimizer
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 at http://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
Re: Clojure code optimizer
On Sat, Mar 17, 2012 at 5:59 PM, 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? > As far as I know this is dead-code elimination. > 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 There's actually some work happening along these lines with Kibit, https://github.com/jonase/kibit. Is this something that interests you? David -- 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
Clojure code optimizer
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
