Skip to content

Instantly share code, notes, and snippets.

@Tritlo
Last active October 4, 2022 13:55
Show Gist options
  • Save Tritlo/2a0e429f2b0037d8c2eb to your computer and use it in GitHub Desktop.
Save Tritlo/2a0e429f2b0037d8c2eb to your computer and use it in GitHub Desktop.
Proper Tail Recursion in Python
(defclass TailCall [Exception]
"An exeception to implement Proper Tail Recursion"
[[--init--
(fn [self __TCFunc &rest args &kwargs kwargs]
(setv self.func __TCFunc)
(setv self.args args)
(setv self.kwargs kwargs)
nil)]])
(defn TailRec [func]
"""A decorator that takes functions that end in raise TailCall(func, *args, **kwargs)
and makes them tail recursive"""
(if (hasattr func "__nonTCO")
func
(do
(defn funcwrapper [&rest args &kwargs kwargs]
(setv funcwrapper.__nonTCO func)
(setv tc (apply TailCall (cons func (list args)) kwargs))
(while True
(try (if (hasattr tc.func "__nonTCO")
(setv ret (apply tc.func.__nonTCO (list tc.args) tc.kwargs))
(setv ret (apply tc.func (list tc.args) tc.kwargs)))
(catch [err TailCall]
(setv tc err))
(else (break))))
ret)
funcwrapper)))
class TailCall(Exception):
def __init__(self, __TCFunc, *args,**kwargs):
self.func = __TCFunc
self.args = args
self.kwargs = kwargs
def TailRec(func):
if hasattr(func,"__nonTCO"):
return func
def funcwrapper(*args,**kwargs):
# This is so we don't get a stack overflow when
# calling TailRec funcs
funcwrapper.__nonTCO = func
tc = TailCall(func,*args,**kwargs)
# We can add this to enable debugging of TCO funcs,
# by keeping track of from whence we came
# tcs = []
# tcs.append(tc)
while True:
try:
if hasattr(tc.func,"__nonTCO"):
return tc.func.__nonTCO(*tc.args,**tc.kwargs)
else:
return tc.func(*tc.args,**tc.kwargs)
except TailCall as err:
tc = err
# tcs.append(tc)
# except Exception as err:
# print("Exception in TailCall! Call Stack:")
# displayTailCallLog(tcs)
# raise err
return funcwrapper
# def displayTailCallLog(tcs):
# for tc in tcs:
# print(tc.func, tc.args,tc.kwargs)
@TailRec
def even(n):
if n == 0:
return True
raise TailCall(odd,n-1)
@TailRec
def odd(n):
if n == 0:
return False
raise TailCall(even,n-1)
@TailRec
def fact(n):
def facthelper(n,i):
if n == 0:
return i
raise TailCall(facthelper,n-1,i*n)
raise TailCall(facthelper,n,1)
def nontcoeven(n):
if n == 0:
return True
return nontcoodd(n-1)
def nontcoodd(n):
if n == 0:
return False
return nontcoeven(n-1)
def NonTailRecFact(n):
def nontailrectfacthelper(n,i):
if n == 0:
return i
return nontailrectfacthelper(n-1,i*n)
return nontailrectfacthelper(n,1)
# TailRec decorator is idempotent, so it doesn't
# break functions that don't raise TailCall
@TailRec
@TailRec
def NotATailRecursiveFunction(a,b):
return a + b
print(NotATailRecursiveFunction(2,3))
print(fact(10000))
print(even(1000))
try:
print("Non TCO Factorial")
print(NonTailRecFact(1000))
except RuntimeError as err:
print("RuntimeError: %s" % (format(err),))
try:
print("Non TCO Even function")
print(nontcoeven(1000))
except RuntimeError as err:
print("RuntimeError: %s" % (format(err),))
@knolog
Copy link

knolog commented Oct 4, 2022

Hi Tritio,

Thanks for sharing this Hy script. However, I try to run with the following error. I am a newbie to Hy and Lisp. Highly appreciate if you can fix it. Thanks a lot!

hy.errors.syntaxerrors: "try" can not have "else" without "except"

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment