Sequential Computational Model

A function call can be described as a change of execution of instructions to the execution of instructions of the called functions, and where the arguments of the function call are made available to the called function. After the execution of instructions of the called function is finished, the result is made available at the point of the function call, and the execution of instructions prior to the change is continued.

Sequential Function Execution

A function call is implemented in the machine model using some convention. Usually that involves a stack for storing the information that is to be exchanged between caller and function. Below we describe such a scheme that is based on a calling sequence described in ''The C Language Calling Sequence'' (S.C. Johnson and D.M. Ritchie, Computing Science Technical Report No. 102, Bell Laboratories, September 1981) and the generated assembly code of some C compilers.

1. The arguments for the function are pushed onto the stack.
2. The return address is pushed onto the stack.
3. Control is passed to the function by setting the program counter to the start of the function.
   1. The contents of registers used inside the function are saved on the stack.
   2. Stack space is allocated for local variables of the function.
   3. The body of the function is executed.
   4. The return value is stored somewhere on the stack so that it can be obtained by the caller.
   5. Stack space is freed and register values are restored.
   6. The return address is popped of the stack.
   7. Control is given back to the caller by setting the program counter to the return address.
4. The return value is taken from the stack.
5. All the values that had been pushed onto the stack are now popped from the stack and execution continues.

The use of a stack in the above scheme makes the recursive calls of functions possible. There is no special mechanism involved that takes care of the function call. Instead, the instructions for handling the function call are put inline with the other instructions.

Generic Sequential Function Execution

In the scheme described above, the data on the stack is usually accessed through the register called stack pointer. The part of the stack that contains the data for a particular function call is called a stack frame, and holds the arguments for the function, the return address, and the local variables of the function. Alternatively, such a frame may be accessed through a special register called frame pointer pointing to the position of the frame on the stack, to allow for manipulation of the stack pointer during execution of the function.

We can describe this more general without the use of a stack.

1. The arguments for the function and the return address are put in a frame.
2. The frame is saved in a place that is available to the function.
3. An environment for the function is set up.
4. Control is passed to the called function.
   1. The function builds up its own frame for storing local variables and saving contents of registes used inside the function.
   2. Arguments are taken from the frame.
   3. The body of the function is executed.
   4. The return value is saved in the frame of the caller.
   5. The function disposes it own frame.
   6. The return address is taken from the frame and control is given back to the caller.
5. The environment for the functio is taken down.
6. The return value is taken from the frame.
7. The frame is disposed off.

Although it is called a stack frame, the actual use of a stack is not necessary in the scheme. The frame can be communicated to the function by pushing it onto the stack as a whole, but alternatvies are also possible, such as communicating only the location of the frame through the stack or using a dedicated register for this.

Abstract Sequential Function Call

Using the generic model above, we can obtain an abstract model that hides the details of how a function call is implemented. From the caller's viewpoint in abstraction the call of the function can be seen as making the arguments available to the function. Making a similar abstraction on the function side the following scheme results.

1. Caller makes arguments and return address available.
2. An environment for the function is set up.
3. Control is passed to the function.
   1. Function initializes.
   2. Function gets arguments.
   3. Function executes its body.
   4. Function makes return value available.
   5. Function cleans up.
   6. Control is given back.
4. Environment is take down.
5. Caller gets return value.

The model above abstracts from all possible details of implementation and focusses on the sequential computation of function call. This is the sequential computational model.