X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=exercises%2Fassignment3_answers.mdwn;h=ea0256da9f15416f2b770090a7fd6bf7bfe2daac;hp=7530534f3c4e086c6260aaaface0b1b6b4126809;hb=fd6b36c3552b1b3c7d0d2eb497b3c925cab9418f;hpb=c9938f8210260c15fd1a7d5308b3115858e7e9c6 diff --git a/exercises/assignment3_answers.mdwn b/exercises/assignment3_answers.mdwn index 7530534f..ea0256da 100644 --- a/exercises/assignment3_answers.mdwn +++ b/exercises/assignment3_answers.mdwn @@ -238,23 +238,6 @@ Reduce the following forms, if possible: Using the mapping specified in this week's notes, translate the following lambda terms into combinatory logic: - -Let's say that for any lambda term T, [T] is the equivalent Combinatory Logic term. Then we define the [.] mapping as follows. - - 1. [a] = a - 2. [(\aX)] = @a[X] - 3. [(XY)] = ([X][Y]) - -Wait, what is that @a ... business? Well, that's another operation on (a variable and) a CL expression, that we can define like this: - - 4. @aa = I - 5. @aX = KX if a is not in X - 6. @a(Xa) = X if a is not in X - 7. @a(XY) = S(@aX)(@aY) - - - -
  1. [\x x] = @x x = I
  2. [\x y. x] = @x [\y. x] = @x. (@y x) = @x (Kx) = S (@x K) (@x x) = S (KK) I; in general expressions of this form S(KM)I will behave just like M for any expression M @@ -284,6 +267,12 @@ S (S (KS) (S (KK) (S (KS) K))) (KI); this is the B combinator, whi 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. + This generalization depends on you omitting the translation rule: + + 6. @a(Xa) = X if a is not in X + + > With that shortcut rule omitted, then there turn out to be one `I` in the result corresponding to each occurrence of a bound variable in the original term. + Evaluation strategies in Combinatory Logic ------------------------------------------