1 /*jslint bitwise: true,
23 // substitution and translation algorithms from Chris Hankin, An Introduction to Lambda Calculi for Comptuer Scientists
25 function Db_free(variable) {
26 this.variable = variable;
27 this.subst = function (m, new_term) {
30 this.renumber = function (m, i) {
33 // we assume that other will have variable iff it's a Db_free
34 this.equal = function (other) {
35 return other.variable && this.variable.equal(other.variable);
37 this.contains = this.equal;
40 function Db_index(i) {
42 this.subst = function (m, new_term) {
45 } else if (this.index > m) {
46 return new Db_index(this.index - 1);
48 return new_term.renumber(this.index, 1);
51 this.renumber = function (m, i) {
55 return new Db_index(this.index + m - 1);
58 // we assume that other will have index iff it's a Db_index
59 this.equal = function (other) {
60 return this.index === other.index;
62 this.contains = this.equal;
65 function Db_app(left, right) {
68 this.subst = function (m, new_term) {
69 return new Db_app(this.left.subst(m, new_term), this.right.subst(m, new_term));
71 this.renumber = function (m, i) {
72 return new Db_app(this.left.renumber(m, i), this.right.renumber(m, i));
74 // we assume that other will have left iff it's a Db_app
75 this.equal = function (other) {
76 return other.left && this.left.equal(other.left) && this.right.equal(other.right);
78 this.contains = function (other) {
79 if (other.left && this.left.equal(other.left) && this.right.equal(other.right)) {
82 return this.left.contains(other) || this.right.contains(other);
87 function Db_lam(body) {
89 this.subst = function (m, new_term) {
90 return new Db_lam(this.body.subst(m + 1, new_term));
92 this.renumber = function (m, i) {
93 return new Db_lam(this.body.renumber(m, i + 1));
95 // we assume that other will have body iff it's a Db_lam
96 this.equal = function (other) {
97 return other.body && this.body.equal(other.body);
99 this.contains = function (other) {
100 if (other.body && this.body.equal(other.body)) {
103 return this.body.contains(other);
110 // substitution and normal-order evaluator based on Haskell version by Oleg Kisleyov
111 // http://okmij.org/ftp/Computation/lambda-calc.html#lambda-calculator-haskell
113 function Variable(name, tag) {
116 this.to_string = function () {
117 // append count copies of str to accum
118 // function markup(accum, count) {
119 // if (count === 0) {
122 // return markup(accum + "'", count - 1);
125 // return markup(this.name, this.tag);
127 for (var count = 0; count < this.tag; count += 1) {
132 this.equal = function (other) {
133 return (this.tag === other.tag) && (this.name === other.name);
135 // position of this in seq
136 this.position = function (seq) {
137 for (var i = 0; i < seq.length; i += 1) {
138 if (this.equal(seq[i])) {
139 return new Db_index(i + 1);
142 return new Db_free(this);
146 // if v occurs free_in term, returns Some v' where v' is the highest-tagged
147 // variable with the same name as v occurring (free or bound) in term
149 function free_in(v, term) {
150 var res = term.has_free(v);
151 return res[0] && res[1];
154 function subst(v, new_term, expr) {
155 if (new_term.variable && new_term.variable.equal(v)) {
158 return expr.subst(v, new_term);
162 function equal(expr1, expr2) {
163 return expr1.debruijn([]).equal(expr2.debruijn([]));
166 function contains(expr1, expr2) {
167 return expr1.debruijn([]).contains(expr2.debruijn([]));
171 function Lambda_var(variable) {
172 this.variable = variable;
173 this.debruijn = function (seq) {
174 return this.variable.position(seq);
176 this.to_string = function (as_atom) {
177 return this.variable.to_string();
179 this.has_free = function (v) {
180 if (v.name !== this.variable.name) {
182 } else if (v.tag === this.variable.tag) {
185 return [false, this.variable];
188 this.subst = function (v, new_term) {
189 if (this.variable.equal(v)) {
195 this.check_eta = function () {
198 this.eval_loop = function (stack, eta) {
199 function unwind(left, stack) {
200 // if (stack.length === 0) {
204 // var xs = stack.slice(1);
205 // return unwind(new Lambda_app(left, x.eval_loop([], eta)), xs);
208 while (stack.length) {
210 // res = new Lambda_app(res, x.eval_loop([], eta));
211 res = new Lambda_app(res, reduce(x, eta, false));
215 // return unwind(this, stack);
216 // trampoline to, args
217 return [null, unwind(this, stack)];
219 this.eval_cbv = function (aggressive) {
224 function Lambda_app(left, right) {
227 this.debruijn = function (seq) {
228 return new Db_app(this.left.debruijn(seq), this.right.debruijn(seq));
230 this.to_string = function (as_atom) {
232 if (this.left.left) {
233 base = this.left.to_string() + " " + this.right.to_string(true);
235 base = this.left.to_string(true) + " " + this.right.to_string(true);
238 return "(" + base + ")";
243 this.has_free = function (v) {
244 var left_res = this.left.has_free(v);
245 var right_res = this.right.has_free(v);
246 var left_bool = left_res[0];
247 var right_bool = right_res[0];
248 var left_tag = left_res[1].tag;
249 var right_tag = right_res[1].tag;
251 if (left_tag > right_tag) {
256 return [left_bool || right_bool, res];
258 this.subst = function (v, new_term) {
259 return new Lambda_app(subst(v, new_term, this.left), subst(v, new_term, this.right));
261 this.check_eta = function () {
264 this.eval_loop = function (stack, eta) {
265 var new_stack = stack.slice(0);
266 new_stack.unshift(this.right);
267 // return this.left.eval_loop(new_stack, eta);
268 // trampoline to, args
269 return [this.left, new_stack, eta];
271 this.eval_cbv = function (aggressive) {
272 var left = this.left.eval_cbv(aggressive);
273 var right = this.right.eval_cbv(aggressive);
275 return subst(left.bound, right, left.body).eval_cbv(aggressive);
277 return new Lambda_app(left, right);
283 // (* if v occurs free_in term, returns Some v' where v' is the highest-tagged
284 // * variable with the same name as v occurring (free or bound) in term *)
287 function Lambda_lam(variable, body) {
288 this.bound = variable;
290 this.debruijn = function (seq) {
291 var new_seq = seq.slice(0);
292 new_seq.unshift(this.bound);
293 return new Db_lam(this.body.debruijn(new_seq));
295 this.to_string = function (as_atom) {
296 var base = "\\" + this.to_string_funct();
298 return "(" + base + ")";
303 this.to_string_funct = function () {
304 if (this.body.to_string_funct) {
305 return this.bound.to_string() + " " + this.body.to_string_funct();
307 return this.bound.to_string() + ". " + this.body.to_string();
310 this.has_free = function (v) {
311 if (this.bound.equal(v)) {
314 return this.body.has_free(v);
317 this.subst = function (v, new_term) {
318 function bump_tag(v1, v2) {
320 if (v1.tag > v2.tag) {
325 return new Variable(v1.name, max + 1);
327 function bump_tag2(v1, v2) {
328 if (v1.name !== v2.name) {
331 return bump_tag(v1, v2);
334 if (this.bound.equal(v)) {
337 var res = free_in(this.bound, new_term);
338 // if x is free in the inserted term new_term, a capture is possible
340 // this.bound is free in new_term, need to alpha-convert
341 var uniq_x = bump_tag2(bump_tag(this.bound, res), v);
342 var res2 = free_in(uniq_x, this.body);
344 uniq_x = bump_tag(uniq_x, res2);
346 var body2 = subst(this.bound, new Lambda_var(uniq_x), this.body);
347 return new Lambda_lam(uniq_x, subst(v, new_term, body2));
349 // this.bound not free in new_term, can substitute new_term for v without any captures
350 return new Lambda_lam(this.bound, subst(v, new_term, this.body));
354 this.check_eta = function () {
355 if (this.body.right && this.body.right.variable && this.bound.equal(this.body.right.variable) && !free_in(this.bound, this.body.left)) {
356 return this.body.left;
361 this.eval_loop = function (stack, eta) {
362 if (stack.length === 0) {
363 // var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
364 var term = new Lambda_lam(this.bound, reduce(this.body, eta, false));
366 return [null, term.check_eta()];
372 var xs = stack.slice(1);
373 // return subst(this.bound, x, this.body).eval_loop(xs, eta);
374 // trampoline to, args
375 return [subst(this.bound, x, this.body), xs, eta];
378 this.eval_cbv = function (aggressive) {
380 return new Lambda_lam(this.bound, this.body.eval_cbv(aggressive));
385 this.to_int = function (sofar) {
386 // if (this.body.body && this.body.body.variable && this.body.bound.equal(this.body.body.variable)) {
388 // } else if (this.body.variable && this.bound.equal(this.body.variable)) {
390 // } else if (this.body.body && this.body.body.left && this.body.body.left.variable && this.bound.equal(this.body.body.left.variable)) {
391 // var new_int = new Lambda_lam(this.bound, new Lambda_lam(this.body.bound, this.body.body.right));
392 // return new_int.to_int(1 + sofar);
394 // return "not a church numeral";
396 var res = 0, s = this.bound, z, cursor;
397 if (this.body.variable && s.equal(this.body.variable)) {
399 } else if (this.body.bound) {
401 cursor = this.body.body;
402 while (cursor.left && cursor.left.variable && s.equal(cursor.left.variable)) {
404 cursor = cursor.right;
406 if (cursor.variable && z.equal(cursor.variable)) {
410 return "not a church numeral";
416 ///////////////////////////////////////////////////////////////////////////////////
418 // cbv is false: use call-by-name
419 // cbv is 1: use call-by-value, don't descend inside lambda
420 // cbv is 2: applicative order
421 function reduce(expr, eta, cbv) {
423 return expr.eval_cbv(cbv > 1);
425 // return expr.eval_loop([], eta);
426 var to_eval = expr, res = [[], eta];
427 while (to_eval !== null) {
428 res = to_eval.eval_loop.apply(to_eval, res);
429 to_eval = res.shift();
435 function make_var(name) {
436 return new Variable(name);
438 function make_app(aa, bb) {
439 return new Lambda_app(aa, bb);
441 function make_lam(a, aa) {
442 return new Lambda_lam(a, aa);
446 if (console && console.debug) {
448 console.debug.apply(this, arguments);
455 let false = \x y. y in
456 let and = \l r. l r false in
457 let or = \l r. l true r in
458 let pair = \u v f. f u v in
459 let triple = \u v w f. f u v w in
460 let succ = \n s z. s (n s z) in
461 let pred = \n s z. n (\u v. v (u s)) (K z) I in
462 let ifzero = \n. n (\u v. v (u succ)) (K 0) (\n withp whenz. withp n) in
463 let add = \m n. n succ m in
464 let mul = \m n. n (\z. add m z) 0 in
465 let mul = \m n s. m (n s) in
466 let sub = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
467 let min = \m n. sub m (sub m n) in
468 let max = \m n. add n (sub m n) in
469 let lt = (\mzero msucc mtail. \n m. n mtail (m msucc mzero) true (\x. true) false) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
470 let leq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
471 let eq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 (K (pair 1 I))) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
472 let divmod = (\mzero msucc mtail. \n divisor.
473 (\dhead. n (mtail dhead) (\sel. dhead (sel 0 0)))
474 (divisor msucc mzero (\a b c. c x))
475 (\d m a b c. pair d m) )
476 (triple succ (K 0) I)
477 (\d. triple I succ (K d))
478 (\dhead d. d (\dz mz df mf drest sel. drest dhead (sel (df dz) (mf mz)))) in
479 let div = \n d. divmod n d true in
480 let mod = \n d. divmod n d false in
481 let Y = \f. (\y. f(y y)) (\y. f(y y)) in
482 let Z = (\u f. f(u u f)) (\u f. f(u u f)) in
483 let fact = \y. y (\f n. ifzero n (\p. mul n (f p)) 1) in
489 // // Basic data structure, essentially a LISP/Scheme-like cons
490 // // pre-terminal nodes are expected to be of the form new cons(null, "string")
491 // function cons(car, cdr) {
496 // // takes a stack of symbols, returns a pair: a tree and the remaining symbols
497 // function parse(split) {
498 // if (split == null) return (new cons (null, null));
499 // if (split.length == 0) return (new cons (null, null));
500 // var token = split.shift();
501 // if (token == ")") return (new cons (null, split));
502 // var next = parse(split);
503 // if (token == "(") {
504 // var nextnext = parse(next.cdr);
505 // return (new cons ((new cons (next.car, nextnext.car)),
508 // return (new cons ((new cons ((new cons (null, token)),
513 // // substitute arg in for v in tree
514 // function sub(tree, v, arg) {
515 // if (tree == null) return (null);
516 // if (tree.car == null) if (tree.cdr == v) return (arg);
517 // if (tree.car == null) return (tree);
519 // // perform alpha reduction to prevent variable collision
520 // if (isBindingForm(tree))
521 // return (new cons (tree.car,
522 // sub(sub(tree.cdr, // inner sub = alpha reduc.
524 // fresh(tree.cdr.car.cdr)),
528 // return (new cons ((sub (tree.car, v, arg)),
529 // (sub (tree.cdr, v, arg))))
532 // // Guaranteed unique for each call as long as string is not empty.
534 // function fresh(string) {
536 // if (typeof(string) != "string") return (string);
537 // return (new cons (null,
538 // string.substring(0,1) + (i).toString()));
541 // // Keep reducing until there is no more change
542 // function fixedPoint (tree) {
543 // var t2 = reduce(tree);
544 // if (treeToString(tree) == treeToString(t2)) return (tree);
545 // return (fixedPoint (t2));
548 // // Reduce all the arguments, then try to do beta conversion on the whole
549 // function reduce(tree) {
550 // if (tree == null) return (tree);
551 // if (typeof(tree) == "string") return (tree);
552 // return (convert (new cons (reduce (tree.car), mapReduce (tree.cdr))));
555 // // Reduce all the arguments in a list
556 // function mapReduce(tree) {
557 // if (tree == null) return (tree);
558 // if (tree.car == null) return (tree);
559 // return (new cons (reduce (tree.car), mapReduce(tree.cdr )));
562 // // If the list is of the form ((lambda var body) arg), do beta reduc.
563 // function convert(tree) {
564 // if (isLet(tree)) {
565 // return (sub(tree.cdr.car, tree.car.cdr.car.cdr, tree.car.cdr.cdr.car));}
567 // if (isConvertable(tree)) {
568 // return (sub(tree.car.cdr.cdr.car, tree.car.cdr.car.cdr, tree.cdr.car));}
569 // else return(tree);
572 // // Is of form ((let var arg) body)?
573 // function isLet(tree) {
574 // if (tree == null) return (false);
575 // if (!(isBindingForm(tree.car))) return (false);
576 // if (tree.car.car.cdr != "let") return (false);
577 // if (tree.cdr == null) return (false);
578 // if (tree.cdr.car == null) return (false);
582 // // Is of form ((lambda var body) arg)?
583 // function isConvertable(tree) {
584 // if (tree == null) return (false);
585 // if (!(isBindingForm(tree.car))) return (false);
586 // if (tree.car.car.cdr != "lambda") return (false);
587 // if (tree.cdr == null) return (false);
588 // if (tree.cdr.car == null) return (false);
592 // // Is of form (lambda var body)?
593 // function isBindingForm(tree) {
594 // if (tree == null) return (false);
595 // if (tree.car == null) return (false);
596 // if (tree.car.car != null) return (false);
597 // if ((tree.car.cdr != "lambda")
598 // && (tree.car.cdr != "let")
599 // && (tree.car.cdr != "exists")
600 // && (tree.car.cdr != "forall")
601 // && (tree.car.cdr != "\u03BB")
602 // && (tree.car.cdr != "\u2200")
603 // && (tree.car.cdr != "\u2203")
606 // if (tree.car.cdr == null) return (false);
607 // if (tree.cdr.car == null) return (false);
608 // if (tree.cdr.car.car != null) return (false);
609 // if (tree.cdr.cdr == null) return (false);
613 // function treeToString(tree) {
614 // if (tree == null) return ("")
615 // if (tree.car == null) return (tree.cdr)
616 // if ((tree.car).car == null)
617 // return (treeToString(tree.car) + " " + treeToString(tree.cdr))
618 // return ("(" + treeToString(tree.car) + ")" + treeToString(tree.cdr))
621 // // use this instead of treeToString if you want to see the full structure
622 // function treeToStringRaw(tree) {
623 // if (tree == null) return ("@")
624 // if (typeof(tree) == "string") return (tree);
625 // return ("(" + treeToStringRaw(tree.car) + "." +
626 // treeToStringRaw(tree.cdr) + ")")
629 // // Make sure each paren will count as a separate token
630 // function stringToTree(input) {
631 // input = input.replace(/let/g, " ( ( let ");
632 // input = input.replace(/=/g, " ");
633 // input = input.replace(/in/g, " ) ");
634 // input = input.replace(/\(/g, " ( ");
635 // input = input.replace(/\)/g, " ) ");
636 // input = input.replace(/;.*\n/g," ");
637 // input = input.replace(/\^/g, " ^ ");
638 // input = input.replace(/[\\]/g, " lambda ");
639 // input = input.replace(/\u03BB/g, " lambda ");
640 // return ((parse(input.split(/[ \f\n\r\t\v]+/))).car)
643 // // Adjust spaces to print pretty
644 // function formatTree(tree) {
645 // output = treeToStringRaw (tree);
646 // output = output.replace(/^[ \f\n\r\t\v]+/, "");
647 // output = output.replace(/[ \f\n\r\t\v]+$/, "");
648 // output = output.replace(/[ \f\n\r\t\v]+\)/g, ")");
649 // output = output.replace(/\)([^)(])/g, ") $1");
650 // output = output.replace(/lambda/g, "\\");
651 // // output = output.replace(/lambda/g, "\u03BB");
652 // // output = output.replace(/exists/g, "\u2203");
653 // // output = output.replace(/forall/g, "\u2200");
657 // function mytry(form) {
659 // form.result.value = formatTree((stringToTree(form.input.value)));
660 // // form.result.value = formatTree(fixedPoint(stringToTree(form.input.value)));