Optimize referentially transparent macros.

[jbearer]

Most macro handlers are referentially transparent: executing them has no side-effects, and they always return the same parse tree in terms of the inputs. These handlers ought not to be invoked and interpreted every time the macro is expanded. Instead, we should associate with each such macro definition a "parse tree with holes", that can be instantiated with concrete values for the sub-trees in about as long as it takes to copy a parse tree, without executing bl:mp code.

The basic idea is to execute the macro handler once, when the macro is defined, using placeholders ("holes") for the input sub-trees. As long as the macro does not try to destruct its inputs (by sending to them) then this will succeed, and the result can be converted to a ParseTree with holes. We then register the macro with a new handler (like OptimizedMacroHandler) and the parse tree template as an argument. When the macro is invoked, we simply walk the template parse tree, copying as we go, and replacing holes with the input sub-trees. This should be about as fast as a normal, built-in production, with no overhead despite the macro being defined in bl:mp.

The caveat is that, right now, it is hard to detect when macro handlers are referentially transparent, because virtually all of them use local state, as the only way to extract the individual sub-trees of a parse tree with the current parse tree protocol is to instantiate a local counter variable. The interpreter currently has a very hard time proving that that symbol is not defined outside the local scope of the macro handler (and if it were, that would constitute a use of global state that breaks referential transparency). To get around this, we can do one or more of the following:

• Wait until static symbol analysis reaches the point where we can often identify the scope of a symbol at compile time, and thus eliminate local variables from the referential transparency check. This is the most general solution but it's far off.
• Add a very simple, overly conservative "is-symbol-in-scope?" analysis pass. This is just a heavily stripped down version of the above, and so should only be added if it proves really necessary.
• Change the parse tree protocol to make it easier to extract sub-trees of a parse tree without state. There is actually a very simple change we can make that effectively turns parse tree visitors into curried callbacks that receive all of the sub-trees as arguments: instead of sending each sub-tree to the same visitor, send each sub-tree to the return value of the previous visitor. Most bl:mp parse tree objects already do this, as they assume the visitor returns itself each time and accepts method chaining. All we'd have to do is codify the pattern and implement it for built-in parse tree objects. Then we can write code using visitors that return not themselves but a new visitor for the next sub-tree, capturing the original sub-tree in scope, like so

  \> {...some macro definition...} {^toks
      ^toks {^first_sub_tree{^second_sub_tree{^etc
          {...some parse tree using ^first_sub_tree, ^second_sub_tree, ^etc}
      }}}
  }
  

  This solution is not as general as improved symbol scope analysis. However, it allows us to optimize many common macro definitions with no additional static analysis, and it is such an improvement to the parse tree API that it may be worth doing regardless. Still, this will not improve the performance of macros using the std prelude syntax syntax and parse_tree data structures. Those will almost inevitably use at least local state and global constants, and so will require symbol analysis to optimize.