Essentials of interpretation, ML version: Lesson 1: Arithmetic expressions evaluator

eoi-ml-lesson1-ae.ml

(*
 * "Essentials of interpretation. Semantics of programming languages"
 *
 * Lesson 1: Arithmetic expressions evaluator.
 *
 * BNF grammar:
 *
 *   NUMBER -> \d+
 *
 *   Exp -> NUMBER
 *        | Exp + Exp
 *        | Exp - Exp
 *        | Exp * Exp
 *        | Exp / Exp
 *
 * See also JavaScript version with more detailed comments:
 * https://github.com/DmitrySoshnikov/Essentials-of-interpretation/blob/master/src/lesson-1.js
 *
 * by Dmitry Soshnikov <[email protected]>
 * MIT Style License
 *)

type exp =
| Number of int
| Addition of exp * exp
| Subtraction of exp * exp
| Multiplication of exp * exp
| Division of exp * exp;;

(*
 * The `eval` accepts an expression to evaluate, and depending on the
 * expression's type executes appropriate evaluating procedure.
 *)
let rec eval exp =
  match exp with
  | Number n                  -> n
  | Addition (lhs, rhs)       -> eval(lhs) + eval(rhs)
  | Subtraction (lhs, rhs)    -> eval(lhs) - eval(rhs)
  | Multiplication (lhs, rhs) -> eval(lhs) * eval(rhs)
  | Division (lhs, rhs)       -> eval(lhs) / eval(rhs);;

(* Expression: `5 * 3 + 2` *)
let exp = Addition(Multiplication(Number 5, Number 3), Number 2);;

(* Result: 17 *)
print_string "Result: "; print_int(eval exp);

(*
 * Exercise 1: Implement code generator for the expression types.
 *
 * Using the same `exp` data type, instead of direct interpretation of the
 * expression, we can compile it to a string, providing basic code generator.
 *
 * E.g. having an expression:
 *
 *   `Addition(Multiplication(Number 5, Number 3), Number 2)`
 *
 * The code generator can return a string:
 *
 *   "((5 * 3) + 2)"
 *)