Ocaml AST implementation with mutually recursive functions

Hello, I just started my journey in Ocaml been a week and trying to write abstract syntax tree of a simple arithmetic language. There is couple of things that I want to mention An arithmetic expression (expr) will be either a numeric constant called Const, or a variable called Var, or addition (Plus), multiplication (Mult), difference (Minus), or division (Div) of two arithmetic expressions. Since we are dealing with binary arithmetic operators, the arguments are defined with the names Arg1 and Arg2. Finally, writing a function called evaluate, which takes as input a single arithmetic expression you defined
in above, and gives as output its final value. You may assume that the input arithmetic expression to
this function will only non-negative integer numeric values (i.e., no variables and no floats). This was my goal I tried to implement it as following ;

type expr  =
  | Const of int
  | Var of string
  | Plus  of expr* expr  (* e1 + e2 *)
  | Minus of expr * expr   (* e1 - e2 *)
  | Mult of expr * expr   (* e1 * e2 *)
  | Div of expr * expr   (* e1 / e2 *)
let rec eval = function
  | Const c -> c
  | Plus (f, g) -> eval f + eval g
  | Minus(f, g) -> eval f - eval g
  | Mult(f, g) -> eval f * eval g
  | Div(f, g) -> eval f / eval g 

and the test case I was given was

Plus { arg1 = (Mult {arg1 = Const 2; arg2 = Var “x”});
arg2 = (Mult {arg1 = Const 3; arg2 = (Minus {arg1 = Var “y”; arg2 =Const 1})})

However, I keep getting errors that I have no idea how to fix the hint that I have given was "The way you would want to approach this is to define the type expr as a mutually recursive type using the “and” keyword with two types defined. One of them is defined using “|” and another using “;”
That’s about all the hints I give regarding how to do this problem. " if someone can guide me through it would be great.

Hi @robin_prince.

Bearing in mind that we can’t do your homework for you, it looks like the test case you’ve been given expects you to have defined a record type in addition to your existing variant type (the so called "type defined using ;"). Together, those two types will capture the same basic structure as you’ve currently done with expr, but in such a way that makes the syntax of the test case correct.

I advise you to read the Real World OCaml section on record types to get a better understanding of how to do this, then work backwards from the test case to get the correct implementation.

“Bearing in mind that we can’t do your homework for you” I am sorry that was not my intention. Also thank you for the reference will check it right now.

No problem, I didn’t mean to be accusatory :slightly_smiling_face: (Only to justify why my explanation is probably less than enlightening!)

Thank you again that book for implementing the expression part worked like a charm.

type expr = Const of int 
          | Var of string
          | Plus of args
          | Mult of args
          | Minus of args
          | Div of args
and args = {arg1:expr; arg2:expr};; 

However, when I tried to re-implement the part for “eval” I got this error “Error: This pattern matches values of type 'a * 'b but a pattern was expected which matches values of type args” And really not sure to fix that any suggestions?

1 Like

It’s not easy without seeing the code, but I imagine that somewhere it is pattern-matching as if it were using the old definition of expr, e.g.

| Plus (f, g) -> (* [Plus] is a constructor with two arguments, [f] 
                    and [g] *)

when what you’ll now need is something like e.g.

| Plus { arg1; arg2 } -> (* [Plus] is a constructor with one argument,
                            which is an [args] record with two fields named
                            [arg1] and [arg2] *)

The compiler error is probably coming from the fact that the former is a pattern for a tuple (f, g) of type ('a * 'b), but the type-system knows that Plus can only ever contain a single value of type args.

1 Like

This warning is generally considered to be a big deal in the community :wink: It means that your eval function does not support the Var case, and indeed it is not defined for that case which is why you are getting a match failure exception.

Your assignment seems to say that no inputs to the eval function will ever contain variables, and so it is odd that your test case does.

Forgive my ignorance lol. Thank you again @CraigFe

1 Like