Models of Computation

This reading introduces two models of computation: one that will be familiar from CSC 151, and a second that aligns with how C (and your computer more generally) executes code. Understanding these models allows us to reason about our programs’ behavior without running them. This will come in handy on quizzes and exams in this course, but thinking through a computation in a way that aligns with C’s semantics is a powerful skill that will help you plan, write, and debug programs.

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. 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") has the effect of printing the text "hello world" to the console. Calling the printf function also happens to produce a value (the number of characters printed) but we often ignore this result.

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

• Variable declaration.
• Variable assignment.
• Printing to the console.
• Reading from or writing to a file.
• Receiving data from the network.

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

The Substitution 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:

-->   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 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 (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 float. In the first case, we lose precision—the fractional value .5 is lost—whereas in the second case, we get the exact answer. For this reason, C states the result of 3 + 3.5 is a float rather than an int. Likewise, if we simply assign an int to a float variable, e.g., float 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 (float)3 produces the value 3.0 of type float. Note that casts have higher precedence than arithmetic operators, so 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 because 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 result. This is unsuitable if we want to retain the fractional portion of the result.

The following expression, which includes a cast, also loses the fractional portion of the result:

(float)((x + y + z) / 3)

Why? Because the cast occurs after the division has taken place. To fix this we need to introduce a float conversion before the division occurs. The following expressions all work identically:

(x + y + z) / 3.0
(x + y + z) / (float)3
(float)(x + y + z) / 3
(x + (float)y + z) / 3

In every case, the result is a floating point value that includes any fractional part of the average of x, y, and z.

The Stack Model

Functional languages, like the one you used in CSC 151, use expressions almost exclusively. For these languages, the substitution model aligns well with the actual computation a program will perform.

But for C (and other imperative languages) substitution is not enough to understand computation. We can use substitution for expressions, but not statements. This is because statements have side effects, which 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);

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 start assigning new values to variables. 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. Conditional statements make things even more complicated:

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, often called a program counter;
2. a collection of stack frames, which captures the set of functions currently being executed;
3. within each stack frame, the values of local variables from that function; and
4. the active stack frame, which corresponds to the function that is currently running.

An Example

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

1
2
3
4
5
6
7
8
9
10

          
          

            
void printNum() {
  int y = 5;
  printf("%d\n", y);
}

int main() {
  int x = 0;
  printNum();
  return 0;
}

          
        
      
    
  

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

Program Counter: 7

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

The program counter is the current line we will execute. Because our program starts in main, we start execution of the program with the first statement of main at line seven. 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 seven , we execute a variable declaration that adds the local variable to main’s stack frame. We then update our state to:

Program Counter: 8

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

On line eight, we execute a function call, which causes the execution of the program to jump to printNum. The function call has three important effects on the stack representation:

1. We add a return address to main’s stack frame. The return address is the statement that will run after printNum finishes.
2. We add a stack frame for printNum.
3. The program counter is changed to the first line of printNum.

Program Counter: 2

The Stack
=========
--- main
  x [0]
  Return Address: 9
--- printNum
  (empty)

We say that printNum is the active stack frame. Even though we often draw frames with the active frame at the bottom, you will sometimes hear this referred to as the “top” of the stack; This isn’t because computer scientists don’t know the difference between up and down. The source of this confusion relates to the way the stack is actually placed in memory on most computer systems.

While printNum is the active frame, the execution of main is suspended. 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). Data structures with this property are often referred to as last-in, first-out (LIFO).

On line two, we execute another local variable declaration that allocates y within the active stack frame. That changes the program to the following state:

Program Counter: 3

The Stack
=========
--- main
  x [0]
  Return Address: 9
--- printNum
  y [5]

On line three, 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: 4

The Stack
=========
--- main
  x [0]
  Return Address: 9
--- printNum
  y [5]

Output
======
5

Executing printf will produce output, changing the state of the computer where this program is running. We show this output below the stack.

Line four ends the printNum function, so we return from printNum. Returning from a function undoes the steps we followed for a function call:

1. Pop the active stack frame, which removes it from the stack (including its local variables).
2. Take the return address off the stack and set the program counter to the specified address.

Program Counter: 9

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

Output
======
5

The last line of main exits the function with a return statement. When we return from the main function the program’s execution 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() {
  // x is not visible here
}

void bar() {
  // x is not visible here
  int x = 0;
  // x is visible here, up 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 looking 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:

1
2
3
4
5
6
7
8
9
10



  
void foo() {
  int x = 5;
  printf("%d\n", x);
}

int main() {
  int x = 0;
  foo();
  return 0;
}

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

Program Counter: 3

The Stack
=========
--- main
  x [0]
  Return Address: 9
--- foo
  x [5]

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).

The scope of local variables is limited to the function where they are defined. 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.

Function Parameters

