The Elements of Programming

📚

This post is an exerpt from the book Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Sussman, with some modifications, licensed under CC-SA 4.0.

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:

Primitive expressions, which represent the simplest entities the language is concerned with
Means of combination, by which compound elements are built from simpler ones, and
Means of abstraction, by which compound elements can be named and manipulated as units.

In programming, we deal with two kinds of elements: procedures and data. (Later we will discover that they are really not so distinct.) Informally, data is "stuff" that we want to manipulate, and procedures are descriptions of the rules for manipulating the data. Thus, any powerful programming language should be able to describe primitive data and primitive procedures and should have methods for combining and abstracting procedures and data.

In this chapter we will deal only with simple numerical data so that we can focus on the rules for building procedures.

The characterization of numbers as "simple data" is a barefaced bluff. In fact, the treatment of numbers is one of the trickiest and most confusing aspects of any programming language. Some typical issues involved are these: Some computer systems distinguish integers, such as 2, from real numbers, such as 2.71. Is the real number 2.0 different from the integer 2? Are the arithmetic operations used for integers the same as the operations used for real numbers? Does 6 divided by 2 produce 3, or 3.0? How large a number can we represent? How many decimal places of accuracy can we represent? Is the range of integers the same as the range of real numbers? Above and beyond these questions, of course, lies a collection of issues concerning roundoff and truncation errors — the entire science of numerical analysis. Since our focus in this book is on large-scale program design rather than on numerical techniques, we are going to ignore these problems. The numerical examples in this chapter will exhibit the usual roundoff behavior that one observes when using arithmetic operations that preserve a limited number of decimal places of accuracy in noninteger operations.

In later chapters we will see that these same rules allow us to build procedures to manipulate compound data as well.

Expressions

One easy way to get started at programming is to examine some typical interactions with an interpreter for the Scheme dialect of Lisp. Imagine that you are sitting at a computer terminal. You type an expression, and the interpreter responds by displaying the result of its evaluating that expression.

One kind of primitive expression you might type is a number. (More precisely, the expression that you type consists of the numerals that represent the number in base 10.) If you present Unison with a number, 486, the interpreter will respond by printing 486:

Expressions representing numbers may be combined with an expression representing a primitive procedure (such as Nat.+ or Nat.*) to form a compound expression that represents the application of the procedure to those numbers. For example:

137 Nat.+ 349

1000 Nat.- 334

5 Nat.* 99

10 Nat./ 5

2.7 Float.+ 10.0

12.7

Expressions such as these are called combinations. The function being applied is is called the operator, and the other elements are called operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

We can add and multiply many numbers using a list:

Nat.sum [21, 35, 12, 7]

Nat.product [25, 4, 12]

Combinations can be nested, that is, we can have combinations whose elements are themselves combinations:

3 Nat.* 5 Nat.+ (10 Nat.- 6)

There is no limit (in principle) to the depth of such nesting and to the overall complexity of the expressions that the Unison interpreter can evaluate. It is we humans who get confused by still relatively simple expressions such as

3 Nat.* (2 Nat.* 4 Nat.+ (3 Nat.+ 5)) Nat.+ (10 Nat.- 7 Nat.+ 6)