Rutgers CS 314

IMP interpreter in OCaml

An interpreter for a small imperative language, with loops, conditionals and functions.

Programs are read by a lexer and parser generated from grammar files (ocamllex and a .mly grammar) and turned into a syntax tree of OCaml variants: expressions like Plus, Leq and App, and commands like While, Cond and Assg.

The evaluator walks that tree with an environment, a list that maps each variable name to its value. Expressions produce values; commands produce a new environment. Assignments are type-checked, so a variable that holds a number can't be given a boolean.

Functions are values too. Evaluating fun x -> body captures the current environment in a closure, so when the function is called later it still sees the variables that existed where it was defined.

Program

A .imp file

Lexer and parser

Generated from grammar files

Syntax tree

OCaml variants

Evaluator

Environment in, environment out

  • Program to Lexer and parser
  • Lexer and parser to Syntax tree
  • Syntax tree to Evaluator
Simplified to the main pieces and how they talk to each other.

See it work

fact.imp, one of the test programs

int n;
int f;
n := 5;
f := 1;
while (n > 1) {
  f := f * n;
  n := n - 1;
};

From the repo. It computes 5 factorial, leaving f = 120.

lambda1.imp: a function that remembers where it was made

int n;
int sum;
lambda f;
int k;
n := 100;
sum := 0;
k := 0;
f := fun x -> x + n + sum;
while (n > 0) {
    sum := sum + n;
    k := (f n) + k;
    n := n - 1;
};

From the repo. f is defined while n is 100 and sum is 0, and its closure keeps those values, even as the loop changes the real n and sum.

How a function call is evaluated, from eval.ml

| Fun (x, body) -> Closure (env, x, body)
| App (e1, e2) ->
    (match eval_expr e1 env with
     | Closure (closure_env, x, body) ->
         let arg_val = eval_expr e2 env in
         let new_env = (x, arg_val) :: closure_env in
         eval_expr body new_env
     | _ -> raise TypeError)

A fun becomes a closure holding its environment. Calling it evaluates the argument, binds it on top of that saved environment, and runs the body there.