|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes | |||
Review: Continuations, CPS¶
This notebook summarizes our exploration into Continuation-Passing Style (CPS) in Python.
Consider the old favorite, factorial, written with standard recursion:
def fact(n):
if n == 1:
return 1
else:
return n * fact(n - 1)
fact(5)
print fact(976)
This works, in Python!
But this type of code will fail in languages like C and Java for a completely different reason: you will "overflow" the bits that a number can contain. We'll discuss types later. But for now, realize that both Scheme and Python do a smart thing here: they automatically switch from Integers to BigNums (a data structure-based number representation).
But if we try to compute just one more:
try:
print fact(977)
except:
print "Fail!"
Why?
try:
print fact(977)
except Exception as e:
print e.message
This is the problem that we are exploring with continuations and CPS.
We can rewrite fact in CPS. Here, we use functions to represent continuations. So in this example, a continuation is a function that takes a value. When you get a result, you "pass it to the continuation"... meaning that since the continuation is a function, you simply "call" the continuation with the result as an argument.
Recall the three steps of CPS transformation:
- Add a continuation, k, to the recursive function
- Give any result to the continuation
- Any computation that is left to do after a recursive call must be done in a new continuation
def fact_cps(n, k):
if n == 1:
return k(1)
else:
return fact_cps(n - 1,
lambda v: k(v * n))
fact_cps(2, lambda i: i)
And give the identity function as the initial continuation:
fact_cps(5, lambda i: i)
Yet:
try:
print fact_cps(1000, lambda i: i)
except Exception as e:
print e.message
The first thing we can do is move the "calling of the continuation" out from inside the recursive function:
def fact_cps(n, k):
if n == 1:
return ["apply-cont", k, 1]
else:
return fact_cps(n - 1,
lambda v: ["apply-cont", k, v * n])
And then make a "trampoline" to run it:
def trampoline(result):
while isinstance(result, list):
result = result[1](result[2])
return result
trampoline(fact_cps(5, lambda i: i))
Yet:
try:
print trampoline(fact_cps(1000, lambda i: i))
except Exception as e:
print e.message
The problem is that we are still calling the recursive function recursively. We can move out the recursive call, similarly to what we did with the calling of the continuation.
We note that after we have transformed a function into CPS, the rest of the computation could be carried out by a simple GOTO. We approximate this by returning a "goto" list that contains the name of the function, and its arguments. Really, we are just moving the "calling of the recursive function" from inside the recursive function to the trampoline:
def fact_cps(n, k):
if n == 1:
return ["apply-cont", k, 1]
else:
return ["goto", fact_cps, n - 1,
lambda v: ["apply-cont", k, v * n]]
def trampoline(result):
while isinstance(result, list):
if result[0] == "apply-cont":
result = result[1](result[2])
elif result[0] == "goto":
result = apply(result[1], result[2:])
return result
Thus, we have three things that calling a recursive CPS function can return:
- a continuation
- a goto, a recursive call
- a result
The trampoline will bounce through these until a result is gotten:
try:
print trampoline(fact_cps(1000, lambda i: i))
except Exception as e:
print e.message
At this point, there is no stack!
That doesn't mean we can compute the factorial of any huge number... fact_cps still takes memory in the form of a continuation for each recursion. But there are no more stack limits to hold us back!
On the other hand, some recursions can now run forever, because they don't take any more continuations. Consider:
def loop():
return loop()
try:
loop()
except:
print "Fail!"
But we can do the same tricks:
def loop_cps(k):
return ["goto", loop_cps, k]
trampoline(loop_cps(lambda i: i))
(I had to press the Interrupt button to stop, as this would run forever)
Handling multiple recursions can get a little tricky, but is still very mechanical. Consider fib:
def fib(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
fib(5)
Again, the three steps of CPS transformation:
- Add a continuation, k, to the recursive function
- Give any result to the continuation
- Any computation that is left to do after a recursive call must be done in a new continuation
First, we write it in standard CPS form:
def fib_cps(n, k):
if n == 0:
return k(1)
elif n == 1:
return k(1)
else:
return fib_cps(n - 1,
lambda v1: fib_cps(n - 2,
lambda v2: k(v1 + v2)))
fib_cps(5, lambda i: i)
Then, we "unroll" the function calls so that they are done in the trampoline:
def fib_cps(n, k):
if n == 0:
return ["apply-cont", k, 1]
elif n == 1:
return ["apply-cont", k, 1]
else:
return ["goto", fib_cps, n - 1,
lambda v1: ["goto", fib_cps, n - 2,
lambda v2: ["apply-cont", k, v1 + v2]]]
trampoline(fib_cps(5, lambda i: i))
This will take forever for numbers over 20 something. Why? Not because it is recursive, but because it is stupidly re-computing things over and over.
Don't confuse recursion with stupidity! Recursion is often the right tool for the job, especially if you have a recursive data structure, and are working an appropriate programming language.