From ffe08a8b7b983eb0919882f2a2e9c72aa27394ea Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 19 Sep 2010 22:28:11 -0400 Subject: [PATCH] expand assignment 2 Signed-off-by: Jim Pryor --- assignment2.mdwn | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/assignment2.mdwn b/assignment2.mdwn index 04c3a282..f6bde83d 100644 --- a/assignment2.mdwn +++ b/assignment2.mdwn @@ -1,3 +1,39 @@ +More Lambda Practice +-------------------- + +Insert all the implicit `( )`s and λs into the following abbreviated expressions: + +1. `x x (x x x) x` +2. `v w (\x y. v x)` +3. `(\x y. x) u v` +4. `w (\x y z. x z (y z)) u v` + +Mark all occurrences of `x y` in the following terms: + +
    +
  1. `(\x y. x y) x y` +
  2. `(\x y. x y) (x y)` +
  3. `\x y. x y (x y)` +
+ +Reduce to beta-normal forms: + +
    +
  1. `(\x. x (\y. y x)) (v w)` +
  2. `(\x. x (\x. y x)) (v w)` +
  3. `(\x. x (\y. y x)) (v x)` +
  4. `(\x. x (\y. y x)) (v y)` + +
  5. `(\x y. x y y) u v` +
  6. `(\x y. y x) (u v) z w` +
  7. `(\x y. x) (\u u)` +
  8. `(\x y z. x z (y z)) (\u v. u)` +
+ + +Lists and Numbers +----------------- + We'll assume the "Version 3" implementation of lists and numbers throughout. So: 
zero ≡ \s z. z
-- 
2.11.0