lambda_evaluator.mdwn

   1 Lambda Evaluator
   2 ----------------
   3
   4 There is now a [lambda evaluator](http://lambda.jimpryor.net/lambda-let.html) available.
   5 It will allow you to write lambda terms and evaluate (that is, normalize) them, and inspect the results.
   6 (This won't work in Racket, because Racket doesn't even try to represent the internal structure of a function in a human-readable way.)
   7
   8 *Lambda terms*: lambda terms are written with a backslash, thus: `((\x (\y x)) z)`.
   9
  10 If you click "Normalize", the system will try to produce a normal-form lambda expression that your original term reduces to (~~>). So `((\x (\y x)) z)` reduces to `(\y z)`.
  11
  12 *Let*: in order to make building a more elaborate set of terms easier, it is possible to define values using `let`.
  13 In this toy system, `let`s should only be used at the beginning of a file.  If we have, for intance,
  14
  15     let true = (\x (\y x)) in
  16     let false = (\x (\y y)) in
  17     ((true yes) no)
  18
  19 the result is `yes`.
  20
  21 *Comments*: anything following a semicolon to the end of the line is ignored.
  22 Blank lines are fine.
  23
  24 *Abbreviations*: In an earlier version, you couldn't use abbreviations. `\x y. y x x` had to be written `(\x (\y ((y x) x)))`. We've upgraded the parser though, so now it should be able to understand any lambda term that you can.
  25
  26 *Constants*: `true` and `false` are pre-defined to their standard values. So too are the combinators `S`, `K`, `I`, `C`, `B`, `W`, and `T`. Finally, integers will automatically be converted to Church numerals. (`0` is `\s z. z`, `1` is `\s z. s z`, and so on.)
  27
  28
  29
  30 <textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
  31 let true = \x y. x in
  32 let false = \x y. y in
  33 let and = \l r. l r false in
  34 (
  35         (and true true yes no)
  36         (and true false yes no)
  37         (and false true yes no)
  38         (and false false yes no)
  39 )
  40 </textarea>
  41 <input id="PARSE" value="Normalize" type="button">
  42 <noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
  43 <script language=JavaScript src="code/tokens.js"></script>
  44 <script language=JavaScript src="code/parse.js"></script>
  45 <script language=JavaScript src="code/lambda.js"></script>
  46 <script language=JavaScript src="code/json2.js"></script>
  47 <pre id="OUTPUT">
  48 </pre>
  49 <script>
  50 /*jslint evil: true */
  51
  52 /*members create, error, message, name, prototype, stringify, toSource,
  53     toString, write
  54 */
  55
  56 /*global JSON, make_parse, parse, source, tree */
  57
  58 // Make a new object that inherits members from an existing object.
  59
  60 if (typeof Object.create !== 'function') {
  61     Object.create = function (o) {
  62         function F() {}
  63         F.prototype = o;
  64         return new F();
  65     };
  66 }
  67
  68 // Transform a token object into an exception object and throw it.
  69
  70 Object.prototype.error = function (message, t) {
  71     t = t || this;
  72     t.name = "SyntaxError";
  73     t.message = message;
  74     throw t;
  75 };
  76
  77
  78 (function () {
  79     var parse = make_parse();
  80
  81     function go(source) {
  82         var string, tree;
  83         try {
  84             tree = parse(source);
  85 //             string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
  86 //             string = JSON.stringify(tree.handler(), ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
  87                         string = tree.handler().to_string();
  88         } catch (e) {
  89             string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
  90                     'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
  91         }
  92         document.getElementById('OUTPUT').innerHTML = string
  93             .replace(/&/g, '&amp;')
  94             .replace(/[<]/g, '&lt;');
  95     }
  96
  97     document.getElementById('PARSE').onclick = function (e) {
  98         go(document.getElementById('INPUT').value);
  99     };
 100 }());
 101
 102 </script>
 103
 104
 105
 106 Under the hood
 107 ---------------
 108
 109 The interpreter is written in JavaScript (which is not closely related to Java), and runs inside your browser.
 110 So if you decide to reduce a term that does not terminate (such as `((\x (x x)) (\x (x x)))`), it will be your
 111 browser that stops responding, not the wiki server.
 112
 113 The main code is [here](http://lambda.jimpryor.net/code/lambda.js). Suggestions for improvements welcome.
 114
 115 The code is based on:
 116
 117 *       Chris Barker's JavaScript lambda calculator
 118 *       [Oleg Kiselyov's Haskell lambda calculator](http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell).
 119 *       The top-down JavaScript lexer and parser at <http://javascript.crockford.com/tdop/index.html>.
 120
 121 Improvements we hope to add soon: the ability to reduce Combinatory Logic combinators and report the result as combinators, rather than in lambda forms.
 122
 123 For these assignments, you'll probably want to use a "lambda calculator" to check your work. This accepts any grammatical lambda expression and reduces it to normal form, when possible. See our [lambda-let page](/lambda-let.html),
 124