Previous lesson Next lesson

---

Up to this point, we have discussed functions, parameters of functions, and local variables, and we had discussed that parameters and local variables require memory, but we have not discussed where this memory is allocated. In this topic, we will look at the ubiquitous call stack used to allocate memory for function calls.

A poor approach

Each function requires instructions that are executed. We could then pack these instructions together with data and space for any local variables:

Instruction

...

Constant 1

Constant 2

...

Parameter 1

Parameter 2

...

Local variable 1

Local variable 2

...

Let's consider the following program. The Gamma function $\Gamma(x)$ can be approximated on the interval $[1, 2]$ by the polynomial

$(1 - 2\gamma)x^3 + (9\gamma - 4) x^2 + (5 - 13\gamma) x + (6\gamma - 1)$

where $\gamma \approx 0.57721566490153286$. Two applications of this function in engineering are related to the mean time to failure of equipment and communication loads. Now, if $x > 2$, then $\Gamma(x) = (x - 1)\Gamma(x - 1)$, and if $x < 1$ then $\Gamma(x + 1)/x = \Gamma(x)$. We can implement this function as follows:

// Pre-process include directives
#include <iostream>
#include <cassert>

// Function declarations
int main();
double Gamma( double x );

// Function definitions
int main() {
    std::cout << gamma( 0.1 ) << std::endl;
    std::cout << gamma( 0.9 ) << std::endl;
    std::cout << gamma( 2.1 ) << std::endl;
    std::cout << gamma( 2.9 ) << std::endl;

    return 0;
}

double gamma( double x ) {
    if ( x > 2 ) {
        return gamma( x - 1 )*(x - 1);
    } else if ( x < 1 ) {
        return gamma( x + 1 )/x;
    }

    assert( (x >= 1.0) && (x <= 2.0) );

    // Approximation of gamma(x) on [1, 2]
    return ((
        -0.15443132980306572*x + 1.1949409841137957
    )*x - 2.5038036437199272)*x + 2.4632939894091972;
}

You can view this source code on repl.it.

If we try to calculate $\Gamma(2.1)$, this calls $\Gamma(1.1)$ and multiplies this result by $1.1$, and if we try to calculate $\Gamma(2.9)$, this calls $\Gamma(1.9)$ and multiplies this result by $1.9$.

If we used the above model for storing a function, where a single block of code is used to store all instructions, then this function would be represented by the following:

• A list of instructions.
• Four constants (being the coefficients of the polynomial).
• One parameter.
• No local variables.

This block may look something like the following:

FUNCTION gamma

LOAD x → D0

BRANCH D0 <= 2 goto FLAG_1

ADD '-1' + D0 → D1

STORE D1 → ARGUMENT

CALL gamma

LOAD RETURN-VALUE → D2

MULTIPLY D1 * D2 → D3

STORE D3 → RETURN-VALUE

RETURN-FROM-FUNCTION

FLAG_1: BRANCH D0 >= 1 goto FLAG_2

ADD '1' + DO → D1

STORE D1 → ARGUMENT

CALL gamma

LOAD RETURN-VALUE → D2

DIVIDE D2 / D0 → D3

STORE D3 → RETURN-VALUE

RETURN-FROM-FUNCTION

LOAD CONSTANT_0 → D1

MULTIPLY D0 * D1 → D2

LOAD CONSTANT_1 → D1

ADD D1 + D2 → D2

MULTIPLY D0 * D2 → D2

LOAD CONSTANT_2 → D1

ADD D1 + D2 → D2

MULTIPLY D0 * D2 → D2

LOAD CONSTANT_3 → D1

ADD D1 + D2 → D2

STORE D2 → RETURN-VALUE

RETURN-FROM-FUNCTION

CONSTANT_0: -0.15443132980306572

CONSTANT_1: 1.1949409841137957

CONSTANT_2: -2.5038036437199272

CONSTANT_3: 2.4632939894091972

x:

At this point in your undergraduate career, you do not need to understand the instructions (which you will see in your course on digital computers) or how these instructions are generated (which you will see in your course on compilers). What is important is where the argument.

Suppse we now call this with the argument 0.1. The call would place the value 0.1 in the field for x:

FUNCTION gamma

...(instructions for gamma)...

RETURN-FROM-FUNCTION

CONSTANT_0: -0.15443132980306572

CONSTANT_1: 1.1949409841137957

CONSTANT_2: -2.5038036437199272

CONSTANT_3: 2.4632939894091972

x: 0.1

The program would then add '1' to this argument and then call the function with that new value as an argument. Calling the function a second time would overwrite the 0.1 with 1.1. Now, the original value 0.1 is lost, so when we try to divide the result by 0.1, we no longer have access to that value.

A modern approach

In the above section, we describe why having fixed locations for parameters and local varaibles may be a serious problem: if we only ever call a function once, this will not be a problem, but we will see that many functions are recursive, meaning, they call themselves.

Consequently, we need a different approach. For this, we separate the instructions and constants (that which never changes) from the parameters and local variables:

FUNCTION gamma

...(instructions for gamma)...

RETURN-FROM-FUNCTION

CONSTANT_0: -0.15443132980306572

CONSTANT_1: 1.1949409841137957

CONSTANT_2: -2.5038036437199272

CONSTANT_3: 2.4632939894091972

...

FUNCTION main

...(instructions for main)...

STORE '0' → RETURN-VALUE

RETURN-FROM-FUNCTION

CONSTANT_0: 0.1

CONSTANT_1: 0.9

CONSTANT_2: 2.1

CONSTANT_3: 2.9

At the end of memory, we designate that the base of the call stack:

...

base of the call stack

The function main(), has no paraemters, but if it had four local variables, they would be allocated at the base:

...

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

Now, suppose you call a function from main() and want to call f( 3, 4 ). Those arguments would be placed on top of the stack:

...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

When we call the function f(...), it may have three local variables. Memory for those local variables is allotted for on the stack:

...

3rd local variable for f: ...

2nd local variable for f: ...

1st local variable for f: ...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

Suppose now that f calls a function g, and g has one parameter. Suppose the function call is g(3). In this case, the argument for g would also be placed on the call stack:

...

1st parameter for g: 2

3rd local variable for f: ...

2nd local variable for f: ...

1st local variable for f: ...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

Now, suppose that g has two local variables. For this specific call, the local variables would be stored on top of the stack again:

...

2nd local variable for g: ...

1st local variable for g: ...

1st parameter for g: 2

3rd local variable for f: ...

2nd local variable for f: ...

1st local variable for f: ...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

When a function returns, the memory previously used by the parameters and local variables is given up, and instead, the memory location of the first parameter is replaced with any return value. Thus, if g returns a value of 5, the call stack now looks like:

...

-

-

return value for g: 5

3rd local variable for f: ...

2nd local variable for f: ...

1st local variable for f: ...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

The function f can now access this return value and do something with it. The function f then continues to execute using its local variables:

...

-

-

-

3rd local variable for f: ...

2nd local variable for f: ...

1st local variable for f: ...

2nd parameter for f: 4

1st parameter for f: 3

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

Suppose now that f now returns with a value of 21. In this case, all the memory for the local variables and parameters of f is freed, and the return value is placed at the top of the stack:

...

-

-

-

-

-

-

-

return value for f: 21

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

The function main knows where to access this return value, and it can be either stored, printed, or used in a computation. Now main can continue executing:

...

-

-

-

-

-

-

-

-

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

Suppose now that main calls the function g directly. In this case, we could now reuse the memory on top of the call stack. The one argument being passed to g would now be placed on top of the call stack, so let us assume we call g(47) directly from main:

...

-

-

-

-

-

-

-

1st parameter for g: 47

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

In this case, the memory for the local variables in g is now allocated in the next two locations:

...

-

-

-

-

-

2nd local variable for g: ...

1st local variable for g: ...

1st parameter for g: 47

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

You will notice that the memory used on this second call to g reused the memory that was previously used by the call to f. When g finally returns, it dutifully places its return value on top of the stack, and returns back to main, and suppose that returned value is 99:

...

-

-

-

-

-

-

-

return value for g: 99

4th local variable for main: ...

3rd local variable for main: ...

2nd local variable for main: ...

1st local variable for main: ...

The function main has access to this returned value, and then main continues executing. Suppose main now executes return 0. In this case, the memory for all the local variables of main is freed, and the return value is placed on top of the stack:

...

-

-

-

-

-

-

-

-

-

-

-

return value for main: 0

