PAST::Transformer and the Foundation for PAST Optimization

Coding for GSoC officially began this Monday, but I decided to get a head start and started working on PAST::Walker Thursday. PAST::Walker is the foundation for the rest of what I will be doing regarding PAST Optimization, and the foundation is largely laid. There have been a few complications, and a few decisions remain to be made(and implemented) before I can say that PAST::Walker and PAST::Transformer are finished, but implementing PAST::Walker has gone smoothly and quickly for the most part.

PAST::Walker is in part modeled on Python's ast.NodeVisitor. Initially, I wasn't planning to create an equivalent to ast.NodeTransformer. If you wanted to change the tree, you would just change the tree in your walk multi-method. Of course, I soon realized that this doesn't work well for removing a node or replacing it with a different type of node. For that purpose I created PAST::Transformer, a subclass of PAST::Walker that is designed for modifying the tree, including removing nodes and replacing nodes with other types of nodes. It is indeed similar to Python's ast.NodeTransformer, with the walk multi-method returning either null to indicate deleting the node it was walking or the new node with which to replace it(with the original node unchanged being a possibility).

A pair of issues came up when I wrote an example of how to perform a very simple constant-folding optimization on Integer addition with PAST::Transformer. Firstly: I was reminded that PAST::Nodes can have other PAST::Nodes in their attributes as well as in their children array. This presents me with a question: should 'walkChildren' traverse the PAST::Nodes in these attributes? It seems desirable, but the second issue makes it a little problematic: Parrot Abstract Syntax Trees aren't strictly trees. They can have cycles. In fact, it seems common. Just try compiling "say(1+2);" to PAST with NQP. I haven't yet seen any cycles in the actual children of any PASTs. If cycles turn out to be present in the children, too, I'll definitely have to add some sort of cycle-detection code to PAST::Walker.

So, a couple of questions about PAST::Walker/PAST::Transformer:

  1. Should PAST::Walker and PAST::Transformer traverse PAST::Nodes in attributes as well as in the array part of parent nodes?
  2. If I implement cycle-detection in traversal, I am considering doing that by reworking the API of PAST::Walker/PAST::Transformer so that the overridden multi-method would be named 'visit' or something similar, and so that 'walk' instead contains the necessary cycle-detection code and should not be overridden. Does anyone have any suggestions or objections to this?

Now I'm off to implement PAST::Walker::Dynamic. As always, any feedback is welcome via IRC, email, or parrot-dev.