Basics

Section 4.1 Basics

int factorial(int n) {
  int res;          /* declaration of a variable */
  res = 1;          /* statement: assignment expression */
  while (n > 1) {   /* statement: loop */
    res = res * n;  /* statement: assignment expression */
    n   = n - 1;    /* statement: assignment expression */
  }
  return res;       /* statement: return to caller */
}

int main() {
  int res;
  res = factorial(3);
  printf("%d\n", res);
  return 0;
}

Run

Listing 4.1.1. A C program consisting of two functions. It computes the factorial of 3 and writes it on the screen.

Subsection 4.1.1 Static Properties

Consider a first C program in Listing 4.1.1. We start by discussing its syntactical properties and the properties of the static semantics. These are properties that the program has, independently of any concrete input. They therefore do not concern individual program executions, but the structure of the program.

Every C program consists of at least one file. Each such file constitutes a translation unit.

In every translation unit, there is a list of declarations. Every declaration establishes a name, or identifier, for some entity. The letter sequences factorial, n, res, main, and printf in Listing 4.1.1 are identifiers. The other, highlighted words are keywords. They are markers for specific syntactic constructs (e.g., while) or are predefined identifiers (e.g., int). Identifiers can occur in two ways: defining and using. Our example shows a translation unit where two functions, factorial and main, are declared. The occurrence of factorial in line 1 is defining, as the identifier factorial is established for the function there, whereas the occurrence in line 12 is using, since factorial here refers to the previously defined function.

Remark 4.1.2.

Although the C language specification calls these constructs “functions”, they are not functions in the mathematical sense. Besides computing values, C's functions can affect memory and interact with the user. Executing a function twice with the same arguments can therefore easily result in different values. C's functions correspond to the subroutines that we have seen in Section 2.8

Consider first the function, factorial. The function declaration in line 1 establishes that factorial has a parameter n of the type int and the return type int. The function's code, its body, consists of a block: A sequence of statements enclosed in braces. Each statement that does not end itself with a nested block is terminated by a semicolon. Therefore, the outer block of our example program consists of four statements in the lines 2, 3, 4 and 8. The while-loop in line 4 is a statement that contains another, nested block with two more statements.

We separate statements into four categories: variable declarations, expressions, blocks, and control-flow constructs. We will discuss them in more detail in the following sections.

The first statement in factorial's body is a variable declaration. These always consist of a type, in this case int, and an identifier, here: res. The identifier that occurs in a variable declaration is called a variable. The occurrence of a variable in a declaration is defining. All other occurrences are using. The parameter n in line 1 is a variable as well.

Remark 4.1.3.

The term “variable” is not used consistently in literature. We follow the usual naming from mathematics, where the occurrence of a letter (sequence) in a term is called a variable. Nevertheless, the meaning of variables in imperative programs differs from mathematics, see Remark 4.3.3.

Every declaration has a scope. The scope of a declaration for an identifier determines the part of the program text in which another (using) occurrence of the identifier refers to this declaration. For example, the variable res is in scope (or visible) in the entire body of factorial (starting from its declaration). Therefore, the occurrences in the statement res = res * n refer to this declaration. The scope of a local variable, i.e., one defined inside a function, starts at its declaration and ends with the innermost block that encloses its declaration.

Remark 4.1.4.

Since blocks can be nested, variable declarations can be shadowed, as in this example:

void foo(int x) {
    int y = 0;
    if (x > 0) {
        int y = 0;
        y += 1;
    }
}

Run

Here, the using occurrence of y inside the if statement refers to the innermost declaration, not the one in the second line.

Subsection 4.1.2 Dynamic Properties

We now informally discuss the dynamic properties, i.e. the semantics of C. These are properties that determine what happens when we execute a C Program. The execution model of imperative languages (and particularly C) is very closely derived from the behavior of the underlying machines. As discussed in the introduction to this chapter, imperative languages provide abstractions for the fundamental building blocks of a machine language, to enable programming "close to the hardware."

(Imperative) variables, whose static properties we have briefly discussed in the previous section, are an abstraction that is characteristic of imperative programming. The dynamic behavior of a variable in imperative programming differs from the similarly-named concepts in mathematics (and functional programming). As this behavior is central for understanding imperative programming languages, we discuss it in Section 4.3 in more detail. For now, it is sufficient to understand that each variable during execution denotes a container that can carry any value of some type. For example, executing the variable declaration in line 2 allocates a new container that can carry a value of type int.

The execution of every C program starts with the function declared with the name main. For our example, this is line 12. Just like the instructions of an assembly program, the statements in a function's body are executed one after the other. The first statement (in line 12) allocates a new container to carry an int value and binds it to the identifier res. Afterwards, the function factorial is called (line 13). When calling a function, new containers for all parameters of the called function are allocated. In the example, this is one container, for the parameter n. Then, the expressions in the parentheses after the name of the called function (separated by comma; in the example, there is only one: 3) are evaluated. The resulting values are the arguments or actual parameters. These values are placed into the containers for the corresponding parameters. In our example, the 3 is placed into the container bound to n. The program execution then continues in the called function, factorial.

The statements of a block are executed in sequence. The function's execution therefore starts in line 2 by allocating a container for factorial's res variable. The statement in line 3 evaluates the expression on the right-hand side of the assignment operators (the constant 1) and writes the resulting value to the memory location given by the left-hand side (the previously allocated container for res).

The while loop evaluates its break condition (here n > 1). If the result is not equal to 0, it executes the statement of its body (here a nested block). These two steps are repeated until the break condition evaluates to 0. Within the loop body, there are two assignments that are evaluated as described for line 3.

After termination of the loop, the return statement returns the execution to the calling function, main, providing the current value of factorial's variable res as the return value. In main, the assignment in line 13 is completed by writing the return value to the variable res. Next, the printf function is called with two arguments, which prints the value of res to the screen. Afterwards, the program execution is terminated with the execution of the return statement in the last line.

An Introduction to Imperative Programming

Search Results: