Section 2

Numbers, Expressions, Simple Programs

In the beginning, people thought of computers as number crunchers. And indeed, computers are very good at working with numbers. Since teachers start their first-graders on computing with numbers, we start with numbers, too. Once we know how computers deal with numbers, we can develop simple programs in no time; we just translate common sense into our programming notation. Still, even developing such simple programs requires discipline, and so we introduce the outline of the most fundamental design recipe and the basic programming guideline at the end of this section.

2.1  Numbers and Arithmetic

Computing

Numbers come in many different flavors: positive and negative integers, fractions (also known as rationals), and reals are the most widely known classes of numbers:

Like a pocket calculator, the simplest of computers, Scheme permits programmers to add, subtract, multiply, and divide numbers:

Stepper

As in arithmetic or algebra, we can nest expressions:

  (* (+ 2 2) (/ (* (+ 3 5) (/ 30 10)) 2))

Scheme evaluates these expressions exactly as we do. It first reduces the innermost parenthesized expressions to numbers, then the next layer, and so on:

  (* (+ 2 2) (/ (* (+ 3 5) (/ 30 10)) 2))
= (* 4 (/ (* 8 3) 2))
= (* 4 (/ 24 2))
= (* 4 12)
= 48

Because every Scheme expression has the shape

(operation A ... B)

there is never any question about which part has to be evaluated first. Whenever A ... B are numbers, the expression can be evaluated; otherwise, A ... B are evaluated first. Contrast this with

which is an expression that we encounter in grade school. Only a substantial amount of practice guarantees that we remember to evaluate the multiplication first and the addition afterwards.⁴

Finally, Scheme not only provides simple arithmetical operations but a whole range of advanced mathematical operations on numbers. Here are five examples:

1. (sqrt A) computes (A)^1/2;

2. (expt A B) computes A^B;

3. (remainder A B) computes the remainder of the integer division A/B;

4. (log A) computes the natural logarithm of A; and

5. (sin A) computes the sine of A radians.

When in doubt whether a primitive operation exists or how it works, use DrScheme to test whether an operation is available with a simple example.

A Note on Numbers: Scheme computes with EXACT integers and rationals as long as we use primitive operations that produce exact results. Thus, it displays the result of (/ 44 14) as 22/7. Unfortunately, Scheme and other programming languages compromise as far as real numbers are concerned. For example, since the square root of 2 is not a rational but a real number, Scheme uses an INEXACT NUMBER:

  (sqrt 2)
= #i1.4142135623731

