week3 evaluator fix

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index c4ea316..8c22dfa 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -9,39 +9,38 @@ assignment much faster and more secure.
 Recall that version 1 style lists are constructed like this (see
 [[lists and numbers]]):
 
 Recall that version 1 style lists are constructed like this (see
 [[lists and numbers]]):
 

-<pre>
-; 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 fixed-point 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 pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil))) in
-let leq = \m n. isZero(n pred m) in
-let eq = \m n. and (leq m n)(leq n m) in
-
-eq 2 2 yes no
-</pre>
+       ; 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 make_pair = \f s g. g f s in
+       let fst = true in
+       let snd = false in
+       let empty = make_pair true junk in
+       let isempty = \x. x fst in
+       let make_list = \h t. make_pair false (make_pair h t) in
+       let head = \l. isempty l err (l snd fst) in
+       let tail = \l. isempty l err (l snd snd) in
+
+       ; a list of numbers to experiment on
+       let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
+
+       ; a fixed-point 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. isempty l 0 (succ (length (tail l)))) in
+       let pred = \n. iszero n 0 (length (tail (n (\p. make_list junk p) empty)))
+       in
+       let leq = \m n. iszero(n pred m) in
+       let eq = \m n. and (leq m n)(leq n m) in
+
+       eq 2 2 yes no

 
 
 Then `length mylist` evaluates to 3.
 
 
 Then `length mylist` evaluates to 3.


@@ -52,41 +51,44 @@ 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 n-1.)
 
 function, write a function that computes factorials.  (Recall that n!,
 the factorial of n, is n times the factorial of n-1.)
 

-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.
+4. (Still easy) Now write the same function, but don't use the length
+function.

 
 

-5. In assignment 2, we discovered that version 3-type lists (the ones that
+5. In assignment 2, we discovered that version 3-type lists (the ones
+that

 work like Church numerals) made it much easier to define operations
 work like Church numerals) made it much easier to define operations

-like `map` and `filter`.  But now that we have recursion in our toolbox,
+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
 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.
+reach.  Give definitions for `map` and a `filter` for verson 1 type
+lists.

 
 #Computing with trees#
 
 
 #Computing with trees#
 

-Linguists analyze natural language expressions into trees.  
+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
 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:
 
 <pre>
 Then we have the following representations:
 
 <pre>

-   (a)           (b)             (c)  
+   (a)           (b)             (c)

     .
    /|\            /\              /\
   / | \          /\ 3            1 /\
     .
    /|\            /\              /\
   / | \          /\ 3            1 /\


@@ -106,29 +108,31 @@ 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 these
 trees.
 
 be your base case for your recursive functions that operate on these
 trees.
 

-1.    Write a function that sums the number of leaves in a tree.
+<OL start=6>
+<LI>Write a function that sums the number of leaves in a tree.

 
 Expected behavior:
 
 
 Expected behavior:
 

-<pre>
-let t1 = (make-list 1 nil) in
-let t2 = (make-list 2 nil) in
-let t3 = (make-list 3 nil) in
-let t12 = (make-list t1 (make-list t2 nil)) in
-let t23 = (make-list t2 (make-list t3 nil)) in
-let ta = (make-list t1 t23) in
-let tb = (make-list t12 t3) in
-let tc = (make-list t1 (make-list t23 nil)) in
-
-count-leaves t1 ~~> 1
-count-leaves t2 ~~> 2
-count-leaves t3 ~~> 3
-count-leaves t12 ~~> 3
-count-leaves t23 ~~> 5
-count-leaves ta ~~> 6
-count-leaves tb ~~> 6
-count-leaves tc ~~> 6
-</pre>
+       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 t3) in
+       let tc = (make_list t1 (make_list t23 empty)) in
+
+       sum-leaves t1 ~~> 1
+       sum-leaves t2 ~~> 2
+       sum-leaves t3 ~~> 3
+       sum-leaves t12 ~~> 3
+       sum-leaves t23 ~~> 5
+       sum-leaves ta ~~> 6
+       sum-leaves tb ~~> 6
+       sum-leaves tc ~~> 6
+
+
+<LI>Write a function that counts the number of leaves.

 
 

-2.   Write a function that counts the number of leaves.
+</OL>