Dive into Systems

Python is an interpreted programming language, which means that another program, the Python interpreter, runs Python programs: the Python interpreter acts like a virtual machine on which Python programs are run. To run a Python program, the program source code (hello.py) is given as input to the Python interpreter program that runs it. For example ($ is the Linux shell prompt):

The Python interpreter is a program that is in a form that can be run directly on the underlying system (this form is called binary executable) and takes as input the Python program that it runs (Figure 4).

To run a C program, it must first be translated into a form that a computer system can directly execute. A C compiler is a program that translates C source code into a binary executable form that the computer hardware can directly execute. A binary executable consists of a series of 0’s and 1’s in a well-defined format that a computer can run.

For example, to run the C program hello.c on a Unix system, the C code must first be compiled by a C compiler (for example, the GNU C compiler, GCC) that produces a binary executable (by default named a.out). The binary executable version of the program can then be run directly on the system (Figure 5):

(Note that some C compilers might need to be explicitly told to link in the math library: -lm):

Like Python, C uses variables as named storage locations for holding data. Thinking about the scope and type of program variables is important to understand the semantics of what your program will do when you run it. A variable’s scope defines when the variable has meaning (that is, where and when in your program it can be used) and its lifetime (that is, it could persist for the entire run of a program or only during a function activation). A variable’s type defines the range of values that it can represent and how those values will be interpreted when performing operations on its data.

In C, all variables must be declared before they can be used. To declare a variable, use the following syntax:

A variable can have only a single type. The basic C types include char, int, float, and double. By convention, C variables should be declared at the beginning of their scope (at the top of a { } block), before any C statements in that scope.

Below is an example C code snippet that shows declarations and uses of variables of some different types. We discuss types and operators in more detail after the example.

Note the semicolons galore. Recall that C statements are delineated by ;, not line breaks — C expects a semicolon after every statement. You’ll forget some, and gcc almost never informs you that you missed a semicolon, even though that might be the only syntax error in your program. In fact, often when you forget a semicolon, the compiler indicates a syntax error on the line after the one with the missing semicolon: the reason is that gcc interprets it as part of the statement from the previous line. As you continue to program in C, you’ll learn to correlate gcc errors with the specific C syntax mistakes that they describe.

C supports a small set of built-in data types, and it provides a few ways in which programmers can construct basic collections of types (arrays and structs). From these basic building blocks, a C programmer can build complex data structures.

C defines a set of basic types for storing numeric values. Here are some examples of numeric literal values of different C types:

The C char type stores a numeric value. However, it’s often used by programmers to store the value of an ASCII character. A character literal value is specified in C as a single character between single quotes.

C doesn’t support a string type, but programmers can create strings from the char type and C’s support for constructing arrays of values, which we discuss in later sections. C does, however, support a way of expressing string literal values in programs: a string literal is any sequence of characters between double quotes. C programmers often pass string literals as the format string argument to printf:

Python supports strings, but it doesn’t have a char type. In C, a string and a char are two very different types, and they evaluate differently. This difference is illustrated by contrasting a C string literal that contains one character with a C char literal. For example:

We discuss C strings and char variables in more detail in the Strings section later in this chapter. Here, we’ll mainly focus on C’s numeric types.

C’s printf function is very similar to formatted print in Python, where the caller specifies a format string to print. The format string often contains formatting specifiers, such as special characters that will print tabs (\t) or newlines (\n), or placeholders for values in the output. Placeholders consist of % followed by a type specifier letter (for example, %d represents a placeholder for an integer value). For each placeholder in the format string, printf expects an additional argument. Table 3 contains an example program in Python and C with formatted output:

When run, both versions of this program produce identically formatted output:

The main difference between C’s printf and Python’s print functions are that the Python version implicitly prints a newline character at the end of the output string, but the C version does not. As a result, the C format strings in this example have newline (\n) characters at the end to explicitly print a newline character. The syntax for listing the argument values for the placeholders in the format string is also slightly different in C’s printf and Python’s print functions.

C uses the same formatting placeholders as Python for specifying different types of values. The preceding example demonstrates the following formatting placeholders:

C additionally supports the %c placeholder for printing a character value. This placeholder is useful when a programmer wants to print the ASCII character associated with a particular numeric encoding. Here’s a C code snippet that prints a char as its numeric value (%d) and as its character encoding (%c):

When run, the program’s output looks like this:

C’s scanf function represents one method for reading in values entered by the user (via the keyboard) and storing them in program variables. The scanf function can be a bit picky about the exact format in which the user enters data, which means that it’s not very robust to badly formed user input. In the "I/O" section in Chapter 2, we discuss more robust ways of reading input values from the user. For now, remember that if your program gets into an infinite loop due to badly formed user input, you can always press CTRL-C to terminate it.

Reading input is handled differently in Python and C: Python uses the input function to read in a value as a string, and then the program converts the string value to an int, whereas C uses scanf to read in an int value and to store it at the location in memory of an int program variable (for example, &num1). Table 4 displays example programs for reading user input values in Python and C:

When run, both programs read in two values (here, 30 and 67):

Like printf, scanf takes a format string that specifies the number and types of values to read in (for example, "%d" specifies one int value). The scanf function skips over leading and trailing whitespace as it reads in a numeric value, so its format string only needs to contain a sequence of formatting placeholders, usually with no whitespace or other formatting characters between the placeholders in its format string. The arguments for the placeholders in the format string specify the locations of program variables into which the values read in will be stored. Prefixing the name of a variable with the & operator produces the location of that variable in the program’s memory — the memory address of the variable. The "Pointers" section in Chapter 2 discusses the & operator in more detail. For now, we use it only in the context of the scanf function.

Here’s another scanf example, in which the format string has placeholders for two values, the first an int and the second a float:

When inputting data to a program via scanf, individual numeric input values must be separated by at least one whitespace character. However, because scanf skips over additional leading and trailing whitespace characters (for example, spaces, tabs, and newlines), a user could enter input values with any amount of space before or after each input value. For instance, if a user enters the following for the call to scanf in the preceding example, scanf will read in 8 and store it in the x variable, and then read in 3.14 and store it in the pi variable:

C doesn’t provide a Boolean type with true or false values. Instead, integer values evaluate to true or false when used in conditional statements. When used in conditional expressions, any integer expression that is:

C has a set of relational and logical operators for Boolean expressions.

The relational operators take operand(s) of the same type and evaluate to zero (false) or nonzero (true). The set of relational operators are:

Here are some C code snippets showing examples of relational operators:

C’s logical operators take integer "Boolean" operand(s) and evaluate to either zero (false) or nonzero (true). The set of logical operators are:

C’s short-circuit logical operator evaluation stops evaluating a logical expression as soon as the result is known. For example, if the first operand to a logical and (&&) expression evaluates to false, the result of the && expression must be false. As a result, the second operand’s value need not be evaluated, and it is not evaluated.

The following is an example of conditional statements in C that use logical operators (it’s always best to use parentheses around complex Boolean expressions to make them easier to read):

Like Python, C supports for and while loops. Additionally, C provides do-while loops.

The execution stack keeps track of the state of active functions in a program. Each function call creates a new stack frame (sometimes called an activation frame or activation record) containing its parameter and local variable values. The frame on the top of the stack is the active frame; it represents the function activation that is currently executing, and only its local variables and parameters are in scope. When a function is called, a new stack frame is created for it (pushed on the top of the stack), and space for its local variables and parameters is allocated in the new frame. When a function returns, its stack frame is removed from the stack (popped from the top of the stack), leaving the caller’s stack frame on the top of the stack.

For the example preceding program, at the point in its execution right before max executes the return statement, the execution stack will look like Figure 6. Recall that the argument values to max passed by main are passed by value, meaning that the parameters to max, x and y, are assigned the values of their corresponding arguments, a and b from the call in main. Despite the max function changing the value of x, the change doesn’t affect the value of a in main.

The following full program includes two functions and shows examples of calling them from the main function. In this program, we declare function prototypes for max and print_table above the main function so that main can access them despite being defined first. The main function contains the high-level steps of the full program, and defining it first echoes the top-down design of the program. This example includes comments describing the parts of the program that are important to functions and function calls. You can also download and run the full program.

C arrays can store multiple data values of the same type. In this chapter, we discuss statically declared arrays, meaning that the total capacity (the maximum number of elements that can be stored in an array) is fixed and is defined when the array variable is declared. In the next chapter, we discuss dynamically allocated arrays and multi-dimensional arrays.

Table 8 shows Python and C versions of a program that initializes and then prints a collection of integer values. The Python version uses its built-in list type to store the list of values, whereas the C version uses an array of int types to store the collection of values.

In general, Python provides a high-level list interface to the programmer that hides much of the low-level implementation details. C, on the other hand, exposes a low-level array implementation to the programmer and leaves it up to the programmer to implement higher-level functionality. In other words, arrays enable low-level data storage without higher-level list functionality, such as len, append, insert, and so on.

