Pattern-Matching Visitors

This idea of viewing rscc as a dialect of ml is mentioned elsewhere. For example, we can define functions in ML like this:

datatype expr = True
              | False
              | If of expr*expr*expr

let visit True = ...
let visit False = ...
let visit If(a,True,False) = ...
let visit If(If(a,b,c),d,e) = ...

I propose that we allow this in rscc. Specifically, I propose that we do so in the context of the visitor pattern. A flavor of the proposed extension:

Visitor myvisitor {
  /* Think of this as the private members of a class */
  /* They are only accessible to myvisitor methods */
  int infndef;
}

VisitorAction
myvisitor::previsit fndef
{
  infndef = 1;  // accessed like a private class member
  ...
  return someVisitorAction;
}

VisitorAction
myvisitor::previsit expr{true}
{
  ...
}

VisitorAction
myvisitor::postvisit expr{if (if \a then \b else \c) then \d else \e}
{
  ...
}

This allows the programmer to implement the visitor pattern using pattern-matching guards for each block of code. This has a few advantages over the compile/rewrite idiom currently in rscc:

Visit actions

Not sure exactly what the supported visit actions should be, so I'll borrow from CIL:

struct VisitorAction {
  Action type;
  AST*   code;    // only valid for one of the ChangeTo* actions
};
enum Action {
  DoChildren,     // proceed normally (without changing the AST)
  SkipChildren,   // even if we have matching visitors, don't visit
                  //  the children of this AST node
  ChangeToDo,     // replace the visited AST with some new code and
                  //  traverse on that new code
  ChangeToSkip,   // replace the visited AST with some new code but
                  //  do not traverse it
};

Implementation

Each visitor should be compiled into a static, name-mangled function which is placed in a dispatch table (somehow indexed by pattern). We should consult previous research to see how this is done in ML. Also, the compiler could warn the user about redundant or ambiguous patterns. For example, if two patterns can match the same code it is not clear which should be dispatched. (Is this checking even decidable? The OCaml compiler does emit warnings for "in-exhaustive matches" and other things, so it is probably possible in some cases, atleast.)

We probably want to allow some ambiguity in patterns, as ML does. For example, the last pattern matches everything the first two patterns do, but the first two patterns should be invoked wherever possible because they are more specific:

expr{if true then \t else \f}
expr{if (if \a then \b else \c) then \t else \f}
expr{if \c then \t else \f}