Does the OS create its own bootstrapped stack frame when running a program?

Question

I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main method of the program.

In other languages such as C, Java or even interpreted languages like PHP, does the OS/interpreter/VM automatically create its own first frame on the stack, and then invokes the main method of the program as a new second stack frame?

I'm trying to think about how initial arguments are passed to a program, and how programs are able to return values. Does each OS have a standard way of creating this initial stack frame which all languages adhere to? When I run a program from command prompt and pass it arguments, what is actually creating that initial stack frame that pushes these arguments onto the stack and that invokes my main method?

Answer 1

I have no idea how each system operates, and do not inquire since I usually do not need to know. However it seems rather easy to make an educated guess, based on whatever experience I have. There are many variants that exist. For example a program is often byte code to be interpreted by a virtual machine. It is all very flexible.

Usually, the program will have its own run time environment, for which some inital space can be allocated at the bottom of the stack, or anywhere else, since it will not have to move while the program executes, and also because it will exist in only one copy for a run of the program (it is not called recursively). But bottom of stack is probably simpler. Whether you want to consider that space as a frame or not is probably not very important. However, it may be simpler for the compiler/interpreter to maintain a structural consistency with frames at least for that part which may be visible to or accessed by the rest of the program, so that access is always done consistently.

This is set up by code inserted by the compiler in the compiled code (or linked to it), and is supposed to respect some standards of communication with the OS (operating system) it is intended for, so that data can be passed by the OS to the application, and returned from the application to the OS.

Such standards are usually OS dependant, and must be conformed to by the language compiler. The standard may simply imply agreement on the location were the information to be passed is stored, and possibly ways of specifying its size, upon call to or return from the program.

The stack of frame policy is needed for recursion, and it is possible only as long as you do not have functions (called also methods, sub-program, procedure ...) that can return functions as result. The first important recursive language with that property was Algol 60, and the stack of frames was invented for the implementation of Algol 60.

The stack of frame was invented to implement recursion. However it is useful even for allocating space to non-recursive function, as it is a convenient, simple, fast and easy way to allocate storage for the function only for the exact duration of that function execution.

Note that the stack policy no longer work as simply if functions can have functions as result. Then frames may have to be allocated on a heap (managed with a garbage collector) or occasionally transfered from the stack to the heap.

The OS does not create an initial frame, whether on stack or anywhere else. There must be a separation of responsibility. Some languages (at least older ones) do not even use frames, while others do use frames, but not organized as a stack. The role of the OS is to allocate some space for the program to run, to place the data to be passed to the program in some predetermined place in that space, and then to pass control to the program code (if compiled), or to the interpreter of the program (if interpreted) with a reference to the program as additional argument.

The code of the application program will then organize the allocated space, initialize what has to be, possibly move data passed by the OS in a more convenient location, etc, and then start with the code that is specific to the application, what you call main method or main program, thus creating its frame on the stack. This is usually done by a standard piece of code included by the compiler with proper parameters.

In the case of interpreted code, the program that is actually called is the interpreter, and the address of the program to be excuted is passed to it as additional data. The interpreter will organize the space, and reserve some for its own needs. Then it will start interpreting your main method/program, thus creating the stack frame for it.

But, as I said, there are many variants. Does this answer your question? or did I miss a point?

Answer 2

Simple: Check it. If you write a small C program, and compile to assembler (gcc -S ...), you'll see that C doesn't build a global frame.

But C programs aren't run just like that, the operating system really calls the ELF interpreter (here /usr/lib64/ld-2.18.so, see ld.so(8)), and that one starts the program itself. That one sets up the main() arguments, calls main(), collects what it returns, and hands it back.

If I remember correctly, the UCSD Pascal compiler did set up a stack frame for the program, just like a procedure/function. This simplifies the search for global variables (in Pascal you have a stack of nested procedures/functions, and in UCSD Pascal the search for global variables walks down the nesting frames using a static link pointer in each frame). Some Algol compilers used a display, an array of pointers to the frames at each nesting level, and had no specific global frame. This is harder to handle, but more efficient.

So the answer to your question is that it depends. In Algol-type languages (nested procedures) there might be a global frame or not. C-type languages (no nested environments) it isn't needed.