open Ast
(** [parse s] parses [s] into an AST. *)
let parse (s : string) : expr =
let lexbuf = Lexing.from_string s in
let ast = Parser.prog Lexer.read lexbuf in
ast
(** [Env] is module to help with environments, which
are maps that have strings as keys. *)
module Env = Map.Make(String)
(** [env] is the type of an environment, which maps
a string to a value. *)
type env = value Env.t
(** [value] is the type of a lambda calculus value.
In the environment model, that is a closure. *)
and value =
| Closure of string * expr * env
let unbound_var_err = "Unbound variable"
type scope_rule = Lexical | Dynamic
let scope = Lexical
(** [eval env e] is the [ ==> v] relation. *)
let rec eval (env : env) (e : expr) : value = match e with
| Var x -> eval_var env x
| App (e1, e2) -> eval_app env e1 e2
| Fun (x, e) -> Closure (x, e, env)
(** [eval_var env x] is the [v] such that [ ==> v]. *)
and eval_var env x =
try Env.find x env with Not_found -> failwith unbound_var_err
(** [eval_app env e1 e2] is the [v] such that [ ==> v]. *)
and eval_app env e1 e2 =
match eval env e1 with
| Closure (x, e, defenv) -> begin
let v2 = eval env e2 in
let base_env_for_body =
match scope with
| Lexical -> defenv
| Dynamic -> env in
let env_for_body = Env.add x v2 base_env_for_body in
eval env_for_body e
end
(** [interp s] interprets [s] by parsing
and evaluating it with the big-step model,
starting with the empty environment. *)
let interp (s : string) : value =
s |> parse |> eval Env.empty