Sunday, March 11, 2007

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())

No comments: