The use of closed nonterminals

Motivated by a modular well-definedness analysis for higher-order attribute grammars with forwarding that I developed (for which I just noticed I really need to get a pdf up), I added the concept of “closed nonterminals” to Silver this last year.

Nonterminals in Silver allow extensions to introduce new productions, but only so long as those productions forward back down to the host language.  Extensions are then free to introduce new synthesized attributes, confident that they can always be evaluated via forwarding.  It’s a nice way of solving a very, very strong form of the expression problem.

Closed nonterminals are introduced because we wanted to sometimes make the dual trade-off.  Instead, extensions are allowed to introduce new attributes, but only so long as those attributes have a default value.  Then, new (not necessarily forwarding) productions can be introduced by extensions, confident that if they lack an explicit equation, there will be a default value instead.

In some sense, this switches from a “datatype-like” form of extension to an “object-like” form of extension.  We were motivated to introduce this to handle transformations from concrete syntax tree to abstract syntax trees.  Without closed nonterminals, you’d have a really stupid time trying to write what your new concrete syntax productions have to forward to.  When they’re closed, you don’t have to bother with that, and instead you just can’t add any new truly meaningful attributes to the concrete syntax tree… which is fine because we don’t want to.

At the time of introduction, I also noticed one other specific usage for closed nonterminals… as part of an environment pattern.  We’d write something like:

nonterminal Defs with ...
closed nonterminal Def with ...

To allow extensions to introduce entirely new kinds of definitions into the environment.

Since then, I’d started to feel the urge to use them a little more often, nearly always the same case of handling lists of things: Defs with Def, top level Dcls with Dcl, etc.  However, I had resisted so far, because I wasn’t sure why this would be okay.  Perhaps down the road, we’d suddenly discover this was the wrong decision?  I’d want an explanation for why this is right, and not just convenient now, before I’d start to allow it to be used.  There was a good story for concrete syntax, and for the environment pattern, but not so far for much else.

Simply choosing to make all “list element” nonterminals closed all the time is definitely wrong: Stmts, for example, very very much does not mean Stmt can be a closed nonterminal.  It’d eliminate the ability of an extension to introduce any sort of new analysis.

But, I think I’ve come up with an explanation: any list that exists to only permit an unordered collection of syntax can have its “list element” be a closed nonterminal.  A  good example is modifiers: “public static final,” “final public static,” who cares? The point is simply to recognize what’s there.

I’m still not completely convinced this is sufficient justification for using a closed nonterminal, but it appears to be a necessary condition for some particular class of valid uses.  Modifiers seems very safe, but the idea of making top-level declarations (which meet this criterion, at least for Silver itself) closed still makes me nervous…  The trouble is, we’re running into some extensions we want to write that demand it be closed, but I don’t yet know what sort of interesting extensions would be precluded by doing so.  Which, of course, isn’t evidence that there aren’t any. :)

This entry was posted in Attribute grammars, Compilers, Language extension, Silver and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s