fix link
[lambda.git] / code / parse.js
1 // Parser for lambda with let written in Simplified JavaScript
2 //      by Jim Pryor 2010-09-22
3 //      Stripped down from Top Down Operator Precedence : parse.js
4 //      http://javascript.crockford.com/tdop/index.html
5 //      Douglas Crockford 2010-06-26
6
7 //      See also http://effbot.org/zone/simple-top-down-parsing.htm
8
9
10 /*jslint onevar: false
11  */
12
13 /*   members create, error, message, name, prototype, stringify, toSource,
14     toString, write
15 */
16
17 /*global make_var, make_app, make_lam, Lambda_var */
18
19 var make_parse = function () {
20     var symbol_table = {};
21     var token;
22     var tokens;
23     var token_nr;
24
25     var advance = function (id) {
26         var a, o, t, v;
27         if (id && token.id !== id) {
28             token.error("Expected '" + id + "'.");
29         }
30         if (token_nr >= tokens.length) {
31             token = symbol_table["(end)"];
32             return;
33         }
34         t = tokens[token_nr];
35         token_nr += 1;
36         v = t.value;
37         a = t.type;
38         if (a === "name") {
39             o = symbol_table[v];
40             if (!o || typeof o === 'function') {
41                 o = symbol_table["(name)"];
42             } else {
43                 a = o.arity || "keyword";
44             }
45         } else if (a ===  "number") {
46             o = symbol_table["(number)"];
47                         a = "literal";
48         } else if (a === "operator") {
49             o = symbol_table[v];
50             if (!o) {
51                 t.error("Unknown operator.");
52             }
53             a = "keyword";
54         } else {
55             t.error("Unexpected token.");
56         }
57         token = Object.create(o);
58         token.from  = t.from;
59         token.to    = t.to;
60         token.value = v;
61         token.arity = a; // will be: name, keyword, literal
62         return token;
63     };
64
65     var original_symbol = {
66         handler: function () {
67             this.error("Undefined.");
68         }
69     };
70
71         /*
72         try {
73                 if (console && console.debug) {
74                         function print() {
75                                 console.debug.apply(this, arguments);
76                         }
77                 }
78         } catch (e) {}
79         */
80
81     var symbol = function (id) {
82         var s = symbol_table[id];
83         if (!s) {
84             s = Object.create(original_symbol);
85             s.id = s.value = id;
86             symbol_table[id] = s;
87         }
88         return s;
89     };
90
91     var var_table;
92     var name_table;
93
94     var name_handler = function () {
95         var n = name_table[this.value];
96         if (!n) {
97             n = make_var(this.value);
98             var_table[this.value] = n;
99             n = new Lambda_var(n);
100             name_table[this.value] = n;
101         }
102         if (this.first) {
103             return make_app(this.first.handler(), n);
104         } else {
105             return n;
106         }
107     };
108
109     var branch_handler = function () {
110         var n = this.second.handler();
111         if (this.first) {
112             return make_app(this.first.handler(), n);
113         } else {
114             return n;
115         }
116     };
117
118     var lambda_handler = function () {
119         var body = this.second.handler();
120         var n, v;
121         while (this.first.length) {
122             n = this.first.pop().value;
123             v = var_table[n];
124             if (!v) {
125                 v = make_var(n);
126                 var_table[n] = v;
127                 name_table[n] = new Lambda_var(v);
128             }
129             body = make_lam(v, body);
130         }
131         return body;
132     };
133
134     symbol("(end)");
135     symbol("(name)").handler = name_handler;
136     symbol("let").handler = lambda_handler;
137     symbol("=").handler = branch_handler;
138     symbol("in");
139     symbol(")").handler = branch_handler;
140     symbol("(");
141     symbol("\\").handler = lambda_handler;
142     symbol("lambda").handler = lambda_handler;
143     symbol("\u03bb").handler = lambda_handler;
144     // symbol("\u2203").handler = exists_handler;
145     // symbol("\u2200").handler = forall_handler;
146     symbol(".");
147
148         function make_constants() {
149
150                 function make_lam2(a, b, aa) {
151                         return make_lam(a, make_lam(b, aa));
152                 }
153                 function make_lam3(a, b, c, aa) {
154                         return make_lam(a, make_lam(b, make_lam(c, aa)));
155                 }
156                 function make_app3(aa, bb, cc) {
157                         return make_app(make_app(aa, bb), cc);
158                 }
159                 var u = make_var("u");
160                 var v = make_var("v");
161                 var x = make_var("x");
162                 var s = make_var("s");
163                 var z = make_var("z");
164                 var uu = new Lambda_var(u);
165                 var vv = new Lambda_var(v);
166                 var xx = new Lambda_var(x);
167                 var ss = new Lambda_var(s);
168                 var zz = new Lambda_var(z);
169                 var_table = { u: u, v: v, x: x, s: s, z: z};
170                 name_table = {u: uu, v: vv, x: xx, s: ss, z: zz};
171                 number_table = {};
172
173                 // constants have their own id and arity = literal
174                 // numbers have id = "(number)" and arity = literal
175                 symbol("(number)").handler = function () {
176                         var n = this.value;
177                         var res = number_table[n];
178                         if (!res) {
179                                 res = zz;
180                                 while (n > 0) {
181                                         n -= 1;
182                                         res = make_app(ss, res);
183                                 }
184                                 res = make_lam2(s, z, res);
185                                 number_table[this.value] = res;
186                         }
187                         if (this.first) {
188                                 return make_app(this.first.handler(), res);
189                         } else {
190                                 return res;
191                         }
192                 }
193
194                 var constant = function (s, v) {
195                         var x = symbol(s);
196                         x.handler = function () {
197                                 this.value = symbol_table[this.id].value;
198                                 if (this.first) {
199                                         return make_app(this.first.handler(), this.value);
200                                 } else {
201                                         return this.value;
202                                 }
203                         };
204                         x.arity = "literal";
205                         x.value = v;
206                         return x;
207                 };
208
209                 constant("S", make_lam3(u, v, x, make_app3(uu, xx, make_app(vv, xx))));
210                 constant("K", make_lam2(u, v, uu));
211                 constant("I", make_lam(x, xx));
212                 constant("B", make_lam3(u, v, x, make_app(uu, make_app(vv, xx))));
213                 constant("C", make_lam3(u, v, x, make_app3(uu, xx, vv)));
214
215                 // trush \uv.vu = CI = box
216                 constant("T", make_lam2(u, v, make_app(vv, uu)));
217                 // vireo \uvw.wuv = pair
218                 constant("V", make_lam3(u, v, x, make_app3(xx, uu, vv)));
219                 // warbler \uv.uvv = C(BM(BBT) = C(BS(C(BBI)I))I
220                 constant("W", make_lam2(u, v, make_app3(uu, vv, vv)));
221                 // mockingbird \u.uu = SII = omega
222                 constant("M", make_lam(u, make_app(uu, uu)));
223                 // lark \uv.u(vv) = CBM = BWB
224                 constant("L", make_lam2(u, v, make_app(uu, make_app(vv, vv))));
225                 // Y is SLL
226
227         }
228         make_constants();
229
230     var expression = function (in_let) {
231         var t, n;
232         if (token.id === "\\" || token.id === "lambda") {
233             token.value = "lambda";
234             t = token;
235             advance();
236             n = token;
237             if (n.arity !== "name") {
238                 n.error("Expected a variable name.");
239             }
240             advance();
241             if (token.id === "(") {
242                 t.first = [n];
243                 advance();
244                 t.second = expression(false);
245                 advance(")");
246                 return t;
247             } else {
248                 t.first = [];
249                 while (token.arity === "name" || token.id === "\\") {
250                     if (token.id !== "\\") {
251                       t.first.push(n);
252                       n = token;
253                     }
254                     advance();
255                 }
256                                 if (token.arity === "literal" && t.first.length === 0) {
257                                         t.first.push(n);
258                                         t.second = token;
259                                         advance();
260                                 } else if (token.id === ".") {
261                     t.first.push(n);
262                     advance();
263                     t.second = expression(in_let);
264                 } else if (t.first.length === 1) {
265                     t.second = n;
266                 } else {
267                     t.first.push(n);
268                     t.error("Can't parse lambda abstract.");
269                 }
270                 return t;
271             }
272         } else {
273             n = null;
274             while (token.id === "(") {
275                 advance();
276                 t = expression(false);
277                 token.first = n;
278                 token.second = t;
279                 n = token;
280                 advance(")");
281                 if (in_let && token.id === "let" || token.id === "(end)" || token.id === ")") {
282                     return n;
283                 }
284             }
285             while (true) {
286                                 if (n && (in_let && token.id === "in" || token.id === "(end)" || token.id === ")")) {
287                     return n;
288                 } else if (token.id === "(") {
289                     advance();
290                     t = expression(false);
291                     token.first = n;
292                     token.second = t;
293                     n = token;
294                     advance(")");
295                 } else {
296                     if (token.arity !== "name" && token.arity !== "literal") {
297                         token.error("Expected a variable name or literal.");
298                     }
299                     token.first = n;
300                     n = token;
301                     advance();
302                 }
303             }
304         }
305         };
306
307     return function (source) {
308         tokens = source.tokens();
309         token_nr = 0;
310         advance();
311
312         // let n = c in b
313         // (\n. b) c
314
315         var t = null, eq, c, base = {};
316         var target = base;
317
318         while (token.id === "let") {
319             t = token;
320             advance();
321             if (token.arity !== "name") {
322                 token.error("Expected a variable name.");
323             }
324             t.first = [token];
325             advance();
326             eq = token; // token.id === "="
327             advance("=");
328             c = expression(true);
329
330                         eq.first = t;
331                         eq.second = c;
332                         target.second = eq;
333
334 //             c.first = eq;
335 //             eq.second = t;
336 //             target.second = c;
337
338             target = t;
339             advance("in");
340         }
341
342         target.second = expression(false);
343
344         advance("(end)");
345         return base.second;
346     };
347
348 };
349