Compile lambdas on evaluation, not on execution.

This cuts down the cost of calling a function, as it now reuses an existing continuation rather than reconstructing the continuation for each call. Tail calls are now slightly more explicit.

23 files changed, 72 insertions, 52 deletions

diff --git a/.hypothesis/examples/17015ad1b47afd98/04cd75f4500229f7 b/.hypothesis/examples/17015ad1b47afd98/04cd75f4500229f7
deleted file mode 100644
index 51140b6..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/04cd75f4500229f7
+++ /dev/null
@@ -1 +0,0 @@
-���]

\ No newline at end of file
diff --git a/.hypothesis/examples/17015ad1b47afd98/2f292b4e710e8682 b/.hypothesis/examples/17015ad1b47afd98/2f292b4e710e8682
new file mode 100644
index 0000000..b647d27
--- /dev/null
+++ b/.hypothesis/examples/17015ad1b47afd98/2f292b4e710e8682
diff --git a/.hypothesis/examples/17015ad1b47afd98/3c306aae35f9118a b/.hypothesis/examples/17015ad1b47afd98/3c306aae35f9118a
deleted file mode 100644
index f2bd8ef..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/3c306aae35f9118a
+++ /dev/null
@@ -1 +0,0 @@
-

j�N
\ No newline at end of file
diff --git a/.hypothesis/examples/17015ad1b47afd98/49e6f38c5cc772ec b/.hypothesis/examples/17015ad1b47afd98/49e6f38c5cc772ec
new file mode 100644
index 0000000..5c100e8
--- /dev/null
+++ b/.hypothesis/examples/17015ad1b47afd98/49e6f38c5cc772ec
diff --git a/.hypothesis/examples/17015ad1b47afd98/69b43aa9ca8c9717 b/.hypothesis/examples/17015ad1b47afd98/69b43aa9ca8c9717
deleted file mode 100644
index 9398068..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/69b43aa9ca8c9717
+++ /dev/null
diff --git a/.hypothesis/examples/17015ad1b47afd98/9430c84dca3c0657 b/.hypothesis/examples/17015ad1b47afd98/9430c84dca3c0657
deleted file mode 100644
index bd07345..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/9430c84dca3c0657
+++ /dev/null
diff --git a/.hypothesis/examples/17015ad1b47afd98/99f5153a6bf37865 b/.hypothesis/examples/17015ad1b47afd98/99f5153a6bf37865
deleted file mode 100644
index 8b5421a..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/99f5153a6bf37865
+++ /dev/null
diff --git a/.hypothesis/examples/17015ad1b47afd98/9b99593353a610c4 b/.hypothesis/examples/17015ad1b47afd98/9b99593353a610c4
new file mode 100644
index 0000000..5407bf3
--- /dev/null
+++ b/.hypothesis/examples/17015ad1b47afd98/9b99593353a610c4
diff --git a/.hypothesis/examples/17015ad1b47afd98/ae775858a7e56781 b/.hypothesis/examples/17015ad1b47afd98/ae775858a7e56781
new file mode 100644
index 0000000..ec47c8b
--- /dev/null
+++ b/.hypothesis/examples/17015ad1b47afd98/ae775858a7e56781
diff --git a/.hypothesis/examples/17015ad1b47afd98/c92920944247d80c b/.hypothesis/examples/17015ad1b47afd98/c92920944247d80c
deleted file mode 100644
index 03afaa5..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/c92920944247d80c
+++ /dev/null
@@ -1 +0,0 @@
-

\ No newline at end of file
diff --git a/.hypothesis/examples/17015ad1b47afd98/f0784713cbccb244 b/.hypothesis/examples/17015ad1b47afd98/f0784713cbccb244
new file mode 100644
index 0000000..c835d02
--- /dev/null
+++ b/.hypothesis/examples/17015ad1b47afd98/f0784713cbccb244
@@ -0,0 +1 @@
+


\ No newline at end of file
diff --git a/.hypothesis/examples/17015ad1b47afd98/facfba17520f8be9 b/.hypothesis/examples/17015ad1b47afd98/facfba17520f8be9
deleted file mode 100644
index 5f2dd82..0000000
--- a/.hypothesis/examples/17015ad1b47afd98/facfba17520f8be9
+++ /dev/null
diff --git a/.hypothesis/examples/641567e7f1117698/089136b03318a8ae b/.hypothesis/examples/641567e7f1117698/089136b03318a8ae
deleted file mode 100644
index af43500..0000000
--- a/.hypothesis/examples/641567e7f1117698/089136b03318a8ae
+++ /dev/null
diff --git a/.hypothesis/examples/641567e7f1117698/3923acd66c0b7e18 b/.hypothesis/examples/641567e7f1117698/3923acd66c0b7e18
new file mode 100644
index 0000000..70f3b85
--- /dev/null
+++ b/.hypothesis/examples/641567e7f1117698/3923acd66c0b7e18
@@ -0,0 +1 @@
+




