straight-line program interpreter in OCaml

(*                straight-line program interpreter in OCaml                *)
(*     Ch.1 Programming excercise in Modern Compiler Implementation in ML   *)

(*--------------------------------------------------------------------------*)
(*         straight-line program abstract grammar tree definition           *)
(*--------------------------------------------------------------------------*)
type id = string;;

type binop = Plus | Minus | Times | Div;;

(* Notes: OCaml support the following grammar
   type-definition ::= type typedef { and typedef } *)
type stm = CompoundStm of stm * stm
	     | AssignStm of id * exp
	     | PrintStm of exp list

and exp = IdExp of id
	     | NumExp of int
             | OpExp of exp * binop * exp
             | EseqExp of stm * exp;;



(*--------------------------------------------------------------------------*)
(*   symbol table definition and operations implementation on symbol table  *)
(*--------------------------------------------------------------------------*)
(* exception defintion *)             
exception Not_Found;;

(* 
    table in linked-list, a list of id * int pairs.  
    Notes: I am familar with the name 'symbol table' than table.
*)
type table = Table of (id * int) list;;

(*
    update function 
        val update : table -> id -> int -> table = 
    description:
        this function put a new cell at the head of the linked list,
        assume that the first occurrence of i in the list takes precedence
        over any later occurrence.
        maybe it is much better to call it insert function.
*)
let update t i v = match t with
    Table(x) -> Table((i,v)::x);;

(* 
    lookup function
        val lookup : table -> id -> int = 
*)
let rec lookup t i =
  match t with
      Table((id, v)::rest) ->  if id = i then v else lookup (Table rest) i
      | Table([]) -> raise Not_Found
      ;;



(*--------------------------------------------------------------------------*)
(*                    interpreter function implementation                   *)
(*     val interpStm : stm -> table -> table =                         *)
(*     val interpExp : exp -> table -> int * table =                   *)
(*--------------------------------------------------------------------------*)

let rec interpStm stm table =
    match stm with
        CompoundStm(x, y) ->
            let table = interpStm x table in interpStm y table
      | AssignStm(id, e) ->  
            let (i, table) = interpExp e table in update table id i
      | PrintStm(exps) ->
            let rec loop exps =
                match exps with
                    | [] -> print_newline(); table
                    | exp::rest ->
                        let (i, table) = interpExp exp table in
                            print_int i;
                            print_char ' ';
                            interpStm (PrintStm rest) table
            in loop exps

and interpExp exp table =
    match exp with
        IdExp(id) -> ((lookup table id), table)
      | NumExp(i) -> (i, table)
      | OpExp(a, op, b) ->
          let (i, table) = interpExp a table in
              let (j, table) = interpExp b table in
                  ((match op with
                      Plus  -> i+j
                    | Minus -> i-j
                    | Times -> i*j
                    | Div   -> i/j), table)
      | EseqExp(stm, exp) ->
         let table = interpStm stm table in
             interpExp exp table
      ;;

let interp stm = interpStm stm (Table []); () ;;



(*--------------------------------------------------------------------------*)
(* test program: AST for a := 5+3; b := (print(a, a - 1), 10*a); print (b)  *)
(*--------------------------------------------------------------------------*)
let prog =
  CompoundStm
    (AssignStm("a",OpExp(NumExp 5, Plus, NumExp 3)),
     CompoundStm
       (AssignStm
          ("b",
           EseqExp
             (PrintStm[IdExp "a"; OpExp(IdExp "a", Minus, NumExp 1)],
              OpExp(NumExp 10, Times, IdExp "a"))),
        PrintStm[IdExp "b"]))
    ;;
   
interp prog;;


上述代码在OCaml解释器中执行结果如下图。