Machine Model I

A computer program consists of source code that determines what the program does. The program itself is run on a machine, and the program directs the machine on what computation should be preferred. In order to understand a program, it is important to have a machine model that helps us reason about how the source code relates to what happens at runtime.

As an example, consider the following C++ program:

int main() {
  int x = 3;
  double y = 4.1;
  int z = x;
  x = 5;
}

When the program runs, execution starts at main(). Each variable in the program is a name that refers to some object in memory, a region of memory that holds the data value for the variable. The variable’s type determines how much memory is required, and how the data are represented – generally, data are stored in bytes, which themselves are sequences of eight bits, each of which is a binary digit that is zero or one. For instance, in typical C++ implementations, a variable of type int requires four bytes (32 bits) of storage, while one of type double requires eight bytes (64 bits).

Figure 3 Variables correspond to objects in memory, each of which stores a data value represented in binary.

It is often useful to think of memory as a large array, with data values stored at different indices into the array, as shown in Figure 4.

Figure 4 Simplified machine model, with memory as a linear (array) structure with slots for different objects.

Here, the program is using memory index 6 for x, index 2 for y, and index 4 for z. (Later, we will see that a program uses a more systematic method for locating the local variables of a function.) The contents of memory illustrated above are after the initialization of x and y but before the initialization of z. The location for x has a representation of the int value 3, the location for y has a representation of the double value 4.1, and the location for z has some indeterminate value.

When the program proceeds to initialize z, it copies the value 3 from the memory for x into the memory for z, as demonstrated in Figure 5.

Figure 5 Initializing an object as a copy of another.

Finally, the assignment x = 5 modifies the value of x to be 5, as Figure 6 illustrates.

Figure 6 Modifying the value of an object.

In order to discuss the conceptual spaces for source code and runtime in more detail, we need some terminology. In source code, a name refers to some entity such as a variable, function, or type. As mentioned above, a variable is a name that refers to an object in memory. A name has a scope, which determines what region of code can use that name to refer to an entity. For example, the scope of y in the code above begins at the declaration of y and ends at the end of the function definition for main(). Attempting to use y outside this region will result in a compiler error. A declaration is what introduces a name into the program and begins its scope.

At runtime, an object is a piece of data in memory, and it is located at some address in memory (corresponding to the index in our basic machine model above). An object has a lifetime during which it is legal to use that object. More specifically, an object is created at some point in time, and at some later point in time it is destroyed. The storage duration of an object determines its lifetime. There are three options that we will see in C++:

• static: the lifetime is essentially the whole program

• automatic (also called local): the lifetime is tied to a particular scope, such as a block of code

• dynamic: the object is explicitly created and destroyed by the programmer

The former two durations are controlled by the compiler, while the latter is specified by the programmer. We will restrict ourselves to static and automatic storage duration until later in the course.

A variable is not the same thing as a memory object: a variable is a concept associated with source code, while an object is associated with the runtime. The same variable can refer to different objects at different times, such as a local variable in a function that is called more than once. An object that has dynamic storage duration is not associated with a variable at all.

An important consideration in the design of a language is the semantics of an initialization or assignment of the form x = y. Does this change which object x is referring to, or does it modify the value of the object that x is referring to? The first option is known as reference semantics, while the second is value semantics.

In C++, the default is value semantics. Consider the following program:

int x = 42;    // initialize value of x to 42
int y = 99;    // initialize value of y to 99
x = y;         // assign value of y to value of x

The assignment in the last line copies the value stored in the memory object associated with y into the memory object for x, as shown in Figure 7.

Figure 7 Assignment copies a value from the right-hand side into the left-hand-side object.

C++ supports reference semantics only when initializing a new variable. Placing an ampersand (&) to the left of the new variable name causes the name to be associated with an existing object. The following is an example with a local variable:

int x = 42;  // initialize value of x to 42
int z = 3;   // initialize value of z to 3
int &y = x;  // y and x are now names for the same object
x = 24;      // assigns 24 to object named x/y
y = z;       // Does NOT re-bind y to a different object
             // Value semantics used here.

The declaration int &y = x; introduces y as a new name for the object associated with x. Any subsequent modification to this object is reflected through both names, regardless of the name used to perform the modification. Figure 8 shows the effects of the assignments in the code above.

Figure 8 A reference is another name for an existing object.

Since C++ only supports reference semantics in initialization, the association between a variable and a memory object can never be broken, except when the variable goes out of scope.

Pointers

Recall that in C++, an object is a piece of data in memory, and that it is located at some address in memory. The compiler and runtime determine the location of an object when it is created; aside from deciding whether an object is in the global segment, on the stack, or in the heap segment (the segment used for dynamic memory), the programmer generally does not control the exact location where an object is placed [1]. Given the same program and the same inputs to that program, different systems will often end up placing the same objects at different memory locations. In fact, in many implementations, running the same program twice on the same system will result in different addresses for the objects.

[1]

C++ has placement new, which allows a programmer to initialize a new object in a given memory location. However, even with placement new, the original memory must have been allocated by the programmer, and the programmer does not control the exact address produced by that allocation.