���
\ No newline at end of file
diff --git a/.hypothesis/examples/641567e7f1117698/5e762c293b8926ea b/.hypothesis/examples/641567e7f1117698/5e762c293b8926ea
new file mode 100644
index 0000000..cdf9180
--- /dev/null
+++ b/.hypothesis/examples/641567e7f1117698/5e762c293b8926ea
diff --git a/.hypothesis/examples/641567e7f1117698/5ec5c4954a59b6a4 b/.hypothesis/examples/641567e7f1117698/5ec5c4954a59b6a4
new file mode 100644
index 0000000..e915073
--- /dev/null
+++ b/.hypothesis/examples/641567e7f1117698/5ec5c4954a59b6a4
diff --git a/.hypothesis/examples/641567e7f1117698/824e5f0d69863752 b/.hypothesis/examples/641567e7f1117698/824e5f0d69863752
deleted file mode 100644
index 54c356a..0000000
--- a/.hypothesis/examples/641567e7f1117698/824e5f0d69863752
+++ /dev/null
@@ -1 +0,0 @@
-


h�FU3�d&��rd
\ No newline at end of file
diff --git a/.hypothesis/examples/641567e7f1117698/b6420ce3b52b1ab7 b/.hypothesis/examples/641567e7f1117698/b6420ce3b52b1ab7
new file mode 100644
index 0000000..798716b
--- /dev/null
+++ b/.hypothesis/examples/641567e7f1117698/b6420ce3b52b1ab7
diff --git a/.hypothesis/examples/641567e7f1117698/d1f7b282fca409b2 b/.hypothesis/examples/641567e7f1117698/d1f7b282fca409b2
new file mode 100644
index 0000000..5d072ed
--- /dev/null
+++ b/.hypothesis/examples/641567e7f1117698/d1f7b282fca409b2
diff --git a/actinide/__init__.py b/actinide/__init__.py
index 338eace..0f09299 100644
--- a/actinide/__init__.py
+++ b/actinide/__init__.py
@@ -15,8 +15,8 @@ class BaseSession(object):
 
     def eval(self, form):
         form = expander.expand(form, self.symbols)
-        cps = evaluator.eval(form, self.environment, self.symbols, None)
-        return evaluator.run(cps)
+        cps = evaluator.eval(form, self.symbols, None)
+        return evaluator.run(cps, self.environment)
 
     def run(self, port):
         form = self.read(port)
diff --git a/actinide/evaluator.py b/actinide/evaluator.py
index 747a428..bf97911 100644
--- a/actinide/evaluator.py
+++ b/actinide/evaluator.py
@@ -44,9 +44,9 @@ from . import types as t
 # The result of evaluating a continuation is always a Python tuple. For
 # expressions, this tuple contains the value(s) produced by the expression. For
 # forms which do not produce a value, this returns the empty tuple.
-def run(continuation, args=()):
+def run(continuation, environment, args=()):
     while continuation is not None:
-        continuation, args = continuation(*args)
+        continuation, environment, args = continuation(environment, *args)
     return args
 
 # ## FLAT CONTINUATIONS
@@ -57,31 +57,33 @@ def run(continuation, args=()):
 # Returns a continuation which yields a single value, verbatim, and chains to a
 # known target continuation. This implements evaluation for literals.
 def literal(value, continuation):
-    return lambda: (continuation, (value,))
+    return lambda environment: (continuation, environment, (value,))
 
 # Returns a continuation which looks up a symbol in an environment, yields the
 # result, and chains to a known target continuation. This implements evaluation
 # for variable lookups.
-def symbol(symb, environment, continuation):
-    return lambda: (continuation, (environment.find(symb),))
+def symbol(symb, continuation):
+    return lambda environment: (continuation, environment, (environment.find(symb),))
 
 # Returns a continuation which yields a newly-created procedure, and chains to a
 # known target continuation. This implements evaluation for the tail of a lambda
 # form. (The head of the lambda form must be discarded before calling this
 # factory.)
-def lambda_(defn, environment, symbols, continuation):
+def lambda_(defn, symbols, continuation):
     formals = t.flatten(t.head(defn))
     body = t.head(t.tail(defn))
