Function Calls and the Call Stack

Previously, we saw a basic machine model in which the program places each object at a different location in memory. We now examine a more structured model, stack-based memory management, that is used by many language implementations.

In most implementations, the data for a function call are collectively stored within an activation record, which contains space for each of the function’s parameters and local variables, temporary objects, the return address, and other items that are needed by the function. In this course, we will generally only consider the parameters and local variables in an activation record, ignoring the other pieces of data there.

In stack-based memory management, activation records are stored in a data structure called a stack. A stack works just like a stack of pancakes: when a new pancake is made, it is placed on top of the stack, and when a pancake is removed from the stack, it is the top pancake that is taken off. Thus, the last pancake to be made is the first to be eaten, resulting in last-in, first-out (LIFO) behavior. Activation records are similarly stored: when an activation record is created, it is placed on top of the stack, and the first activation record to be destroyed is the last one that was created. This gives rise to an equivalent term stack frame for an activation record.

As an example, consider the following program:

void bar() {
}

void foo() {
  bar();
}

int main() {
  foo();
}

When the program is run, the main() function is called, so an activation record is created and added to the top of the stack. Then main() calls foo(), which places an activation record for foo() on the top of the stack. Then bar() is called, so its activation record is put on the stack. When bar() returns, its activation record is removed from the stack. Then foo() completes, removing its activation record. Finally, the activation record for main() is destroyed when the function returns. Figure 6 shows the state of the stack after each call and return.

Figure 6 A stack that stores activation records.

In many implementations, the stack is actually stored upside down in memory, so that it grows downward rather than upward as shown in Figure 7. However, it still has the same LIFO behavior as a right-side-up stack.

Figure 7 A stack that grows downward rather than upward.

As a more complex example, consider the following program:

int plus_one(int x) {
  return x + 1;
}

int plus_two(int x) {
  return plus_one(x + 1);
}

int main() {
  int result = 0;
  result = plus_one(0);
  result = plus_two(result);
  cout << result;             // prints 3
}

At program startup, the main() function is called, creating an activation record that holds the single local variable result. The declaration of result initializes its value to 0, and the program proceeds to call plus_one(0). This creates an activation record for plus_one() that holds the parameter x. The program initializes the value of x to the argument value 0 and runs the body of plus_one(). The body computes the value of x + 1 by obtaining the value of x and adding 1 to it, resulting in a value of 1, which the function then returns. The return value replaces the original call to plus_one(0), and the activation record for plus_one is discarded before main() proceeds. The code then assigns the return value of 1 to result. Figure 8 illustrates the activation records up to this point.

Figure 8 Activation record for plus_one().

The program then proceeds to call plus_two(result). First, result is evaluated to obtain the value 1. Then an activation record is created for plus_two(), with space for its parameter x. Observe that this activation record is located in memory where the previous activation record for plus_one() was – the latter is no longer in use, so the memory can be reused. After the new activation record is created, the parameter x is initialized with the argument value 1. Then the program runs the body of plus_two().

The body of plus_two() in turn calls plus_one(x + 1). This evaluates x + 1 to obtain the value 2, creates an activation record for plus_one(), initializes the value of x in the new activation record to be 2, and then runs the body of plus_one(). The state of memory at this point is shown in Figure 9.

Figure 9 State of stack in second call to plus_one().

Observe that the new activation record for plus_one() is distinct from the previous one – each invocation of a function gets its own activation record. In addition, there are now two variables x in the program. Within the scope of plus_one(), x refers to the object located in the activation record for plus_one(), and its value is 2. Within plus_two(), x refers to the object in the activation record for plus_two(), and its value is 1.

The invocation of plus_one() computes 3 as its return value, so that value replaces the call to plus_one(), and the activation record for plus_one() is discarded. plus_two() returns that same value 3, so the value 3 replaces the call to plus_two() in main(), and the activation record for plus_two() is discarded. Then main() proceeds to assign the value 3 to result and print it out. Finally, when main() returns, its activation record too is discarded.

Function-Call Process

To summarize, the following steps occur in a function call:

1. For pass-by-value parameters, the argument expressions are evaluated to obtain their values.

   For a pass-by-reference parameter, the corresponding argument expression is evaluated to obtain an object [1] rather than its value.

   [1]

   C++ allows references to const to bind to values (i.e. rvalues in programming-language terms) rather than objects (lvalues). So a reference of type const int & can bind to just the value 3, as in const int &ref = 3;.

   The order in which arguments are evaluated is unspecified in C++.

2. A new and unique activation record is created for the call, with space for the function’s parameters, local variables, and metadata. The activation record is pushed onto the stack.

3. The parameters are passed, using the corresponding arguments to initialize the parameters. For a pass-by-value parameter, the corresponding argument value is copied into the parameter. For a pass-by-reference parameter, the parameter is initialized as an alias of the argument object.

4. The body of the called function is run. This transfer of control is often called active flow, since the code actively tells the computer which function to run.

5. When the called function returns, if the function returns a value, that value replaces the function call in the caller.

6. The activation record for the called function is destroyed. In simple cases, implementations will generally just leave in memory what is already there, simply marking the memory as no longer in use.

7. Execution proceeds from the point of the function call in the caller. This transfer of control is often called passive flow, since the code does not explicitly tell the computer which function to run.

The following program is an example of pass by reference:

void swap(int &x, int &y) {
  int tmp = x;
  x = y;
  y = tmp;
}

int main() {
  int a = 3;
  int b = 7;
  cout << a << ", " << b << endl;  // prints 3, 7
  swap(a, b);
  cout << a << ", " << b << endl;  // prints 7, 3
}

The program starts by creating an activation record for main(), with space for the local variables a and b. It initializes a to 3 and b to 7 and then prints out their values. The program then calls swap(a, b), which evaluates the expressions a and b to obtain their objects, creates an activation record for swap(), and initializes the parameters from the argument objects. Since the two parameters are references, the activation record does not contain user-accessible memory for the parameters. (The metadata for the function, however, may include information about the parameters.) The activation record does contain explicit space for the local variable tmp, since it is not a reference. Figure 10 illustrates the activation record.

Figure 10 Activation record for a function that uses pass by reference.

Here, the reference parameters are depicted with a dotted line between the names and the objects they reference.

The program proceeds to run the body of swap(). First, tmp is initialized to the value of x – since x refers to the same object as a in main(), the value 3 of that object is copied into the memory for tmp. Then the assignment x = y copies the value 7 from the object associated with y (b in main()) to the object associated with x (a in main()). Finally, the assignment y = tmp copies the value 3 from tmp into the object associated with y (b in main()). When swap() returns, its activation record is destroyed, and execution continues in main(). The latter prints out the new values of 7 and 3 for a and b, respectively.

Procedural Abstraction

Abstraction is the principle of separating what something is or does from how it does it. It is the primary tool for managing complexity in Computer Science and other fields. As a non-programming example, consider the task of making a sandwich. In order to make a sandwich, we don’t need to know how bread is made, nor peanut butter nor jelly. All we need to know is how to put those ingredients together to construct a sandwich. Thus, we rely on the abstractions of bread, peanut butter, and jelly to make a sandwich. Similarly, the person who eats our sandwich doesn’t need to know how it’s made – all they need to know is that it is a delicious sandwich.

Figure 11 Abstraction layers for making a sandwich.

In a complex system, there are multiple layers of abstraction, each of which relies on the “what” knowledge of the lower layers without needing to know the “how.” In the case of a sandwich, the top layer is the consumer of the sandwich, who only needs to know that it is a sandwich. The layer below is the maker of the sandwich, who needs to know what bread, peanut butter, and jelly are and how to combine them into a sandwich. They do not need to know how to make each of the ingredients. The jelly manufacturer needs to know how to combine fruit and other ingredients into a container and apply heat to make jelly. However, they do not need to know how to grow fruit. That’s a farmer’s job, who needs to know how to use plants, water, and pollinators in order to produce fruit.

Computer programs are similarly built using layers of abstraction. When it comes to computational procedures, functions are our mechanism for defining procedural abstractions. The user of a function need only know what the function does without caring about how the function accomplishes its task. Specifically, the user needs to know the interface of the function, including its actual code interface and the documentation of what the function does. The user does not need to concern themselves with the implementation of the function, the actual details of how the function works.

Code Organization in C++

In general, we organize a program by decomposing it into independent modules, defined in separate files. In C++, a single module is further decomposed into a header file and a source file. In this course, we will use the .hpp extension for header files and the .cpp extension for source files [2]. The header contains the interface of the module, while the source file contains the actual implementation.

