HM Type Inference in Go

Grammar

<Expr> ::= <Cons>

<Cons> ::= <Comp>
         | <Comp> ":" <Cons>

<Comp> ::= <Add>
         | <Comp> <CompOp> <Add>

<CompOp> ::= "=="
           | "!="
           | "<"
           | "<="
           | ">"
           | ">="

<Add> ::= <Mult>
        | <Add> <AddOp> <Mult>

<AddOp> ::= "+"
          | "++"
          | "-"

<Mult> ::= <Unary>
         | <Mult> <MultOp> <Unary>

<MultOp> ::= "*"
           | "/"
           | "%"

<Unary> ::= "not" <Unary>
          | <App>

<App> ::= <Postfix>
        | <App> <Postfix>

<Postfix> ::= <Atom>
            | <Postfix> "." <ProjectionIndex>

<ProjectionIndex> ::= <IntLit>

<Atom> ::= <IntLit>
         | <BoolLit>
         | <StringLit>
         | <Var>
         | <IfExpr>
         | <ParenExpr>
         | <NegExpr>
         | <TupleExpr>
         | <ListExpr>
         | <LetExpr>
         | <LambdaExpr>
         | <MatchExpr>

<NegExpr> ::= "(" "-" <Expr> ")"

<IfExpr> ::= "if" <Expr> "then" <Expr> "else" <Expr>

<ParenExpr> ::= "(" <Expr> ")"

<TupleExpr> ::= "(" <Expr> "," <TupleTail> ")"

<TupleTail> ::= <Expr>
              | <Expr> "," <TupleTail>

<ListExpr> ::= "["
             | "[" <ListItems> "]"

<ListItems> ::= <Expr>
              | <Expr> "," <ListItems>

<LetExpr> ::= "let rec" <Var> <LetRecBinding>
            | "let" <Var> "=" <Expr> "in" <Expr>

<LetRecBinding> ::= "(" <Var> ":" <Type> ")" ":" <Type>
                    "=" <Expr> "in" <Expr>
                  | <Var> "=" <Expr> "in" <Expr>

<LambdaExpr> ::= "\" "(" <Var> ":" <Type> ")" "->" <Expr>
               | "\" <Var> "->" <Expr>

<MatchExpr> ::= "match" <Expr> "with" <MatchCases>

<MatchCases> ::= "|" <MatchCase>
               | <MatchCases> "|" <MatchCase>

<MatchCase> ::= <Pattern> "->" <Expr>

<Pattern> ::= <PatternAtom>
            | <PatternAtom> ":" <Pattern>

<PatternAtom> ::= "_"
                | <Var>
                | <IntLit>
                | <BoolLit>
                | <StringLit>
                | <ParenPattern>
                | <TuplePattern>
                | <ListPattern>

<ParenPattern> ::= "(" <Pattern> ")"

<TuplePattern> ::= "(" <Pattern> "," <PatternTupleTail> ")"

<PatternTupleTail> ::= <Pattern>
                     | <Pattern> "," <PatternTupleTail>

<ListPattern> ::= "["
                | "[" <PatternListItems> "]"

<PatternListItems> ::= <Pattern>
                     | <Pattern> "," <PatternListItems>

<Type> ::= <TypeArrow>

<TypeArrow> ::= <TypeTuple>
              | <TypeTuple> "->" <TypeArrow>

<TypeTuple> ::= <TypeAtom>
              | <TypeAtom> "*" <TypeTuple>

<TypeAtom> ::= "int"
             | "bool"
             | "string"
             | "[" <Type> "]"
             | "(" <Type> ")"