(*
- This is a simplified version of the code at ...
+ This is a simplified version of the code at http://lambda.jimpryor.net/code/untyped_full-1.7.tgz
You can use this code as follows:
1. First, use a text editor to fill in the (* COMPLETE THIS *) portions.
`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.
+ The two interpreters presented below are (VersionA) a substitute-and-repeat
+ interpreter, and (VersionB) an environment-based interpreter. We discuss the
+ differences between these in the course 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
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
+ simplified program: it means that Lambdas (or Closures, in VB) 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 VA interpreter
+ presented here. In the fuller code, they have a limited role in the VA
+ interpreter. In the VB interpreter, the environments are essential.
*)
type identifier = string
type term =
| Var of identifier
| App of term * term
- | Lambda of identifier * term (* in V2, never used as a result *)
+ | Lambda of identifier * term (* in VB, never used as a result *)
| Let of identifier * term * term
| If of term * term * term
- (* the following variant is never used as a term, only as a V2 result *)
+ (* the following variant is never used as a term, only as a VB result *)
| Closure of identifier * term * env
(* in the fuller code, we separate the term and result types *)
(* 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 : identifier) (env : env) : term option =
+ match env with
+ | [] -> None
+ | (ident, binding) :: _ when ident = sought_ident -> Some binding
+ | _ :: env' -> lookup sought_ident env'
(*
eval raises this exception when it fails to reduce/evaluate
a term, because it has components for which no
reduction/evaluation is defined, such as `x y`. The
- reduction-based interpreter just signals this with a normal
+ substitute-and-repeat interpreter just signals this with a normal
return value; but the environment-based interpreter uses an
exception to abort prematurely.
In this simplified version of the code, we also use this
- exception to report a failed term in V1, since we lack
+ exception to report a failed term in VA, since we lack
the resources to print the term instead, as the full code does.
*)
exception Stuck of term
-module V1 = struct
+module VA = struct
(* ---------------------------------------------------------------
Interpreter that reduces by substituting, using:
val reduce_head_once : term -> env -> reduceOutcome
| Lambda _ -> AlreadyResult term
| Var var -> failwith ("Unbound variable `" ^ var ^ "`")
- | Closure _ -> assert false (* no Closures in V1 *)
+ | Closure _ -> assert false (* no Closures in VA *)
(* In this simplified version there are no Bool Literals, so If terms are always stuck
| If(Literal(Bool true),yes,no) -> ReducedTo yes
| StuckAt subterm -> raise (Stuck subterm)
| ReducedTo term' -> reduce term' env (* keep trying *)
-end (* module V1 *)
+end (* module VA *)
-module V2 = struct
+module VB = struct
(* ---------------------------------------------------------------
Interpreter that employs an "environment" or assignment
function of results, using:
let evaluate (term : term) (env : env) : result =
eval term env (* in the fuller code, this function catches the Stuck errors and prints them more nicely *)
-end (* module V2 *)
+end (* module VB *)
-let reduce term = V1.reduce term empty
-let evaluate term = V2.evaluate term empty
+let reduce term = VA.reduce term empty
+let evaluate term = VB.evaluate term empty