Evaluator in OCaml/ML

Question

type bool_exp =
    TT
  | FF
  | Var of string
  | And of bool_exp * bool_exp
  | Not of bool_exp ;;

 eval : bool_exp -> (string -> bool) -> bool

I am trying to write an evaluator function called eval. I am very new to OCaml and not used to the syntax. Where can I start in writing this?

Answer 1

The main device when working with datatypes like your bool_exp is pattern-matching. That is, for every possible case of the input to your function you specify its behaviour separately. A skeleton for your eval function could look like

let rec eval e env =
  match e with
    TT -> ...
  | FF -> ...
  | Var x -> ...
  | And (e1, e2) -> ...
  | Not e
;;

The first argument e is the expression that should be evaluated, and the second env is often called an environment, mapping variables (represented by strings) to values (here just Boolean constants).

The rec is needed whenever the defined function is recursive (i.e., using itself in the function body), and since your datatype is defined recursively, also eval will be recursive. E.g., in order to evaluate And (e1, e2) you will first have to know the values of e1 and e2 w.r.t. the same environment.

This should get you started.

Answer 2

Continuing with Chris' answer, your function will look pretty much exactly like this:

let rec eval e env =
  match e with
    TT -> true
  | FF -> false
  | Var x -> x env
  | And (e1, e2) -> (eval e1 env) && (eval e2 env)
  | Not e -> not (eval e env) ;;

Then while running the code to test it, you will declare a function called env, like this:

let env y = true;;

Or...

let env y = false;;

Since the type is "eval : bool_exp -> (string -> bool) -> bool", you need to define what the function for (string -> bool) is before you use the function.

So,

1. Declare data type bool_exp.
2. Declare that function I gave you.
3. Declare env as a function, either one you want, there's only two possible ones.
4. You can now use the function.

Merry functional programming to you. =)