On Wed, May 20, 2015 at 1:44 PM, 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
Technically, I don't think that counts as a GADT, since it doesn't even have a type parameter. But I understand the similarity. > 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. I see that it'd be easier, more efficient, and more reliable if we could express it in the type. I don't have an opinion on where to perform the checks at runtime. > 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 can't figure out what you're getting at here. Don't you just want something like: type Node<T> = MetaData * T type AST = ... and Expr = | MulExpr of Node<Expr> * Node<Expr> Then a recursive function might look like: fooAST : Node<AST> -> Foo fooAST (md,d) = match d with ... fooExpr : Node<Expr> -> Foo fooExpr (md,d) = match d with | MulExpr(el,er) -> ... Is that too heavy? Still seems shorter than writing checkers or builders. _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