The C and Python versions of this program have several similarities, most notably that individual elements can be accessed via indexing, and that index values start at 0. That is, both languages refer to the very first element in a collection as the element at position 0.

The main differences in the C and Python versions of this program relate to the capacity of the list or array and how their sizes (number of elements) are determined.

In the Python version, the programmer doesn’t need to specify the capacity of a list in advance: Python automatically increases a list’s capacity as needed by the program. For example, the Python append function automatically increases the size of the Python list and adds the passed value to the end.

In contrast, when declaring an array variable in C, the programmer must specify its type (the type of each value stored in the array) and its total capacity (the maximum number of storage locations). For example:

The preceding declarations create one variable named arr, an array of int values with a total capacity of 10, and another variable named str, an array of char values with a total capacity of 20.

To compute the size of a list (size meaning the total number of values in the list), Python provides a len function that returns the size of any list passed to it. In C, the programmer has to explicitly keep track of the number of elements in the array (for example, the size variable in Table 8).

Another difference that might not be apparent from looking at the Python and C versions of this program is how the Python list and the C array are stored in memory. C dictates the array layout in program memory, whereas Python hides how lists are implemented from the programmer. In C, individual array elements are allocated in consecutive locations in the program’s memory. For example, the third array position is located in memory immediately following the second array position and immediately before the fourth array position.

Python provides multiple ways to access elements in its lists. C, however, supports only indexing, as described earlier. Valid index values range from 0 to the capacity of the array minus 1. Here are some examples:

This example declares the array with a capacity of 10 (it has 10 elements), but it only uses the first six (our current collection of values is size 6, not 10). It’s often the case when using statically declared arrays that some of an array’s capacity will remain unused. As a result, we need another program variable to keep track of the actual size (number of elements) in the array (num in this example).

Python and C differ in their error-handling approaches when a program attempts to access an invalid index. Python throws an IndexError exception if an invalid index value is used to access elements in a list (for example, indexing beyond the number of elements in a list). In C, it’s up to the programmer to ensure that their code uses only valid index values when indexing into arrays. As a result, for code like the following that accesses an array element beyond the bounds of the allocated array, the program’s runtime behavior is undefined:

The C compiler is happy to compile code that accesses array positions beyond the bounds of the array; there is no bounds checking by the compiler or at runtime. As a result, running this code can lead to unexpected program behavior (and the behavior might differ from run to run). It can lead to your program crashing, it can change another variable’s value, or it might have no effect on your program’s behavior. In other words, this situation leads to a program bug that might or might not show up as unexpected program behavior. Thus, as a C programmer, it’s up to you to ensure that your array accesses refer to valid positions!

The semantics of passing arrays to functions in C is similar to that of passing lists to functions in Python: the function can alter the elements in the passed array or list. Here’s an example function that takes two parameters, an int array parameter (arr), and an int parameter (size):

The [] after the parameter name tells the compiler that the type of the parameter arr is array of int, not int like the parameter size. In the next chapter, we show an alternate syntax for specifying array parameters. The capacity of the array parameter arr isn’t specified: arr[] means that this function can be called with an array argument of any capacity. Because there is no way to get an array’s size or capacity just from the array variable, functions that are passed arrays almost always also have a second parameter that specifies the array’s size (the size parameter in the preceding example).

To call a function that has an array parameter, pass the name of the array as the argument. Here is a C code snippet with example calls to the print_array function:

In C, the name of the array variable is equivalent to the base address of the array (that is, the memory location of its 0th element). Due to C’s pass by value function call semantics, when you pass an array to a function, each element of the array is not individually passed to the function. In other words, the function isn’t receiving a copy of each array element. Instead, an array parameter gets the value of the array’s base address. This behavior implies that when a function modifies the elements of an array that was passed as a parameter, the changes will persist when the function returns. For example, consider this C program snippet:

The call in main to the test function is passed the argument arr, whose value is the base address of the arr array in memory. The parameter a in the test function gets a copy of this base address value. In other words, parameter a refers to the same array storage locations as its argument, arr. As a result, when the test function changes a value stored in the a array (a[3] = 8), it affects the corresponding position in the argument array (arr[3] is now 8). The reason is that the value of a is the base address of arr, and the value of arr is the base address of arr, so both a and arr refer to the same array (the same storage locations in memory)! Figure 7 shows the stack contents at the point in the execution just before the test function returns.

