Recursion Error While Handling Recursion Error
Here’s a Python function. What happens when it gets called?
If you guessed
RecursionError, then congratulations.
Here’s another one. What happens when it gets called?
The correct answer here is “Which version of Python?”
In Python 3, the interpreter freaks out and bails.
More specifically, the interpreter hits a recursion error, then tries to back off and handle it. While handling the error, it hits another one. Knowing that it’s already in stack limit recovery mode, the interpreter decides that the stack is unsalvageable and it aborts. (This, at least, is what I’ve been able to figure out from reading the CPython source.1)
g in Python 2 results in the interpreter apparently hanging indefinitely, unable even to respond to a keyboard interrupt. I’d show the REPL output, but nothing shows up after the call. A variation on
g points to what is happening:
h(0) results in the following output:
As far as I can tell, what’s happening is that the interpreter hits its stack limit, then tries to back off and keep going, then hits the limit again, and it just goes on bouncing around the top of the stack like a paddle ball, catching its own thrown exceptions, in an infinite loop. This loop does not include handling keyboard interrupts, which is why it’s impossible to regain control with
I know this sounds like a piece of stupid programming language trivia, but I actually came across this in real life. It occurs when you run Pylint with a certain version of Astroid against some very specific and gravely erroneous Python code. I opened an issue about this, which contains all the details. It was closed recently with the ruling that it is not the interpreter’s problem.
What’s the appropriate behavior for an interpreter in this kind of situation? The Python 2 response is clearly bad, but the Python 3 response isn’t great either.
Process Python aborted (core dumped) makes it sound like the interpreter hit a bug, but that isn’t the case; the intended behavior is that the program won’t continue when the stack gets into a certain state, and that’s what happens.
How do other languages handle it? Thinking about this question brought me to the startling realization that I don’t have a great grasp of error handling in very many languages! I have a passable understanding of how it works in Emacs Lisp, so let’s look at that.. For reference, here’s the function
f to begin with:
As expected, it hits a stack depth error:
g, the one that causes Python 3 to abort and causes Python 2 to get stuck:
In Emacs, this function seems to have the same behavior as in Python 2, except that it responds just fine to
C-g). That is, it gets itself into a stack-bouncing loop, but it’s easy to get out.
Here’s the function
h to give some visibility:
The output of
(h 0) looks a lot like the output of
h(0) in Python 2, though with a shorter stack2:
Scheme uses tail-call elimination, so the function
f doesn’t cause any kind of stack error. It uses a fixed amount of stack space, and it will happily execute as long as you let it:
g is not tail-recursive, so it will grow the stack. I can’t come up with a more sophisticated example because I don’t know how to do error-handling in Scheme:
(g) in Racket causes my laptop to slow to a crawl, though it will eventually respond to a keyboard interrupt.
I don’t know if it’s even possible to state this problem in statically-typed languages like Haskell and Rust.
2 I’ve seen the printed number get as high as 269, but that might be platform-dependent.