Tuesday, March 6, 2007

EOPL - 2.3.4 - Alternative Representation

A simple representation of environments as a list of pairs (syms, vals) where syms is a list of symbols and vals is a list of values positionally associated with the symbols.

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

No comments: