notes for week 4

[lambda.git] / assignment3.mdwn

diff --git a/assignment3.mdwn b/assignment3.mdwn
index d00dba0..f93afd6 100644 (file)
--- a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ -4,92 +4,94 @@ Assignment 3
 Once again, the lambda evaluator will make working through this
 assignment much faster and more secure.
 
 Once again, the lambda evaluator will make working through this
 assignment much faster and more secure.
 

-*Writing recursive functions on version 1 style lists*
+##Writing recursive functions on version 1 style lists##

 
 Recall that version 1 style lists are constructed like this:
 
 
 Recall that version 1 style lists are constructed like this:
 

-<textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
+<pre>
+; booleans

 let true = \x y. x in
 let false = \x y. y in
 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 makePair = \f s g. g f s in

-let nil = makePair true meh in
-let makeList = \h t. makePair false (makePair h t) in
-let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in

 let fst = true in
 let snd = false in
 let fst = true in
 let snd = false in

+let nil = makePair true meh in

 let isNil = \x. x fst 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
 let head = \l. isNil l err (l snd fst) in
 let tail = \l. isNil l err (l snd snd) in

-let succ = \n s z. s (n s z) 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
 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 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
+</pre>
+
+
+Then `length mylist` evaluates to 3.
+
+1. Warm-up: What does `head (tail (tail mylist))` evaluate to?

 
 

-length mylist
-</textarea>
-<input id="PARSE" value="Normalize" type="button">
-<input id="ETA" type="checkbox">do eta-reductions too
-<noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
-<script src="/code/lambda.js"></script>
-<script src="/code/tokens.js"></script>
-<script src="/code/parse.js"></script>
-<script src="/code/json2.js"></script>
-<pre id="OUTPUT">
+2. Using the `length` function as a model, and using the predecessor
+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).
+
+
+3. Write a function `listLenEq` that returns true just in case two lists have the
+same length.  That is,
+
+     listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+
+     listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
+
+4. Now write the same function, but don't use the length function (hint: use `leq` as a model).
+
+##Trees##
+
+Since we'll be working with linguistic objects, let's approximate
+trees as follows: a tree is a version 1 list
+a Church number is a tree, and 
+if A and B are trees, then (make-pair A B) is a tree.
+
+
+
+
+[The following should be correct, but won't run in my browser:
+
+let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
+
+<pre>
+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)))

 </pre>
 </pre>

-<script>
-/*jslint evil: true */
-
-/*members create, error, message, name, prototype, stringify, toSource,
-    toString, write
-*/
-
-/*global JSON, make_parse, parse, source, tree */
-
-// Make a new object that inherits members from an existing object.
-
-if (typeof Object.create !== 'function') {
-    Object.create = function (o) {
-        function F() {}
-        F.prototype = o;
-        return new F();
-    };
-}
-
-// Transform a token object into an exception object and throw it.
-
-Object.prototype.error = function (message, t) {
-    t = t || this;
-    t.name = "SyntaxError";
-    t.message = message;
-    throw t;
-};
-
-
-(function () {
-    var parse = make_parse();
-
-    function go(source) {
-        var string, tree, expr, eta;
-        try {
-            tree = parse(source);
- //           string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
-                       expr = tree.handler();
-            // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
-//                     string = expr.to_string() + "\n\n~~>\n\n";
-                       string = '';
-                       eta = document.getElementById('ETA').checked;
-                       string = string + reduce(expr, eta, false).to_string();
-        } catch (e) {
-            string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
-                    'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
-        }
-        document.getElementById('OUTPUT').innerHTML = string
-            .replace(/&/g, '&amp;')
-            .replace(/[<]/g, '&lt;');
-    }
-
-    document.getElementById('PARSE').onclick = function (e) {
-        go(document.getElementById('INPUT').value);
-    };
-}());
-
-</script>
+
+It may require more resources than my browser is willing to devote to
+JavaScript.]
+