The #i notation warns the programmer that the result is an approximation of the true number. Once an inexact number has become a part of a calculation, the process continues in an approximate manner. To wit:

  (- #i1.0 #i0.9)
= #i0.09999999999999998

but

  (- #i1000.0 #i999.9)
= #i0.10000000000002274

even though we know from mathematics that both differences should be 0.1 and equal. Once numbers are inexact, caution is necessary.

This imprecision is due to the common simplification of writing down numbers like the square root of 2 or as rational numbers. Recall that the decimal representations of these numbers are infinitely long (without repetition). A computer, however, has a finite size, and therefore can only represent a portion of such a number. If we choose to represent these numbers as rationals with a fixed number of digits, the representation is necessarily inexact. Intermezzo 6 will explain how inexact numbers work.

To focus our studies on the important concepts of computing and not on these details, the teaching languages of DrScheme deal as much as possible with numbers as precise numbers. When we write 1.25, DrScheme interprets this number as a precise fraction, not as an inexact number. When DrScheme's Interactions window displays a number such as 1.25 or 22/7, it is the result of a computation with precise rationals and fractions. Only numbers prefixed by #i are inexact representations. 

Exercise 2.1.1.  

Find out whether DrScheme has operations for squaring a number; for computing the sine of an angle; and for determining the maximum of two numbers.    Solution

Exercise 2.1.2.   Evaluate (sqrt 4), (sqrt 2), and (sqrt -1) in DrScheme. Then, find out whether DrScheme knows an operation for determining the tangent of an angle.    Solution

2.2  Variables and Programs

Programming

In algebra we learn to formulate dependencies between quantities using VARIABLE EXPRESSIONS. A variable is a placeholder that stands for an unknown quantity. For example, a disk of radius r has the approximate area⁵

In this expression, r stands for any positive number. If we now come across a disk with radius 5, we can determine its area by substituting 5 for r in the above formula and reducing the resulting expression to a number:

More generally, expressions that contain variables are rules that describe how to compute a number when we are given values for the variables.

A program is such a rule. It is a rule that tells us and the computer how to produce data from some other data. Large programs consist of many small programs and combine them in some manner. It is therefore important that programmers name each rule as they write it down. A good name for our sample expression is area-of-disk. Using this name, we would express the rule for computing the area of a disk as follows:

(define (area-of-disk r) 
  (* 3.14 (* r r)))

The two lines say that area-of-disk is a rule, that it consumes a single INPUT, called r, and that the result, or OUTPUT, is going to be (* 3.14 (* r r)) once we know what number r represents.

Programs combine basic operations. In our example, area-of-disk uses only one basic operation, multiplication, but defined programs may use as many operations as necessary. Once we have defined a program, we may use it as if it were a primitive operation. For each variable listed to the right of the program name, we must supply one input. That is, we may write expressions whose operation is area-of-disk followed by a number:

  (area-of-disk 5)

We also say that we APPLY area-of-disk to 5.

The application of a defined operation is evaluated by copying the expression named area-of-disk and by replacing the variable (r) with the number we supplied (5):

  (area-of-disk 5) 
= (* 3.14 (* 5 5))
= (* 3.14 25)
= 78.5

Many programs consume more than one input. Say we wish to define a program that computes the area of a ring, that is, a disk with a hole in the center:

The area of the ring is that of the outer disk minus the area of the inner disk, which means that the program requires two unknown quantities: the outer and the inner radii. Let us call these unknown numbers outer and inner. Then the program that computes the area of a ring is defined as follows:

(define (area-of-ring outer inner) 
  (- (area-of-disk outer)
     (area-of-disk inner)))

The three lines express that area-of-ring is a program, that the program accepts two inputs, called outer and inner, and that the result is going to be the difference between (area-of-disk outer) and (area-of-disk inner). In other words, we have used both basic Scheme operations and defined programs in the definition of area-of-ring.

When we wish to use area-of-ring, we must supply two inputs:

  (area-of-ring 5 3) 

The expression is evaluated in the same manner as (area-of-disk 5). We copy the expression from the definition of the program and replace the variable with the numbers we supplied:

  (area-of-ring 5 3) 

= (- (area-of-disk 5)
     (area-of-disk 3))

= (- (* 3.14 (* 5 5))
     (* 3.14 (* 3 3)))
= ...

The rest is plain arithmetic.

Exercise 2.2.1.   Define the program Fahrenheit->Celsius,⁶ which consumes a temperature measured in Fahrenheit and produces the Celsius equivalent. Use a chemistry or physics book to look up the conversion formula.

Teachpacks

When the function is fully developed, test it using the teachpack convert.ss. The teachpack provides three functions: convert-gui, convert-repl, and convert-file. The first creates a graphical user interface. Use it with

(convert-gui Fahrenheit->Celsius)

The expression will create a new window in which users can manipulate a slider and buttons.

The second emulates the Interactions window. Users are asked to enter a Fahrenheit temperature, which the program reads, evaluates, and prints. Use it via

(convert-repl Fahrenheit->Celsius)

The last operation processes entire files. To use it, create a file with those numbers that are to be converted. Separate the numbers with blank spaces or new lines. The function reads the entire file, converts the numbers, and writes the results into a new file. Here is the expression:

(convert-file "in.dat" Fahrenheit->Celsius "out.dat")

This assumes that the name of the newly created file is in.dat and that we wish the results to be written to the file out.dat. For more information, use DrScheme's Help Desk to look up the teachpack convert.ss.    Solution

Exercise 2.2.2.   Define the program dollar->euro, which consumes a number of dollars and produces the euro equivalent. Use the currency table in the newspaper to look up the current exchange rate.    Solution

Exercise 2.2.3.   Define the program triangle. It consumes the length of a triangle's side and the perpendicular height. The program produces the area of the triangle. Use a geometry book to look up the formula for computing the area of a triangle.    Solution

Exercise 2.2.4.   Define the program convert3. It consumes three digits, starting with the least significant digit, followed by the next most significant one, and so on. The program produces the corresponding number. For example, the expected value of

(convert3 1 2 3) 

is 321. Use an algebra book to find out how such a conversion works.    Solution

Exercise 2.2.5.   A typical exercise in an algebra book asks the reader to evaluate an expression like

for n = 2, n = 5, and n = 9. Using Scheme, we can formulate such an expression as a program and use the program as many times as necessary. Here is the program that corresponds to the above expression:

(define (f n)
  (+ (/ n 3) 2))

First determine the result of the expression at n = 2, n = 5, and n = 9 by hand, then with DrScheme's stepper.

Also formulate the following three expressions as programs:

1. n² + 10

2. (1/2) · n² + 20

3. 2 - (1/n)

Determine their results for n = 2 and n = 9 by hand and with DrScheme.    Solution

2.3  Word Problems

Programmers are rarely handed mathematical expressions to turn into programs. Instead they typically receive informal problem descriptions that often contain irrelevant and sometimes ambiguous information. The programmers' first task is to extract the relevant information and then to formulate appropriate expressions.

Here is a typical example:

Company XYZ & Co. pays all its employees $12 per hour. A typical employee works between 20 and 65 hours per week. Develop a program that determines the wage of an employee from the number of hours of work.

Now that we have a rule, we can formulate a Scheme program:

(define (wage h)
  (* 12 h))

The program is called wage; its parameter h stands for the hours an employee works; and its result is (* 12 h), the corresponding wage.

Exercise 2.3.1.   Utopia's tax accountants always use programs that compute income taxes even though the tax rate is a solid, never-changing 15%. Define the program tax, which determines the tax on the gross pay.

Also define netpay. The program determines the net pay of an employee from the number of hours worked. Assume an hourly rate of $12.    Solution

Exercise 2.3.2.   The local supermarket needs a program that can compute the value of a bag of coins. Define the program sum-coins. It consumes four numbers: the number of pennies, nickels, dimes, and quarters in the bag; it produces the amount of money in the bag.    Solution

Exercise 2.3.3.   An old-style movie theater has a simple profit function. Each customer pays $5 per ticket. Every performance costs the theater $20, plus $.50 per attendee. Develop the function total-profit. It consumes the number of attendees (of a show) and produces how much income the attendees produce.    Solution

2.4  Errors

Errors

When we write Scheme programs, we must follow a few carefully designed rules, which are a compromise between a computer's capabilities and human behavior.⁷ Fortunately, forming Scheme definitions and expressions is intuitive. Expressions are either ATOMIC, that is, numbers and variables; or they are COMPOUND expressions, in which case they start with ``('', followed by an operation, some more expressions, and terminated by ``)''. Each expression in a compound expression should be preceded by at least one space; line breaks are permissible, and sometimes increase readability.

Definitions have the following schematic shape:

(define (f x ... y)
  an-expression)

That is, a definition is a sequence of several words and expressions: ``('', the word ``define'', ``('', a non-empty sequence of names separated by spaces, ``)'', an expression, and a closing ``)''. The embedded sequence of names, f x ... y, introduces the name of the program and the names of its parameters.

Syntax Errors:⁸ Not all parenthesized expressions are Scheme expressions. For example, (10) is a parenthesized expression, but Scheme does not accept it as a legal Scheme expression because numbers are not supposed to be included in parentheses. Similarly, a sentence like (10 + 20) is also ill formed; Scheme's rules demand that the operator is mentioned first. Finally, the following two definitions are not well formed:

(define (P x)
  (+ (x) 10))

(define (Q x)
  x 10)

The first one contains an extra pair of parentheses around the variable x, which is not a compound expression; the second contains two atomic expressions, x and 10, instead of one.

When we click DrScheme's Execute button, the programming environment first determines whether the definitions are formed according to Scheme's rules. If some part of the program in the Definitions window is ill formed, DrScheme signals a SYNTAX ERROR with an appropriate error message and highlights the offending part. Otherwise it permits the user to evaluate expressions in the Interactions window.

Errors

Exercise 2.4.1.   Evaluate the following sentences in DrScheme, one at a time:

(+ (10) 20)
(10 + 20)
(+ +)

Read and understand the error messages.    Solution

Exercise 2.4.2.   Enter the following sentences, one by one, into DrScheme's Definitions window and click Execute:

(define (f 1)
  (+ x 10))

(define (g x)
  + x 10)

(define h(x) 
  (+ x 10))

Read the error messages, fix the offending definition in an appropriate manner, and repeat until all definitions are legal.    Solution

Run-time Errors: The evaluation of Scheme expressions proceeds according to the intuitive laws of algebra and arithmetic. When we encounter new operations, we will extend these laws, first intuitively and then, in section 8, rigorously. For now, it is more important to understand that not all legal Scheme expressions have a result. One obvious example is (/ 1 0). Similarly, if we define

(define (f n)
  (+ (/ n 3) 2))

we cannot ask DrScheme to evaluate (f 5 8).

When the evaluation of a legal Scheme expression demands a division by zero or similarly nonsensical arithmetic operations, or when a program is applied to the wrong number of inputs, DrScheme stops the evaluation and signals a RUN-TIME ERROR. Typically it prints an explanation in the Interactions window and highlights the faulty expression. The highlighted expression triggered the error signal.

Exercise 2.4.3.   Evaluate the following grammatically legal Scheme expressions in DrScheme's Interactions window:

(+ 5 (/ 1 0))

(sin 10 20)

(somef 10)

Read the error messages.    Solution

Exercise 2.4.4.   Enter the following grammatically legal Scheme program into the Definitions window and click the Execute button:

(define (somef x)
  (sin x x))

Then, in the Interactions window, evaluate the expressions:

(somef 10 20)

(somef 10)

and read the error messages. Also observe what DrScheme highlights.    Solution

Logical Errors: A good programming environment assists the programmer in finding syntax and runtime errors. The exercises in this section illustrate how DrScheme catches syntax and run-time errors. A programmer, however, can also make LOGICAL ERRORS. A logical mistake does not trigger any error messages; instead, the program computes incorrect results. Consider the wage program from the preceding section. If the programmer had accidentally defined it as

(define (wage h)
  (+ 12 h))

the program would still produce a number every time it is used. Indeed, if we evaluate (wage 12/11), we even get the correct result. A programmer can catch such mistakes only by designing programs carefully and systematically.

2.5  Designing Programs

Designing Programs

The preceding sections show that the development of a program requires many steps. We need to determine what's relevant in the problem statement and what we can ignore. We need to understand what the program consumes, what it produces, and how it relates inputs to outputs. We must know, or find out, whether Scheme provides certain basic operations for the data that our program is to process. If not, we might have to develop auxiliary programs that implement these operations. Finally, once we have a program, we must check whether it actually performs the intended computation. This might reveal syntax errors, run-time problems, or even logical errors.

To bring some order to this apparent chaos, it is best to set up and to follow a DESIGN RECIPE, that is, a step-by-step prescription of what we should do and the order⁹ in which we should do things. Based on what we have experienced thus far, the development of a program requires at least the following four activities:

;; Contract: area-of-ring : number number  ->  number

;; Purpose: to compute the area of a ring whose radius is
;; outer and whose hole has a radius of inner

;; Example: (area-of-ring 5 3) should produce 50.24

;; Definition: [refines the header]
(define (area-of-ring outer inner)
  (- (area-of-disk outer)
     (area-of-disk inner)))
  
;; Tests:
(area-of-ring 5 3) 
;; expected value
50.24

Understanding the Program's Purpose:

The goal of designing a program is to create a mechanism that consumes and produces data. We therefore start every program development by giving the program a meaningful name and by stating what kind of information it consumes and produces. We call this a CONTRACT.

Here is how we write down a contract for area-of-ring, one of our first programs:¹⁰

;; area-of-ring : number number  ->  number

The semicolons indicate that this line is a COMMENT. The contract consists of two parts. The first, to the left of the colon, states the program's name. The second, to the right of the colon, specifies what kind of data the program consumes and what it produces; the inputs are separated from the output by an arrow.

Once we have a contract, we can add the HEADER. It restates the program's name and gives each input a distinct name. These names are (algebraic) variables and are referred to as the program's PARAMETERS.¹¹

Let's take a look at the contract and header for area-of-ring:

;; area-of-ring : number number  ->  number
(define (area-of-ring outer inner) ...)

It says that we will refer to the first input as outer and the second one as inner.

Finally, using the contract and the parameters, we should formulate a short PURPOSE STATEMENT for the program, that is, a brief comment of what the program is to compute. For most of our programs, one or two lines will suffice; as we develop larger and larger programs, we may need to add more information to explain a program's purpose.

Here is the complete starting-point for our running example:

;; area-of-ring : number number  ->  number
;; to compute the area of a ring whose radius is
;; outer and whose hole has a radius of inner
(define (area-of-ring outer inner) ...)

Hints: If the problem statement provides a mathematical formula, the number of distinct variables in the formula suggests how many inputs the program consumes.

For other word problems, we must inspect the problem to separate the given facts from what is to be computed. If a given is a fixed number, it shows up in the program. If it is an unknown number that is to be fixed by someone else later, it is an input. The question (or the imperative) in the problem statement suggests a name for the program.

Program Examples:

To gain a better understanding of what the program should compute, we make up examples of inputs and determine what the output should be. For example, area-of-ring should produce 50.24 for the inputs 5 and 3, because it is the difference between the area of the outer disk and the area of the inner disk.

We add examples to the purpose statement:

  ;; area-of-ring : number number  ->  number
  ;; to compute the area of a ring whose radius is
  ;; outer and whose hole has a radius of inner
  ;; example: (area-of-ring 5 3) should produce 50.24
  (define (area-of-ring outer inner) ...)

Making up examples -- before we write down the program's body -- helps in many ways. First, it is the only sure way to discover logical errors with testing. If we use the finished program to make up examples, we are tempted to trust the program because it is so much easier to run the program than to predict what it does. Second, examples force us to think through the computational process, which, for the complicated cases we will encounter later, is critical to the development of the function body. Finally, examples illustrate the informal prose of a purpose statement. Future readers of the program, such as teachers, colleagues, or buyers, greatly appreciate illustrations of abstract concepts.

The Body:

Finally, we must formulate the program's body. That is, we must replace the ``...'' in our header with an expression. The expression computes the answer from the parameters, using Scheme's basic operations and Scheme programs that we already defined or intend to define.

We can only formulate the program's body if we understand how the program computes the output from the given inputs. If the input-output relationship is given as a mathematical formula, we just translate mathematics into Scheme. If, instead, we are given a word problem, we must craft the expression carefully. To this end, it is helpful to revisit the examples from the second step and to understand how we computed the outputs for specific inputs.

In our running example, the computational task was given via an informally stated formula that reused area-of-disk, a previously defined program. Here is the translation into Scheme:

(define (area-of-ring outer inner)
  (- (area-of-disk outer)
     (area-of-disk inner)))

Testing:

After we have completed the program definition, we must still test the program. At a minimum, we should ensure that the program computes the expected outputs for the program examples. To facilitate testing, we may wish to add the examples to the bottom of the Definitions window as if they were equations. Then, when we click the Execute button, they are evaluated, and we see whether the program works properly on them.

Testing cannot show that a program produces the correct outputs for all possible inputs -- because there are typically an infinite number of possible inputs. But testing can reveal syntax errors, run-time problems, and logical mistakes.

For faulty outputs, we must pay special attention to our program examples. It is possible that the examples are wrong; that the program contains a logical mistake; or that both the examples and the program are wrong. In either case, we may have to step through the entire program development again.

Figure 3 shows what we get after we have developed the program according to our recipe. Figure 4 summarizes the recipe in tabular form. It should be consulted whenever we design a program.

Phase Goal                  Activity Contract Purpose and Header          to name the function; to specify its classes of   input data and its   class of output data; to describe its purpose; to formulate a header choose a name that fits the problem study the problem for clues on how many unknown ``givens'' the function consumes pick one variable per input; if possible, use names that are mentioned for the ``givens'' in the problem statement describe what the function should produce using the chosen variables names formulate the contract and header:  ;; name : number ...--> number  ;; to compute ... from x1 ...  (define (name x1 ...) ...) Examples          to characterize the input- output relationship via examples search the problem statement for examples work through the examples validate the results, if possible make up examples Body                  to define the function formulate how the function computes its results develop a Scheme expression that uses Scheme's primitive operations, other functions, and the variables translate the mathematical expressions in the problem statement, when available Test                 to discover mistakes   (``typos'' and logic) apply the function to the inputs of the examples check that the outputs are as predicted Figure 4:  The design recipe at a glance

The design recipe is not a magic bullet for the problems we encounter during the design of a program. It provides some guidance for a process that can often appear to be overwhelming. The most creative and most difficult step in our recipe concerns the design of the program's body. At this point, it relies heavily on our ability to read and understand written material, on our ability to extract mathematical relationships, and on our knowledge of basic facts. None of these skills is specific to the development of computer programs; the knowledge we exploit is specific to the application domain in which we are working. The remainder of the book will show what and how much computing can contribute to this most complicated step.

Domain Knowledge: Formulating the body of a program often requires knowledge about the area, also known as domain, from which the problem is drawn. This form of knowledge is called DOMAIN KNOWLEDGE. It may have to be drawn from simple mathematics, such as arithmetic, from complex mathematics, such as differential equations, or from non-mathematical disciplines: music, biology, civil engineering, art, and so on.

Because programmers cannot know all of the application domains of computing, they must be prepared to understand the language of a variety of application areas so that they can discuss problems with domain experts. The language is often that of mathematics, but in some cases, the programmers must invent a language, especially a data language for the application area. For that reason, it is imperative that programmers have a solid understanding of the full possibilities of computer languages.