Chapter 5: Functions and Function Calls | Memory as a Programming Concept in C and C++

Overview

System stack, activation frame, activation frame as the storage for local auto objects and for function arguments. Passing arguments by value as opposed to by reference. Calling sequence. Recursion and its relation to activation frames and the system stack. The price of recursion.

Any program of even modest complexity must be modularized for many reasons: readability, testability, validation, extendibility, maintainability, and many others, all outside the scope of this book. However, we assume that the reader understands that any reasonable programming language must allow for some modularization; C and C++ are no exceptions. Besides modularization on the level of source files, virtually the only modularization feature of C consists of structuring a program into separate functions. The object orientation of C++ allows for a more complex and far better-controlled modularization .

A C/C++ function is a programming module with a precisely defined interface that consists of the function's header, which specifies the function's name , the data types of the arguments (the input to the function - though it is possible for a function not to have any arguments), and the data type of a single return value (the output of the function; again, it is possible for a function to return nothing at all). Let us observe that computer scientists prefer to speak of procedures (if no value is returned) and functions (if a value is returned and the execution has no "side effects", meaning that it does not modify any data not local to the function). However, we shall employ the usual C/C++ terminology and call them all functions regardless of whether or not a value is returned or any side effects occur. Similarly, the input to procedures and functions are generally called parameters, yet we will use the more traditional C/C++ term arguments.

In this chapter we take a detailed look at the mechanism underlying the function calls, with our customary focus on the role of memory.

The most important aspect of a function call is the sequence of activities that take place or (more properly) the flow of control. This sequence can be described in broad terms as:

the instruction just before the call is executed,
the function is called and its body is executed, and
the instruction following the function call is executed,

and the execution of the program then continues in its customary top-down fashion. During a function call, control is passed to the callee (the function being called) and returned back to the caller (the function doing the calling) upon termination of the callee. This flow of control requires that the "execution environment" of the caller is somehow preserved and that the "execution environment" of the callee is somehow installed and used for the execution of the callee's body. On the termination of the callee, the execution environment of the callee is somehow disposed of and the previously preserved execution environment of the caller is reinstated. The flow of control during function calls is illustrated in Figure 5.1.

Figure 5.1: Flow of control during function calls

We are very much interested in the "execution environment" part, for it is intimately tied to memory. The data structure to hold the information of this environment is called an activation frame (or activation record ), since each call to (or invocation of) a function represents an activation of the function. A schematized activation frame is depicted in Figure 5.2.

Figure 5.2: A general activation frame

The returned value field is reserved for the value the function is returning, and this is where the value is stored prior to termination of the function. The actual arguments field holds the values of, or references to, "objects" being passed to the function. The optional control link field, if used, points to the activation frame of the caller, and the optional access link field, if needed, is used to refer to nonlocal data stored in other activation frames. The temporaries field holds temporary values (such as those arising from the evaluation of expressions); the saved machine status field holds the values of system registers (e.g., program counter) at the moment of the call; and, most interesting to us, the local data field is where all local "objects" are stored. The precise nature and layout of the activation frame depends on the particular compiler and is not really important to us.

Before we embark on a detailed discussion of the steps involved in a function call, the calling sequence and return sequence, we will discuss general allocation strategies for activation frames. Generally, there are three ways to allocate (create) the activation frames.

Static allocation - lays out storage for the activation frame at compile time.
Dynamic allocation on the system heap - each activation frame is dynamically allocated on the system heap at run time during the actual function call.
Dynamic allocation on the system stack - same as above but with the system stack rather than the heap.

There are some trade-offs associated with each strategy. The static allocation has the advantage in the performance it facilitates: the compiler creates "empty" activation frames at compile time and, during the actual function call, only the relevant data are stored there, so the overhead of the function call remains low and thus enables very fast execution. The downside of static allocation is that multiple activations of the same function are not possible; in particular, recursion is not permitted. Fortran (up to the Fortran77 standard) allowed only static allocation of activation frames, but the later standards (Fortran87, 88, 89, now known under the umbrella term of Fortran90) allow the programmer to choose whether a procedure is static or recursive. However, computationally intensive applications of an iterative nature (e.g., weather modeling or fluid dynamics modeling), colloquially referred to as "number crunching ", benefit from a low-overhead strategy; this is why languages with static allocation have their place in such applications.

