# Example: Evaluating Integer Expressions

For representing integer expressions, we declare a datatype IEXP as follows:

```datatype IEXP =
| IEXPcst of int // constants
| IEXPneg of (IEXP) // negative
| IEXPsub of (IEXP, IEXP) // subtraction
| IEXPmul of (IEXP, IEXP) // multiplication
| IEXPdiv of (IEXP, IEXP) // division
// end of [IEXP]
```

The meaning of the constructors associated with IEXP should be obvious. A value of the type IEXP is often referred to as an abstract syntax tree. For instance, the abstract syntax tree for the expression (~1+(2-3)*4) is the following one:

```IEXPadd(IEXPneg(IEXPcst(1)), IEXPmul(IEXPsub(IEXPcst(2), IEXPcst(3)), IEXPcst(4)))
```

Translating an integer expression written in some string form into an abstract syntax tree is called parsing, which we will not do here. The following defined function eval_iexp takes the abstract syntax tree of an integer expression and returns an integer that is the value of the expression:

```fun
eval_iexp
(e0: IEXP): int =
(
case+ e0 of
| IEXPcst (n) => n
| IEXPneg (e) => ~eval_iexp (e)
| IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
| IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
| IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
| IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e2)
) (* end of [eval_iexp] *)
```

Suppose we also allow the construct if-then-else to be use in forming integer expressions. For instance, we may write an integer expression like (if 1+2 <= 3*4 then 5+6 else 7-8). Note that the test (1+2 <= 3*4) is a boolean expression rather than an integer expression. This indicates that we also need to declare a datatype BEXP for representing boolean expressions. Furthermore, IEXP and BEXP should be defined mutually recursively as follows:

```datatype IEXP =
| IEXPcst of int // integer constants
| IEXPneg of (IEXP) // negative
| IEXPsub of (IEXP, IEXP) // subtraction
| IEXPmul of (IEXP, IEXP) // multiplication
| IEXPdiv of (IEXP, IEXP) // division
| IEXPif of (BEXP(*test*), IEXP(*then*), IEXP(*else*))
// end of [IEXP]

and BEXP = // [and] for combining datatype declarations
| BEXPcst of bool // boolean constants
| BEXPneg of BEXP // negation
| BEXPconj of (BEXP, BEXP) // conjunction
| BEXPdisj of (BEXP, BEXP) // disjunction
| BEXPeq of (IEXP, IEXP) // equal-to
| BEXPneq of (IEXP, IEXP) // not-equal-to
| BEXPlt of (IEXP, IEXP) // less-than
| BEXPlte of (IEXP, IEXP) // less-than-equal-to
| BEXPgt of (IEXP, IEXP) // greater-than
| BEXPgte of (IEXP, IEXP) // greater-than-equal-to
// end of [BEXP]
```

Evidently, we also need to evaluate boolean expressions when evaluating integer expressions. The following two functions eval_iexp and eval_bexp for evaluating integer and boolean expressions, respectively, are defined mutually recursively as can be expected:

```fun
eval_iexp
(
e0: IEXP
) : int = (
//
case+ e0 of
| IEXPcst n => n
| IEXPneg (e) => ~eval_iexp (e)
| IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
| IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
| IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
| IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e1)
| IEXPif
(
e_test, e_then, e_else
) =>
(
eval_iexp (if eval_bexp (e_test) then e_then else e_else)
) // end of [IEXPif]
//
) (* end of [eval_iexp] *)

and
eval_bexp
(
e0: BEXP
) : bool = (
//
case+ e0 of
| BEXPcst b => b
| BEXPneg (e) => ~eval_bexp (e)
| BEXPconj (e1, e2) =>
if eval_bexp (e1) then eval_bexp (e2) else false
| BEXPdisj (e1, e2) =>
if eval_bexp (e1) then true else eval_bexp (e2)
| BEXPeq (e1, e2) => eval_iexp (e1) = eval_iexp (e2)
| BEXPneq (e1, e2) => eval_iexp (e1) != eval_iexp (e2)
| BEXPlt (e1, e2) => eval_iexp (e1) < eval_iexp (e2)
| BEXPlte (e1, e2) => eval_iexp (e1) <= eval_iexp (e2)
| BEXPgt (e1, e2) => eval_iexp (e1) > eval_iexp (e2)
| BEXPgte (e1, e2) => eval_iexp (e1) >= eval_iexp (e2)
//
) (* end of [eval_bexp] *)
```

The integer and boolean expressions used in this example are all constant expressions containing no variables. Therefore, there is no need for an environment to evaluate them. I will present a more advanced example elsewhere to demonstrate how an evaluator for a simple call-by-value functional programming language like the core of ATS can be implemented.

Please find on-line the entirety of the code in this section plus some additional code for testing.