[2]

The extensions .hxx and .h are other common conventions for header files, and .cxx and .cc are also common for source files.

As an example, the following is a subset of stats.hpp from Project 1:

#include <vector>

//REQUIRES: v is not empty
//EFFECTS: returns the arithmetic mean of the numbers in v
double mean(std::vector<double> v);

Only a declaration of the mean() function appears in the header, along with its documentation. The actual definition goes in stats.cpp, the source file for the module:

#include "stats.hpp"
#include "p1_library.hpp"

using namespace std;

double mean(vector<double> v) {
  return sum(v) / count(v);
}

Other source files that use the functions in the stats module need only include the header file (stats.hpp) with the #include directive:

#include <iostream>
#include "stats.hpp"

using namespace std;

int main() {
  vector<double> data = { 1, 2, 3 };
  cout << mean(data) << endl;
}

A source file that uses the stats module only needs to know about the interface of the module. As long as the interface remains the same, the implementation of a module can change arbitrarily without affecting the behavior of a source file that uses it.

The #include directive actually pulls in the code from the target into the current file. So the end result is as if the declarations for the stats functions actually were written in this source file as well. We get access to those functions’ declarations without having to manually repeat them.

Library modules such as vector and iostream are surrounded by angle brackets (e.g. #include <vector>) in a #include directive. Non-library headers that are located in the same directory are surrounded by double quotes (e.g. #include "stats.hpp"). For the purposes of this course, we never #include anything other than header files and standard libraries – we never #include a .cpp source file.

The using namespace std; directive allows us to refer to standard-library entities without prefixing them with std::. An alternative is to avoid the prefix for specific entities with individual using declarations:

#include <iostream>
#include "stats.hpp"

using std::cout;  // allow cout to be used without std::
using std::endl;  // allow endl to be used without std::

int main() {
  // must prefix vector with std::
  std::vector<double> data = { 1, 2, 3 };
  // can elide std:: with cout and endl
  cout << mean(data) << endl;
}

It is considered bad practice among C++ programmers to include a using namespace std; directive, or generally other using declarations, in a header file – this forces those directives and declarations on anyone who #includes the header. On the other hand, they are fine to place in a source file, since source files are generally not #included.

The overall file structure for Project 1 is shown in Figure 12, excluding testing modules.

Figure 12 File structure for Project 1.

Arrows are shown between header files and the source files that #include them.

When compiling the project, only source files are passed to the compiler. The header files are folding into the source files through the #include directives:

$ g++ --std=c++17 -pedantic -g -Wall -Werror p1_library.cpp stats.cpp main.cpp -o main.exe

Any number of source files can be passed to the compiler, but only one of those may contain a main() function.

The Compilation Process

Consider the compilation command above. The elements of the command are:

• g++ is the C++ compiler we are invoking.

• The --std=c++17 argument tells it to compile according to the C++17 language standard.

• The -pedantic argument tells the compiler to adhere strictly to the C++ standard. Without this flag, compilers often provide extensions or allow behavior that is not permitted by the standard.

• The -g argument tells the compiler to produce an executable that facilitates debugging.

• The -Wall argument asks the compiler to generate warnings about possible programming errors.

• The -Werror argument configures the compiler to treat warnings as errors, so that it does not compile code that has warnings.

• The arguments -o main.exe tell the compiler to produce the output file main.exe.

• The remaining three arguments are the source files for our program – p1_library.cpp, stats.cpp, and main.cpp.

For the source files, the compiler will compile each of them separately, producing temporary object files. It will then attempt to link the object files together into the output executable. The linking step can fail if:

• A function is declared and used in the source files, but no definition is found. For example, if the definition for percentile() is missing, a linker error such as the following results:

  Undefined symbols for architecture x86_64:
    "percentile(std::__1::vector<double, std::__1::allocator<double> >, double)", referenced from:
        _main in main-dc223c.o
  ld: symbol(s) not found for architecture x86_64
  clang: error: linker command failed with exit code 1 (use -v to see invocation)
  

• Multiple definitions of the same function are found. For example, if we try to compile and link multiple source files that define a main() function, we get a linker error like the following:

  duplicate symbol _main in:
      /var/folders/gc/0lqwygqx381fmx9hhvj0373h0000gp/T/main-9eba7c.o
      /var/folders/gc/0lqwygqx381fmx9hhvj0373h0000gp/T/stats_tests-b74225.o
  ld: 1 duplicate symbol for architecture x86_64
  clang: error: linker command failed with exit code 1 (use -v to see invocation)
  

Upon success, the result of the linking step is the final program executable, main.exe for the compilation command above.

Specification Comments (RMEs)

The interface of a function includes its signature, which consists of the function’s name and parameter types. The return type of the function [3] is also part of its interface.

[3]

Technically, the return type of a regular (i.e. non-template) function is not part of its signature as defined by the C++ standard (see [defns.signature] in the standard). It is, however, part of the function’s interface.

Another part of a function’s interface is documentation about what it does, as in the following:

//REQUIRES: v is not empty
//EFFECTS: returns the arithmetic mean of the numbers in v
double mean(std::vector<double> v);

This documentation describes the what of the function, so it is an integral part of what a user of the function needs to know.

The documentation format we use in this course is an RME, which consists of a REQUIRES clause, a MODIFIES clause, and an EFFECTS clause.

REQUIRES Clause

The REQUIRES clause lists what the function requires in order to accomplish its task. If the requirements are not met, then the function provides no guarantees – the behavior is undefined, and anything the function does (e.g. crashing your computer, stealing your credit-card info, etc.) is valid. Thus, a user should never call a function with arguments or in a state that violates the REQUIRES clause.

Within the function definition, the implementation is allowed to assume that the REQUIRES clause is met – again, a user should never call the function if they are violated. A good practice is to assert that the REQUIRES clause is met, if it is possible to do so:

#include <cassert>
#include "stats.hpp"
#include "p1_library.hpp"

using namespace std;

double mean(vector<double> v) {
  assert(!v.empty());
  return sum(v) / count(v);
}

In order to use assert, the <cassert> header must be included. Then a boolean expression can be passed to assert. If the expression evaluates to a true value, execution proceeds normally. However, if it evaluates to a false value, then the program crashes with a meaningful error message:

Assertion failed: (!v.empty()), function mean, file stats.cpp, line 8.

This is much more desirable than computing a wrong answer (or stealing your credit-card info!), as it tells the user they did something wrong and where the requirements were violated.

If a function doesn’t have any requirements, the REQUIRES clause may be elided. Such a function is called complete, while one that has requirements is called partial.

MODIFIES Clause

The MODIFIES clause specifies the entities outside the function that might be modified by it. This includes pass-by-reference parameters, global variables (not in this course – only global constants are permitted), and input and output streams (e.g. cout, cin, a file stream, etc.):

//MODIFIES: v
//EFFECTS: sorts v in ascending order
void sort(std::vector<double> &v);

The MODIFIES clause only specifies what entities may be modified, leaving out any details about what those modifications actually might be. The latter is the job of the EFFECTS clause. Instead, the purpose of the MODIFIES clause is for the user to quickly tell what items might be modified.

If no non-local entities are modified, the MODIFIES clause may be elided.

EFFECTS Clause

The EFFECTS clause specifies what the function actually does. This includes details about what modifications are made, if any, as well as what the return value means, if there is one. All functions should have an EFFECTS clause – if a function does nothing, there is no point to writing the function.

The EFFECTS clause should generally only indicate what the function does without getting into implementation details (the how). It is part of the interface of a function, so it should not be affected if the implementation were to change.

Properties of Procedural Abstraction

As mentioned previously, the implementation of an abstraction should be able to change without affecting the way the abstraction is used. More formally, abstractions are substitutable – we should be able to swap out an implementation of an abstraction for a different one. As long as the interface remains the same, code that uses the abstraction will still work.

Abstractions should also be local, meaning that it should be possible to understand the implementation of one abstraction without knowing anything about the implementation of other abstractions. This implies that the implementation of one abstraction should not rely on implementation details of another – instead, the former should only work with the latter through the interface of the latter.

Testing

Testing is the primary mechanism we have for determining whether or not code is correct. Most programs are too complex to formally prove correct with reasonable effort. Instead, thorough testing provides a measure of confidence that the code behaves correctly.

Insufficient testing can lead to code that breaks when deployed, with potentially disastrous consequences. A canonical example is the Therac-25, a radiation-therapy machine from the 1980s. A combination of poor design and software bugs led to several cases where patients received massive radiation overdoses. Three patients died as a result. A more recent example of software bugs leading to catastrophic failure is Knight Capital Group, a financial-services firm that engaged in high-frequency trading. Lack of regression testing, poor software maintenance, and a mistake in deployment caused a new version of their software to execute millions of trades that bought shares at high prices and sold them at lower ones – all in a span of just 45 minutes. The end result was a pre-tax loss of $440 million, and the company was forced to sell itself to a competitor.

In this course, the stakes aren’t quite as high as in the cases above. However, it is often the case that the difference between doing poorly on a project and doing well is how well you test your code. Testing is the mechanism for determining whether or not code is buggy. Once a bug has been detected, debugging is the process used to identify and fix the source of the bug.

There are two main categories of test cases:

• Unit tests test once piece of code at a time, often at the granularity of individual functions or small groups of functions. This helps to find bugs early as well as make them easier to debug, since a failed unit test identifies exactly which function is broken.

• System tests test an entire module or program as a whole. This can identify bugs that occur when integrating multiple units together – it’s possible that two units appear to work individually, but one unit makes an incorrect assumption about the other that only manifests when they are tested together. System tests can also be closer to the real use case of a program, providing a measure of confidence that the program works as a whole.

In software development, it is important to maintain a set of regression tests, or tests that are run every time a code change is made. That way, a breaking change is identified immediately and can be fixed before the software is deployed. Regression tests generally include both unit and system tests.

Test-driven development is a common programming practice that integrates writing tests with developing the implementation of a program. Once the interface of a unit has been determined, tests can be written even before the implementation – that way, once the implementation is written, there are tests that can be run immediately. Furthermore, the process of writing tests can help inform the right strategy to use in implementation, reducing development time. The implementation in turn inspires new test cases, based on an understanding of what mistakes could have been made in the code. The result is an iterative process: writing tests for a unit, implementing the unit, writing more tests, fixing bugs, and so on until the code has been thoroughly vetted.

Only valid test cases should be written. Those that don’t compile are useless, as well as those that result in undefined behavior (e.g. by violating the REQUIRES clause of a function). There are several types of valid test cases:

• Simple test cases are for the “average” case. For instance, in testing a mode() function in Project 1, an example of a simple test case is one that tests a vector that contains exactly one mode (e.g. { 1, 2, 3, 2 }).

• Edge cases are those that test special cases in a unit’s behavior. For instance, the mode() function requires that its argument vector be non-empty. Thus, the smallest vector that can be passed to mode() is one with a single element – this is an edge case. Another special case is when the input has two modes – in this case, the documentation of the function specifies that it returns the smaller one. So we should test that the function indeed behaves correctly in this case.

• Stress tests are intensive tests that ensure that a system will work under a heavy load. For example, an autograder for a 1000-person course should be able to withstand hundreds of students trying to submit right before the deadline. Thus, it is important to test the autograder with large numbers of concurrent requests. Stress tests will not be used in this course, since the projects we will focus on are not performance-critical.

Test cases should focus on cases that realistically could be erroneous. For example, a malicious programmer could insert a bug that only occurs for a specific, arbitrary input (e.g. if the number 42 is in the input). However, we generally can’t test every possible input, so we have to concentrate on those cases where a reasonable programmer could make a mistake. (Other mechanisms, such as code reviews, are used to guard against malicious programmers.)

The small scope hypothesis states that thorough testing with “small” test cases is sufficient to catch most bugs in a system [4]. Thus, our test cases need not be large – in general, they should be small enough where we can compute the expected results by hand. Similarly, having more test cases is not necessarily better. Fewer test cases that are meaningfully different is more effective than having many, redundant test cases. As an example, the data sets { 1, 1, 2, 2, 2 } and { 1, 1, 2, 2, 2, 2 } are not meaningfully different for the mode() function – there is no good reason why it would behave differently in the two cases. On the other hand, the data set { 1, 1, 2, 2 } is meaningfully different, since it contains two modes.

[4]

See Evaluating the “Small Scope Hypothesis” by Andoni et al. and On the Small-Scope Hypothesis for Testing Answer-Set Programs by Oetsch et al. for empirical evaluations of the hypothesis.