How can I write a function to evaluate custom datatype

Question

datatype mixed_expression =
   ME_NUM of int
 | ME_PLUS of mixed_expression * mixed_expression
 | ME_TIMES of mixed_expression * mixed_expression
 | ME_LESSTHAN of mixed_expression * mixed_expression;

datatype value =
   INT_VAL of int
 | BOOL_VAL of bool
 | ERROR_VAL;

I am given these data types and this is my approach

fun eval e = 
  case e of 
    ME_NUM x       => INT_VAL x 
  | ME_PLUS (l, r) => eval l + eval r

I got the following error message.

**Error: overloaded variable not defined at type
  symbol: +
  type: value**

I have no clues on how to solve these issues since I am not allowed to use mutation.

Answer 1

The error message tells you what you need to know. When you write:

eval l + eval r

The expressions eval l and eval r yield type value. There is no + operator for this type.

As a style note, your case is extraneous in this situation.

fun eval(ME_NUM x)       = INT_VAL x
  | eval(ME_PLUS (l, r)) = eval l + eval r

You should also get a warning about pattern-matching being non-exhaustive as you haven't handled ME_TIMES or ME_LESSTHAN.

Really, what you need to do is define a function which can add two value values.

fun me_add(INT_VAL a, INT_VAL b)  = INT_VAL (a + b)
  | me_add(INT_VAL a, BOOL_VAL b) = (* ... *)

There are lots of combinations you'll need to pattern-match on. You may want to just define a function that coerces a value into an int.

fun toInt(INT_VAL a)      = a
  | toInt(BOOL_VAL True)  = 1
  | toInt(BOOL_VAL False) = 0
  | (* and so on... *)

Then you could write something like:

fun me_add(a, b) = INT_VAL(toInt a + toInt b)

Answer 2

The problem is that there is no + operator defined for the value type.
(You would not solve this by using mutation.)

You need to "pick apart" the results of eval and then build a new value from the addition.

The most naive approach would be a case analysis, but this gets unreadable very quickly:

  eval (ME_PLUS (e1, e2)) = (case eval e1 of
                                   INT_VAL x1 => (case eval e2 of
                                                      INT_VAL x2 => INT_VAL (x1 + x2)
                                                    | _ => ERROR_VAL)
                                 | _ => ERROR_VAL)

and you would need one of these uglinesses for each case.

A tidier approach is to define the operations on values as separate functions:

fun add (INT_VAL x1) (INT_VAL x2) = INT_VAL (x1 + x2)
  | add _ _ = ERROR_VAL;

and so on.
Then you define your interpreter in terms of these operations:

fun eval (ME_NUM x) = INT_VAL x
  | eval (ME_PLUS (e1, e2)) = add (eval e1) (eval e2)
  | eval (ME_TIMES (e1, e2)) = multiply (eval e1) (eval e2)
  | eval (ME_LESSTHAN (e1, e2)) = less_than (eval e1) (eval e2);