Skip to content

Instantly share code, notes, and snippets.

@obriencj

obriencj/tailcall.py

Created Mar 14, 2014
Embed
What would you like to do?
playing chicken with the python stack using exceptions
#! /usr/bin/env python3
from functools import partial
from inspect import currentframe
import sys
STACK_LIMIT = 64
class ContinueCall(BaseException):
pass
def countstack():
# this is the slowest part, by far. How does Python count its call
# depth faster than we do? TODO: reify THAT number instead!
counter = 0
frame = currentframe()
while frame:
frame = frame.f_back
counter += 1
return counter
def tailcall(work, *args):
if countstack() > STACK_LIMIT:
raise ContinueCall(partial(work, *args)).with_traceback(None)
else:
work(*args)
def tailrecursive(func, final_cont, *args):
work = partial(func, final_cont, *args)
while True:
try:
work()
except ContinueCall as cc:
work = cc.args[0]
else:
break
def add_1_recursively(cont, x):
# recurs, accumulating x each time, until x reaches the limit,
# then calls the continuation with the acculumated x value.
if x < LIMIT:
tailcall(foo, cont, x + 1)
else:
tailcall(cont, x)
def factorial(cont, num):
if num == 0 or num == 1:
tailcall(cont, 1)
else:
k = lambda x: tailcall(cont, num * x)
tailcall(factorial, k, num - 1)
def main(value):
#tailrecursive(add_1_recursively, print, value)
tailrecursive(factorial, print, value)
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Give us a positive integer")
else:
try:
value = int(sys.argv[1])
except Exception as e:
print(e)
else:
main(value)
#
# The end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment