assignment3.mdwn

   1 Assignment 3
   2 ------------
   3
   4 Once again, the lambda evaluator will make working through this
   5 assignment much faster and more secure.
   6
   7 *Writing recursive functions on version 1 style lists*
   8
   9 Recall that version 1 style lists are constructed like this:
  10
  11 <textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
  12 let true = \x y. x in
  13 let false = \x y. y in
  14 let makePair = \f s g. g f s in
  15 let nil = makePair true meh in
  16 let makeList = \h t. makePair false (makePair h t) in
  17 let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
  18 let fst = true in
  19 let snd = false in
  20 let isNil = \x. x fst in
  21 let head = \l. isNil l err (l snd fst) in
  22 let tail = \l. isNil l err (l snd snd) in
  23 let succ = \n s z. s (n s z) in
  24 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
  25 let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
  26
  27 length mylist
  28 </textarea>
  29 <input id="PARSE" value="Normalize" type="button">
  30 <input id="ETA" type="checkbox">do eta-reductions too
  31 <noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
  32 <script src="/code/lambda.js"></script>
  33 <script src="/code/tokens.js"></script>
  34 <script src="/code/parse.js"></script>
  35 <script src="/code/json2.js"></script>
  36 <pre id="OUTPUT">
  37 </pre>
  38 <script>
  39 /*jslint evil: true */
  40
  41 /*members create, error, message, name, prototype, stringify, toSource,
  42     toString, write
  43 */
  44
  45 /*global JSON, make_parse, parse, source, tree */
  46
  47 // Make a new object that inherits members from an existing object.
  48
  49 if (typeof Object.create !== 'function') {
  50     Object.create = function (o) {
  51         function F() {}
  52         F.prototype = o;
  53         return new F();
  54     };
  55 }
  56
  57 // Transform a token object into an exception object and throw it.
  58
  59 Object.prototype.error = function (message, t) {
  60     t = t || this;
  61     t.name = "SyntaxError";
  62     t.message = message;
  63     throw t;
  64 };
  65
  66
  67 (function () {
  68     var parse = make_parse();
  69
  70     function go(source) {
  71         var string, tree, expr, eta;
  72         try {
  73             tree = parse(source);
  74  //           string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
  75                         expr = tree.handler();
  76             // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
  77 //                      string = expr.to_string() + "\n\n~~>\n\n";
  78                         string = '';
  79                         eta = document.getElementById('ETA').checked;
  80                         string = string + reduce(expr, eta, false).to_string();
  81         } catch (e) {
  82             string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
  83                     'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
  84         }
  85         document.getElementById('OUTPUT').innerHTML = string
  86             .replace(/&/g, '&amp;')
  87             .replace(/[<]/g, '&lt;');
  88     }
  89
  90     document.getElementById('PARSE').onclick = function (e) {
  91         go(document.getElementById('INPUT').value);
  92     };
  93 }());
  94
  95 </script>