ocamlmlevaluator

Evaluator in OCaml/ML


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?


Solution

  • 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.