In the beginning, people thought of computers as number crunchers. And indeed, computers are very good at working with numbers. Since teachers start their firstgraders 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.
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:
5 5 2/3 17/3 #i1.4142135623731 
Like a pocket calculator, the simplest of computers, Scheme permits programmers to add, subtract, multiply, and divide numbers:
(+ 5 5) (+ 5 5) (+ 5 5) ( 5 5) (* 3 4) (/ 8 12) 
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.^{4}
Finally, Scheme not only provides simple arithmetical operations but a whole range of advanced mathematical operations on numbers. Here are five examples:
(sqrt A)
computes (A)^{1/2};
(expt A B)
computes A^{B};
(remainder A B)
computes the remainder of the integer division A/B;
(log A)
computes the natural logarithm of A
;
and
(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.
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
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^{5}
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 areaofdisk
. Using this name,
we would express the rule for computing the area of a disk as
follows:
(define (areaofdisk r) (* 3.14 (* r r)))
The two lines say that areaofdisk
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, areaofdisk
uses only one basic operation, multiplication, but define
d
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
areaofdisk
followed by a number:
(areaofdisk 5)
We also say that we APPLY
areaofdisk
to 5
.
The application
of a define
d operation is evaluated by copying the
expression named areaofdisk
and by replacing the variable
(r
) with the number we supplied (5
):
(areaofdisk 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 (areaofring outer inner) ( (areaofdisk outer) (areaofdisk inner)))
The three lines express that areaofring
is a program, that the
program accepts two inputs, called outer
and inner
, and that the result is going to be the difference
between (areaofdisk outer)
and (areaofdisk
inner)
. In other words, we have used both basic Scheme operations
and define
d programs in the definition of areaofring
.
When we wish to use areaofring
, we must supply two inputs:
(areaofring 5 3)
The expression is evaluated in the same manner as (areaofdisk
5)
. We copy the expression from the definition of the program and replace
the variable with the numbers we supplied:
(areaofring 5 3) = ( (areaofdisk 5) (areaofdisk 3)) = ( (* 3.14 (* 5 5)) (* 3.14 (* 3 3))) = ...
The rest is plain arithmetic.
Exercise 2.2.1.
Define the program Fahrenheit>Celsius
,^{6} 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:
convertgui
, convertrepl
, and convertfile
.
The first creates a graphical user interface. Use it with
(convertgui 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
(convertrepl 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:
(convertfile "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:
n^{2} + 10
(1/2) · n^{2} + 20
2  (1/n)
Determine their results for n = 2 and n = 9 by hand and with DrScheme. Solution
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.The last sentence is the first to mention the actual task: to write a program that determines one quantity based on some other quantity. More specifically, the program consumes one quantity, the number of hours of work, and produces another one, the wage in dollars. The first sentence implies how to compute the result, but doesn't state it explicitly. In this particular example, though, this poses no problem. If an employee works h hours, the wage is
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, neverchanging 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 sumcoins
. 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 oldstyle 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 totalprofit
. It consumes the number
of attendees (of a show) and produces how much income the attendees
produce.
Solution
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.^{7} 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) anexpression)
That is, a definition is a sequence of several words and expressions:
``('', the word ``define'', ``('', a nonempty 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:^{8} 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
Runtime 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 RUNTIME 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 runtime 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.
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, runtime 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 stepbystep prescription of what we should do and the order^{9} 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:
Here is how we write down a contract for areaofring
, one of our
first programs:^{10}
;; areaofring : 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.^{11}
Let's take a look at the contract and header for areaofring
:
;; areaofring : number number > number
(define (areaofring 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 startingpoint for our running example:
;;areaofring : number number > number
;; to compute the area of a ring whose radius is ;;outer
and whose hole has a radius ofinner
(define (areaofring 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.
areaofring
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:
;;areaofring : number number > number
;; to compute the area of a ring whose radius is ;;outer
and whose hole has a radius ofinner
;; example:(areaofring 5 3) should produce 50.24
(define (areaofring 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.
define
d 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 inputoutput 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 areaofdisk
, a previously
define
d program. Here is the translation into Scheme:
(define (areaofring outer inner) ( (areaofdisk outer) (areaofdisk inner)))
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, runtime 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.

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 nonmathematical 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.
^{4} Another advantage of Scheme's notation is that we always know where to place an operator or where to find it: to the immediate right of the opening parenthesis. This is important in computing because we need many more operators than just the few numerical operators that we use in arithmetic and algebra.
^{5} It is common to speak of the area of a circle, but mathematically speaking, the circle is only the disk's outer edge.
^{6} An arrow is keyed in as  followed by >.
^{7} This statement is true for any other programming
language
as well, for example, spreadsheet languages, C, word processor
macro. Scheme is simpler than most of these and easy to understand for
computers. Unfortunately, to human beings who grow up on infix expressions
such as 5 + 4, Scheme prefix expressions such as (+ 5 4)
initially appear to be complicated. A bit of practice will quickly
eliminate this misconception.
^{8} We will find out in section 8 why such errors are called syntax errors.
^{9} As we will see later, the order is not completely fixed. It is possible, and for a number of reasons, desirable to switch the order of some steps in some cases.
^{10} An arrow is keyed in as  followed by >.
^{11} Others also call them FORMAL ARGUMENTS or INPUT VARIABLES.