Mental Models of Computation

Introduction

To verify how our programs work, we can compile them, run the resulting executables, and check that they behave as expected. Testing is a powerful, direct method of program verification, but it can be insufficient or infeasible for a variety of reasons:

For these reasons, we would like alternative methods of verifying our programs that we can use in tandem with testing.

To this end, we introduce mental models of computation for C. A mental model of computation is simply a model of execution of our computer programs we can perform in our head or on paper. This allows us to quickly verify our programs—usually small pieces of it like an individual function—by hand. Furthermore, our mental models of computation closely aligns with the semantics of the C programming language, so understanding these models will, in turn, help us deeply understand C. Finally, our mental models of computation help us debug our code by giving us the ability to crisply describe what is going wrong in our programs.

Textbook Reading

Read the following textbook sections to give you important background and refreshers on the newer material below.

Expressions and Statements

Before we introduce the two models of computation that we will use in this course, we first review the two major syntactic categories in C: expressions and statements.

Expressions

Expressions in a programming language generalize arithmetic expressions found in mathematics. An expression is a language construct that evaluates to a value. For example, the expression 3 + 5 * 8 evaluates to 43. We know this via operator precedence, which tells us that multiplication must be carried out before addition. An expression is typically composed of sub-expressions, i.e.,, smaller expressions. In mathematics, we usually call these sub-expressions operands. 5 * 8, 3, 5, and 8 are all sub-expressions of the expression above. 43 is both an expression but also a value.

A value is an expression that takes no further steps of evaluation. An example of a floating-point value is 3.5. The string "hello world" is also a value.

Finally, types categorize sets of values as well as expressions. A type classifies a set of values. By extension a type also classifies expressions (by the type of value they produce). The expression 3 + 5 * 8 as well as its resulting value 43 have type int. Note that it is not always the case that an expression must be entirely composed of the same type. For example, comparison expressions such as x * 2 < 3 + 5 have int sub-expressions but the final computed value is a boolean.

Mathematics defines a series of operators and rules of precedence over them: +, -, *, /. Programming languages typically add many more operators that operate over different types, e.g., the mod operator %, boolean "and'' and "or'' operators && and ||, and boolean negation !. Boolean negation is an example of a unary operator, an operator that only takes a single argument. Function calls that return values, e.g., sqrt(2), are also operators where the arguments to the function are the operands.

Statements

In contrast to expressions, which perform computation via repeated evaluation, statements do not produce any values that can be used like an expression.

A statement is a program fragment that does not evaluate to a value but instead produces one or more side-effects, i.e. they do something. We cannot, for example, insert a variable declaration statement, e.g., int x = 5, into an addition expression because the declaration does not produce a value. Instead, it has the effect of creating a new variable x and assigning it the value 5. Likewise, printf("hello world") also does not produce any values¹ but has the effect of printing the text "hello world" to the console.

While expressions perform the actual computation in our program, effects are typically how we interact with the "outside world" with respect to our program. Examples of effects include:

The various statements in our programming language either perform these effects directly or manage the execution of statements in our program.

The Substitutive Model

The first model we discuss concerns expressions. An expression evaluates via repeated substitution, and our model mirrors this process exactly. For example, here is how the expression 

1 * 3 + 4 / 2 - 1
might evaluate step-by-step: 
    1 * 3 + 4 / 2 - 1
-->   3   + 4 / 2 - 1   [ evaluated 1 * 3 ]
-->   3   +   2   - 1   [ evaluated 4 / 2 ]
-->       5       - 1   [ evaluated 3 + 2 ]
-->         4           [ evaluated 5 - 1 ]

The process of evaluating an expression proceeds as follows:

  1. Find a next sub-expression to evaluate via operator precedence.
  2. Evaluate that sub-expression to a value.
  3. Substitute that sub-expression with its resulting value.
  4. Repeat the process until the overall expression is a value.

Note that above we said it might evaluate in this order. That's because strictly speaking, C does not specify the order in which sub-expressions are evaluated.

For the arithmetic operations that we are familiar with, this process is straightforward. However, things become trickier when we add in more operators. For example, how do we evaluate the following expression? 

3 * 5 > 4 || 3 > 8 / 2 && 3 < 5

It turns out that the arithmetic operations have higher precedence than the comparison operators, which have higher precedence than the logical operators. Finally, logical-and (i.e., &&) has strictly higher precedence than logical-or (||), so we have: 

     3 * 5 > 4 || 3 > 8 / 2 && 3 < 5
-->*   15  > 4 || 3 >   4   && 3 < 5
-->*     true  ||  false    && true
-->      true  ||      false
-->           true

