From: Chris <chris.barker@nyu.edu>
Date: Sat, 14 Mar 2015 18:15:58 +0000 (-0400)
Subject: exx
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=62596aa94c32e1b4c01e4a04ab3c53590003df43

exx
---

diff --git a/exercises/_assignment6.mdwn b/exercises/_assignment6.mdwn
index 10657258..e68d3f1a 100644
--- a/exercises/_assignment6.mdwn
+++ b/exercises/_assignment6.mdwn
@@ -70,7 +70,7 @@ get it working:
     # reduce (App (Abstract ("x", Var "x"), Constant (Num 3)));;
     - : lambdaTerm = Constant (Num 3)
 
-What kind of evaluation strategy does this evaluator use?  In
+4. What kind of evaluation strategy does this evaluator use?  In
 particular, what are the answers to the three questions about
 evaluation strategy as given in the discussion of [[evaluation
 strategies|topics/week3_evaluation_order]] as Q1, Q2, and Q3?
@@ -79,6 +79,34 @@ strategies|topics/week3_evaluation_order]] as Q1, Q2, and Q3?
 
 Ok, the previous strategy sucked: tracking free and bound variables,
 computing fresh variables, it's all super complicated.
-Here's a better strategy.
 
+Here's a better strategy. Instead of keeping all of the information
+about which variables have been bound or are still free implicitly
+inside of the terms, we'll keep score.  This will require us to carry
+around a scorecard, which we will call an "environment".  This is a
+familiar strategy, since it amounts to evaluating expressions relative
+to an assignment function.  The difference between the assignment
+function approach above, and this approach, is one huge step towards
+monads.
+
+5. First, you need to get [[the evaluation
+code|code/reduction_with_environments.ml]]  working.  Look in the
+code for places where you see "not yet implemented", and get enough of
+those places working that you can use the code to evaluate terms.
+
+6. A snag: what happens when we want to replace a variable with a term
+that itself contains a free variable?  
+
+    term          environment
+    ------------- -------------
+    (\w.(\y.y)w)2 []
+    (\y.y)w       [w->2]
+    y             [w->2, y->w]
+
+In the first step, we bind `w` to the argument `2`.  In the second
+step, we bind `y` to the argument `w`.  In the third step, we would
+like to replace `y` with whatever its current value is according to
+our scorecard.  On the simple-minded view, we would replace it with
+`w`.  But that's not the right result, because `w` itself has been
+mapped onto 2.