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.