1 This lambda evaluator will allow you to write lambda terms and evaluate (that is, normalize) them, and inspect the results.
2 (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.)
4 *Lambda terms*: lambda terms are written with a backslash, thus: `((\x (\y x)) z)`.
6 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)`.
8 *Let*: in order to make building a more elaborate set of terms easier, it is possible to define values using `let`.
9 In this toy system, `let`s should only be used at the beginning of a file.  If we have, for intance,
11     let true = (\x (\y x)) in
12     let false = (\x (\y y)) in
13     ((true yes) no)
15 the result is `yes`.
17 *Comments*: anything following a semicolon to the end of the line is ignored.
18 Blank lines are fine.
20 *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.
22 *Constants*: The combinators `S`, `K`, `I`, `C`, `B`, `W`, `T`, `M` (aka <code>&omega;</code>) and `L` are pre-defined to their standard values. Also, integers will automatically be converted to Church numerals. (`0` is `\s z. z`, `1` is `\s z. s z`, and so on.)
24 *Variables*: Variables must start with a letter and can continue with any sequence of letters, numbers, `_`, `-`, or `/`. They may optionally end with `?` or `!`. When the evaluator does alpha-conversion, it may change `x` into `x'` or `x''` and so on. But you should not attempt to use primed variable names yourself.
27 <textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
28 let true = \x y. x in
29 let false = \x y. y in
30 let and = \l r. l r false in
31 (
32         (and true true yes no)
33         (and true false yes no)
34         (and false true yes no)
35         (and false false yes no)
36 )
37 </textarea>
38 <input id="PARSE" value="Normalize" type="button">
39 <input id="ETA" type="checkbox">do eta-reductions too
40 <noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
41 <script src="/code/lambda.js"></script>
42 <script src="/code/tokens.js"></script>
43 <script src="/code/parse.js"></script>
44 <script src="/code/json2.js"></script>
45 <pre id="OUTPUT">
46 </pre>
47 <script>
48 /*jslint evil: true */
50 /*members create, error, message, name, prototype, stringify, toSource,
51     toString, write
52 */
54 /*global JSON, make_parse, parse, source, tree */
56 // Make a new object that inherits members from an existing object.
58 if (typeof Object.create !== 'function') {
59     Object.create = function (o) {
60         function F() {}
61         F.prototype = o;
62         return new F();
63     };
64 }
66 // Transform a token object into an exception object and throw it.
68 Object.prototype.error = function (message, t) {
69     t = t || this;
70     t.name = "SyntaxError";
71     t.message = message;
72     throw t;
73 };
76 (function () {
77     var parse = make_parse();
79     function go(source) {
80         var string, tree, expr, eta;
81         try {
82             tree = parse(source);
83  //           string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
84                         expr = tree.handler();
85             // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
86 //                      string = expr.to_string() + "\n\n~~>\n\n";
87                         string = '';
88                         eta = document.getElementById('ETA').checked;
89                         string = string + reduce(expr, eta, false).to_string();
90         } catch (e) {
91             string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
92                     'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
93         }
94         document.getElementById('OUTPUT').innerHTML = string
95             .replace(/&/g, '&amp;')
96             .replace(/[<]/g, '&lt;');
97     }
99     document.getElementById('PARSE').onclick = function (e) {
100         go(document.getElementById('INPUT').value);
101     };
102 }());
104 </script>
108 Under the hood
109 ---------------
111 The interpreter is written in JavaScript and runs inside your browser.
112 So if you decide to reduce a term that does not terminate (such as `((\x (x x)) (\x (x x)))`), it will be your
113 browser that stops responding, not the wiki server.
115 The main code is [here](http://lambda.jimpryor.net/code/lambda.js). Suggestions for improvements welcome.
117 The code is based on:
119 *       Chris Barker's JavaScript lambda calculator