You will learn more about the call stack and how it works in your course on digital computers. The call stack is actually more complex than we described above, as there must be more information stored with each function call:

• where the parameters actually are
• where to put the return value
• what instruction to continue executing when returning from a function call
• etc.

For now, however, what is important for you to understand is how the call stack grows with each new function call, and how it again shrinks when a function returns. Ultimately, there is a single value returned from main, and that value is used by the operating system.

A thought experiment revisited

What do you think happens when the following program is executed:

// Pre-processor include directives
#include <iostream>

// Function declarations
void f( int param );
int main();

// Function definitions

// f( int param )
//   - print out the uninitialized local variable 'loc'
//   - assign 'loc' the value of the parameter 'param'
void f( int param ) {
    int loc;   // Uninitialized!!!
    std::cout << loc << std::endl;
    loc = param + 1;
}

int main() {
    std::cout << "Hello world!" << std::endl;
    f( 42 );
    f( 91 );
    f( 150 );

    return 0;
} 

You can execute this program on repl.it.

When executed on one computer, the output is:

Hello world!
0
43
92

but when executed on a different computer, the output changes:

Hello world!
286223742
43
92

Indeed, each time I execute this code on repl.it, the integer printed immediately after Hello world! changes. However, the second time it is executed, default value of n is the previous parameter value. Let us see why this is the case:

To begin, main has no parameters or local variables. Thus, the call stack remains empty. When the first call to f( 42 ) is made, 42 is placed on the call stack:

...

param: 42

Now, when the function call occurs, memory is allocated for the local variable loc. Because it is not initailized, it takes on whatever value is located there:

...

loc: ????

param: 42

When f prints out loc, the mystery value is printed to the screen. The next command assigns loc = param + 1;, which overrites the unknown value with 43:

...

loc: 43

param: 42

The function f does not return anything, so it just returns back to main, which keeps executing:

...

43

42

You will notice, however, that the values on the stack were not cleaned up when f exited; instead, they were just left untouched.

Thus, the next we call f(91), so 91 is copied to the parameter location for the call to f:

...

43

param: 91

Next, the position immediately above the parameter is reserved for the local variable loc, but because that local variable is not being initialized, it keeps the value 43:

Now, when we print loc, we print the value that is there. Next, we assign the local variable the value of the paramter: loc = param + 1;, so the value stored in loc is updated:

...

loc: 92

param: 91

The function f returns, so we are now back in main, but the values remain there in the call stack:

...

92

91

Next, we call f( 150 ), which then places 150 in the place reserved for the parameter of f:

...

92

param: 150

When the function call is made, the next location is again reserved for the local variable loc, which, being uninitialized, takes on whatever value was there, in this case, 92.

...

loc: 92

param: 150

Next, we assign loc = param + 1;, so the value 151 overwrites the value stored in that location:

...

loc: 151

param: 150

The function f then returns, and finally, back in main, we execute return 0;, which places that return value on the call stack:

...

92

0

which is then accessible to the operating system when main returns.

Note: you may notice that we are ignoring how the std::cout statements work. We will see that much later in this course.

Assigning to parameters?

You may have noticed that parameters occupy memory in much the same way as local variables, so you may ask: if we can assign to local variables, can we not also assign to paramters? The answer is yes. For example, suppose we want to write a cosine function. We know from trigonometry that $\cos(-x) = \cos(x)$, so if the parameter is negative, we can just make it positive:

#include <iostream>
#include <cassert>

int main();
double fast_cos( double x );

int main() {
    std::cout << fast_cos( 0.1 ) << std::endl;
    std::cout << fast_cos( 1.5 ) << std::endl;

    return 0;
}

double fast_cos( double x ) {
    if ( x < 0 ) {
        x = -x;
    }

    // We are now guaranteed that x = |x|

    // This expression only approximates cos(x) for
    // values of 'x' in the interval [0, pi/2]
    assert( (x >= 0) && (x <= 1.5707963267948966) );

    return (
        0.11073981636184074*x - 0.57923443134047191
    )*x*x + 1.0;
}

You can execute this program on repl.it.

Questions and practice:

1. Go back to the $\Gamma$ function and calculate the following:

$\Gamma(1)$, $\Gamma(2)$, $\Gamma(3)$, $\Gamma(4)$, and $\Gamma(5)$. Do you recognize these values?

---

Previous lesson Next lesson