EOPL - Section 3.1

This is the first interpreter from Chapter 3, shown in Section 3.1. It needs an implementation of environments, I chose the simplest one and attached it before the code for the interpreter.

// implementation of environments 
// (represented as lists of pairs; the first in pair is 
//  a list of symbols, the second is a list of associated values)
let list_find_position a lst = 
    let rec loop l = 
        match l with
          [] -> None
        | (x :: l') when x = a -> Some (List.length l')
        | (x :: l') -> loop l' in
    loop (List.rev lst)

let empty_env () = 
    []
    
let extend_env syms vals env =
    (syms, vals) :: env
    
let rec apply_env env sym = 
    match env with
      [] -> failwith (sprintf "No binding for %s" sym)
    | (syms, vals) :: env' -> 
        match list_find_position sym syms with 
          None -> apply_env env' sym
        | Some i -> List.nth vals i
        
// types for primitives, expressions and programs
type Primitive = AddPrim | SubtractPrim | MultPrim | IncrPrim | DecrPrim
type Expression = LitExp of int | VarExp of string 
                | PrimAppExp of (Primitive * Expression list)
type Program = Exp of Expression

let apply_primitive prim args = 
    match (prim, args) with
      (AddPrim, [a; b]) -> a + b
    | (SubtractPrim, [a; b]) -> a - b
    | (MultPrim, [a; b]) -> a * b
    | (IncrPrim, [a]) -> a + 1
    | (DecrPrim, [a]) -> a - 1
    | _ -> failwith "Incorrect argument list for primitive" 

let init_env () = 
    extend_env ["i"; "v"; "x"] [1; 5; 10] (empty_env ())
    
let rec eval_expression exp env = 
    match exp with
      LitExp datum -> datum
    | VarExp id -> apply_env env id
    | PrimAppExp (prim, rands) -> let args = eval_rands rands env in 
                                  apply_primitive prim args
and eval_rands rands env = 
    List.map (eval_rand env) rands
and eval_rand env rand = 
    eval_expression rand env

let eval_program pgm = 
    match pgm with
      Exp body -> eval_expression body (init_env())