started exercises
[lambda.git] / exercises / _assignment7.mdwn
1 # Assignment 6 (week 7)
2
3 ## Evaluation order in Combinatory Logic
4
5 1. Give a term that the lazy evaluators (either the Haskell evaluator,
6 or the lazy version of the OCaml evaluator) do not evaluate all the
7 way to a normal form, i.e., that contains a redex somewhere inside of
8 it after it has been reduced.
9
10 <!-- reduce3 (FA (K, FA (I, I))) -->
11
12
13 2. One of the 
14 [[criteria we established for classifying reduction strategies|
15 topics/week3_evaluation_order]]
16 strategies is whether they reduce subexpressions hidden under lambdas.
17 That is, for a term like `(\x y. x z) (\x. x)`, do we reduce to
18 `\y.(\x.x) z` and stop, or do we reduce further to `\y.z`?  Explain
19 what the corresponding question would be for CL. Using either the
20 OCaml CL evaluator or the Haskell evaluator developed in the wiki
21 notes, prove that the evaluator does reduce expressions inside of
22 "functional" CL expressions.  Then provide a modified evaluator that
23 does not perform reductions in those positions.
24
25 <!-- just add early no-op cases for Ka and Sab -->