Syntax for specifying operator precedence and associativity

[j-hui]

Right now, we are lexing and parsing operators like +, -, etc., and then doing some late-stage parsing to assemble OpRegions into proper expression-level applications in AST. But we're doing so based on some hard-coded rules.

We should be exposing some kind of syntax/mechanism for users to control this late-stage parsing, so that they may define their own late-stage parsers for this kind of thing. Basically, something like Haskell's infixl and infixr constructs.

[j-hui]

I should note that I am not a fan of Haskell's parser programming interface. I'm not actually sure what happens when one specifies different precedence/associativity for the same operator, in two different modules. I am hoping that whatever solution we arrive at will be compatible with modularity.

Coq's Notations solve this issue with scopes. But having played around with that, my takeaways are: (1) having to explicitly annotate the scope takes away from the brevity it's supposed to bring; (2) when scopes aren't annotated, I have no idea how infers what it infers; and (3) error messages related to this are inscrutible, though I'm not sure if that's more so due to the size and power of its Notation system and indeed the rest of its type system.

[j-hui]

In any case, we should draft out a few basic examples of things we'd want to do, i.e., the kinds of operator syntax we'd like to specify. The usual suspects are:

• Binary operator associativity and precedence
• Unary operator precedence

Something that always bothers me is that precedence is typically specified as some arbitrary, hard-coded number. I would much prefer to say something like "I would like my operator to have higher precedence than + but lower than *, and then let the parser figure out a total order from that.

[sedwards-lab]

Haskell doesn't do custom unary operators. For the moment, we can leave them built-in and later consider whether to just use Haskell's simple model or try to come up with something more. This is a low priority thing

[sedwards-lab]

I believe Swift has a more "relational" specification of precedence levels (e.g., "this is above that"). It gets tricky because you need to make sure it's deterministic, feasible, etc.