-    proc = t.Procedure(body, formals, environment, symbols)
-    return lambda: (continuation, (proc,))
+    def lambda__(environment):
+        proc = t.Procedure(body, formals, environment, symbols)
+        return continuation, environment, (proc,)
+    return lambda__
 
 # Returns a continuation which takes a value and binds that value to a symbol in
 # a specific environment, then chains to a known target continuation. This
 # implements evaluation of the `define` special form, once the value is known.
-def bind(symbol, environment, continuation):
-    def bind_(value):
+def bind(symbol, continuation):
+    def bind_(environment, value):
         environment.define(symbol, value)
-        return (continuation, ())
+        return (continuation, environment, ())
     return bind_
 
 # Returns a continuation which takes a value and returns one of two known target
@@ -90,14 +92,14 @@ def bind(symbol, environment, continuation):
 # this chains to the `on_false` continuation. In either case, the continuation
 # not chained to is discarded.
 def branch(on_true, on_false):
-    return lambda val: (on_true if val else on_false, ())
+    return lambda environment, val: (on_true if val else on_false, environment, ())
 
 # Returns a continuation which receives values, and appends them to the values
 # passed to this factory, before chaining to a known target continuation. This
 # implements intermediate evaluation of list forms, where part of the list is
 # already known, as well as splicing for forms that yield multiple values.
 def append(args, continuation):
-    return lambda *tail: (continuation, (*args, *tail))
+    return lambda environment, *tail: (continuation, environment, (*args, *tail))
 
 # Transforms a continuation which should receive function results into a
 # function call continuation. A function call continuation receives a function
@@ -106,21 +108,45 @@ def append(args, continuation):
 # If the function is a procedure, this instead returns a continuation which will
 # invoke the procedure, then chain to the wrapped continuation.
 def invoke(continuation):
-    def invoke_(fn, *args):
+    def invoke_(environment, fn, *args):
         if isinstance(fn, t.Procedure):
-            return procedure_call(fn, *args)
-        return builtin(fn, *args)
+            return procedure_call(environment, fn, *args)
+        return builtin(environment, fn, *args)
 
-    def procedure_call(fn, *args):
+    def procedure_call(environment, fn, *args):
         call_env = fn.invocation_environment(*args)
-        call_cont = fn.continuation(call_env, continuation)
-        return (call_cont, ())
+        call_cont = fn.continuation
+        return_cont = tail_graft(continuation, environment, call_cont)
+        return return_cont, call_env, ()
 
-    def builtin(fn, *args):
+    def builtin(environment, fn, *args):
         result = fn(*args)
-        return (continuation, result)
+        return (continuation, environment, result)
     return invoke_
 
+# Continuation transformer. Given a guarded continuation, and a graft
+# continuation and environment, if the graft continuation is None then this
+# returns the guarded continuation unchanged. Otherwise, this replaces the
+# guarded continuation with a guard.
+#
+# The guard calls guarded continuation when applied, but if the guarded
+# continuation chains to None, the guard replaces the returned continuation and
+# environment with the graft continuation and environment. This handles
+# environment restoration after a function call.
+def tail_graft(continuation, environment, guarded):
+    # Tail call magic: if we're not going to transition to another continuation,
+    # don't bother grafting environment recovery on.
+    if continuation is None:
+        return guarded
+
+    def guard(env, *args):
+        next, env, args = guarded(env, *args)
+        if next is None:
+            return continuation, environment, args
+        return tail_graft(continuation, environment, next), env, args
+
+    return guard
+
 # ## RECURSIVE CONTINUATIONS
 #
 # The following continuation factories recurse, producing complex chains of
@@ -133,20 +159,20 @@ def invoke(continuation):
 # This is the heart of the continuation-passing transformation. Every valid form
 # can be translated into continuation-passing form throught this factory. This
 # handles literals, symbols, special forms, and function application.
-def eval(value, environment, symbols, continuation):
+def eval(value, symbols, continuation):
     if t.symbol_p(value):
-        return symbol(value, environment, continuation)
+        return symbol(value, continuation)
     if t.nil_p(value) or not t.list_p(value):
         return literal(value, continuation)
     # Special forms (all of which begin with a special symbol, discarded here)
     if t.head(value) == symbols['if']:
-        return if_(t.tail(value), environment, symbols, continuation)
+        return if_(t.tail(value), symbols, continuation)
     if t.head(value) == symbols['define']:
-        return define(t.tail(value), environment, symbols, continuation)
+        return define(t.tail(value), symbols, continuation)
     if t.head(value) == symbols['lambda']:
-        return lambda_(t.tail(value), environment, symbols, continuation)
+        return lambda_(t.tail(value), symbols, continuation)
     # Ran out of alternatives, must be a function application
