What does it really mean that a programming language is stackless?

Question

According to this answer

https://stackoverflow.com/questions/551950/what-stackless-programming-languages-are-available/671296#671296

all of these programming languages are stackless

• Stackless Python
• PyPy
• Lisp
• Scheme
• Tcl
• Lua
• Parrot VM

What does it really mean for them to be stackless? Does it mean they don't use a call stack? If they don't use a call stack, what do they use?

Answer 1

What does it really mean for them to be stackless? Does it mean they don't use a call stack?

Yes, that's about right.

If they don't use a call stack, what do they use?

The exact implementation will, of course, vary from language to language. In Stackless Python, there's a dispatcher which starts the Python interpreter using the topmost frame and its results. The interpreter processes opcodes as needed one at a time until it reaches a CALL_FUNCTION opcode, the signal that you're about to enter into a function. This causes the dispatcher to build a new frame with the relevant information and return to the dispatcher with the unwind flag. From there, the dispatcher begins anew, pointing the interpreter at the topmost frame.

Stackless languages eschew call stacks for a number of reasons, but in many cases it's used so that certain programming constructs become much easier to implement. The canonical one is continuations. Continuations are very powerful, very simple control structures that can represent any of the usual control structures you're probably already familiar with (while, do, if, switch, et cetera).

If that's confusing, you may want to try wrapping your head around the Wikipedia article, and in particular the cutesy continuation sandwich analogy:

Say you're in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there's a sandwich on the counter, and all the materials used to make it are gone. So you eat it.

Answer 2

They don't use a call stack, because they operate in continuation-passing style. If you're not familiar with tail call optimization, that's probably a good first step to understanding what this means.

To emulate the traditional call/return on this model, instead of pushing a return address and expecting the remainder of the frame to remain untouched the caller closes over the remainder of its code and any variables that are still needed (the rest are freed). It then performs a tail call to the callee, passing this continuation as an argument. When the callee "returns", it does so by calling this continuation, passing the return value as an argument to it.

As far as the above goes, it's merely a complicated way to do function calls. However, it generalizes very nicely to more complex scenarios:

1. exception/finally/etc blocks are very easily modeled - if you can pass one "return" continuation as an argument, you can pass 2 (or more) just as easily. lisp-y "condition handler" blocks (which may or may not return control to the caller) are also easy - pass a continuation for the remainder of this function, that might or might not be called.
2. Multiple return values are similarly made easy - pass several arguments on to the continuation.
3. Return temporaries/copying are no longer different than function argument passing. This often makes it easier to eliminate temporaries.
4. Tail recursion optimization is trivial - the caller simply passes on the "return" continuation it received rather than capturing a new one.