typo in untyped_evaluator
[lambda.git] / code / parse.js
index fe079dc..9712809 100644 (file)
@@ -1,8 +1,20 @@
 // Parser for lambda with let written in Simplified JavaScript
 // Parser for lambda with let written in Simplified JavaScript
-//             by Jim Pryor 2010-09-22
-//             Stripped down from Top Down Operator Precedence : parse.js
-//             http://javascript.crockford.com/tdop/index.html
-//             Douglas Crockford 2010-06-26
+//      by Jim Pryor 2010-09-22
+//      Stripped down from Top Down Operator Precedence : parse.js
+//      http://javascript.crockford.com/tdop/index.html
+//      Douglas Crockford 2010-06-26
+
+//      See also http://effbot.org/zone/simple-top-down-parsing.htm
+
+
+/*jslint onevar: false
+ */
+
+/*   members create, error, message, name, prototype, stringify, toSource,
+    toString, write
+*/
+
+/*global make_var, make_app, make_lam, Lambda_var */
 
 var make_parse = function () {
     var symbol_table = {};
 
 var make_parse = function () {
     var symbol_table = {};
@@ -24,21 +36,21 @@ var make_parse = function () {
         v = t.value;
         a = t.type;
         if (a === "name") {
         v = t.value;
         a = t.type;
         if (a === "name") {
-                       o = symbol_table[v];
-                       if (o && typeof o !== 'function' ) {
-                               a = "keyword";
-                       } else {
-                               o = symbol_table["(name)"];
-                       }
+            o = symbol_table[v];
+            if (!o || typeof o === 'function') {
+                o = symbol_table["(name)"];
+            } else {
+                a = o.arity || "keyword";
+            }
         } else if (a ===  "number") {
         } else if (a ===  "number") {
-            o = symbol_table["(literal)"];
-            a = "literal";
+            o = symbol_table["(number)"];
+                       a = "literal";
         } else if (a === "operator") {
             o = symbol_table[v];
             if (!o) {
                 t.error("Unknown operator.");
             }
         } else if (a === "operator") {
             o = symbol_table[v];
             if (!o) {
                 t.error("Unknown operator.");
             }
-                       a = "keyword";
+            a = "keyword";
         } else {
             t.error("Unexpected token.");
         }
         } else {
             t.error("Unexpected token.");
         }
@@ -53,9 +65,19 @@ var make_parse = function () {
     var original_symbol = {
         handler: function () {
             this.error("Undefined.");
     var original_symbol = {
         handler: function () {
             this.error("Undefined.");
-        },
+        }
     };
 
     };
 
+       /*
+       try {
+               if (console && console.debug) {
+                       function print() {
+                               console.debug.apply(this, arguments);
+                       }
+               }
+       } catch (e) {}
+       */
+
     var symbol = function (id) {
         var s = symbol_table[id];
         if (!s) {
     var symbol = function (id) {
         var s = symbol_table[id];
         if (!s) {
@@ -66,185 +88,261 @@ var make_parse = function () {
         return s;
     };
 
         return s;
     };
 
+    var var_table;
+    var name_table;
 
 
-//     try {
-//         if (console && console.debug) {
-//             function print() {
-//                 console.debug.apply(this, arguments);
-//             }
-//         }
-//     } catch (e) {}
+    var name_handler = function () {
+        var n = name_table[this.value];
+        if (!n) {
+            n = make_var(this.value);
+            var_table[this.value] = n;
+            n = new Lambda_var(n);
+            name_table[this.value] = n;
+        }
+        if (this.first) {
+            return make_app(this.first.handler(), n);
+        } else {
+            return n;
+        }
+    };
 
 
+    var branch_handler = function () {
+        var n = this.second.handler();
+        if (this.first) {
+            return make_app(this.first.handler(), n);
+        } else {
+            return n;
+        }
+    };
 
 
-    var itself = function () {
-        return this;
+    var lambda_handler = function () {
+        var body = this.second.handler();
+        var n, v;
+        while (this.first.length) {
+            n = this.first.pop().value;
+            v = var_table[n];
+            if (!v) {
+                v = make_var(n);
+                var_table[n] = v;
+                name_table[n] = new Lambda_var(v);
+            }
+            body = make_lam(v, body);
+        }
+        return body;
     };
 
     };
 
-       var var_table = {};
-       var name_table = {};
+    symbol("(end)");
+    symbol("(name)").handler = name_handler;
+    symbol("let").handler = lambda_handler;
+    symbol("=").handler = branch_handler;
+    symbol("in");
+    symbol(")").handler = branch_handler;
+    symbol("(");
+    symbol("\\").handler = lambda_handler;
+    symbol("lambda").handler = lambda_handler;
+    symbol("\u03bb").handler = lambda_handler;
+    // symbol("\u2203").handler = exists_handler;
+    // symbol("\u2200").handler = forall_handler;
+    symbol(".");
+
+       function make_constants() {
 
 
-       var name_handler = function () {
-               var n = name_table[this.value];
-               if (!n) {
-                       n = make_var(this.value);
-                       var_table[this.value] = n;
-                       n = new Lambda_var(n);
-                       name_table[this.value] = n;
+               function make_lam2(a, b, aa) {
+                       return make_lam(a, make_lam(b, aa));
                }
                }
-               if (this.first) {
-                       return make_app(this.first.handler(), n);
-               } else {
-                       return n;
+               function make_lam3(a, b, c, aa) {
+                       return make_lam(a, make_lam(b, make_lam(c, aa)));
                }
                }
-       };
-
-       var branch_handler = function () {
-               var n = this.second.handler();
-               if (this.first) {
-                       return make_app(this.first.handler(), n);
-               } else {
-                       return n;
+               function make_app3(aa, bb, cc) {
+                       return make_app(make_app(aa, bb), cc);
                }
                }
-       };
+               var u = make_var("u");
+               var v = make_var("v");
+               var x = make_var("x");
+               var s = make_var("s");
+               var z = make_var("z");
+               var uu = new Lambda_var(u);
+               var vv = new Lambda_var(v);
+               var xx = new Lambda_var(x);
+               var ss = new Lambda_var(s);
+               var zz = new Lambda_var(z);
+               var_table = { u: u, v: v, x: x, s: s, z: z};
+               name_table = {u: uu, v: vv, x: xx, s: ss, z: zz};
+               number_table = {};
 
 
-       var lambda_handler = function () {
-               var body = this.second.handler();
-               var n, v;
-               while (this.first.length) {
-                       n = this.first.pop().value;
-                       v = var_table[n];
-                       if (!v) {
-                               v = make_var(n);
-                               var_table[n] = v;
-                               name_table[n] = new Lambda_var(v);
+               // constants have their own id and arity = literal
+               // numbers have id = "(number)" and arity = literal
+               symbol("(number)").handler = function () {
+                       var n = this.value;
+                       var res = number_table[n];
+                       if (!res) {
+                               res = zz;
+                               while (n > 0) {
+                                       n -= 1;
+                                       res = make_app(ss, res);
+                               }
+                               res = make_lam2(s, z, res);
+                               number_table[this.value] = res;
+                       }
+                       if (this.first) {
+                               return make_app(this.first.handler(), res);
+                       } else {
+                               return res;
                        }
                        }
-                       body = make_lam(v, body);
                }
                }
-               return body;
-       };
 
 
-    symbol("(end)");
-       symbol("(name)").handler = name_handler;
-    symbol("(literal)").handler = itself;
-       symbol("let").handler = lambda_handler;
-       symbol("=").handler = branch_handler;
-       symbol("in");
-       symbol(")").handler = branch_handler;
-       symbol("(");
-       symbol("\\").handler = lambda_handler;
-       symbol("lambda").handler = lambda_handler;
-       symbol(".");
-
-       var expression = function (in_let) {
-               var t, n;
-               if (token.id === "\\" || token.id === "lambda") {
-                       token.value = "lambda";
-                       t = token;
-                       advance();
-                       n = token;
-                       if (n.arity !== "name") {
-                               n.error("Expected a variable name.");
-                       }
-                       advance();
-                       if (token.id === "(") {
-                               t.first = [n];
-                               advance();
-                               t.second = expression(false);
-                               advance(")");
-                               return t;
-                       } else {
-                               t.first = [];
-                               while (token.arity === "name") {
-                                       t.first.push(n);
-                                       n = token;
-                                       advance();
-                               }
-                               if (token.id === ".") {
-                                       t.first.push(n);
-                                       advance();
-                                       t.second = expression(in_let);
-                               } else if (t.first.length === 1) {
-                                       t.second = n;
+               var constant = function (s, v) {
+                       var x = symbol(s);
+                       x.handler = function () {
+                               this.value = symbol_table[this.id].value;
+                               if (this.first) {
+                                       return make_app(this.first.handler(), this.value);
                                } else {
                                } else {
-                                       t.first.push(n);
-                                       t.error("Can't parse lambda abstract.");
+                                       return this.value;
                                }
                                }
-                               return t;
                        };
                        };
-               } else {
-                       n = null;
-                       while (token.id === "(") {
-                               advance();
-                               t = expression(false);
-                               token.first = n;
-                               token.second = t;
-                               n = token;
-                               advance(")");
-                               if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
-                                       return n;
-                               }
-                       }
-                       if (token.arity != "name") {
-                               token.error("Expected a variable name.");
-                       }
-                       token.first = n;
-                       n = token;
-                       advance();
-                       while (true) {
-                               if (in_let && token.id === "in" || token.id === "(end)" || token.id === ")") {
-                                       return n;
-                               } else if (token.id === "(") {
-                                       advance();
-                                       t = expression(false);
-                                       token.first = n;
-                                       token.second = t;
-                                       n = token;
-                                       advance(")");
-                               } else {
-                                       if (token.arity != "name") {
-                                               token.error("Expected a variable name.");
-                                       }
-                                       token.first = n;
-                                       n = token;
-                                       advance();
-                               }
-                       }
-               }
+                       x.arity = "literal";
+                       x.value = v;
+                       return x;
+               };
+
+               constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
+               constant("K", make_lam2(u, v, uu));
+               constant("I", make_lam(x, xx));
+               constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
+               constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
+
+               // trush \uv.vu = CI = box
+               constant("T", make_lam2(u, v, make_app(vv, uu)));
+               // vireo \uvw.wuv = pair
+               constant("V", make_lam3(u, v, x, make_app3(xx, uu, vv)));
+               // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I
+               constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
+               // mockingbird \u.uu = SII = omega
+               constant("M", make_lam(u, make_app(uu, uu)));
+               // lark \uv.u(vv) = CBM = BWB
+               constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv))));
+               // Y is SLL
+
        }
        }
+       make_constants();
+
+    var expression = function (in_let) {
+        var t, n;
+        if (token.id === "\\" || token.id === "lambda") {
+            token.value = "lambda";
+            t = token;
+            advance();
+            n = token;
+            if (n.arity !== "name") {
+                n.error("Expected a variable name.");
+            }
+            advance();
+            if (token.id === "(") {
+                t.first = [n];
+                advance();
+                t.second = expression(false);
+                advance(")");
+                return t;
+            } else {
+                t.first = [];
+                while (token.arity === "name" || token.id === "\\") {
+                   if (token.id !== "\\") {
+                      t.first.push(n);
+                      n = token;
+                   }
+                    advance();
+                }
+                               if (token.arity === "literal" && t.first.length === 0) {
+                                       t.first.push(n);
+                                       t.second = token;
+                                       advance();
+                               } else if (token.id === ".") {
+                    t.first.push(n);
+                    advance();
+                    t.second = expression(in_let);
+                } else if (t.first.length === 1) {
+                    t.second = n;
+                } else {
+                    t.first.push(n);
+                    t.error("Can't parse lambda abstract.");
+                }
+                return t;
+            }
+        } else {
+            n = null;
+            while (token.id === "(") {
+                advance();
+                t = expression(false);
+                token.first = n;
+                token.second = t;
+                n = token;
+                advance(")");
+                if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
+                    return n;
+                }
+            }
+            while (true) {
+                               if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
+                    return n;
+                } else if (token.id === "(") {
+                    advance();
+                    t = expression(false);
+                    token.first = n;
+                    token.second = t;
+                    n = token;
+                    advance(")");
+                } else {
+                    if (token.arity !== "name" && token.arity !== "literal") {
+                        token.error("Expected a variable name or literal.");
+                    }
+                    token.first = n;
+                    n = token;
+                    advance();
+                }
+            }
+        }
+       };
 
     return function (source) {
 
     return function (source) {
-               tokens = source.tokens();
+        tokens = source.tokens();
         token_nr = 0;
         advance();
         token_nr = 0;
         advance();
-               
-               // let n = c in b
-               // (\n. b) c
-
-               var t = null, eq, c, base = {};
-               var target = base;
-
-               while (token.id == "let") {
-                       t = token;
-                       advance();
-                       if (token.arity !== "name") {
-                               token.error("Expected a variable name.");
-                       }
-                       t.first = [token];
-                       advance();
-                       eq = token; // token.id === "="
-                       advance("=");
-                       c = expression(true);
-                       c.first = eq;
-                       eq.second = t;
-                       target.second = c;
-                       target = t;
-                       advance("in");
-               }
-       
-               target.second = expression(false);
+
+        // let n = c in b
+        // (\n. b) c
+
+        var t = null, eq, c, base = {};
+        var target = base;
+
+        while (token.id === "let") {
+            t = token;
+            advance();
+            if (token.arity !== "name") {
+                token.error("Expected a variable name.");
+            }
+            t.first = [token];
+            advance();
+            eq = token; // token.id === "="
+            advance("=");
+            c = expression(true);
+
+                       eq.first = t;
+                       eq.second = c;
+                       target.second = eq;
+
+//             c.first = eq;
+//             eq.second = t;
+//             target.second = c;
+
+            target = t;
+            advance("in");
+        }
+
+        target.second = expression(false);
 
         advance("(end)");
 
         advance("(end)");
-               return base.second;
+        return base.second;
     };
 
 };
     };
 
 };