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