I am writing a parser that will parse a simple functional toy language.
I'm having tough time with operator precedence and associativity of morphism, product and coproduct operators.
My toy language looks a tiny bit like Haskell. Example for context:
let point: (int, int) = (0, 0) // product
let either: (int | str) = "hello" // coproduct
let increment: int -> int = a -> a 1 // morphism
In parsing types, I have a hard time deciding if the binary infix morphism operator ->
should be right or left associative. The binary infix functional composition operator .
is right associative if I'm not mistaken; maybe it's the same with this operator too?
Should int -> int -> int
be parsed as (int -> int) -> int
or int -> (int -> int)
?
What is the precedence of this operator in relation with the binary infix product and coproduct operators (,
, |
)?
Right now I have the following priorities (from highest to lowest):
- morphism
- product
- coproduct
This means that in absence of round grouping parenthesis (...)
the language behaves as follows:
The product str, int -> int, str
gets parsed as str, (int -> int), str
.
The coproduct int | str -> int | str
has the same effect int | (str -> int) | str
.
And str, int -> int | int
gets parsed as (str, (int -> int) | int)
.
Is that correct or am I doing something wrong?
Reasons why this is a valid question
I apologise but I'm avoiding getting flagged when this is a good question because:
- I could not find resources that explain how these three operators are related to each other, in which way, precedence and associativity.
- I can't split the question in smaller questions because a change in the general behaviour of one of those things will affect the others significantly.
- This is a programming related question since it is about abstract syntax tree generation of a programming language.
- I haven't found similar questions regarding these operators in here (maybe I'm using the wrong keywords).
- Other people might stumble upon the same problem when making a parser.
- It doesn't look like it's opinion based to me.
So please consider leaving a comment to tell me how I should improve the question.
CodePudding user response:
There is a good reason for associativity rules in Haskell. They follow the idea of the currying adjunction. A function of two arguments is isomorphic to a function returning a function. So (a, b) -> c
is curried to a -> (b -> c)
. This is why a->b->c
is interpreted as a function returning a function and not (a->b)->c
, which would be a function taking a function as an argument. Conversely, for function application we parse f g h
as f
taking two arguments f
and g
. So function application is left associative, (f g) h
: f
acting on g
produces a function that subsequently acts on h
. As for products and coproducts, they are just treated like multiplication and addition with the usual precedence rules. Incidentally, a->b
corresponds to the exponential b
to the power of a
, which also makes sense as far as associativity goes.