Dynamic allocation on the system heap may cause the activation frame to "outlive" activation of the function itself or even the caller's activation. Yet for such languages the activation trees - which depict the way control enters and leaves activations or (more roughly ) the entering and exiting of functions during execution - do not correctly depict the flow of control, so this strategy is generally not used.

Allocation on the system stack benefits from the system stack functioning as a control stack of the function calls: the activation frame is pushed onto the stack when the function is invoked and popped from the stack when the function terminates. Thus, the top of the stack correctly reflects the flow of control and this approach neatly facilitates not only multiple activations of functions but also recursion in its most general form. The disadvantage of this approach lies in the significant overhead associated with (a) the dynamic creation of a new activation frame, (b) pushing it onto the system stack at the beginning of a function call, and (c) popping it from the stack upon termination of the function. Nonetheless, in most cases the trade-off is worthwhile: the slowdown in execution is more than compensated by the problem-solving power gained .

We can now reward the patient reader and reveal that C and C++ are languages that follow the third strategy of dynamic allocation of the activation frames on the system stack. As such, C/C++ allows multiple invocation of functions and, in particular, recursion. Unfortunately, we are still not ready to discuss the C/C++ calling and return sequences. We have one more topic to cover, namely, how arguments are passed to functions. Again, we first discuss general strategies.

In essence, the simplest possible method is call- by-value , or passing the arguments by value. Here the caller evaluates the arguments prior to the call and passes the values (copies) to the callee as the actual arguments. The advantage of this method is in the safety of "information hiding", for operations performed on the actual arguments do not affect the values in the activation frame of the caller. The disadvantage is the memory required for copies of values requiring large storage, such as complex structures and objects. The C language passes arguments exclusively in this way (well, almost exclusively - see the discussion of arrays in Chapters 6 and 7); C++ also uses call-by-value as its default call method.

In call-by-reference (also known as call-by-address or call-by-location ), arguments are passed by reference (also known as passing by address or by location ). In this case a reference (address, location, pointer, etc.) of the argument is passed to the function. Of course, this means the argument must have a reference and, if an expression, the argument must evaluate to a reference. The advantage of this method is lower overhead for the call (no need to copy the values) and lower memory requirements, especially if we are passing arguments requiring large storage. The disadvantage is that the callee can modify data from the caller's activation frame, with possibly serious implications. (See Chapters 6 and 7 for a discussion of why arrays are in fact passed by reference.) In C++ the programmer is allowed to state explicitly that an argument should be passed by reference.

The other two generally used methods are copy-restore and call-by-name. We may briefly describe copy-restore as follows : First, use copies of arguments as in call-by-value; then, at termination of the function, use the newly computed values as replacements for the values of the original arguments. This "feels" like a call-by-reference, but it poses some quirky and subtle problems. The call-by-name method has probably been encountered by the reader in C/C++ macro-expansion or in ANSI C and C++ inlining. Both of these calling methods lie outside our present interests.

We are finally ready to tackle the calling and return sequences. The actual details depend on the compiler being used (as does the detailed structure of the activation frame), but for our purposes a broad description will suffice. Some of the steps are performed by the caller, whereas others are performed by the callee. This division is to some degree arbitrary and may depend on such factors as the operating system, the target platform, and so forth. However, in our discussion, "who does what" is less important than "what must be done".

Here is the calling sequence.

The activation frame for the callee is created by the caller.
The arguments are evaluated by the caller. For an argument, if passing by value is required, then the value of the argument is stored in the "actual arguments" field; if if passing by reference is required, the pointer to the argument is stored there.
The callee saves the machine's status in its activation frame - in particular, the value of the program counter that indicates which instruction should be executed next (i.e., the one right after the call).
The callee initializes its local data and starts executing.

The return sequence proceeds as follows.

The callee stores the return value in the "returned value" field in its activation frame.
The callee uses the information from the "saved machine status" field and restores the registers for the caller; this includes popping the system stack.
The callee branches to the return address of the caller.
The caller copies the returned value from the activation frame of the callee. Even though the system stack was "popped", the data is still there because we do not deallocate the memory but only manipulate the register that points to the top of the stack.
If a value is returned, then the caller uses it for evaluation of an expression and continues with its normal execution.

