"The stack is one of those things that would fall under "support for common paradigms"."
Maybe for imperative languages where there is no support for lambda expressions (like C), but in Lisp or in functional languages call stacks are not part of the basic semantics. To put this in C terms, compilers for those languages will rewrite functions to take an extra argument called the "continuation", which is itself a pointer to a function, that is called when a function "returns." The result is that all function calls are tail calls, and by heap-allocating arguments and local variables (which is also necessary because it is possible to create and return a lexical closure), no call stack is needed (but you do wind up relying on a garbage collector). Other continuations are also used e.g. to support exceptions in Common Lisp.
Call stacks are almost always used in implementations of functional languages as well, even those that support first-class continuations. Even implementations that use CPS as you describe don't necessarily lose call-stack discipline (e.g. guile); that's a separate choice that some (e.g. SML/NJ) choose to make.
The call stack provides very cache-friendly and gc-friendly memory. It's still a very useful construct in functional languages.
Maybe for imperative languages where there is no support for lambda expressions (like C), but in Lisp or in functional languages call stacks are not part of the basic semantics. To put this in C terms, compilers for those languages will rewrite functions to take an extra argument called the "continuation", which is itself a pointer to a function, that is called when a function "returns." The result is that all function calls are tail calls, and by heap-allocating arguments and local variables (which is also necessary because it is possible to create and return a lexical closure), no call stack is needed (but you do wind up relying on a garbage collector). Other continuations are also used e.g. to support exceptions in Common Lisp.