added some exercises related to CL
[lambda.git] / exercises / assignment3.mdwn
index d1cec2a..21997ee 100644 (file)
@@ -6,7 +6,7 @@
 
 2. What does `[ 10*x + y | y from [4], x from [1, 2, 3] ]` evalaute to?
 
-3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hints]], if you need it.
+3. Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hint1]], if you need it.
 
 
 ## Lists
@@ -17,7 +17,7 @@
 
 6. Continuing to encode lists in terms of their left-folds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
 
-7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a hint|assignment3 hints]], if you need it.
+7. Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging. [[Here is a solution|assignment3 hint2]], if you need help.
 
 
 ## Numbers
@@ -68,6 +68,25 @@ Using the mapping specified in this week's notes, translate the following lambda
 
 23. For each of the above translations, how many `I`s are there? Give a rule for describing what each `I` corresponds to in the original lambda term.
 
+Evaluation strategies in Combinatory Logic
+------------------------------------------
+
+23. Find a term in CL that behaves like Omega does in the Lambda
+Calculus.  Call it Skomega.
+
+24. Are there evaluation strategies in CL corresponding to leftmost
+reduction and rightmost reduction in the lambda calculus?  
+What counts as a redex in CL? 
+
+25. Consider the CL term K I Skomega.  Does leftmost (alternatively,
+rightmost) evaluation give results similar to the behavior of K I
+Omega in the lambda calculus, or different?  What features of the
+lambda calculus and CL determine this answer?
+
+26. What should count as a thunk in CL?  What is the equivalent
+constraint in CL to forbidding evaluation inside of a lambda abstract?
+
+
 More Lambda Practice
 --------------------