Though the programmer does not have control over the address at which an object is located, the programmer does have the ability to query the address on an object once it has been created. In C++, the & (usually pronounced “address-of”) operator can be applied to an object to determine its address:

int main() {
  int x = 3;
  double y = 5.5;
  cout << &x << endl; // sample output: 0x7ffee0659a2c
  cout << &y << endl; // sample output: 0x7ffee0659a20
}

Addresses are usually written in hexadecimal (base-16) notation, with a leading 0x followed by digits in the range 0-9 and a-f, with a representing the value 10, b the value 11, and so on. Most modern machines use 64 bits for an address; since each digit in a hexadecimal number represents four bits (\(2^4 = 16\) values), a 64-bit address requires up to 16 hexadecimal digits. The examples above use only 12 digits, implying that the leading four digits are zeros. Most examples in this text use fewer digits for conciseness.

In addition to being printed, addresses can also be stored in a category of objects called pointers [2]. A pointer variable can be declared by placing a * symbol to the left of the variable name in its declaration:

int x = 3;
int *ptr = &x;
cout << ptr << endlt; // sample output: 0x7ffee0659a2c

[2]

The terms address and pointer are often used interchangeably. Technically, a pointer is an object that holds an address as its value, while the address is the value itself.

A pointer type consists of two elements:

• the type of the objects whose addresses the pointer can hold as a value. For example, an int * pointer can hold the address of an int, but not that of any other data type.

• the * symbol, which indicates that the type is a pointer

Each data type in C++ has a corresponding pointer type. For instance, int * is the pointer type corresponding to int, double * is the pointer type corresponding to double, and double ** is the pointer type corresponding to double *.

A pointer object can be dereferenced to obtain the object whose address the pointer is holding by applying the * (usually pronounced “star” or “dereference”) operator:

int x = 3;
int y = 4;
int *ptr = &x;
cout << *ptr << endl; // prints 3
ptr = &y;
cout << *ptr << endl; // prints 4

We often say that a pointer “points to” an object, and that the * operator “follows” the pointer to the object it is pointing at. In keeping with this terminology, a pointer is often pictured as an arrow from the pointer to the object it is pointing at, as shown in Figure 9.

Figure 9 An arrow indicates the object whose address a pointer holds.

Usually, we are not concerned with actual address values – they are implementation-dependent and can vary between program runs. Instead, we only concern ourselves with which object each pointer is referring to. Thus, we often draw just an arrow to illustrate which object a pointer is pointing to, as in Figure 10, without the actual address value.

Figure 10 Pointers are often illustrated by just an arrow, without the actual address value.

The following is another example of working with a pointer:

int main() {
  int foo = 1;
  int *bar = &foo;
  foo += 1;
  *bar += 1;

  cout << foo << endl;   // prints 3
  cout << bar << endl;   // prints address of foo (e.g. 0x1000)
  cout << *bar << endl;  // prints 3
}

Figure 11 Example of modifying an object through a pointer.

The code initializes the pointer bar with the address of foo. It proceeds to increment foo directly, then dereferences bar to increment the object it is pointing at. Since it is pointing at the object associated with foo, the result is that foo has value 3. The state of memory at each point is shown in Figure 11.

Pointers and References

The * and & symbols mean different things when they are used as part of a type and when they are used in an expression:

• When used in a type, * means that the type is a pointer type, while & means the type is a reference type.

• When used as a unary prefix operator in an expression, * is used to dereference a pointer, while & is used to obtain the address of an object.

• When used as a binary infix operator, * is multiplication, while & is a bitwise and operation (which is outside the scope of this course).

The following illustrates some examples:

int x = 3;
int *ptr = &x;
int &ref = *ptr;

In the second line, * is used in a type, so ptr is a pointer to an int. The initialization is an expression, so the & obtains the address of the object corresponding to x. In the third line, & is used as part of the type, so ref is a reference variable. Its initialization is an expression, so the * dereferences ptr to get to the object associated with x. The result is that ref is an alias for the same object as x.

Pointers allow us to work indirectly with objects. The following is an implementation of a swap function that uses pointers to refer to the objects whose values to swap:

void swap_pointed(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int main() {
  int a = 3;
  int b = 5;
  swap_pointed(&a, &b);
  cout << a << endl;     // prints 5
  cout << b << endl;     // prints 3
}

Figure 12 demonstrates the execution of this code.

Figure 12 Pointers enable redirection, allowing a function to modify objects in a different scope.

References can also be used to indirectly refer to other objects. However, a pointer actually holds the address of another object, while a reference just acts as another name for an existing object. A reference must be initialized to refer to another object, and the association between the reference and its object cannot be broken. On the other hand, a pointer need not be initialized to point to an object, and the address value it holds can be later changed to be the address of a different object. A pointer can be null or have an undefined value, so it must be used carefully to avoid undefined behavior. On the other hand, while it is possible to construct an invalid reference, it usually does not occur in the normal course of programming in C++.

Both pointers and references allow objects to be used across scopes. They both enable subtype polymorphism, a concept we will see later in the course. Both can also be used to refer to objects in dynamic memory, as we will also see later.

Pointers are strongly connected to arrays. Indexing into an array actually works through pointer arithmetic, as we will see later.