Type checking with try/with statements in Ocaml?

Question

I'm implementing a mock interpreter using Ocaml. One of the mock functionalities is to evaluate a made up expression using pattern matching. The issue is trivial and definitely fixable, but I'm trying to find a more elegant way of doing this, so read on if you're still interested!

A snippet of my user defined type looks like this:

type value =
  | Val_Int of int
  | Val_Bool of bool

type expr =
  | Id of string
  | Int of int
  | Bool of bool
  | Plus of expr * expr
  | Equal of expr * expr

Of course, I have a function for evaluating these expressions in the form of (string * value) list -> expr -> value, a snippet of the function looks like this:

(* Ignore this helper function if you'd like *)
let rec lookup env x = match env with
  | [] -> raise (DeclarationError "Declaration Error")
  | (y,v)::env_t -> if x = y then v else lookup env_t x
;;

(* The evaluation function *)
let rec eval_expr env e = match e with
  | Id(x) -> lookup env x
  | Int(x) -> Val_Int(x)
  | Bool(x) -> Val_Bool(x)
  | Plus(x,y) ->  (try
                    let Val_Int n1 = eval_expr env x in
                    let Val_Int n2 = eval_expr env y in
                    Val_Int (n1 + n2)
                  with _ -> raise (TypeError "Type Error Plus"))
  | Equal(x,y) -> (try
                    let value n1 = eval_expr env x in
                    let value n2 = eval_expr env y in
                    Val_Bool (n1 = n2)
                  with _ -> raise (TypeError "Type Error Equal"))
;;

Here I'm using try/with statements to catch any native error types and throwing my own error TypeError. I'm using polymorphic variants like Val_Int n1 to protect my variables from invalid type operations like 1 + true, which should throw TypeError.

The issue is more for Equals expressions. Equals should only be evaluated when the two arguments are of the same type (i.e. both Val_Int or both Val_Bool), and throw TypeError if something like Equals(Val_Int(0), Val_Bool(false)) is passed in.

With Plus, I'm able to explicitly define my types as Val_Int, so something like Plus(Val_Int(0), Val_Bool(false)) would throw match failure and it would be caught by the try/with statement, but I can't do this for Equals, which could be of either Val_Int or Val_Bool. That is, something like Equals(Val_Int(0), Val_Bool(false)) will only return Val_Bool(false) instead of throwing an error.

One way I could fix this is if I used match/with statements instead of try/with, like if I did something like:

|Equal(x,y)->(match (eval_expr env x,eval_expr env y) with
            |(Val_Int(a),Val_Int(b)) -> Val_Bool(a = b) 
            |(Val_Bool(a),Val_Bool(b)) -> Val_Bool(a = b)
            |(_,_) -> raise (TypeError "TypeError Equals"))

but I'm trying to find a more elegant way of doing this. Any Suggestions?

Answer 1

Another way of doing it would be to use mutually recursive functions : one for the arithmetic evalution and one for the boolean evaluation. Also, your expr type would become :

type expr = Arith   of aexpr
          | Boolean of bexpr

and aexpr = Int of int
          | Plus of aexpr * aexpr

and bexpr = Bool of bool
          | EqualArith of aexpr * aexpr
          | EqualBool of bexpr * bexpr

This way, Plus can only accept arithmetical expression by construction. Similarily you have one constructor for boolean equality, and one for arithmetical equality. Also you have to split your evaluation function into two :

let rec eval_expr env = function
  | Arith e -> Val_int (eval_aexpr e)
  | Boolean b -> Val_bool (eval_bexpr b)

and eval_aexpr = function
  | Int i    -> i
  | Plus i,j -> (eval_aexpr i) + (eval_aexpr j)

and eval_bexpr = function
  | Bool b        -> b
  | EqualArith (e1,e2) -> 
      let v_e1 = eval_aexpr e1 and v_e2 = eval_aexpr e2 in
      v_e1 = v_e2
  | EqualBool (e1,e2) -> 
      let v_e1 = eval_bexpr e1 and v_e2 = eval_bexpr e2 in
      v_e1 = v_e2

This way of coding allows you to only modify your artithmetical (resp, boolean) evaluator when you add arithmetical(resp boolean) constructions

Answer 2

Catching Match_failure is very poor style, you are correct to look for a cleaner way.

Here's a straightforward approach which factors out matching on values. Replace the assertions with your own error messages.

type value =
  | Val_Int of int
  | Val_Bool of bool

type expr =
  | Id of string
  | Int of int
  | Bool of bool
  | Plus of expr * expr
  | Equal of expr * expr

let rec lookup env x = match env with
  | [] -> assert false
  | (y,v)::env_t -> if x = y then v else lookup env_t x

let int_of_val = function
  | Val_Int n -> n
  | _ -> assert false

let val_equal a b =
  match a, b with
  | Val_Int x, Val_Int y -> x = y
  | Val_Bool x, Val_Bool y -> x = y
  | _, _ -> assert false

let rec eval_expr env = function
  | Id name -> lookup env name
  | Int n -> Val_Int n
  | Bool b -> Val_Bool b
  | Plus (x, y) ->
    Val_Int (int_of_val (eval_expr env x) +
             int_of_val (eval_expr env y))
  | Equal (x,y) ->
    Val_Bool (val_equal (eval_expr env x) (eval_expr env y))

Answer 3

Well, challenge accepted.

First of all, you don't need your type value since you already have Int and Bool in your expression. But you could keep this type value so it has a type in it, and that's what I'd do :

type expr =
  | Id of string
  | Int of int
  | Bool of bool
  | Plus of expr * expr
  | Equal of expr * expr

type ty = Int | Bool

(* I used the type expr but we know that we will only put Int or Bool in it *)
type value = { e : expr; t : ty }

exception DeclarationError of string
exception TypeError of string

module SMap = Map.Make (struct 
  type t = string    
  let compare = compare
end)

let rec lookup env x =
  try SMap.find x env
  with Not_found ->raise (DeclarationError "Declaration Error")
;;

let rec eval_expr env e = match e with
  | Id x -> lookup env x
  | Int _ -> {e; t = Int}
  | Bool _ -> {e; t = Bool}
  | Plus (e1, e2) -> 
    let v1 = eval_expr env e1 and
        v2 = eval_expr env e2 in
    begin
      match v1.e, v2.e with
        | Int e1, Int e2 -> {e = Int (e1 + e2); t = Int}
        | _ -> raise (TypeError "Type Error Plus")
    end
  | Equal (e1, e2) -> 
    let v1 = eval_expr env e1 and
        v2 = eval_expr env e2 in
    if v1.t = v2.t then {e = Bool (v1.e = v2.e); t = Bool}
    else raise (TypeError "Type Error Equal")

Yes, in that case the type is only used once, in case of an Equal construct, but if you want a more complex system you'll just have to add more types and it will work well.

Notice that in the Plus construct I match the expressions, not the types, because I need the values in it.

I took a moment to use a Map and not a List for your lookup function.