-    return apply(value, environment, symbols, invoke(continuation))
+    return apply(value, symbols, invoke(continuation))
 
 # Returns a continuation which fully evaluates a `(define symbol expr)` form,
 # before chaining to a known target continuation. First, the returned
@@ -154,15 +180,15 @@ def eval(value, environment, symbols, continuation):
 # continuation`. The result of this evaluation is chained to a `bind`
 # continuation, to store the result of evaluation in the target environment.
 # Finally, the `bind` continuation chains to the target continuation.
-def define(value, environment, symbols, continuation):
+def define(value, symbols, continuation):
     symb, expr = t.flatten(value)
 
     if not t.symbol_p(symb):
         raise RuntimeError("Argument to define not a symbol: {t.display(symb)}")
 
-    bind_cont = bind(symb, environment, continuation)
-    eval_cont = eval(expr, environment, symbols, bind_cont)
-    return lambda: (eval_cont, ())
+    bind_cont = bind(symb, continuation)
+    eval_cont = eval(expr, symbols, bind_cont)
+    return lambda environment: (eval_cont, environment, ())
 
 # Returns a continuation which fully evaluates an `(if cond if-true if-false)`
 # form, before chaining to a known target continuation. First, the returned
@@ -170,14 +196,14 @@ def define(value, environment, symbols, continuation):
 # construct the continuation), which chains to a `branch` continuation
 # containing continuations for the `if-true` and `if-false` epxressions. The
 # `if-true` and `if-false` continuations each chain to the target continuation.
-def if_(value, environment, symbols, continuation):
+def if_(value, symbols, continuation):
     cond, if_true, if_false = t.flatten(value)
 
-    if_true_cont = eval(if_true, environment, symbols, continuation)
-    if_false_cont = eval(if_false, environment, symbols, continuation)
+    if_true_cont = eval(if_true, symbols, continuation)
+    if_false_cont = eval(if_false, symbols, continuation)
     branch_cont = branch(if_true_cont, if_false_cont)
 
-    return eval(cond, environment, symbols, branch_cont)
+    return eval(cond, symbols, branch_cont)
 
 # Returns a continuation which fully evaluates the elements of a list, before
 # chaining to a target continuation. If this is applied to an empty list, the
@@ -186,8 +212,8 @@ def if_(value, environment, symbols, continuation):
 # list (recursively, using `eval` to prepare the continuation), then chains to
 # an `append` continuation to glue the result onto the result of recursively
 # calling `apply` on the tail of the list.
-def apply(list, environment, symbols, continuation):
+def apply(list, symbols, continuation):
     if t.nil_p(list):
-        return lambda *args: (continuation, args)
-    tail_cont = apply(t.tail(list), environment, symbols, continuation)
-    return lambda *args: (eval(t.head(list), environment, symbols, append(args, tail_cont)), ())
+        return lambda environment, *args: (continuation, environment, args)
+    tail_cont = apply(t.tail(list), symbols, continuation)
+    return lambda environment, *args: (eval(t.head(list), symbols, append(args, tail_cont)), environment, ())
diff --git a/actinide/types.py b/actinide/types.py
index 97ccdbb..b5b87cd 100644
--- a/actinide/types.py
+++ b/actinide/types.py
@@ -211,21 +211,17 @@ def flatten(list):
 class Procedure(object):
     def __init__(self, body, formals, environment, symbols):
         self.body = body
+        self.continuation = e.eval(body, symbols, None)
         self.formals = formals
         self.environment = environment
-        self.symbols = symbols
 
     def __call__(self, *args):
         call_env = self.invocation_environment(*args)
-        call_cont = self.continuation(call_env, None)
-        return e.run(call_cont, ())
+        return e.run(self.continuation, call_env, ())
 
     def invocation_environment(self, *args):
         return Environment(zip(self.formals, args), self.environment)
 
-    def continuation(self, environment, continuation):
-        return e.eval(self.body, environment, self.symbols, continuation)
-
 @fn
 def procedure_p(value):
     return callable(value)
diff --git a/tests/test_evaluator.py b/tests/test_evaluator.py
index d989f85..dbccbce 100644
--- a/tests/test_evaluator.py
+++ b/tests/test_evaluator.py
@@ -13,6 +13,6 @@ from .programs import *
 def test_evaluator(program_result):
     program, result, bindings = program_result
     environment = Environment()
-    assert run(eval(program, environment, symbol_table, None)) == result
+    assert run(eval(program, symbol_table, None), environment) == result
     for symbol, value in bindings:
         assert environment[symbol] == value