The reader may now better appreciate the overhead associated with dynamic function calls and start wondering whether recursion is really worth the trouble. In the rest of this chapter we will examine recursion in more detail and attempt to persuade the reader that it is worth the cost.

Let us consider a simple C++ program:

 #include <iostream.h> #define dot 1 #define id 2 #define error 3 int A(char*,int&); int B(char*,int&); int Next(char*,int&); // function main ------------------------------ int main() { int sp = 0;    char s[]="..a..";    if (A(s,sp))      cout << "syntax correct\n";    else      cout << "syntax error\n";    return 0; }//end main // function A --------------------------------- int A(char* s,int& sp) {    if (!B(s,sp))      return 0;    if (Next(s,sp) != id)      return 0;    if (!B(s,sp))      return 0;    return 1; }//end A // function B --------------------------------- int B(char* s,int& sp) {    int sp1 = sp;    if (Next(s,sp) != dot) {      sp = sp1;      return 1;    }    if (!B(s,sp)) {      sp = sp1;      return 1;    }    return 1; }//end B // function Next ------------------------------ int Next(char* s,int& sp) {    if (s[sp]=='.') {      sp++;      return dot;    }else if ('a'<=s[sp] && s[sp]<='c') {      while('a'<=s[sp] && s[sp]<='c') sp++;      return id;    }else      return error; }//end Next

The program is a recursive descent parser for a language that consists of strings in the form "a sequence of dots, possibly empty, followed by a sequence consisting of characters 'a' , 'b' , and 'c' , followed by a sequence of dots, possibly empty". For instance, "..a.." is a such a string. The input to the parser is a character string s (see more on strings in Chapter 6), and sp is the string position variable, which keeps track of how much of the input has been consumed. The function Next() is the "scanner" of this parser, and it returns:

a "token" dot if it has recognized and consumed '.' on the input;
a "token" id if it has recognized and consumed a string consisting of characters 'a' , 'b' , and 'c' on the input; or
a "token" error in all other cases.

If the input string is from the language, the program displays a syntax correct message and exits; otherwise , it displays a syntax error message and exits.

Let us discuss the program as it is running. We will take "snapshots" of the system stack at various times to illustrate how the stack controls the execution and keeps track of the recursion. All the functions involved, except main() , have two arguments passed by reference: the input string s and the string position indicator sp . The function B() has, in addition, a local variable sp1 . Hence these three arguments are depicted in the schematic activation frames.

In the function main() , a local variable s (a character array) is initialized and holds a string "..a.." while another local variable sp is set to 0. Then A() is called:

The activation frame for A() is created and pushed on the system stack (the arrows indicate the "reference"), and A() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes s[0] (the first '.' ), updates sp (in the activation frame of main() as sp is passed by reference), and returns dot :

Back to B() , B() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes s[1] (the second '.' ), updates sp , and returns dot :

Back to B() , B() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes s[2] ( 'a' ), updates sp , and returns id :

B() does not like id returned by Next() , restores sp to 2, and returns 1:

Back to B() , it has finished its job and returns 1:

Back to A() , A() calls Next() :

Next() consumes s[2] ( 'a' ), updates sp , and returns id :

Back to A() , A() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes s[3] , updates sp , and returns dot :

Back to B() , B() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes sp[4] , updates sp to 5, and returns dot :

Back to B() , B() calls B() :

B() saves sp in sp1 and calls Next() :

Next() consumes s[5] , updates sp to 6, and returns error :

Back to B() , B() does not like the value error returned by Next() , restores sp to 5, and returns 1:

Back to B() , B() returns 1:

Back to A() , A() returns 1:

Back to main() , main() displays syntax correct and exits:

The execution of the program is over.

So, is recursion worth the trouble? Obviously yes, for otherwise the programming language and compiler designers would not bother. We are not really trying to beg the question, so here is our real answer. There are many areas in which recursion is a powerful and convenient tool: recursive descent parsers; implementation of backtracking algorithms; algorithms for data structures (this alone would be sufficient reason to use recursion; see Chapter 9); and, of course, the famous Hanoi towers puzzle and its (infamous?) recursive solution. It is a well-established mathematical fact that whatever can be achieved by recursion can also be achieved by plain old iteration (if you do not mind complex and messy programs). It is the clarity, simplicity, and convenience of recursive solutions that compel us to implement recursion in most general-purpose programming languages, including C and C++.