PAST Optimization: GSoC is over

The Google Summer of Code pencils-down date was last Monday. GSoC is now over, but I don't plan to stop working on my project.

The initial goals listed in my project proposal were:

  • A library for PAST traversal.
  • A framework for PAST optimization and analysis tools.
  • A regular-expression-like pattern matching library for PASTs.
  • An optimization to turn tail-calls in PAST into PIR ".tailcall".

The first item, a library for PAST traversal, exists as PAST::Walker and PAST::Transformer in the tree-optimizations module, which is available via Plumage. In addition, they have been generalized to Tree::Walker and Tree::Transformer, which can traverse any Capture. It's fairly full-featured, although I need to add to Tree::Transformer the ability to replace a single node with multiple.

The tree-optimization module also contains a framework for PAST optimizations. This is Tree::Optimizer and its specialized form for PAST optimizations, PAST::Optimizer. It doesn't really have any explicit support for analysis yet, although you can treat analyses as optimization passes that place the information in an unused attribute of the PAST. There's also currently a bug in Tree::Optimizer.run(:combine) which makes it unusable.

The pattern-matching library, Tree::Pattern and its subclasses, is in tree-optimization, as well. It supports exact, global, and recursive single matching, as well as global transformations.

The tail-call optimization and a simple constant-folding optimization are available for use with PAST::Optimizer in the simple-optimizations module, which has not yet been added to Plumage. The constant-folding optimization has the limitation that it may not produce the same result type (although it does produce the right result value). This appears to be due to a PCT bug.

I got most of the things I initially planned accomplished. There are some bugs to fix and probably some performance improvements that can be made. The documentation and tests can both still be improved. I plan to work on those some more.

From here, I want to work towards getting tree-optimization either merged into Parrot or included in ext/. Once that's done, I want to get some simple optimizations (possibly including those in simple-optimizations) added to NQP-rx. In the long term, I want to develop either an SSA or CPS form to and from which to transform PASTs in order to more easily perform typical optimizations.

Happy hacking, folks!