Building Blocks

All the data that we process on computer ultimately decompose into individual bits, but writing programs that exclusively process bits would be tiresome indeed. Types allow us to specify how we will use particular sets of bits and functions allow us to specify the operations that we will perform on the data. We use C structures to group together heterogeneous pieces of information, and we consider these basic C mechanisms, in the context of presenting a general approach to organizing our programs. Our primary goal is to lay the groundwork for the development, of the higher-level constructs that will serve as the basis for most of the algorithm in this book.

We write programs that process information derived from mathematical or natural-language descriptions of the world we live; accordingly, computing environments need to provide built-in support for the basic building blocks of such descriptions -- numbers and characters. In C, our programs are all built from just a few basic types of data:

• Integers (ints)
• Floating-point numbers (floats)
• Characters (chars)

It is customary to refer to these basic types by their C names -- int, float and char -- although we often use the generic terminology integer, floating-point number, and character, as well. Characters are most often used in higher-level abstractions -- for example to make words and sentences.

We use a fixed number of bits to represent numbers, so ints are by necessity integers that fall within a specific range that depends on the number of bits that we use to represent them. Floating-point numbers approximate real numbers, and the number of bits that we use to represent them affects the precision with which we can approximate a real number. In C, we trade space for accuracy by choosing from among the types int, long int, or short int for integers and from among float or double for floating-point numbers. On most systems, these types correspond to underlying hardware representations. The number of bits used for the representation, and therefore the range of values (in the case of ints) or precision (in the case of floats), is machine-dependent, although C provides certain guarantees.

3.1.1 Data Type

Definition 3.1 A data type is a set of value and a collection of operations on those values.

Operations are associated with types, not the other way around. When we perform an operation, we need to ensure that its operands and result are of the correct type. Neglecting this reponsibility is a common programming error. In some situations, C performs implicit type conversions; in other situations, we use casts, or explicit type conversions. For example, if x and N are integers, the expression:

((float)x) / N

includes both types of conversion: the (float) is a cast that converts the value of x to floating point; then an implicit conversion is performed for N to make both arguments of the divide operator floating point, according to C’s rules for implicit type conversion.

Many of the operations associated with standard data types (for example, the arithmetic operations) are built into the C language. Other operations are found in the form of functions that are defined in standard function libraries; still others take form in the C functions that we define in our programs. That is, the concept of a data type is relevant not just to integer, floating point, and character built-in types. We often define our own data types, as an effective way of organizing our software. When we define a simple function in C, we are effectively creating a new data type, with the operation implemented by that function added to the operations defined for the types of data represented by its arguments. Indeed, in a sense, each C program is a data type -- a list of sets of values (built-in or other types) and associated operations (functions). This point of view is perhaps too broad to be useful, but we shall see that narrowing our focus to understand our programs in terms of data types is valuable.

3.1.2 Function Definition

Program 3.1 Function definition

The mechanism that we use in C to implement new operations on data is function definition.

All functions have a list of arguments and possibly a return value. The function lg here one argument and a return value, each of type int.

#include <stdio.h> 

int lg(int);

int main() {
    int i, N;
    printf("%7s %5s %7s\n", "N","lg(N)","N*lg(N)");
    for (i = 1, N = 10; i <= 6; i++, N *= 10){
        printf("%7d %2d %9d\n", N, lg(N), N * lg(N));
    }
    return 0;
}

int lg(int N) {
    int i;
    for (i = 0; N > 0; i++, N /= 2){}
    return i;
}

• #inclue <stdio.h>: references a system file that contains declarations of system functions such as printf.
• int lg(int): the declaration of function lg. The declaration is optional if the function is defined before it is used, as is the case with main. The declaration provides the information necessary for other functions to call or invoke the function, using arguments of the proper type.

One goal that we have when writing programs is to organize them such that they apply to as broad a variety of situations as possible. The reason for adopting such a goal is that it might put us in the position of being able to reuse an old program to solve a new problem, perhaps completely unrelated to the problem that the program was origianlly intended to solve.

First, by taking care to understand and to specify precisely which operations a program uses, we can easily extend it to any type of data for which we can support those operations.

Second, by taking care to understand and to specify precisely what a program dose, we can add the abstract operation that it performs to the operations at our disposal in solving new problems.

3.1.3 Types of Numbers

// TODO: complete it later 2022-01-21