Skip to end of metadata
Go to start of metadata

Problem Statement

In Clojure every expression is a value, however for targets like JavaScript this is not true. JavaScript makes a distinction between expressions and statements. JavaScript dictates where and when which types of expressions may appear - the most flexible type of expression is the function expression - it is allowed to appear nearly anywhere. This allows us to write compound tests (with `and` and `or`) for if expression - in the compiled JavaScript the test expression will be wrapped in a function that is invoked immediately. While this solves the problem this incurs measurable overhead particularly in critical sections. It is undesirable to provide access to lower level JavaScript boolean operators - it's preferable to allow users to write straightforward code and to optimize this as part of the compilation process.

Originally this was done via the Google Closure Compiler. This worked reasonable well, though Closure could be a bit finicky, immediate function invoke nested to a certain level will not be optimized away, in fact if it's deep enough they'll be left entirely alone. This requires tedious review of the generated JavaScript and manual lifting in the ClojureScript code. While tedious this more or less worked and it was hand optimization that rarely need be applied outside of the most critical sections - Closure would catch most of the cases with simple optimizations (note immediate function invokes not removed by simple optimizations would not be removed with advanced).

Unfortunately the most recent Closure Compiler dependency no longer applies the above optimization slowing down nearly all critical functions that have simple boolean tests involving `and` and `or`. This is because `and` and `or` macroexpand to `let` + `if`.

Possible Solutions

  • Write a simple AST rewriter for the specific case
    • Benefits - easy to implement
    • Tradeoffs 
      • with few improvements to the 2 years old AST design, the cruft is growing and this will only add to it
      • no other forms that generate immediate called JS functions will be optimized
  • Design a pluggable AST pass system
    • Benefits
      • force us to make some basic improvements/standardization around the AST
      • allow any future optimizations to be handled in a modular fashion
      • no longer depend on Closure Compiler for language optimizations that may be ignored because less applicable to mainstream JS practice
    • Tradeoffs
      • More design, more work
        • Needs to consider the AST
        • Need a future looking optimization design
        • Lots of room for potential breakage and unforeseen edges cases
  • Combine the two solutions above
    • Write standalone AST -> ANF library
    • Abstract the complier enough to make it straightforward to plugin a selective pass
    • Restrict the pass to the `if` AST nodes where the test expr is a `let` AST node
Labels:
  1. Aug 22, 2013

    I have found two transforms really useful when compiling expression oriented languages (like Clojure) to statement oriented languages (Go, C, Javascript, ...):

     

    1. alpha conversion
      1. renaming bound names to a unique name lets you easily do things like merge/un-nest lets
      2. http://www.haskell.org/haskellwiki/Alpha_conversion
      3. http://en.wikipedia.org/wiki/Lambda_calculus#Alpha_equivalence
      4. a downside is names in the source don't match up with names in the result anymore
    2. A-Normal Form
      1. http://matt.might.net/articles/a-normalization/
      2. turns a a complex graph of computation in to something less complex and more linear
      3. I've found transforming a conditional expression (if ...) in to a conditional statement if () {} via anf to be tricky
    1. Aug 25, 2013

      What about 2c did you find challenging? ANF appears to cover that case cleanly but maybe I'm missing something?

  2. Aug 22, 2013

    the two solutions above don't seem to be in conflict, if passes take a valid ast and return a valid ast, then you should be able to apply them locally in specific cases

  3. Aug 22, 2013

    I guess what I am saying is there are at least two things here, not one:

    1. what transforms and optimizers would be useful for clojurescript?
      1. and how can we make it easier nicer to use them?
    2. where and how should transforms and optimizers be applied?

    #a sort of blurs the line between #1 and #2 because "it would be easier to use transforms if we had a pluggable system, and a pluggable system would be applied globally" but if a transform is really ast -> ast then #1 and #2 are orthogonal.