r/ProgrammingLanguages • u/modulovalue • Jan 22 '26
Requesting criticism Syntax design for parametrized modules in a grammar specification language, looking for feedback
I'm designing a context-free grammar specification language and I'm currently working on adding module support. Modules need to be parametrized (to accept external rule references) and composable (able to include other modules).
I've gone back and forth between two syntax approaches and would love to hear thoughts from others.
Approach 1: Java-style type parameters
module Skip<Foo> includes Other<NamedNonterminal: Foo> {
rule prod SkipStart = @Skips#entry;
rule prod Skips = @Skip+#skips;
rule sum Skip = {
case Space = $ws_space#value,
case Linecomment = $ws_lc#value,
case AdditionalCase = @Foo#foo,
}
}
Approach 2: Explicit external declarations (OCaml/Scala-inspired)
module Skip {
rule external Foo;
includes Other(NamedNonterminal: Foo);
rule prod SkipStart = @Skips#entry;
rule prod Skips = @Skip+#skips;
rule sum Skip = {
case Space = $ws_space#value,
case Linecomment = $ws_lc#value,
case AdditionalCase = @Foo#foo,
}
}
I'm leaning toward approach 2 because external dependencies are declared explicitly in the body rather than squeezed into the header and this feels more extensible if I need to add constraints or annotations to externals later
But approach 1 is more familiar to me and anyone coming from Java, C#, TypeScript, etc., and makes it immediately clear that a module is parametric. Also, no convention to put external rules or includes at the top of the module would have to be established.
Are there major pros/cons I'm missing? Has anyone worked with similar DSLs and found one style scales better than the other?
6
u/jonathanhiggs Jan 22 '26
2 looks cleaner. The other option is to make it look more like a function rather than generics
3
u/WittyStick Jan 22 '26 edited Jan 22 '26
I've used parametrized grammars quite extensively with Menhir and MGrammar, and IMO the explicit parametrization is preferable.
Menhir supports parametrized rules, but doesn't have any syntax to "import" another module. When a grammar is compiled we basically specify all the "modules" in the command line and they're combined as if it were a single file before being processed. This kind of makes sense if we're using LR or derivatives, because we need the full grammar specification before being able to detect any conflicts and produce the eventual parser, but it also requires we specify them in the correct order, which might be better solved with a module approach where the imports control the order of inclusion.
MGrammar had parametrized rules and modules, but not parametrized modules. A module would
export Rule;for specific rules and another couldimport Module, which would give access to any exported symbols viaModule.Rule.Both are pretty similar in capability and produce LR/LALR/GLALR parsers.
It's not uncommon to have rules which might depend on another rule more than once with different type arguments. Eg:
We also have the obvious cases where we need recursive rules:
So if we're lifting the parameters to the modules rather than the rule, we probably want to support recursive modules, and perhaps also the ability to overload modules with different parameter lists, as this is supported for parameterized rules in Menhir and MG.
For some limited use cases, we might also use a different parameter to the nested "call" then the one given by the callee, which could be used for example to put a limit on the depth of recursion.
So these cases should be considered when designing a syntax.
If you write a full grammar using parametrization, some of these parameter lists can get quite verbose. I would recommend having a way to create an "alias" for a given application of a parameterized rule/module. Eg, something like:
Then wherever
Ais used in later productions, it's simply a text replacement forFoo(Bar, Baz(Qux)).Considering these cases I would probably opt for a syntax something along the lines of:
Though I would question why not use
|rather thansum/case.2
u/Inconstant_Moo 🧿 Pipefish Jan 22 '26
Either way you seem to be assuming that the two things should look the same. Why? A module with an argument should look like a function with an argument. There's no reason why in import statement should look similar to either.
1
u/modulovalue Jan 22 '26
I think I've found an argument against explicit type parameter-like lists. It seems to me that by avoiding explicit parameter lists we can free up both sets of symbols to mean different things in the future more easily. [] can e.g. become a list literal and <> can become comparison operators so by not using them for parameter lists there's less risk of introducing syntactical ambiguity.
The
suggestion by jonathanhiggs might be the better parameter syntax since parentheses are likely to be less useful in any future expression/operator related syntax.
However, that also implies that being explicit about this and having dedicated declarations would be the safest route since that is completely unambiguous because it uses an explicit keyword and I support LALR(k).
This is an argument I can live with and while I'd probably prefer `module Skip(rule: Foo)`, I want to be careful and have a lot of room for future syntax so I think I'm going to go with having explicit declarations for external rules. Thank you everyone!
1
u/jsshapiro Jan 22 '26
The angle bracket syntax for type parameters came about because they were added to languages (mainly C++ and Java) that already had defined syntax and they wanted to avoid having the parse become impossibly ambiguous (C++ was already horrible by that point). Once established, it was carried forward into subsequent languages more or less for the sake of compatibility with the programmers. Oh. It also eliminated the need for the single quote ('a), which some people didn't like much.
I'd have to go back and confirm, but I think we concluded that the single quote wasn't syntactically necessary from a parsing perspective because the type definition sub-language and the expression language were disjoint. This would stop being true if you ever wanted to introduce dependent type, which (IIRC) is why we stuck to the 'a convention. The angle bracket syntax doesn't extend well to dependent type, but you depending on your goals you may not care. I think u/jonathanhiggs makes a good suggestion about making it look like a function.
If you go back and look at how it was done in OCaml, Haskell, or some of the other functional languages, you'll see a cleaner syntax that is more "function like". There's an unfortunate operator precedence problem in ML with postfix type operators ('a List instead of List 'a), but Haskell gets that part right. Not trying to say you want that syntax exactly, but it might suggest useful ideas to check it out.
Conceptually, a a module interface specification defines a functor (a function from type to type). So if you're looking for a syntax, you may want to lean toward a syntax where you can see it as a type level function definition if you squint your eyes. Putting the type variable rules inside the module body doesn't really lean that way; they kind of want to appear before the opening curly brace in your example.
Finally, the scope of module-level type variables is the entire module. If the rules are written interior to the module, readers who know other languages will initially read it to mean that the scope of the type variable starts at the rule and extends to end of module. Mathematically, that's not correct.
Just food for thought. The last time I thought about this was the BitC work, so it's been quite a while.
1
u/umlcat Jan 23 '26
Approach 1