X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment3.mdwn;fp=exercises%2Fassignment3.mdwn;h=674cf40e3087dab73ed20099411a1280b1745a2a;hp=21997eeb707d2304bc8f08c3545ee8b848a992a2;hb=8d11f56b4dd370271a919f2cc037c399851d4bc8;hpb=bc0708caa18ac5d16a57a95a1387c8b7ab855eeb diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index 21997eeb..674cf40e 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -24,7 +24,7 @@ 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. (Here is [some interesting commentary](http://okmij.org/ftp/Computation/lambda-calc.html#predecessor).) 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. -9. Define `leq` for numbers (that is, ≤) in the Lambda Calculus. Here is the expected behavior, +9. 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)`. leq zero zero ~~> true @@ -75,8 +75,8 @@ Evaluation strategies in Combinatory Logic 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? +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