Interpreter in OCaml

A language, as a data type.

In OCaml a program can be described exactly as data: the abstract syntax tree is an algebraic type with one constructor per construct. The language has integers, booleans and strings; arithmetic (sum, difference, product, division, modulo, unary minus); logic and comparisons; if-then-else; let bindings; first-class functions and their application; recursive functions with let rec; and a dictionary type with its own operations.

Pattern matching then makes the interpreter read almost like the language's definition: one case per constructor, each saying what that construct means.

Environments, closures, values.

• Environments map identifiers to values, as a list where the newest binding shadows the older ones: bind adds, lookup finds.
• Expressible values are integers, booleans, strings, dictionaries and functions. Under static scope a function is a closure that carries the environment of its definition; a recursive one carries its own name too.
• Dynamic type checking. Every operation checks the types of its operands at run time and raises a clear error for a type mismatch, a non-boolean guard, a non-functional value or a division by zero.

Where does a function look for its variables?

The interpreter comes in two versions that differ in one decision. With static scope (eval), a function uses the environment where it was defined; with dynamic scope (rt_eval), the one where it is called. The project's test program, animated at the top, shows the difference in four lines: f reads x, and x is redefined between the definition of f and its call. Static scope answers 1, dynamic scope answers 2.

(* Interpreter with static scope rule: a function keeps the environment where it is defined *)let rec eval (e: exp) (r: 't env) : evT =    match e with    |   Den i -> lookup r i    |   Let (i, e1, e2) -> eval (e2) (bind r i (eval e1 r))    |   Fun (param, fbody) -> Closure (param, fbody, r)    |   Apply (eF, eArg) ->            let fclosure = eval eF r in (                match fclosure with                |   Closure (arg, fbody, fDecEnv) ->                        let aVal = eval eArg r in                            let aEnv = bind fDecEnv arg aVal in                                eval fbody aEnv                |   _ -> failwith ("Non functional value")            )(* Interpreter with dynamic scope rule: a function uses the environment where it is called *)let rec rt_eval (e : exp) (r : 't env): evT =    match e with    |   Fun (param, fbody) -> DynFun (param, fbody)    |   Apply (eF, eArg) ->            let fval = rt_eval eF r in (                match fval with                |   DynFun (arg, fbody) ->                        let aVal = rt_eval eArg r in                            let aEnv = bind r arg aVal in                                rt_eval fbody aEnv                |   _ -> failwith ("Non functional value")            )

A data structure in the language itself.

Beyond the usual constructs, the language has a dictionary type with six operations, each one a case of the interpreter: