Merge branch 'master' into working
authorJim <jim.pryor@nyu.edu>
Tue, 10 Feb 2015 11:12:22 +0000 (06:12 -0500)
committerJim <jim.pryor@nyu.edu>
Tue, 10 Feb 2015 11:12:22 +0000 (06:12 -0500)
* master: (22 commits)
  rename exercises/assignment2_answers.mdwn to exercises/_assignment2_answers.mdwn
  just link to hint for `reverse`
  compare `cons`
  create page
  link to answers1
  formatting, code style
  link to answers to week1 homework
  create solutions
  redo hint links
  removed
  create page
  create page
  reorganize, add some (as-yet-unlinked) titles for week 3
  add anchors
  tweak explanation of why `f` is curried
  clarify why Lambda Calculus prefers curried functions, thanks for input Kyle
  38e98c659e1819ddd4457935508ee12824b50241
  edits to combinatory logic
  added old CL text
  clarify constraints
  ...

exercises/assignment3.mdwn
images/randj.jpg [moved from randj.jpg with 100% similarity]
rosetta1.mdwn

index 271d2bf..e2fd962 100644 (file)
 
 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, &leq;) in the Lambda Calculus.
+9. Define `leq` for numbers (that is, &leq;) 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:
+
+<OL start=24>
+<LI>`(\x. x (\y. y x)) (v w)`
+<LI>`(\x. x (\x. y x)) (v w)`
+<LI>`(\x. x (\y. y x)) (v x)`
+<LI>`(\x. x (\y. y x)) (v y)`
+
+<LI>`(\x y. x y y) u v`
+<LI>`(\x y. y x) (u v) z w`
+<LI>`(\x y. x) (\u u)`
+<LI>`(\x y z. x z (y z)) (\u v. u)`
+</OL>
+
similarity index 100%
rename from randj.jpg
rename to images/randj.jpg
index 0a09c7c..e353451 100644 (file)
@@ -2,7 +2,7 @@
 
 ## Can you summarize the differences between your made-up language and Scheme, OCaml, and Haskell? ##
 
-The made-up language we wet our toes in in week 1 is called Kapulet. (I'll tell you [the story behind its name](/randj.jpg) sometime.) The purpose of starting with this language is that it represents something of a center of gravity between Scheme, OCaml, and Haskell, and also lacks many of their idiosyncratic warts. One downside is that it's not yet implemented in a form that you can run on your computers. So for now, if you want to try out your code on a real mechanical evaluator, you'll need to use one of the other languages.
+The made-up language we wet our toes in in week 1 is called Kapulet. (I'll tell you [the story behind its name](/images/randj.jpg) sometime.) The purpose of starting with this language is that it represents something of a center of gravity between Scheme, OCaml, and Haskell, and also lacks many of their idiosyncratic warts. One downside is that it's not yet implemented in a form that you can run on your computers. So for now, if you want to try out your code on a real mechanical evaluator, you'll need to use one of the other languages.
 
 Also, if you want to read code written outside this seminar, or have others read your code, for these reasons too you'll need to make the shift over to one of the established languages.