Note that in the lines marked with an asterisk (*), we have evaluated all equal-precedence sub-expressions at once.

Section 4.4 of King provides a partial table of operator precedence and associativity (i.e., which direction operands are grouped from). The complete list is in Appendix A, and similar tables can also be found online. For ease of reading programs, I generally recommend that you use parentheses to make it clear how you, the program's author, intended that a complex expression be evaluated.

Implicit Conversions and Casting

Recall that there are two broad categories of primitive types in C—integral and floating-point types. A major difference within these categories is simply size. For example, a char often takes up one byte of memory whereas an int usually takes up four. When expressions of different types mix, e.g., 3 + 3.5, we must determine what is the output type to know what value the expression produces.

In general, C favors the type where no information will be lost. In the case of 3 + 3.5, the two sensible results are 6 of type int or 6.5 of type double. In the first case, we lose precision—namely the fractional value .5—whereas in the second case, we obtain the exact answer. For this reason, C states the result of 3 + 3.5 is a double rather than an int. Likewise, if we simply assign an int to a double variable, e.g., double x = 3, C automatically converts 3 to the floating-point value 3.0. These are examples of implicit conversions where C automatically takes a value and converts it to the appropriate destination type.

In addition to implicit conversions, we can also force conversions to occur through the cast operator, a unary operator (i.e., it takes a single argument) with the syntax: 

 (<type>) <expr>
where the <type> above is the target type of the cast and <expr> is the expression whose result will be converted. For example, the expression (double) 3 produces the value 3.0 of type double. Note that casts have higher precedence than the arithmetic operators, so that we need to parenthesize the expression appropriately if we wish to cast its overall value versus just a piece of it. For example: 
(int) 3.5 + 8.2   // produces 11.2, the cast associates with 3.5
(int) (3.5 + 8.2) // produces 11, the cast associates with the whole expression
We can use our mental model of computation to explain how computations involving implicit conversions and casts operate. A common example of this is an averaging calculation, e.g., between int variables x, y, and z: 
(x + y + z) / 3
If left alone, the computation of this expression will perform integer division in the final step, producing an int. This is unsuitable if we wanted to retain the fractional portion of the result. However, the following cast does not produce the desired result: 
(double) ((x + y + z) / 3)
Why? Because the cast occurs after the division has taken place. To remedy the situation, we need to introduce a double conversion before the division occurs. The following expressions all work identically: 
(x + y + z) / 3.0
(x + y + z) / (double) 3
(double) (x + y + z) / 3
(x + (double) y + z) / 3

The Stack Model

We use the substitutive model to describe how expressions evaluate, but we cannot use this model for statements. This is because side-effects are necessarily at odds with substitution. For example, consider the following sequence of statements: 

int x = 1;
printf("%d\n", x);
printf("%d\n", x+3);

For example, how do we handle a variable declaration statement using substitution? One thing we might try is substituting the value of the variable everywhere that variable occurs in the statements. For example, after executing the variable declaration, we would be left with the following statements to execute. 

printf("%d\n", 1);
printf("%d\n", 1+3);

This seems sensible. However, the approach begins to break down when we consider variable assignment in conjunction with declaration. For example, what if we had the following statements instead? 

int x = 1;
printf("%d\n", x);
x = 5;
printf("%d\n", x+3);

We can't simply substitute 1 for the occurrence of x in the second printf because of the intervening assignment to x. We can refine our approach to only substitute for x up until the point it is reassigned. However, in the presence of conditional statements, things get even more complicated. Consider the following. 

int x = 1;
// ...
if (y < 10) {
    x = 5;
}
printf("%d\n", x);

The assignment of 5 to x occurs only if we reach the conditional statement and y < 10. However, because there might be arbitrary code between the variable declaration and the conditional, we do not know at the point of the variable declaration whether we will enter the conditional and thus whether it is safe to substitute 1 for x in the printf below.

Rather than having to work out all these special cases, we instead use a different model of computation to model the execution of statements. This model, the stack model of computation, keeps track of the following:

  1. the current statement being executed;
  2. the stack of active stack frames, which encompass the functions that are currently being executed along with the values of their local variables; and
  3. the output of the program.

An Example

We illustrate the stack model of computation with an example. Consider the following C program. 

void                    //  1
printNum (void) {       //  2
    int y = 5;          //  3
    printf ("%d\n", y); //  4
}                       //  5
                        //  6
int                     //  7
main (void) {           //  8
    int x = 0;          //  9
    printNum();         // 10
    return 0;           // 11
}                       // 12

Execution of this program starts in main. Thus, we record the state of our computation as follows: 

Program Counter: 9

The Stack
=========
--- main
  (empty)

