X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment2.mdwn;h=3e932561960bbc7792c34d868ea008aee1b2fb25;hp=f0e8a0989cfaf28919d7b03ead3ce51529a969e7;hb=f2662f133c25062dc28261f655bb9daf9c2bbb9c;hpb=4c0fb46d0cb9dcbfa5687140afeca2fdb48f668c diff --git a/assignment2.mdwn b/assignment2.mdwn index f0e8a098..3e932561 100644 --- a/assignment2.mdwn +++ b/assignment2.mdwn @@ -1,4 +1,4 @@ -For these assignments, you'll probably want to use a "lambda calculator" to check your work. This accepts any grammatical lambda expression and reduces it to normal form, when possible. See the page on [[using the programming languages]] for instructions and links about setting this up. +For these assignments, you'll probably want to use our [[lambda evaluator]] to check your work. This accepts any grammatical lambda expression and reduces it to normal form, when possible. More Lambda Practice @@ -38,28 +38,31 @@ Combinatory Logic Reduce the following forms, if possible: -1. Kxy -2. KKxy -3. KKKxy -4. SKKxy -5. SIII -6. SII(SII) - -* Give Combinatory Logic combinators that behave like our boolean functions. - You'll need combinators for true, false, neg, and, or, and xor. +
    +
  1. `Kxy` +
  2. `KKxy` +
  3. `KKKxy` +
  4. `SKKxy` +
  5. `SIII` +
  6. `SII(SII)` + +
  7. Give Combinatory Logic combinators that behave like our boolean functions. + You'll need combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`. +
Using the mapping specified in the lecture notes, translate the following lambda terms into combinatory logic: -1. \x.x -2. \xy.x -3. \xy.y -4. \xy.yx -5. \x.xx -6. \xyz.x(yz) - -* For each translation, how many I's are there? Give a rule for +
    +
  1. `\x.x` +
  2. `\xy.x` +
  3. `\xy.y` +
  4. `\xy.yx` +
  5. `\x.xx` +
  6. `\xyz.x(yz)` +
  7. For each translation, how many I's are there? Give a rule for describing what each I corresponds to in the original lambda term. +
Lists and Numbers -----------------