We’ll often want to write functions that take parameters. How can we extend our stack model to handle functions with parameters? We will base our example on the following C program:

1
2
3
4
5
6
7
8
9
10
11



  
void add(int a, int b) {
  int c = a + b;
  printf("%d plus %d is %d\n", a, b, c);
}

int main() {
  int x = 3;
  int y = 8;
  add(x, y+1);
  return 0;
}

The execution of this program will follow the model from earlier, starting at line 7 and running up until the program counter is at line 9. Here is the program state at that point:

Program Counter: 9

The Stack
=========
--- main
  x [3]
  y [8]

Now it is time to issue the function call to add, but this time the function takes parameters. We can extend our list of steps for issuing a function call to handle parameters, with the new step highlighted below:

1. Add a return address to the caller’s stack frame
2. Create a stack frame for the callee (the function being called)
3. Add values for each of the callee’s parameters to the new stack frame.
4. Set the program counter to the start of the function.

To perform step 3 we will need to know the values we assign to the function’s parameters. The value of the first parameter is just x, so we can look that up in main’s stack frame. But the second parameter is an expression, y+1, that must be evaluated first. We can evaluate that expression (as well as the one that was just x) using the substitution model, which gives us the result 9.

At this point, we can issue the function call, which brings us to the following state:

Program Counter: 2

The Stack
=========
--- main
  x [3]
  y [8]
  Return Address: 10
--- add
  a [3]
  b [9]

The add function will evaluate the same way previous function calls did:

Program Counter: 3

The Stack
=========
--- main
  x [3]
  y [8]
  Return Address: 10
--- add
  a [3]
  b [9]
  c [12]

followed by:

Program Counter: 4

The Stack
=========
--- main
  x [3]
  y [8]
  Return Address: 10
--- add
  a [3]
  b [9]
  c [12]

Output
======
3 plus 9 is 12

At this point, we pop add’s stack frame and return to main. The program state at this point looks like this:

Program Counter: 10

The Stack
=========
--- main
  x [3]
  y [8]

Output
======
3 plus 9 is 12

Notice that the function call didn’t change anything in main’s stack frame. That would be true even if add used parameter names x and y instead of a and b. The scoping rules for parameters are the same as for local variables; we only ever look up names in the active stack frame.

Return Values

The final detail we’ll add to our stack model is support for functions that return values. We will use a sample program that is similar to the previous example, but in this version, the add function adds two numbers together and returns the result instead of printing it:

1
2
3
4
5
6
7
8
9
10
11



  
void add(int a, int b) {
  return a + b;
}

int main() {
  int x = 3;
  int y = 8;
  int z = add(x, y+1);
  printf("%d plus %d is %d\n", x, y, z);
  return 0;
}

The program’s execution matches the previous example up until it reaches this state:

Program Counter: 8

The Stack
=========
--- main
  x [3]
  y [8]

Running line 8 requires two things to happen: we need to reserve space for a variable z in main’s stack frame, and we need to call the add function to find out what value to assign to z. C will determine a value for z first, so we’ll proceed with the function call. Making that call takes us to this state:

Program Counter: 2

The Stack
=========
--- main
  x [3]
  y [8]
  Return Address: 8*
-- add
  a [3]
  b [9]

Notice that the return address still points at line 8, although this has been flagged with an asterisk. That’s required because we haven’t finished executing that line of code yet. There’s some imprecision here since it’s not entirely clear where on line 8 we need to resume after add returns. That’s okay for our mental model, but an actual execution will break the line into two steps: one that calls add, and a second that stores the result in a space reserved for z. The return address would point to the second part of line 8 in this case.

The only line in the add function is a return statement. To execute this statement, we first need to evaluate the expression it returns (just like when we pass parameters to functions). Once that evaluation is complete, the return will pop the active stack frame and jump to the return address:

Program Counter: 8*

The Stack
=========
--- main
  x [3]
  y [8]

Remember we’re in the middle of line 8 at this point. We still need to determine the value to assign to z, but we’ve finished running the add function. We can borrow an idea from the substitution model at this point and swap the call to add(x, y+1) with the returned value, 12. That’s enough information to finish the line, which takes us to this state:

Program Counter: 9

The Stack
=========
--- main
  x [3]
  y [8]
  z [12]

From this point on the execution proceeds just as it did in our earlier examples, with a call to printf and a return from main that ends the program.

More Complicated Examples

You can probably come up with more complicated examples that combine elements from earlier examples. These more complicated examples might include:

• Expressions that use return values from more than one function call
• Functions that call the same function multiple times
• Calls to functions that use complex expressions to pass parameter values, possibly even including a nested function call, e.g. add(add(1, 2), 3).

While these examples add complexity, they don’t deviate from the general model of computation we’ve described here. Check your understanding of the stack model by working through programs that include one or more of the above features. You can always check your understanding of the model by running the program on an actual computer to confirm your results.