Is call stack compile time or runtime detail?

Question

I'm sorry if the question is quite naive, but I don't understand if a call stack is a language implementation detail or it depends on OS?

What I'm trying to understand is what decides how to store local variables and parameters of a function - the language's compiler or OS while running the application? Is it possible to write a C compiler, let's say, for Windows so that it won't be stack based? Or the language syntax dictates us that it must be stack-based language?

Sorry if I say something wrong, just trying to get the basic idea how everything works.

Answer 1

The architecture of a computer is where concepts like "heap" and "call stack" originate from. If you take a look at the C standard (http://www.iso-9899.info/wiki/The_Standard) you won't find anything about the stack or heap.

Compilers for a language like C can implement the specification in a number of ways in order to target specific architectures; even ones where memory is not organized in a stack, such as a "LISP cpu" (for example Sussman and Steele's: https://dspace.mit.edu/bitstream/handle/1721.1/5731/AIM-514.pdf?sequence=2) where memory is organized as linked lists.

Of course a language specification could define these things, but I am not aware of any language which goes so far. (The closest I can think of is forth.)

Operating systems and libraries can abstract away some of the details of the underlying architecture via system calls and apis.

Answer 2

The use (or not) of a stack is strictly a matter of the language's implementation. E.g. FORTRAN is (was?) carefully defined so that no recursion is allowed, and no stack is needed. If your FORTRAN compiler uses a stack (and allows recursion) or not is anybody's guess. If your CPU sports a stack, chances are your FORTRAN uses it (as it is the machine's standard/efficient way to manage routine calls). Lisp introduced recursion all over the place, even on machines that don't handle stacks natively.

The machine stacks you see in current CPUs were defined precisely to support Algol (and Pascal, and C, and ...) type languages with recursion easily (and efficiently).

The operating system has no say either way. And shouldn't, it better stay out of the user program's hair as far as possible.