Ackermann function

Question

I just came across the Ackermann–Péter function a few weeks ago, found it to be very interesting, and decided to write a simple implementation of it in a favorite programming language of mine.

def ackermann_peter_10(m, n):
    assert isinstance(m, int) and m >= 0, 'm is unacceptable'
    assert isinstance(n, int) and n >= 0, 'n is unacceptable'
    stack = []
    while True:
        if not m:
            if not stack:
                return n + 1
            m, n = stack.pop(), n + 1
        elif not n:
            m, n = m - 1, 1
        else:
            stack.append(m - 1)
            n -= 1

Can you refactor ackermann_peter_10 any further? It surprised me to see how similar the code is to another version found on Stack Overflow.

Reference: Simple loop Ackermann function

Answer 1

I think the primary issue with your code is you can reasonably assume it will take forever on any hardware that may be running it for all but a handful of possible inputs.

You can reasonably work out what those inputs are. If for instance m and n are bigger than 7, you should throw an error or return something like Infinity immediately. I haven't worked out the exact edge for when it's reasonable to compute the Ackermann function but you should.

Another way to improve this function is to delete it. In your documentation you may explain why it's unreasonable to supply an implementation of the Ackermann function.

Answer 2

Assert statements are a convenient way to insert debugging assertions into a program

Assert statements are not for what you think they are for. Don't use them, instead raise explicit exceptions:

def ackermann_peter_10(m, n):
    if not (isinstance(m, int) and m >= 0):
        raise TypeError('m should be an integer')
    if not (isinstance(n, int) and n >= 0):
        raise TypeError('n should be an integer')
    stack = []
    ...

If you are confused about why assert statements are bad here, it is because there can be errors if your code is run out of debug mode, also known as optimised mode, via the -O flag. This is because assert statements are ignored when you are not in debug mode.

---

After reading @TLW's comment, you may want to know why LBYL is a bad idea in Python, and why EAFP is better.

Python uses duck typing, this means that it categorizes mallards and ducks as 'ducks', where a mallard is not a duck. I.e. both float and int are numbers and different types.

Currently floats are mallards to your function, they can work since they're pretty much ints, and so should be classed as a 'duck'. For example 3. + 1, a simple typo, can cause your function to error on what would be valid input.

To allow floats you can convert the input to an int. The function won't run if the input cannot be converted, as an error will be raised. Which is an EAFP approach.

But there is still a mallard! As stated by @TLW:

This function will throw with any user-defined types, when the function itself would work just fine

Your end user creates the following class:

class Num:
    def __init__(self, num):
        self._num = num

    def __add__(self, other):
        return Num(self._num + other)

    def __iadd__(self, other):
        self._num = self._num + other
        return self

    def __sub__(self, other):
        return Num(self._num - other)

    def __str__(self):
        return 'Num ' + str(self._num)

    def __bool__(self):
        return bool(self._num)

n = Num(0)
print(n)
print(not not n)
n += 1
print(n)
print(n + 1)
print(n - 1)
print(not not n)
# Errors
print(int(n))

As you can guess, it's a number, a 'duck', But it's not an int, a duck. And the above solution of using int to make it a duck doesn't work. But it works in your function!

This raises the question, 'what is a 'duck'?' But figuring out what a 'duck' is can be odd, for example in this function you would need to do:

try:
    m + 1
    m - 1
except TypeError:
    raise TypeError('m should be a number')

But, when the code is more complex, this could not be a viable option, or not fulfil all the requirements for a 'duck'. For example, remove __bool__ from Num, and the function will go into an infinite loop. Do you know how to catch that? Do you know you should catch that? Are there edge-cases? A simple way to solve this is to instead use an EAFP approach. Just hope that it's a 'duck', if it's not your user will notice and fix the input.

def int_(n):
    try:
        return int(n)
    except TypeError:
        return n

def ackermann_peter_10(m, n):
    m = int_(m)
    n = int_(n)
    stack = []
    ...

---

Otherwise, with @oliverpool's changes, your code seems good.

Answer 3

A minor refactoring might be to put the return statement out of the loop. It makes a real uses of the while and remove an indentation block.

def ackermann_peter_10(m, n):
    """Ackermann–Péter function"""
    assert isinstance(m, int) and m >= 0, 'm is unacceptable'
    assert isinstance(n, int) and n >= 0, 'n is unacceptable'
    # The stack stores the `m` of the unfinished calls
    stack = []
    while m or stack:
        if not m:
            m, n = stack.pop(), n + 1
        elif not n:
            m, n = m - 1, 1
        else:
            stack.append(m - 1)
            n -= 1
    return n + 1

I think having a return at the very end is also nice to quickly check the type of result returned by the function.

---

Edit return statement "extraction" (to fulfill @Mat's Mug's comment)

In the original code, the only way to get to the return is when m is 0 and the stack is empty.

while True:
    if not m:
        if not stack:
            return n + 1
        ...

Said the other way around, we do not return while m is positive or the stack has some elements. We just write this sentence into the following code:

while m or stack:
    if not m:
        ...
return n + 1

After we exit the while loop, the result can be returned.

Answer 4

When in the while True, if m is positive, you will call stack.append(m-1) n times before reaching the elif not n. You can simplify and merge the two using:

while True:
    if not m:
        if not stack:
            return n + 1
        m, n = stack.pop(), n + 1
    else:
        m -= 1
        stack.extend([m] * n)
        n = 1

Similarly, when m is 1, there will be n zeroes appended to the stack at once and m will be set to 0 as well. Thus, the loop will reach if not m n times. We can improve that by popping all 0 at once, since we know for sure they are all at the end of the stack:

while True:
    if not m:
        i = stack.index(0)
        n += len(stack) - i
        stack = stack[:i] # popping all 0 at once
        if not stack:
            return n + 1
        m, n = stack.pop(), n + 1
    else:
        m -= 1
        stack.extend([m] * n)
        n = 1

However, doing so we are in trouble in cases the function is called with m = 1 and n = 0.

We can either add a second if not stack before to protect from that case or, my personal favorite, use EAFP approach:

while True:
    if not m:
        try:
            i = stack.index(0)
        except ValueError: # No 0 in stack
            return n + 1
        n += len(stack[i:])
        stack = stack[:i] # popping all 0 at once
        try:
            m, n = stack.pop(), n + 1
        except IndexError: # Stack was left empty removing 0s
            return n + 1
    else:
        m -= 1
        stack.extend([m] * n)
        n = 1

---

First version reads cleaner (especially combined with @oliverpool suggestion), last one performs better (less operations overall, less memory management). Choosing one or another depends what you're after.

Answer 5

It seems from the comments that you share my primary concern with the final version of this code:

(3) there is insufficient proof that the code computes the Ackermann–Péter function

Clever code needs clear commenting. The proof that your code works should be in comments in the code, not in the revision history.