# Ackermann function

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

• HI, I've edited your question. Whilst all your previous work is awesome, it ultimately destracts from your current code. – Kaz Jan 27 '16 at 15:49
• I appreciate your concerns, but I wouldn't worry. (1) Generally speaking, we assume people are honest unless they *obviously* didn't write the code or don't understand it. (2) I appreciate that, and your work is awesome, but CR is ultimately about improving your code *from where it already is*. If you *really* want to share it, you can try making a series of question/selfie answers following the CR guide for follow-up questions, leading up to this one. (3) See (1) about assuming honesty. If you say your code works, then we'll take you at your word unless shown otherwise. – Kaz Jan 27 '16 at 16:21
• What @Zak said. If your post includes a code block for each step of the refactoring process, it makes it harder than it needs to be, to figure out which version of the code you're putting up for review - that's part of why we don't allow code edits to answered questions, too. – Mathieu Guindon Jan 27 '16 at 16:30
• In essence. You would have to be careful that each question and answer was a good, On-Topic CR Q/A in its' own right. For instance, answers that just post better code without explaining how and why it's better are considered very low-quality and worthy of deletion. – Kaz Jan 27 '16 at 17:42
• Don't check if the inputs are ints, please! Better to ask forgiveness than permission. This function will throw with any user-defined types, when the function itself would work just fine (as long as said type implements the appropriate overrides). It's an artificial limitation you've imposed. – TLW Jan 27 '16 at 21:42

## 5 Answers

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.

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.

• Normally you would raise TypeError if not isinstance(m, int). – Dietrich Epp Jan 27 '16 at 22:57
• @DietrichEpp Thank you, I somehow forgot that was an exception... – Peilonrayz Jan 27 '16 at 23:41
• Great answer. One question: "remove __bool__ from Num, and the code breaks." Every class by default will always evaluate as True if __bool__ is not defined. So you wouldn't raise an error from doing this, however the code would not function right. It's best you make that clearer as it sounds as if you mean not m would break if __bool__ wasn't defined. – SuperBiasedMan Feb 1 '16 at 9:45
• @SuperBiasedMan I tried changing the sentence, I dunno if it's any better... I don't understand why you read it differently to what I mean, so I'm finding it hard to fix it... (I understand your comment) Is it any-better? – Peilonrayz Feb 1 '16 at 12:52
• @JoeWallis Yes it works clearly now! Admittedly part of my confusion was that I didn't realise it would lead to an infinite loop (I wasn't thinking about the context of how it's used), I just had it classified in my brain as "not working as intended" rather than an actual serious execution error. – SuperBiasedMan Feb 1 '16 at 13:12

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.

• Definitely. I don't write Python, but having the return statement outside of the loop clearly makes it easier to follow. I'm not sure the loop condition is ideal though, but +1 for getting the return out of there. Can you edit to clarify the while condition? – Mathieu Guindon Jan 27 '16 at 16:33
• @Mat'sMug I just edited my answer: does it clarify the while condition enough? – oliverpool Jan 27 '16 at 18:34

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.

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.