Parameter a is passed the value of the base address of the array argument arr, which means they both refer to the same set of array storage locations in memory. We indicate this with the arrow from a to arr. Values that get modified by the function test are highlighted. Changing the value of the parameter size does not change the value of its corresponding argument n, but changing the value of one of the elements referred to by a (for example, a[3] = 8) does affect the value of the corresponding position in arr.

Python implements a string type and provides a rich interface for using strings, but there is no corresponding string type in C. Instead, strings are implemented as arrays of char values. Not every character array is used as a C string, but every C string is a character array.

Recall that arrays in C might be defined with a larger size than a program ultimately uses. For example, we saw earlier in the section "Array Access Methods" that we might declare an array of size 10 but only use the first six positions. This behavior has important implications for strings: we can’t assume that a string’s length is equal to that of the array that stores it. For this reason, strings in C must end with a special character value, the null character ('\0'), to indicate the end of the string.

Strings that end with a null character are said to be null-terminated. Although all strings in C should be null-terminated, failing to properly account for null characters is a common source of errors for novice C programmers. When using strings, it’s important to keep in mind that your character arrays must be declared with enough capacity to store each character value in the string plus the null character ('\0'). For example, to store the string "hi", you need an array of at least three chars (one to store 'h', one to store 'i', and one to store '\0').

Because strings are commonly used, C provides a string library that contains functions for manipulating strings. Programs that use these string library functions need to include the string.h header.

When printing the value of a string with printf, use the %s placeholder in the format string. The printf function will print all the characters in the array argument until it encounters the '\0' character. Similarly, string library functions often either locate the end of a string by searching for the '\0' character or add a '\0' character to the end of any string that they modify.

Here’s an example program that uses strings and string library functions:

The strlen function in the C string library returns the number of characters in its string argument. A string’s terminating null character doesn’t count as part of the string’s length, so the call to strlen(str1) returns 2 (the length of the string "hi"). The strcpy function copies one character at a time from a source string (the second parameter) to a destination string (the first parameter) until it reaches a null character in the source.

Note that most C string library functions expect the call to pass in a character array that has enough capacity for the function to perform its job. For example, you wouldn’t want to call strcpy with a destination string that isn’t large enough to contain the source; doing so will lead to undefined behavior in your program!

C string library functions also require that string values passed to them are correctly formed, with a terminating '\0' character. It’s up to you as the C programmer to ensure that you pass in valid strings for C library functions to manipulate. Thus, in the call to strcpy in the preceding example, if the source string (str1) was not initialized to have a terminating '\0' character, strcpy would continue beyond the end of the str1 array’s bounds, leading to undefined behavior that could cause it to crash.

In the next chapter, we discuss C strings and the C string library in more detail.

A struct type definition should appear outside of any function, typically near the top of the program’s .c file. The syntax for defining a new struct type is the following (struct is a reserved keyword):

Here’s an example of defining a new struct studentT type for storing student data:

This struct definition adds a new type to C’s type system, and the type’s name is struct studentT. This struct defines four fields, and each field definition includes the type and name of the field. Note that in this example, the name field’s type is a character array, for use as a string.

Once the type has been defined, you can declare variables of the new type, struct studentT. Note that unlike the other types we’ve encountered so far that consist of just a single word (for example, int, char, and float), the name of our new struct type is two words, struct studentT.

To access field values in a struct variable, use dot notation:

When accessing structs and their fields, carefully consider the types of the variables you’re using. Novice C programmers often introduce bugs into their programs by failing to account for the types of struct fields. Table 9 shows the types of several expressions surrounding our struct studentT type.

Here are some examples of assigning a struct studentT variable’s fields:

Figure 8 illustrates the layout of the student1 variable in memory after the field assignments in the preceding example. Only the struct variable’s fields (the areas in boxes) are stored in memory. The field names are labeled on the figure for clarity, but to the C compiler, fields are simply storage locations or offsets from the start of the struct variable’s memory. For example, based on the definition of a struct studentT, the compiler knows that to access the field named gpa, it must skip past an array of 64 characters (name) and one integer (age). Note that in the figure, the name field only depicts the first six characters of the 64-character array.

C struct types are lvalues, meaning they can appear on the left side of an assignment statement. Thus, a struct variable can be assigned the value of another struct variable using a simple assignment statement. The field values of the struct on the right side of the assignment statement are copied to the field values of the struct on the left side of the assignment statement. In other words, the contents of memory of one struct are copied to the memory of the other. Here’s an example of assigning a struct’s values in this way:

Figure 9 shows the values of the two student variables after the assignment statement and call to strcpy have executed. Note that the figure depicts the name fields as the string values they contain rather than the full array of 64 characters.

