XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment3.mdwn;h=5bee7a43484f71cbf42f3016132caafac4489920;hp=9ed9e35bcbcf527ca9a1c128480bb6c9e291ab5d;hb=2f9ea958a1eb9d82d6f8dcad14e9060aeeaf9e4b;hpb=456fa2f81fc4d3378162bb85a11756a188c6ed4c
diff git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn
index 9ed9e35b..5bee7a43 100644
 a/exercises/assignment3.mdwn
+++ b/exercises/assignment3.mdwn
@@ 1,59 +1,115 @@
** *Work In Progress* **
+## Lists and List Comprehensions
## Comprehensions
+1. In Kapulet, what does `[ [x, 2*x]  x from [1, 2, 3] ]` evaluate to?
1. In Kapulet, what does `[ [x, 2*x]  x from [1, 2, 3] ]` evaluate to?
+2. What does `[ 10*x + y  y from [4], x from [1, 2, 3] ]` evalaute to?
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 hintassignment3 hint1]], 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]`.
+4. Last week you defined `head` in terms of `fold_right`. Your solution should be straightforwardly translatable into one that uses our proposed rightfold encoding of lists in the Lambda Calculus. Now define `empty?` in the Lambda Calculus. (It should require only small modifications to your solution for `head`.)

+5. If we encode lists in terms of their *left*folds, instead, `[a, b, c]` would be encoded as `\f z. f (f (f z a) b) c`. The empty list `[]` would still be encoded as `\f z. z`. What should `cons` be, for this encoding?
## Lists
+6. Continuing to encode lists in terms of their leftfolds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
4. Last week you defined `head` in the Lambda Calculus, using our proposed encoding for lists. Now define `empty?` (It should require only small modifications to your solution for `head`.)
+7. Continuing to encode lists in terms of their leftfolds, how should we write `head`? This is challenging. [[Here is a solutionassignment3 hint2]], if you need help.
5. If we encode lists in terms of their *left*folds, instead, `[a, b, c]` would be encoded as `\f z. f (f (f z a) b) c`. The empty list `[]` would still be encoded as `\f z. z`. What should `cons` be, for this encoding?
+8. Suppose you have two lists of integers, `left` and `right`. You want to determine whether those lists are equal, that is, whether they have all the same members in the same order. How would you implement such a list comparison? You can write it in Scheme or Kapulet using `letrec`, or if you want more of a challenge, in the Lambda Calculus using your preferred encoding for lists. If you write it in Scheme, don't rely on applying the builtin comparison operator `equal?` to the lists themselves. (Nor on the operator `eqv?`, which might not do what you expect.) You can however rely on the comparison operator `=` which accepts only number arguments. If you write it in the Lambda Calculus, you can use your implementation of `leq`, requested below, to write an equality operator for Churchencoded numbers. [[Here is a hintassignment3 hint3]], if you need it.
6. Continuing to encode lists in terms of their leftfolds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
+ (The function you're trying to define here is like `eqlist?` in Chapter 5 of *The Little Schemer*, though you are only concerned with lists of numbers, whereas the function from *The Little Schemer* also works on lists containing symbolic atoms  and in the final version from that Chapter, also on lists that contain other, embedded lists.)
7. Continuing to encode lists in terms of their leftfolds, how should we write `head`? This is challenging.

## Numbers
8. Recall our proposed encoding for the numbers, called "Church's encoding". As we explained last week, it's similar to our proposed encoding of lists in terms of their folds. In last week's homework, you defined `succ` for numbers so encoded. Can you now define `pred` in the Lambca Calculus? Let `pred 0` result in whatever `err` is bound to. This is challenging. For some time theorists weren't sure it could be done. However, in this week's notes we examined one strategy for defining `tail` for our chosen encodings of lists, and given the similarities we explained between lists and numbers, perhaps that will give you some guidance in defining `pred` for numbers.
+11. Define `leq` for numbers (that is, ≤) in the Lambda Calculus. Here is the expected behavior,
+where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`.
9. Define `leq` for numbers (that is, ≤) in the Lambda Calculus.
+ leq zero zero ~~> true
+ leq zero one ~~> true
+ leq zero two ~~> true
+ leq one zero ~~> false
+ leq one one ~~> true
+ leq one two ~~> true
+ leq two zero ~~> false
+ leq two one ~~> false
+ leq two two ~~> true
+ ...
## Combinatorial Logic
+ You'll need to make use of the predecessor function, but it's not essential to understanding this problem that you have successfully implemented it yet. You can treat it as a black box.
+
+## Combinatory Logic
Reduce the following forms, if possible:
10. `Kxy`
11. `KKxy`
12. `KKKxy`
13. `SKKxy`
14. `SIII`
15. `SII(SII)`
+
+Kxy
+KKxy
+KKKxy
+SKKxy
+SIII
+SII(SII)
+
16. Give Combinatorial Logic combinators (that is, expressed in terms of `S`, `K`, and `I`) that behave like our boolean functions. You'll need combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`.
+18. Give Combinatory Logic combinators (that is, expressed in terms of `S`, `K`, and `I`) that behave like our boolean functions. Provide combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`.
Using the mapping specified in this week's notes, translate the following lambda terms into combinatory logic:
17. `\x x`
18. `\x y. x`
19. `\x y. y`
20. `\x y. y x`
21. `\x. x x`
22. `\x y z. x (y z)`
+
+\x x
+\x y. x
+\x y. y
+\x y. y x
+\x. x x
+\x y z. x (y z)
+
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.
+25. 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
+
+
+26. Find a term in CL that behaves like Omega does in the Lambda
+Calculus. Call it `Skomega`.
+
+27. Are there evaluation strategies in CL corresponding to leftmost
+reduction and rightmost reduction in the Lambda Calculus?
+What counts as a redex in CL?
+
+28. 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?
+
+29. 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
+
+
+Reduce to betanormal forms:
+
+
+(\x. x (\y. y x)) (v w)
+(\x. x (\x. y x)) (v w)
+(\x. x (\y. y x)) (v x)
+(\x. x (\y. y x)) (v y)
+
+(\x y. x y y) u v
+(\x y. y x) (u v) z w
+(\x y. x) (\u u)
+(\x y z. x z (y z)) (\u v. u)
+
+