XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment3.mdwn;h=e240b732b1405e176d696bbab3c5974a1d125f35;hp=9f64d808f637a1d3c67c1cfa8584e69d0f9e27bf;hb=eb8ac48a126c26a8195d19dfc0e1f60009198746;hpb=71bfc3a4fcf9ae9eddc1854bce2ff6d5f6869644
diff git a/assignment3.mdwn b/assignment3.mdwn
index 9f64d808..e240b732 100644
 a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ 1,47 +1,59 @@
Assignment 3

Once again, the lambda evaluator will make working through this
assignment much faster and more secure.
+Erratum corrected 11PM Sun 3 Oct: the following line
*Writing recursive functions on version 1 style lists*
+ let tb = (make_list t12 (make_list t3 empty)) in
Recall that version 1 style lists are constructed like this:
+originally read
; booleans
let true = \x y. x in
let false = \x y. y in
let and = \l r. l (r true false) false in

; version 1 lists
let makePair = \f s g. g f s in
let fst = true in
let snd = false in
let nil = makePair true meh in
let isNil = \x. x fst in
let makeList = \h t. makePair false (makePair h t) in
let head = \l. isNil l err (l snd fst) in
let tail = \l. isNil l err (l snd snd) in

; a list of numbers to experiment on
let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in

; a fixedpoint combinator for defining recursive functions
let Y = \f. (\h. f (h h)) (\h. f (h h)) in

; church numerals
let isZero = \n. n (\x. false) true in
let succ = \n s z. s (n s z) in
let mult = \m n s. m (n s) in
let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
let predecessor = \n. length (tail (n (\p. makeList meh p) nil)) in
let leq = ; (leq m n) will be true iff m is less than or equal to n
 Y (\leq m n. isZero m true (isZero n false (leq (predecessor m)(predecessor n)))) in
let eq = \m n. and (leq m n)(leq n m) in

eq 3 3

+ let tb = (make_list t12 t3) in
+
+This has been corrected below, and in the preloaded evaluator for
+working on assignment 3, available here: [[assignment 3 evaluator]].
+
+
+
+Once again, the lambda evaluator will make working through this
+assignment much faster and more secure.
+
+#Writing recursive functions on version 1 style lists#
+
+Recall that version 1 style lists are constructed like this (see
+[[lists and numbers]]):
+
+ ; booleans
+ let true = \x y. x in
+ let false = \x y. y in
+ let and = \l r. l (r true false) false in
+
+ let make_pair = \f s g. g f s in
+ let get_fst = true in
+ let get_snd = false in
+ let empty = make_pair true junk in
+ let isempty = \x. x get_fst in
+ let make_list = \h t. make_pair false (make_pair h t) in
+ let head = \l. isempty l err (l get_snd get_fst) in
+ let tail = \l. isempty l err (l get_snd get_snd) in
+
+ ; a list of numbers to experiment on
+ let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
+
+ ; church numerals
+ let iszero = \n. n (\x. false) true in
+ let succ = \n s z. s (n s z) in
+ let add = \l r. l succ r in
+ let mul = \m n s. m (n s) in
+ let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
+ let leq = \m n. iszero(n pred m) in
+ let eq = \m n. and (leq m n)(leq n m) in
+
+ ; a fixedpoint combinator for defining recursive functions
+ let Y = \f. (\h. f (h h)) (\h. f (h h)) in
+ let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
+ let fold = Y (\f l g z. isempty l z (g (head l)(f (tail l) g z))) in
+
+ eq 2 2 yes no
Then `length mylist` evaluates to 3.
@@ 52,98 +64,88 @@ Then `length mylist` evaluates to 3.
function, write a function that computes factorials. (Recall that n!,
the factorial of n, is n times the factorial of n1.)
Warning: my browser isn't able to compute factorials of numbers
greater than 2 (it does't provide enough resources for the JavaScript
interpreter; web pages are not supposed to be that computationally
intensive).
+ Warning: it takes a long time for my browser to compute factorials larger than 4!
3. (Easy) Write a function `listLenEq` that returns true just in case two lists have the
same length. That is,
+3. (Easy) Write a function `equal_length` that returns true just in case
+two lists have the same length. That is,
 listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+ equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
 listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
