From: Jim Pryor <profjim@jimpryor.net>
Date: Wed, 29 Sep 2010 01:17:33 +0000 (-0400)
Subject: lambda.js: try trampolining evals
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=e92da953f3632fdb846999fcc71f78e9c5be4dc5;ds=sidebyside

lambda.js: try trampolining evals

Signed-off-by: Jim Pryor <profjim@jimpryor.net>
---

diff --git a/code/lambda.js b/code/lambda.js
index 609cce03..15a3cf80 100644
--- a/code/lambda.js
+++ b/code/lambda.js
@@ -207,11 +207,14 @@ function Lambda_var(variable) {
 			var res = left, x;
 			while (stack.length) {
 				x = stack.shift();
-				res = new Lambda_app(res, x.eval_loop([], eta));
+				// 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;
@@ -261,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);
@@ -354,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) {
@@ -414,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];
     }
 }