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 -->
  26
  27 3. In the previous homework, one of the techniques for controlling
  28 evaluation order was wrapping expressions in a `let`: `let x = blah in
  29 foo`, you could be sure that `blah` would be evaluated by the time the
  30 interpreter considered `foo` (unless you did some fancy footwork with
  31 thunks).  That suggests the following way to try to arrive at eager
  32 evaluation in our Haskell evaluator for CL:
  33
  34     reduce4 t = case t of
  35       I -> I
  36       K -> K
  37       S -> S
  38       FA a b ->
  39         let b' = reduce4 b in
  40         let a' = reduce4 a in
  41         let t' = FA a' b' in
  42           if (is_redex t') then reduce4 (reduce_one_step t')
  43                            else t'
  44
  45 Will this work?  That is, will `reduce4 (FA (FA K I) skomega)` go into
  46 an infinite loop?  Run the code to find out, if you must, but write
  47 down your guess (and your rationale) first.
  48
  49 <!-- Doesn't work: infinite loop. -->
  50