hw6
[lambda.git] / exercises / _assignment6.mdwn
diff --git a/exercises/_assignment6.mdwn b/exercises/_assignment6.mdwn
new file mode 100644 (file)
index 0000000..aabcbe0
--- /dev/null
@@ -0,0 +1,28 @@
+# Assignment 6 (week 7)
+
+## Evaluation order in Combinatory Logic
+
+1. Give a term that the lazy evaluators (either [[the Haskell
+evaluator|code/ski_evaluator.hs]], or the lazy version of [[the OCaml
+evaluator|code/ski_evaluator.ml]]) do not evaluate all the way to a
+normal form, i.e., that contains a redex somewhere inside of it after
+it has been reduced.
+
+<!-- reduce3 (FA (K, FA (I, I))) -->
+
+2. One of the [[criteria we established for classifying reduction
+strategies|topics/week3_evaluation_order]] strategies is whether they
+reduce subexpressions hidden under lambdas.  That is, for a term like
+`(\x y. x z) (\x. x)`, do we reduce to `\y.(\x.x) z` and stop, or do
+we reduce further to `\y.z`?  Explain what the corresponding question
+would be for CL. Using either the OCaml CL evaluator or the Haskell
+evaluator developed in the wiki notes, prove that the evaluator does
+reduce expressions inside of at least some "functional" CL
+expressions.  Then provide a modified evaluator that does not perform
+reductions in those positions. (Just give the modified version of your
+recursive reduction function.)
+
+<!-- just add early no-op cases for Ka and Sab -->
+
+## Evaluation in the untyped lambda calculus
+