C provides a sizeof operator that takes a type and returns the number of bytes used by the type. The sizeof operator can be used on any C type, including struct types, to see how much memory space a variable of that type needs. For example, we can print the size of a struct studentT type:

When run, this line should print out a value of at least 76 bytes, because 64 characters are in the name array (1 byte for each char), 4 bytes for the int age field, 4 bytes for the float gpa field, and 4 bytes for the int grad_yr field. The exact number of bytes might be larger than 76 on some machines.

Here’s a full example program that defines and demonstrates the use of our struct studentT type:

When run, this program outputs the following:

In C, arguments of all types are passed by value to functions. Thus, if a function has a struct type parameter, then when called with a struct argument, the argument’s value is passed to its parameter, meaning that the parameter gets a copy of its argument’s value. The value of a struct variable is the contents of its memory, which is why we can assign the fields of one struct to be the same as another struct in a single assignment statement like this:

Because the value of a struct variable represents the full contents of its memory, passing a struct as an argument to a function gives the parameter a copy of all the argument struct’s field values. If the function changes the field values of a struct parameter, the changes to the parameter’s field values have no effect on the corresponding field values of the argument. That is, changes to the parameter’s fields only modify values in the parameter’s memory locations for those fields, not in the argument’s memory locations for those fields.

Here’s a full example program using the checkID function that takes a struct parameter:

When main calls checkID, the value of the student struct (a copy of the memory contents of all its fields) is passed to the s parameter. When the function changes the value of its parameter’s age field, it doesn’t affect the age field of its argument (student). This behavior can be seen by running the program, which outputs the following:

The output shows that when checkID prints the age field, it reflects the function’s change to the age field of the parameter s. However, after the function call returns, main prints the age field of student with the same value it had prior to the checkID call. Figure 10 illustrates the contents of the call stack just before the checkID function returns.

Understanding the pass-by-value semantics of struct parameters is particularly important when a struct contains a statically declared array field (like the name field in struct studentT). When such a struct is passed to a function, the struct argument’s entire memory contents, including every array element in the array field, is copied to its parameter. If the parameter struct’s array contents are changed by the function, those changes will not persist after the function returns. This behavior might seem odd given what we know about how arrays are passed to functions, but it’s consistent with the struct-copying behavior described earlier.

A pointer variable stores the address of a memory location in which a value of a specific type can be stored. For example, a pointer variable can store the value of an int address at which the integer value 12 is stored. The pointer variable points to (refers to) the value. A pointer provides a level of indirection for accessing values stored in memory. Figure 12 illustrates an example of what a pointer variable might look like in memory:

Through the pointer variable, ptr, the value (12) stored in the memory location it points to can be indirectly accessed. C programs most frequently use pointer variables for:

Every byte of memory in a program’s memory space has an associated address. Everything the program needs to run is in its memory space, and different types of entities reside in different parts of a program’s memory space. For example, the code region contains the program’s instructions, global variables reside in the data region, local variables and parameters occupy the stack, and dynamically allocated memory comes from the heap. Because the stack and the heap grow at runtime (as functions are called and return and as dynamic memory is allocated and freed), they are typically far apart in a program’s address space to leave a large amount of space for each to grow into as the program runs.

Dynamically allocated memory occupies the heap memory region of a program’s address space. When a program dynamically requests memory at runtime, the heap provides a chunk of memory whose address must be assigned to a pointer variable.

Figure 17 illustrates the parts of a running program’s memory with an example of a pointer variable (ptr) on the stack that stores the address of dynamically allocated heap memory (it points to heap memory).

It’s important to remember that heap memory is anonymous memory, where "anonymous" means that addresses in the heap are not bound to variable names. Declaring a named program variable allocates it on the stack or in the data part of program memory. A local or global pointer variable can store the address of an anonymous heap memory location (e.g. a local pointer variable on the stack can point to heap memory), and dereferencing such a pointer enables a program to store data in the heap.

malloc and free are functions in the standard C library (stdlib) that a program can call to allocate and deallocate memory in the heap. Heap memory must be explicitly allocated (malloc’ed) and deallocated (freed) by a C program.

To allocate heap memory, call malloc, passing in the total number of bytes of contiguous heap memory to allocate. Use the sizeof operator to compute the number of bytes to request. For example, to allocate space on the heap to store a single integer, a program could call:

The malloc function returns the base address of the allocated heap memory to the caller (or NULL if an error occurs). Here’s a full example program with a call to malloc to allocate heap space to store a single int value: