On Wed, May 20, 2015 at 10:44 AM, Jonathan S. Shapiro <[email protected]> wrote: > I've just noticed a problem in my previous AST/MetaAST question, and it > *appears* to me that it forces one of the outcomes rather than the others. > > The variant portion of the AST node is typically expressed as a GADT. The > general idea is that if we know a parent node we know what it's child nodes > are supposed to be. So, for example, we have something like: > > type AST = > ... > and Expr = > | MulExpr of Expr * Expr > > > so far, so good. But now suppose that we want to carry position information > with every AST node. We appear to have two choices: > > 1. Add a Position field (or in the more general case, an ASTMetaData field) > to every tuple on every AST. > 2. Stop checking the tree coherence statically, and instead do it > dynamically. > > The second approach would force us to do something like: > > type AST = > ... > and Expr = > | MulExpr of AST * AST > > where there is a known relationship between the parent node type and the > allowed child node types, but we don't attempt to capture or check them > statically. This is basically what BitC v0 is doing with ASTMaker. We > describe something similar to a GADT in ASTMaker, and generate a sanity > checking function that runs over the AST. We could also (but currently do > not) generate "builder" helper functions to check that the tree is composed > correctly. > > I can do that, of course, but it seems inconsistent with the spirit of > things.
Indeed, this is about where I threw in the towel and just duplicated ASTMetaData across the legs of the AST, going along with the statically checked AST spirit of things > Last option, which I think does not really work, and cannot really be done > in F#, O'Caml, or Haskell, is to exploit the fact that a union leg type > actually *is* a type, and use parameterization. I don't have a way to > syntactically express this in these languages, but the general idea is that > the metadata node and the AST type would be mutually recursive types, and > the metadata node would be of the form MetaASTNode<LegType-or-group-type> I'd think O'Caml and SML can probably do so using functors, not sure about doing so elegantly or if priorities justify it... _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
