lambda.js: try trampolining evals

[lambda.git] / code / lambda.js

diff --git a/code/lambda.js b/code/lambda.js
index c0dbb0f..15a3cf8 100644 (file)
--- a/code/lambda.js
+++ b/code/lambda.js
@@ -115,14 +115,19 @@ function Variable(name, tag) {
     this.tag = tag || 0;
     this.to_string = function () {
         // append count copies of str to accum
-        function markup(accum, count) {
-            if (count === 0) {
-                return accum;
-            } else {
-                return markup(accum + "'", count - 1);
-            }
-        }
-        return markup(this.name, this.tag);
+//         function markup(accum, count) {
+//             if (count === 0) {
+//                 return accum;
+//             } else {
+//                 return markup(accum + "'", count - 1);
+//             }
+//         }
+//         return markup(this.name, this.tag);
+               var s = this.name;
+               for (var count = 0; count < this.tag; count += 1) {
+                       s += "'";
+               }
+               return s;
     };
     this.equal = function (other) {
         return (this.tag === other.tag) && (this.name === other.name);
@@ -192,15 +197,24 @@ function Lambda_var(variable) {
     };
     this.eval_loop = function (stack, eta) {
         function unwind(left, stack) {
-            if (stack.length === 0) {
-                return left;
-            } else {
-                var x = stack[0];
-                var xs = stack.slice(1);
-                return unwind(new Lambda_app(left, x.eval_loop([], eta)), xs);
-            }
+//             if (stack.length === 0) {
+//                 return left;
+//             } else {
+//                 var x = stack[0];
+//                 var xs = stack.slice(1);
+//                 return unwind(new Lambda_app(left, x.eval_loop([], eta)), xs);
+//             }
+                       var res = left, x;
+                       while (stack.length) {
+                               x = stack.shift();
+                               // res = new Lambda_app(res, x.eval_loop([], eta));
+                               res = new Lambda_app(res, reduce(x, eta, false));
+                       }
+                       return res;
         }
-        return unwind(this, stack);
+        // return unwind(this, stack);
+               // post-processor, trampoline to, args
+               return [null, null, unwind(this, stack)];
     };
     this.eval_cbv = function (aggressive) {
         return this;
@@ -250,7 +264,9 @@ function Lambda_app(left, right) {
     this.eval_loop = function (stack, eta) {
         var new_stack = stack.slice(0);
         new_stack.unshift(this.right);
-        return this.left.eval_loop(new_stack, eta);
+        // return this.left.eval_loop(new_stack, eta);
+               // post-processor, trampoline to, args
+               return [null, this.left, new_stack, eta];
     };
     this.eval_cbv = function (aggressive) {
         var left = this.left.eval_cbv(aggressive);
@@ -343,17 +359,29 @@ function Lambda_lam(variable, body) {
         }
     };
     this.eval_loop = function (stack, eta) {
+               function post(evaluated_body) {
+                       var term = new Lambda_lam(this.bound, evaluated_body);
+                       if (eta) {
+                               return term.check_eta();
+                       } else {
+                               return term;
+                       }
+               }
         if (stack.length === 0) {
-            var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
-            if (eta) {
-                return term.check_eta();
-            } else {
-                return term;
-            }
+//             var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
+//             if (eta) {
+//                 return term.check_eta();
+//             } else {
+//                 return term;
+//             }
+                       // post-processor, trampoline to, args
+                       return [post, this.body, [], eta];      
         } else {
             var x = stack[0];
             var xs = stack.slice(1);
-            return subst(this.bound, x, this.body).eval_loop(xs, eta);
+            // return subst(this.bound, x, this.body).eval_loop(xs, eta);
+                       // post-processor, trampoline to, args
+                       return [null, subst(this.bound, x, this.body), xs, eta];
         }
     };
     this.eval_cbv = function (aggressive) {
@@ -364,16 +392,31 @@ function Lambda_lam(variable, body) {
         }
     };
     this.to_int = function (sofar) {
-        if (this.body.body && this.body.body.variable && this.body.bound.equal(this.body.body.variable)) {
-            return 0 + sofar;
-        } else if (this.body.variable && this.bound.equal(this.body.variable)) {
-            return 1 + sofar;
-        } else if (this.body.body && this.body.body.left && this.body.body.left.variable && this.bound.equal(this.body.body.left.variable)) {
-            var new_int = new Lambda_lam(this.bound, new Lambda_lam(this.body.bound, this.body.body.right));
-            return new_int.to_int(1 + sofar);
-        } else {
-            return "not a church numeral";
-        }
+//         if (this.body.body && this.body.body.variable && this.body.bound.equal(this.body.body.variable)) {
+//             return 0 + sofar;
+//         } else if (this.body.variable && this.bound.equal(this.body.variable)) {
+//             return 1 + sofar;
+//         } else if (this.body.body && this.body.body.left && this.body.body.left.variable && this.bound.equal(this.body.body.left.variable)) {
+//             var new_int = new Lambda_lam(this.bound, new Lambda_lam(this.body.bound, this.body.body.right));
+//             return new_int.to_int(1 + sofar);
+//         } else {
+//             return "not a church numeral";
+//         }
+               var res = 0, s = this.bound, z, cursor;
+               if (this.body.variable && s.equal(this.body.variable)) {
+                       return 1;
+               } else if (this.body.bound) {
+                       z = this.body.bound;
+                       cursor = this.body.body;
+                       while (cursor.left && cursor.left.variable && s.equal(cursor.left.variable)) {
+                               res += 1;
+                               cursor = cursor.right;
+                       }
+                       if (cursor.variable && z.equal(cursor.variable)) {
+                               return res;
+                       }
+               }
+               return "not a church numeral";
     };
 }
 
@@ -388,7 +431,17 @@ function reduce(expr, eta, cbv) {
     if (cbv) {
         return expr.eval_cbv(cbv > 1);
     } else {
-        return expr.eval_loop([], eta);
+        // return expr.eval_loop([], eta);
+               var post = null, to_eval = expr, res = [[], eta];
+               while (to_eval !== null) {
+                       res = to_eval.eval_loop.apply(to_eval, res);
+                       post = res.shift();
+                       to_eval = res.shift();
+                       if (post) {
+                               res = post(res);
+                       }
+               }
+               return res[0];
     }
 }