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)}")
CodePudding user response：
The following code will fix your issue.
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
Part of the reason why your code doesn't work is due to lack of optimality. But that's an entirely different issue, and can be resolve in various ways. If you want the memorization to work, you have to memorize all of your functions. This ensures that at each level, redundant computation is potentially reduced.
-- Edit
As mentioned earlier, your code is sub-optimal. Part of this due to a lack of recursion-optimization (tail-recursion using continuations, and stack optimization using thunks and trampolines).
So lets try fixing your code one step at a time (recursion-optimization has a greater overhead, so using the minimal amount of work should be attempted).
First, lets modify the sum function to make it tail-recursive (no-continuations needed):
@memoize
def sum(n, m):
""" sum a b """
return n if m == 0 else sum(successor(n), m-1))
Or if you really wanted to use continuations for whatever reason.
@memoize
def sum(n, m, cont=lambda x: x):
""" sum a b """
return cont(n) if m == 0 else sum(successor(n), m-1)
Then, we could make use of thunks by adding empty lambda functions for lazy-evaluation:
@memoize
def sum(n, m, cont=lambda x: x):
""" sum a b """
return lambda: cont(n) if m == 0 else lambda: sum(successor(n), m-1, lambda x: lambda: cont(x))
And trampolines using the following util function which begins the recursion:
from typing import Callable
def trampoline(fn):
while(isinstance(fn, Callable)):
fn = fn()
return fn
If we wanted to invoke the function, we could do the following:
trampoline(sum(a,b))
However, if we want to implicitly invocate the thunks, we can make a trampoline decorator
def trampoline(fn):
def trampoline_inner(*args, **kwargs):
fns = fn(*args, **kwargs)
while(isinstance(fns, Callable)):
fns = fns()
return fns
return trampoline_inner
With this, you should have all the tools to fix the remaining functions and prevent recursion-depth-errors.
The full solution:
from typing import Callable
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: sum(successor(n), m-1, lambda x: lambda: cont(x))
print(f"sum({a}, {b}) = {sum(a,b)}")