Concepts, Techniques, and Models of Computer Programming

Programming as defined above has two essential parts: a technology and its scientific foundation. The technology consists of tools, practical techniques, and standards, allowing us to do programming. The science consists of a broad and deep theory with predictive power, allowing us to understand programming. Ideally, the science should explain the technology in a way that is as direct and useful as possible. If either part is left out, we are no longer doing programming. Without the technology, we are doing pure mathematics. Without the science, we are doing a craft, i.e., we lack deep understanding. Teaching programming correctly therefore means teaching both the technology (current tools) and the science (fundamental concepts). Knowing the tools prepares the student for the present. Knowing the concepts prepares the student for future developments.

The most difficult work of programmers, and also the most rewarding, is not writing programs but rather designing abstractions.

Top-down software development Let us summarize the methodology we used to write Pascal: The first step is to understand how to do the calculation by hand. The second step is to write a main function to solve the problem, assuming that some auxiliary functions are known. The third step is to complete the solution by writing the auxiliary functions. The methodology of first writing the main function and filling in the blanks afterward is known as top-down software development. It is one of the best known approaches to program design, but it gives only part of the story as we shall see.

Correctness To prove correctness in general, we have to reason about the program. This means three things: We need a mathematical model of the operations of the programming language, defining what they should do. This model is called the language’s semantics. We need to define what we would like the program to do. Usually, this is a mathematical definition of the inputs that the program needs and the output that it calculates. This is called the program’s specification. We use mathematical techniques to reason about the program, using the semantics. We would like to demonstrate that the program satisfies the specification.

Complexity A lesson we can learn from this example is that using a good algorithm is more important than having the best possible compiler or fastest machine.