`reduce (App(Lambda("x",Var "x"),Lambda("y",Var "y")))`
`evaluate (App(Lambda("x",Var "x"),Lambda("y",Var "y")))`
- The environments play absolutely no role in the simplified V1 interpreter
- presented here. In the fuller code, they have a limited role in the V1
- interpreter. In the V2 interpreter, the environments are essential.
-
The two interpreters presented below are (V1) a substitute-and-replace
interpreter, and (V2) an environment-based interpreter. We discuss the
differences between these in the notes.
result values. But in the fuller code from which this is simplified, it
makes more sense, because there we also have literal number and boolean
values as results, too.
+
+ The environments play absolutely no role in the simplified V1 interpreter
+ presented here. In the fuller code, they have a limited role in the V1
+ interpreter. In the V2 interpreter, the environments are essential.
*)
type identifier = string
(* This simplified code just provides a single implementation of environments;
but the fuller code provides more. *)
-and env = identifier -> term option
+and env = (identifier * term) list
(* Operations for environments *)
-let empty = fun _ -> None
-let shift (ident : identifier) binding env =
- fun (sought_ident : identifier) ->
- if ident = sought_ident
- then Some binding
- else env sought_ident
-let lookup sought_ident env = env sought_ident
+let empty = []
+let shift (ident : identifier) binding env = (ident,binding) :: env
+let rec lookup (sought_ident : ident) (env : env) : term option =
+ match env with
+ | [] -> None
+ | (ident, binding) :: _ when ident = sought_ident -> Some binding
+ | _ :: env' -> lookup sought_ident env'
(*