+ equal_length mylist (make_list junk (make_list junk empty))) ~~> false
4. (Still easy) Now write the same function, but don't use the length function (hint: use `leq` as a model).
+4. (Still easy) Now write the same function, but don't use the length
+function.
5. In assignment 2, we discovered that version 3type lists (the ones that
+5. In assignment 2, we discovered that version 3type lists (the ones
+that
work like Church numerals) made it much easier to define operations
like map and filter. But now that we have recursion in our toolbox,
reasonable map and filter functions for version 3 lists are within our
reach. Give definitions for such a map and a filter.
+like `map` and `filter`. But now that we have recursion in our
+toolbox,
+reasonable map and filter functions for version 1 lists are within our
+reach. Give definitions for `map` and a `filter` for verson 1 type
+lists.
+
+#Computing with trees#
+
+Linguists analyze natural language expressions into trees.
6. Linguists analyze natural language expressions into trees.
We'll need trees in future weeks, and tree structures provide good
opportunities for learning how to write recursive functions.
Making use of the resources we have at the moment, we can approximate
trees as follows: instead of words, we'll use Church numerals.
Then a tree will be a (version 1 type) list in which each element is
itself a tree. For simplicity, we'll adopt the convention that
a tree of length 1 must contain a number as its only element.
+itself a tree. For simplicity, we'll adopt the convention that
+a tree of length 1 must contain a number as its only element.
+
Then we have the following representations:
 (a) (b) (c)
+ (a) (b) (c)
.
/\ /\ /\
 /  \ /\ 3 1/\
+ /  \ /\ 3 1 /\
1 2 3 1 2 2 3
[[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
Limitations of this scheme include the following: there is no easy way
to label a constituent (typically a syntactic category, S or NP or VP,
+to label a constituent with a syntactic category (S or NP or VP,
etc.), and there is no way to represent a tree in which a mother has a
single daughter.
When processing a tree, you can test for whether the tree contains
only a numeral (in which case the tree is leaf node) by testing for
whether the length of the list is less than or equal to 1. This will
be your base case for your recursive functions that operate on trees.

Write a function that sums the number of leaves in a tree.
Expected behavior:

let t1 = (makelist 1 nil)
let t2 = (makelist 2 nil)
let t3 = (makelist 3 nil)
let t12 = (makelist t1 (makelist t2 nil))
let t23 = (makelist t2 (makelist t3 nil))
let ta = (makelist t1 t23)
let tb = (makelist t12 t3)
let tc = (makelist t1 (makelist t23 nil))

countleaves t1 ~~> 1
countleaves t2 ~~> 2
countleaves t3 ~~> 3
countleaves t12 ~~> 3
countleaves t23 ~~> 5
countleaves ta ~~> 6
countleaves tb ~~> 6
countleaves tc ~~> 6

Write a function that counts the number of leaves.
+be your base case for your recursive functions that operate on these
+trees.
+
+ Write a function that sums the values at the leaves in a tree.
+Expected behavior:
+ let t1 = (make_list 1 empty) in
+ let t2 = (make_list 2 empty) in
+ let t3 = (make_list 3 empty) in
+ let t12 = (make_list t1 (make_list t2 empty)) in
+ let t23 = (make_list t2 (make_list t3 empty)) in
+ let ta = (make_list t1 t23) in
+ let tb = (make_list t12 (make_list t3 empty)) in
+ let tc = (make_list t1 (make_list t23 empty)) in
[The following should be correct, but won't run in my browser:
+ sumleaves t1 ~~> 1
+ sumleaves t2 ~~> 2
+ sumleaves t3 ~~> 3
+ sumleaves t12 ~~> 3
+ sumleaves t23 ~~> 5
+ sumleaves ta ~~> 6
+ sumleaves tb ~~> 6
+ sumleaves tc ~~> 6

let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
let reverse =
 Y (\rev l. isNil l nil
 (isNil (tail l) l
 (makeList (head (rev (tail l)))
 (rev (makeList (head l)
 (rev (tail (rev (tail l))))))))) in

reverse (makeList 1 (makeList 2 (makeList 3 nil)))

+  Write a function that counts the number of leaves.
It may require more resources than my browser is willing to devote to
JavaScript.]
+