X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=code%2Flambda_evaluator.mdwn;fp=code%2Flambda_evaluator.mdwn;h=d39086fd257131bb012c1fa5f71191c387c23927;hp=0000000000000000000000000000000000000000;hb=50102e40c57ebd7aef267b201292646587766573;hpb=8d7045981a2a3c5f12fecd1608598bfdd9d678a4

diff --git a/code/lambda_evaluator.mdwn b/code/lambda_evaluator.mdwn
new file mode 100644
index 00000000..d39086fd
--- /dev/null
+++ b/code/lambda_evaluator.mdwn
@@ -0,0 +1,144 @@
+This lambda evaluator will allow you to write lambda terms and evaluate (that is, normalize) them, and inspect the results.
+(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.)  
+
+*Lambda terms*: lambda terms are written with a backslash, thus: `((\x (\y x)) z)`.  
+
+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)`.
+
+*Let*: in order to make building a more elaborate set of terms easier, it is possible to define values using `let`.
+In this toy system, `let`s should only be used at the beginning of a file.  If we have, for intance,
+
+    let true = (\x (\y x)) in
+    let false = (\x (\y y)) in
+    ((true yes) no)
+
+the result is `yes`.
+
+*Comments*: anything following a semicolon to the end of the line is ignored.
+Blank lines are fine.
+
+*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.
+
+*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.)
+
+*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.
+
+
+<textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
+let true = \x y. x in
+let false = \x y. y in
+let and = \l r. l r false in
+(
+	(and true true yes no)
+	(and true false yes no)
+	(and false true yes no)
+	(and false false yes no)
+)
+</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">
+</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>
+
+
+
+Under the hood
+---------------
+
+The interpreter is written in JavaScript and runs inside your browser.
+So if you decide to reduce a term that does not terminate (such as `((\x (x x)) (\x (x x)))`), it will be your 
+browser that stops responding, not the wiki server.
+
+The main code is [here](http://lambda.jimpryor.net/code/lambda.js). Suggestions for improvements welcome.
+
+The code is based on: 
+
+*	Chris Barker's JavaScript lambda calculator
+*	[Oleg Kiselyov's Haskell lambda calculator](http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell).
+*	The top-down JavaScript lexer and parser at <http://javascript.crockford.com/tdop/index.html>.
+
+Improvements we hope to add:
+
+*	detecting some common cases of non-normalizing terms (the problem of determining in general whether a term will normalize is undecidable)
+*	returning results in combinator form (the evaluator already accepts combinators as input)
+*	displaying reductions one step at a time
+*	specifying the reduction order and depth
+*	allow other binders such as &forall; and &exist; (though these won't be interpreted as doing anything other than binding variables)
+
+<a name="other_evaluators"></a>
+Other Lambda Evaluators/Calculutors
+-----------------------------------
+
+*	[Peter Sestoft's Lambda Calculus Reducer](http://www.itu.dk/people/sestoft/lamreduce/index.html): Very nice! Allows you to select different evaluation strategies, and shows stepwise reductions.
+*	[Chris Barker's Lambda Tutorial](http://homepages.nyu.edu/~cb125/Lambda)
+*	[Penn Lambda Calculator](http://www.ling.upenn.edu/lambda/): Pedagogical software developed by Lucas Champollion, Josh Tauberer and Maribel Romero.  Linguistically oriented. Requires installing Java (Mac users will probably already have it installed).
+*	[Mike Thyer's Lambda Animator](http://thyer.name/lambda-animator/): Graphical tool for experimenting with different reduction strategies. Also requires installing Java, and Graphviz.
+*	[Matt Might's Lambda Evaluator](http://matt.might.net/articles/implementing-a-programming-language/) in Scheme (R5RS and Racket).
+
+See also:
+
+*	[Jason Jorendorff's Try Scheme](http://tryscheme.sourceforge.net/about.html): Runs a miniature Scheme interpreter in Javascript, in your browser.
+