The program counter is the current line we will execute. (Note that eventhough the numbers are given after the line, we want the state BEFORE that line executes.) Because our program starts in main, we start execution of the program with the first statement of main at line nine. The stack records the active stack frames of the program. A stack frame records the name of the function call that is currently active with all the local variables declared so far in that function, along with their values. Initially, we do not have any local variables declared in main, so the stack frame corresponding to main is empty.

On line nine, we execute a variable declaration that adds the local variable to main's stack frame. We thus update our state as follows: 

Program Counter: 10

The Stack
=========
--- main
  x [0]

On line ten, we execute a function call, which causes execution of the program to jump to printNum. To record this, we add a new stack frame for printNum above main. The program counter is also changed to be the first line of printNum: 

Program Counter: 3

The Stack
=========
--- printNum
  (empty)
--- main
  x [0]

We say that printNum is the currently active stack frame because it is the top-most frame on the stack. In contrast, the execution of main is suspended, pending the execution of printNum, the function above it on the stack. The stack obtains its name from this arrangement of frames where new frames are placed on top of the stack and we remove frames from the stack starting from the top (like a stack of heavy plates). This is commonly referred to as first-in-last-out (FILO) behavior.

On line three, we execute another local variable declaration that allocates y within the currently active stack frame—printNum: 

Program Counter: 4

The Stack
=========
--- printNum
  y [5]
--- main
  x [0]

On line four, we execute printf, passing in the value of y. The value passed in is the currently-recorded value of y within printNum's stack frame, 5. 

Program Counter: 5

The Stack           Output
=========           ======
--- printNum        5
  y [5]
--- main
  x [0]

Line five ends the printNum function, so we return from printNum. To do this, we pop off the currently active stack frame from the top, which is printNum's stack frame. Popping a stack frame means that the frame is removed from the stack, including its local variables. Execution of the program continues on the line after the call of printNum in main. 

Program Counter: 11

The Stack           Output
=========           ======
--- main            5
  x [0]

The last line of main exits the function with a return statement, so execution of the program is complete!

Scoping and Variable Lookup

We say that the scope of a name, e.g., a variable or function, is the region of code in which it is valid to reference that name. For a variable declaration, we may reference a variable from its point of declaration to the close-curly braces that enclose the declaration. For example, the following code snippet outlines where the local variable x declared in bar is visible: 

void
foo (void) {
    /* x is not visible here */
}

void
bar (void) {
    /* x is not visible here */
    int x = 0;
    /* x is visible here, to the } below */
}

The scope of a variable in C is determined purely by the text of the source code. This is called lexical scope. The compiler determines whether all uses of names in our programs are legal and will reject any program (at compile time) that contains a reference to a name that is out of scope.

Assuming that a variable is visible within the current scope, we determine the value of the variable by lookup in the stack during program execution. Because the active stack frame allows us to discern which function call is active, the entry we look up is unambiguous. For example, consider the following code. 

void                    //  1
foo (void) {            //  2
    int x = 5;          //  3
    printf ("%d\n", x); //  4
}                       //  5
                        //  6
int                     //  7
main (void) {           //  8
    int x = 0;          //  9
    foo();              // 10
    return 0;           // 11
}                       // 12

Here, there are two declarations of variables named x, one in main and the other in foo Which one do we lookup on line four? Our mental model of computation at line four tells us! 

Program Counter: 4

The Stack
=========
--- foo
  x [5]
--- main
  x [0]

foo is the active stack frame, so we look up x's value in foo instead of main. Thus the printf produces 5 (hopefully as you expected).

In effect, local variable names, by definition, are scoped to their containing functions. This allows us to reuse local variable names in our functions without the need for coordinating names between all the functions that we have declared, which helps with procedural abstraction.

Self-Check Exercise

Consider the following program: 

void                    //  1
foo (void) {            //  2
    int x = 5;          //  3
    /* Point A */       //  4
    foo();              //  5
    printf ("%d\n", x); //  6
}                       //  7
                        //  8
int                     //  9
main (void) {           // 10
    foo ();             // 11
    return 0;           // 12
}                       // 13

Give the state of the computation (the program counter as well as the contents of the stack) at Point A */ outlined above. You may set the program counter to be one line after the comment.

Explain the behavior of this program using your model. What happens when this program executes? (Note: this program will compile and run, but it will eventually cause a runtime error ....).

Notes

  1. That's a bit of a lie. printf actually returns the number of characters printed to the console, but that value is very rarely used in practice, so we'll pretend its return type is void.
This is a derivative work of Mental Models of Computation, by Titus Klinge and Peter-Michael Osera, used under a Creative Commons Attribution-NonCommercial 4.0 license.