Tail recursion & Memoisation utilities, Python 3

Tail recursion & Memoisation utilities

#sample usage:
#
# @tailFun
# def fac(n,m=1):
#     if n==0: return m
#     return tailRec(n-1,n*m)
#
# This emulates tail recursion. Under the hood,
# this function is actually not recursive at all.
# Calling tailRec outside of a callable decorated
# with @tailFun will likely result in nasty exceptions.
#
# ------------------------------------------
#
# @memFun
# def fibo(n):
#     if n<=1: return 1
#     return memRec(n-1)+memRec(n-2)
#
# The decorator @memFun makes so that fibo is
# memoised. Also the use of memRec tu recur
# makes sure that fibo is actually not recursive.
# Note that the way it works does not, in general,
# produce an efficient iterative algorithm, although
# it is guaranteed to not throw any RecursionError.
#
# Internally, memRec(*args) wraps a call to fibo(*args)
# by calling memNeed(*args) beforehand; the above
# definition is roughly equivalent to
#
# @memFun
# def fibo2(n):
#     if n<=1: return 1
#     memNeed(n-1)
#     memNeed(n-2)
#     return fibo2(n-1)+fibo2(n-2)
#
# Both syntaxes do the same thing, but be warned that
# if you call memNeed by hand and forget to call it
# on some of the parameters, the resulting callable
# will in general be truly recursive.
# memNeed and memRec can not be used outside of a
# callable decorated by @memFun.
#
# N.B.: due to an implementation quirk, if you wish
# to use memNeed or memRec, make sure that there is
# no variable named _self in the local scope of the
# function you are defining; otherwise they probably
# won't work properly and will fail in confusing ways.

import inspect

class tailRec:
    _args=()
    def __init__(self,*args):
        self._args=args
    def get(self): return self._args

class tailFun:
    _fun=lambda *x: 0
    def __init__(self,fun):
        self._fun=fun
    def __call__(self,*args):
        r0=self._fun(*args)
        while isinstance(r0,tailRec):
            r0=self._fun(*(r0.get()))
        return r0

class memFun:
    _fun=lambda *x: 0
    _HT={}
    def __init__(self,fun):
        def mfun(args,HT):
            if args not in HT: HT[args]=fun(*args)
            return HT[args]
        self._fun=mfun
    def __call__(_self,*args):
        needed=[args]
        while len(needed)>0:
            try: res=_self._fun(needed[0],_self._HT)
            except _NeedMemVal as e: res=e
            if isinstance(res,_NeedMemVal): needed=[res.args[0]]+needed
            else: needed=needed[1:]
        return res

def _reach_back(name):
    try:
        f=inspect.currentframe()
        while name not in f.f_locals:
            f=f.f_back
        return f.f_locals[name]
    finally: del f

class _NeedMemVal(Exception): pass

def memNeed(*args):
    HT=_reach_back('_self')._HT
    if args in HT: return
    raise _NeedMemVal(args)

def memRec(*args):
    memNeed(*args)
    self=_reach_back('_self')
    return self._fun(args,self._HT)

##### EXAMPLE #####

@memFun
def fibo(n):
    if n<=1: return 1
    return memRec(n-1)+memRec(n-2)

print(fibo(10000)) #runs in ~1s


run \| edit \| history \| help	1