CODEWITHSUNDEEP
parsingfunctional-programmingoperatorsoperator-precedencecategory-theory
Cristian
Cristian

Reputation: 666

Morphism, product, coproduct operator precedence and associativity

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):

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:

  1. I could not find resources that explain how these three operators are related to each other, in which way, precedence and associativity.
  2. 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.
  3. This is a programming related question since it is about abstract syntax tree generation of a programming language.
  4. I haven't found similar questions regarding these operators in here (maybe I'm using the wrong keywords).
  5. Other people might stumble upon the same problem when making a parser.
  6. 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.

Upvotes: 0

Views: 85

Answers (1)

Bartosz Milewski
Bartosz Milewski

Reputation: 11630

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.

Upvotes: 2

Related Questions