From 077b3c9d4eb81dc63a3b5cf75d4185812728e1f3 Mon Sep 17 00:00:00 2001 From: Jim Date: Sun, 8 Feb 2015 20:57:10 -0500 Subject: [PATCH] expand assignment3 --- exercises/assignment3.mdwn | 34 +++++++++++++++++++++++++++++++++- 1 file changed, 33 insertions(+), 1 deletion(-) diff --git a/exercises/assignment3.mdwn b/exercises/assignment3.mdwn index 36154531..d1cec2a9 100644 --- a/exercises/assignment3.mdwn +++ b/exercises/assignment3.mdwn @@ -24,7 +24,21 @@ 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. +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 + 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 + ... + + 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. ## Combinatorial Logic @@ -53,3 +67,21 @@ Using the mapping specified in this week's notes, translate the following lambda 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. + +More Lambda Practice +-------------------- + +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)` +
+ -- 2.11.0