`x`_{1}, x_{2}, x_{3}

, and so on? And then the values that get assigned to those variables could just be kept in a stack, with the first value understood to be assigned to `x`_{1}

, and so on. Yes, we could do that. But the advantage of the de Bruijn notation is that we don't have to keep track of which variable is associated with which lambda binder. In the de Bruijn framework, the outermost binder always goes with the top-most member of the stack. In the proposed alternative, that's not so: we could have:
+
+`\x`_{2}. x (\x_{8}. x_{8} x_{2})
+

+
+In any event, though, we won't make use of de Bruijn notation because, though it makes the semantic algorithms more elegant, it also adds an extra level of conceptual complexity, which we don't want to do.]
+
+Now with the environment-based semantics, instead of evaluating terms using substitution, like this:
+
+ (\x. M) N ~~> M {x <- N}
+
+we'll instead evaluate them by manipulating their environment. (To intepret `(\x. M) N` in environment `e`, we'll interpret `M` in an environment like `e {x:= N}` where `x` may have been changed to now be assigned to `N`.
+
+A few comments. First, what the environment associates with the variable `x` will be expressions of the lambda calculus we're evaluating. If we understand the evaluation to be call-by-name, these expressions may be complexes of the form `N P`. If on the other hand, we understand the evaluation to be call-by-value, then these expressions will always be fully evaluated before being inserted into the environment. That means they'll never be of the form `N P`; but onlu of the form `y` or `\y. P`. The latter kinds of expressions are called "values." But "values" here are just certain kinds of expressions. (They could be the denotations of lambda expressions, if one thinks of the lambda expressions as all having (preferably) normal-form lambda terms as their denotations.)
+
+Second, there is a subtlety here we haven't yet discussed. Consider what should be the result of this:
+
+ let x = 1
+ in let f = \y. x
+ in let x = 2
+ in f 0
+
+If we interpret the `x` in `\y. x` by the value it had where that function was being declared, and bound to `f`, then this complex expression should return `1`. If on other hand we interpret the `x` to have the value it has where that function is given an argument and reduced, then the complex should return `2`.
+
+There is no right or wrong behavior here. Both are reasonable. The former behavior is called **lexical scoping**, and it's what we get in the untyped lambda calculus, for example. It's also what's most common in functional programming languages. It's easier for programmers to reason about.
+
+The latter behavior is called **dynamic scoping**. Often it's easier for language-designers to implement. It is also useful in certain settings. But we will assume we're dealing with lexical scoping.
+
+To implement lexical scoping, you can't just associate the bare formula `\y. x` to the variable `f` in an environment. You also have to keep track of what is the value in that context of all the free variables in the formula. This combination of a function expression together with the values of its free variables is called a **function closure**. There are different techniques for handling these. The technique we'll use here is conceptually simple: it just stashes away both the formula `\y. x` and a copy of the current environment. So even if we're later asked to evaluate `f` in a different environment, we have the original environment to use to lookup values for`f`'s free variables. This is conceptually simple---but inefficient, because it stashes a copy of the entire current environment, when really we only need that part of the environment relevant to a few free variables. If you care to read up more about
+operational semantics for the lambda calculus, or the underpinnings of how Scheme or OCaml interpreters work under the hood, you can learn about other more elegant techniques. Here we'll keep things conceptually simple.
+
+With these ideas settled, then, we can present an environment-based operational semantics for the untyped lambda calculus. Here is a call-by-value version, which assumes that expressions are always fully evaluated before being inserted into the environment.
+
+1. When `e` assigns some term `v` to `x`, then `x`reduces in environment `e` to `v`. We write that as: `(e |- x) ==> v`.
+
+2. `(e |- \x. M) ==> closure(e, \x. M)`, where a closure is some data-structure (it might just be a pair of the data-structure `e` and the formula `\x. M`).
+
+3. If `(e |- M) ==> closure(e2, \x. M2)` and `(e |- N) ==> v` and `(e2 {x:=v} |- M2) ==> u`, then `(e |- M N) ==> u`. Here `e {x:=v}` is the environment which is just like `e` except it assigns `v` to `x`.
+
+
+Explicitly manipulating the environment
+---------------------------------------
+
+In the machinery we just discussed, the environment handling was no part of the language being interpreted. It all took place in the interpreting algorithm. Sometimes, though, it's convenient to explicitly manipulate the environment in your program; or at least, some special portion of the environment, set aside to be manipulated in that way.
+
+For example, a common programming exercise when students are learning languages like OCaml is to implement a simple arithmetic calculator. You'll suppose you're given some expressions of the following type:
+
+ type term = Constant of int | Multiplication of (term * term) | Addition of (term*term) | Variable of char | Let of (char*term*term);;
+
+and then you'd evaluate it something like this:
+
+ let rec eval (t : term) = match t with
+ Constant x -> x
+ | Multiplication (t1,t2) -> (eval t1) * (eval t2)
+ | Addition (t1,t2) -> (eval t1) + (eval t2)
+ | Variable c -> ... (* we'll come back to this *)
+ | Let (c,t1,t2) -> ... (* this too *)
+
+With that in hand, you could then evaluate complex terms like `Addition(Constant 1, Multiplication(2, 3))`.
+
+But then how should you evaluate terms like `Let('x',Constant 1,Addition(Variable 'x', Constant 2))`? We'd want to carry along an environment that recorded that 'x' had been associated with the term `Constant 1`, so that we could retrieve that value when evaluating `Addition(Variable 'x', Constant 2)`.
+
+We'll work with a simple model of environments. They'll just be lists. So the empty environment is `[]`. To modify an environment `e` like this: `e {x:=1}`, we'll use:
+
+ ('x', 1) :: e
+
+that is, `e` is a list of pairs, whose first members are `char`s, and whose second members are evaluation results. To lookup a value `'x'` in `e`, we can use the `List.assoc` function, which behaves like this:
+
+ # List.assoc 'x' [('x',1); ('y',2)];;
+ - : int = 1
+ # List.assoc 'z' [('x',1); ('y',2)];;
+ Exception: Not_found.
+
+Then we should give our `eval` function an extra argument for the environment:
+
+ let rec eval (t : term) (e: (char * int) list) = match t with
+ Constant x -> x
+ | Multiplication (t1,t2) -> (eval t1 e) * (eval t2 e)
+ | Addition (t1,t2) -> (eval t1 e) + (eval t2 e)
+ | Variable c ->
+ (* lookup the value of c in the current environment
+ This will fail if c isn't assigned anything by e *)
+ List.assoc c e
+ | Let (c,t1,t2) ->
+ (* evaluate t2 in a new environment where c has been associated
+ with the result of evaluating t1 in the current environment *)
+ eval t2 ((c, eval t1 e) :: e)
+
+Great! Now we've built a simple calculator with let-expressions.
+
+
+Monadizing it
+-------------
+
+As the calculator gets more complex though, it will become more tedious and unsatisfying to have all the clauses like:
+
+ | Addition (t1,t2) -> (eval t1 e) + (eval t2 e)
+
+have to explicitly pass around an environment that they're not themselves making any use of. Would there be any way to hide that bit of plumbing behind the drywall?
+
+Yes! You can do with a monad, in much the same way we did with our checks for divide-by-zero failures.
+
+Here we'll use a different monad. It's called the **reader monad**. We define it like this:
+
+ (* we assume we've settled on some implementation of the environment *)
+ type env = (char * int) list;;
+
+ (* here's the type of our reader monad *)
+ type 'a reader = env -> 'a;;
+
+ (* here's our unit operation; it creates a reader-monad value that
+ ignores the environment and returns x *)
+ let unit x = fun (e : env) -> x;;
+
+ (* here's our bind operation; how does it work? *)
+ let bind (u : 'a reader) (f: 'a -> 'b reader) : 'b reader =
+ fun (e : env) -> f (u e) e
+
+ (* we also define two special-purpose operations on our reader-monad values *)
+
+ (* evaluate a reader-monad value in a shifted environment; how does this work? *)
+ let shift (c : char) (v : int reader) (u : 'a reader) =
+ fun (e : env) -> u ((c, v e) :: e)
+
+ (* lookup the value of c in the current environment
+ this will fail if c isn't assigned anything by that environment
+ a fuller solution would return an int option instead of
+ returning an int or failing *)
+ let lookup (c : char) : int reader =
+ fun (e : env) -> List.assoc c e
+
+
+With this in hand, we can then do our calculator like this. Instead of `int`s, evaluating a term now returns an `int reader`, a monadic value of our new reader-monad type:
+
+ let rec eval (t : term) = match t with
+ Constant x -> unit x
+ | Multiplication (t1,t2) -> lift2 ( * ) (eval t1) (eval t2)
+ | Addition (t1,t2) -> lift2 ( + ) (eval t1) (eval t2)
+ | Variable c -> lookup c
+ | Let (c,t1,t2) -> shift c (eval t1) (eval t2);;
+
+Now if we try:
+
+ # let result = eval (Let('x',Constant 1,Addition(Variable 'x',Constant 2)));;
+ - : int reader =