ocaml interpreter

Question

Can someone give me some help building an ocaml interpreter for the language with the syntax:

Prog ::= Def* Expr
Def ::= id id* = Expr
Expr ::= int | id | Expr '+' Expr | Expr '*' Expr | id Expr* | if Expr then Expr else Expr

so far i did this:

type expr = I of int
| Id of string
| Add of expr * expr
| Multiply of expr * expr
| If of  expr * expr * expr

let rec evaluate = function
| I n -> n 
| Add(e1,e2) -> evaluate e1 + evaluate e2
| Multiply(e1,e2) -> evaluate e1 * evaluate e2
| If(a,b,c) -> if evaluate a<>0 then evaluate b else evaluate c

Is this any good ?

Answer 1

In your grammar a single id can either be matched by the production Expr ::= id or Expr ::= id Expr*. In other words there's no way to distinguish between a nullary function application (assuming the id Expr* production is supposed to match function applications) and variables. Maybe you meant id Expr+ instead (disallowing nullary function applications).

Your existing code looks fine, but it's incomplete:

Your expr type is missing a constructor for the id Expr* production of the grammar, i.e. you're missing a constructor that represents function applications. You should add one and then add a case for it to the evaluate function as well.

In your evaluate function you're missing a case for the Id constructor. That case should lookup the value of the given identifier in a mapping from identifiers to values (ints). To that end your evaluate function should take such a mapping as an additional argument. It should also take another mapping from identifiers to functions, which you can then use to loop up function names in the case for function applications.

Speaking of those mappings, you currently don't have any code to represent or process definitions. You should come up with a type to represent a definition and another to represent functions. The latter type should contain the name of the function parameters and the body as an expr.

Then you should write a function that takes a list of definitions and creates the mappings for variables and functions. For each variable definition it should evaluate the expression on the right and add the resulting values to your variable mapping. For each function definition, you should add a value of your function type to the function mapping. After processing the definitions, you should evaluate the final expression by calling your evaluate function with that expression and the two mappings you created as arguments.

Finally you don't have any code for actually parsing the program, but I think that might be intentional.