In this problem we will look at representing simple expressions from OCaml in OCaml and doing some computations on them based on such a representation. The particular computation we will carry out in this problem is evaluating them, i.e., you will write an interpreter for them. Because the collection of expressions is very limited, the task will be quite simple. However, it will expose you to the basic ideas underlying building interpreters and other programs of this sort and hence will get you prepared for more involved and exciting things of this kind that we will try later.

First, for the expression language. The collection of expressions we will look at are captured by the following type declaration in OCaml

type expr = Id of string (* for identifiers *) | Int of int (* for integers *) | True (* for the boolean value true *) | False (* for the boolean value false *) | Plus of expr * expr (* for exp1 + exp2 *) | Minus of expr * expr (* for exp1 - exp2 *) | Times of expr * expr (* for exp1 * exp2 *) | Div of expr * expr (* for exp1 / exp2, division being for integers *) | Lss of expr * expr (* for exp1 < exp2 *) | Eq of expr * expr (* for exp1 = exp2, = being equality comparison *) | Gtr of expr * expr (* for exp1 > exp2 *) | And of expr * expr (* for exp1 && exp2 *) | Or of expr * expr (* for exp1 || exp2 *) | Not of expr (* for not exp *) | Cond of expr * expr * expr (* for if exp1 then exp2 else exp3 *) | Let of string * expr * expr (* for let = exp1 in exp2 *) 

We have seen this kind of representation before, even in the previous problem in this homework, so we don't need much more introduction to it. The only thing to clarify is perhaps the last form, which is used to represent letexpressions in OCaml. As a concrete example, the OCaml expression let x = 5 in let y = 7 in x + y, would be represented by the following expression of type expr:

Let ("x",(Int 5),Let ("y",(Int 7),Plus ((Id "x"),(Id "y")))) 

1. Your task in this problem is to build an evaluator for the subset of OCaml encoded in the type declaration. Specifically, you are to define a of the following name and type

 eval : expr -> (string * expr) list -> expr 

that takes an expression of type expr and evaluates it using the relevant rules for the different forms of expressions. For example, if we have the following let bindings

 let exp1 = Let ("x",(Int 5),Let ("y",(Int 7),Plus ((Id "x"),(Id "y")))) let exp2 = Let ("x",True,Cond (Not (Id "x"),True,False)) let exp3 = Let ("x", False, Cond (Not (Id "x"), Let ("x",Int 5,Plus (Id "x", Int 3)), Let ("y",Int 7, Id "y"))) 

then we should witness the following interaction with OCaml:

 # eval exp1 [];; - : expr = Int 12 # eval exp2 [];; - : expr = False # eval exp3 [];; - : expr = Int 8 # 

Observe that for the simple language we are considering, the result of evaluation will be one of three forms: Int i for some integer i, True, or False.

You may wonder why eval needs the second argument. This argument provides a binding for identifiers that may appear in the expression. The expressions we try to evaluate at the top level must not have unbound identifiers, so this list will initially be empty. However, as we descend into the bodies of let expressions, we have to carry along the bindings they create and we use this list argument for that purpose. Note that this list, that is often referred to as an environment will associate a value that is an expression of one of the three forms described above with each name: the assumption is that in a let, we evaluate the expression that the identifier is to be bound to eagerly, i.e. before we make the binding.

One question that often arises when one is writing one's first evaluator is the following: what should I do if the result of evaluation is not of the right type? For example, if when I am trying to evaluate an and expression, if an integer shows up rather than one of the values represented by True or False? The answer to this is that you should assume that this will never happen. And why? Because the expressions you try to evaluate will always be type checked beforethey are evaluated by a process similar to what was considered in Problem 5 and that will ensure we always have "good" results.

One final note: When evaluating an if-then-else, organize this so that you evaluate the then or the else part only on demand, i.e. after you have evaluated the condition and determined the case that needs to be evaluated. Similarly for and and or: you evaluate the first argument and only if it does not determine the truth value for the expression do you go on to evaluating the second argument.

Language: Ocaml