[Python] Recursive definition of arithmetic operators: How to memoize / cache?

All arithmetic operators are based on the fact that all natural number do have a successor. For educational purposes I implemented this idea as Python functions:

# recursive definition of arithmetic operators

a = 2
b = 3 # larger numbers won't work: RecursionError


def successor(n):
""" returns n + 1. All other functions use successor recursively """
return n + 1


def sum(n, m):
""" sum a + b """
if m == 0:
return n
if m == 1:
return successor(n)
else:
return successor(sum(n, m - 1))

print(f"sum({a}, {b}) = {sum(a,b)}")


def product(n, m):
""" multiplication n*m"""
if m == 0:
return 0
elif m == 1:
return sum(n, 0)
else:
return sum(product(n, m - 1), n)

print(f"product({a}, {b}) = {product(a, b)}")


def power(n, m):
""" power n**m"""

if m == 0:
return 1
elif m == 1:
return product(n, 1)
else:
return product(power(n, m - 1), n)

print(f"power({a}, {b}) = {power(a, b)}")


def up_arrow_2(n, m):
""" up_arrow operator 2nd degree: n**(n**( ....) m times """
if m == 0:
return 1
elif m == 1:
return power(n, 1)
else:
return power(up_arrow_2(n, m - 1), n)

print(f"up_arrow_2({a}, {b}) = {up_arrow_2(a, b)}")


def up_arrow_3(n, m):
""" up_arrow operator 3rd degree"""
if m == 0:
return 1
elif m == 1:
return up_arrow_2(n, 1)
else:
return up_arrow_2(up_arrow_3(n, m - 1), n)

print(f"up_arrow_3({a}, {b}) = {up_arrow_3(a, b)}")


This works nicely for number up to a=2 and b=3 and then a maximum recursion depth exceeded happens when calculating up_arrow_3(2, 4) (and it's quite obvious why).

If I insert the line return n**m as the first line inside the power function, then much larger numbers can be calculated. Therefore, caching intermediate results seems to be a promising solution.

In order to extend to larger numbers, I tried memoizing using a decorator class such as

class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]


and decorate the functions - without success.

I am looking for an idea how to write another decorator that does the required caching and allows for larger input numbers a, b.

Edit: Here is the solution worked out by @Urmzd using trampoline:

# recursive definition of arithmetic operators
from typing import Callable

a = 2
b = 3

def memoize(func):
cache = {}

def memoize_inner(*args, **kwargs):
str_args = f"{args}{kwargs}"
return cache.get(str_args, func(*args, **kwargs))

return memoize_inner

def trampoline(fn):
def trampoline_inner(*args, **kwargs):
fns = fn(*args, **kwargs)

while(isinstance(fns, Callable)):
fns = fns()

return fns

return trampoline_inner

def successor(n):
""" returns n + 1. All other functions use successor recursively """
return n + 1


@memoize
@trampoline
def _sum(n, m, cont=lambda x:x):
""" sum a + b """
return lambda: cont(n) if m == 0 else lambda: successor(_sum(n, m-1, lambda x: lambda: cont(x)))


@memoize
@trampoline
def product(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: _sum(product(n, m-1, lambda x: lambda: cont(x)), n)

@memoize
@trampoline
def power(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: product(power(n, m-1, lambda x: lambda: cont(x)), n)

@memoize
@trampoline
def ua2(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: power(ua2(n, m-1, lambda x: lambda: cont(x)), n)

@memoize
@trampoline
def ua3(n, m, cont=lambda x:x):
""" a*b """
return lambda: cont(n) if m == 1 else lambda: ua2(ua3(n, m-1, lambda x: lambda: cont(x)), n)


print(f"sum({a}, {b}) = {_sum(a,b)}")
print(f"product({a}, {b}) = {product(a,b)}")
print(f"power({a}, {b}) = {power(a,b)}")
print(f"ua2({a}, {b}) = {ua2(a,b)}")
print(f"ua3({a}, {b}) = {ua3(a,b)}")

Continue reading...