From: Jim Date: Sun, 22 Mar 2015 12:09:43 +0000 (-0400) Subject: add comments to untyped_evals X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=a45c27a801b3740ed6b2eddd012d56ddaabef525 add comments to untyped_evals --- diff --git a/code/untyped_evaluator.ml b/code/untyped_evaluator.ml index cf2a1b41..e5ce1c12 100644 --- a/code/untyped_evaluator.ml +++ b/code/untyped_evaluator.ml @@ -2,7 +2,7 @@ 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`, @@ -15,9 +15,29 @@ `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 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 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. *) type identifier = string @@ -40,7 +60,7 @@ and env = identifier -> term option (* Operations for environments *) let empty = fun _ -> None -let push (ident : identifier) binding env = +let shift (ident : identifier) binding env = fun (sought_ident : identifier) -> if ident = sought_ident then Some binding @@ -247,8 +267,9 @@ module V2 = struct | 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. *) + (* 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 ^ "`")) diff --git a/code/untyped_evaluator_complete.ml b/code/untyped_evaluator_complete.ml index 8408c2b7..308f85a0 100644 --- a/code/untyped_evaluator_complete.ml +++ b/code/untyped_evaluator_complete.ml @@ -15,9 +15,29 @@ `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 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 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. *) type identifier = string @@ -40,7 +60,7 @@ and env = identifier -> term option (* Operations for environments *) let empty = fun _ -> None -let push (ident : identifier) binding env = +let shift (ident : identifier) binding env = fun (sought_ident : identifier) -> if ident = sought_ident then Some binding @@ -247,8 +267,9 @@ module V2 = struct | 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. *) + (* 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 ^ "`")) @@ -265,7 +286,7 @@ module V2 = struct bound to the result of evaluating arg under the current env *) let arg' = eval arg env in - let env' = push bound_var arg' env in + let env' = shift bound_var arg' env in eval body env' | App(head, arg) -> @@ -276,7 +297,7 @@ module V2 = struct (* evaluate body under saved_env to govern its free variables, except that we add a binding of bound_var to arg' *) - let saved_env' = push bound_var arg' saved_env in + let saved_env' = shift bound_var arg' saved_env in eval body saved_env' | head' -> raise (Stuck(App(head',arg))))