This is a simplified version of the code at ...
You can use this code as follows:
- 1. First, use a text editor to fill in the (* COMPLETE THIS *) portions
+ 1. First, use a text editor to fill in the (* COMPLETE THIS *) portions.
2. Then see if OCaml will compile it, by typing `ocamlc -c untyped_evaluator.ml` in a Terminal.
3. If it doesn't work, go back to step 1.
4. If it does work, then you can start up the OCaml toplevel using `ocaml -I DIRECTORY`,
`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 this simplified V1 interpreter. 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.
+
+ The implementeations we provide make both of these call-by-value. When given
+ a term `App(head, arg)`, the steps are: first, reduce or evaluate
+ `head`---it might involve further `App`s itself. Second, reduce or evaluate
+ `arg`. Third, only _when_ `arg` reduces or evaluates to a result value, then
+ "perform" the application. What this last step amounts to is different in
+ the two interpreters. Call-by-name interpreters would "perform" the
+ application regardless, and without even trying to reduce or evaluate arg to
+ a result value beforehand.
+
+ Additionally, these implementations assume that free variables are "stuck"
+ terms rather than result values. That is a bit inconvenient with this
+ simplified program: it means that Lambdas (or Closures, in V2) are the only
+ 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 push (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'
(*
| Var var ->
(match lookup var env with
- (* Free variables will never be pushed to the env, so we can be
- sure this is a result. *) CHECK
+ (* In this call-by-value design, only results get
+ saved in the environment, so we can be sure this
+ is a result. *)
| Some res -> res
| None -> failwith ("Unbound variable `" ^ var ^ "`"))