Our main objectives in this course are (1) to learn about algorithms, step-by-step methods for solving problems, and (2) to learn how to direct computers to perform such algorithms for us. A programming language, such as Scheme, is a formal notation in which one can express algorithms so exactly that a computer can perform them without any other assistance from human beings. The expression of an algorithm in such a notation is called a program, and the computer is said to be executing the program when it is performing the algorithm as directed.
Although not all of the problems that we’d like computers to solve are arithmetical, the simplest examples belong to that category, and we’ll start with a few of them. Here, for instance, is a program, written in Scheme, that directs the computer to find the answer to the question “what is the square root of 137641?”
In order to make the Scheme environment answer that question, you need to learn how to work with Scheme. There are many different implementations of Scheme available. We’ll use DrRacket along with a library of procedures that we have designed for this course. In the DrRacket environment, which you will use to develop your programs, you can work interactively with Scheme, typing a bit of code, finding a result, typing another bit of code, finding a result, and so on and so forth.
> (sqrt 137641) 371
The full Scheme language contains several hundred primitive procedures
– operations, such as finding the square root of a number, for
which a Scheme interpreter can use prepackaged algorithms. DrRacket
includes implementations of all of those procedures, and many more. Some
programmers who are experts on square roots and on the idiosyncrasies
of our computers have figured out and written up a step-by-step method
for computing the square root of any number, using only the very
elementary transformations that the processor can perform. Most Scheme
sqrt as the name of this algorithm and knows
where the processor instructions that carry it out are stored. When the
interpreter receives a command to compute a square root, it recovers
these instructions and arranges for the processor to follow them.
A procedure call is a command that directs the Scheme interpreter
to activate a procedure such as
sqrt is the name of
the procedure, and
(sqrt 137641) is the procedure call.) In Scheme,
every procedure call begins with a left parenthesis and ends with the
matching right parenthesis. Within the parentheses, one always begins by
identifying the procedure to be called and then continues by identifying
the arguments, the values that the procedure is supposed to operate
sqrt procedure takes only one argument, the number of which you
want the square root, but other procedures take two or more arguments,
and some need no arguments at all.
All arithmetic in Scheme is done with procedure calls. The primitive
+ adds numbers together, the primitive procedure
subtracts one number from another. Similarly, the primitive procedure
* performs multiplication, and the primitive procedure
division. The fact that in a procedure call the procedure is identified
first makes calls to these procedures look different from ordinary
arithmetic expressions: For instance, to tell DrRacket to subtract 68343
from 81722, one gives the command
(- 81722 68343). Why someone might
want to compute that value is left as an exercise for the reader.
Other Scheme procedures include
expt. The Scheme procedure
abs computes the absolute value of its argument. The Scheme procedure
for raising a number to some power is
As you may have noted, the appropriate way to write a Scheme expression
(operation operand_1 ... operand_n). That is, you parenthesize
the expression (and any nontrivial subexpressions) and you place the
operation before the operands.
It is harmless, though unproductive, to try to give a Scheme interpreter ordinary arithmetic expressions, in which the procedure is written between the operands.
However, it is both harmful and unproductive to include extra parentheses.
If you write
(sqrt (123)), the Scheme interpreter will issue an error
message to tell you that
123 is not an operation. Why? The Scheme
interpreter assumes that operations come after
What if you want to compute something more complex than a simple sum, product, difference, or whatever? Sometimes, you want to combine operations. For example, to find the average of four numbers, we need to both sum the numbers and divide the result by four. One strategy would be to compute the sum, copy that number, and then insert it into an expression that divides by four.
However, Scheme provides a much more sensible solution: You can
nest expressions, one inside another. When Scheme encounters nested
expressions, it evaluates the inner expressions first. For example,
consider the expression
(/ (+ 90 80 10 90) 4) tells the Scheme
interpreter to first add 90, 80, 10, and 90, and then to divide the
result by 4. Similarly,
(+ (* 80 0.45) (* 95 0.35) (* 100 0.20))
tells the Scheme interpreter to multiply 80 by 0.45, to multiply 95 by
0.35, to multiply 100 by 0.20, and to sum the results. Interestingly,
the Scheme interpreter is free to do the multiplications in any order,
as long as it completes all three before it does the sum. For example,
it might first multiply 100 by 0.20 or it might first multiply 80 by
0.45. (DrRacket tends to evaluate subexpressions from left-to-right.)
DrRacket’s Scheme interpreters, like most versions of Scheme, can
also learn new names for things by reading definitions. Here’s what a
definition looks like
(define name value). For example:
(define days-in-a-week 7)
Like a procedure call, a definition begins and ends with matching
parentheses. To distinguish between definitions and procedure calls,
the Scheme interpreter looks at what comes immediately after the left
parenthesis. In a definition, the keyword
define must appear at that
point. The keyword
define is not the name of a procedure; it is part
of the syntactic structure of the Scheme programming language. Its only
role is to serve as the mark of a definition.
After the keyword
define, a definition contains the name being defined
and an expression that identifies the value that the name should stand
for. In this example, the name is
days-in-a-week. (Notice that in Scheme
a name can, and often does, contain hyphens internally.) The value that
it names is the number 7. Once DrRacket’s Scheme interpreter has seen
this definition, it remembers that
days-in-a-week stands for 7.
The value that gets a new name need not be a number; it can be anything,
even a computation or the name of a procedure. For example, if you don’t
like the name
* for the multiplication procedure and would rather call
it by the name
multiply, just start each sequence of interactions with
DrRacket by giving it the definition
(define multiply *). (Alternately,
place the definition in a file, and load the file in your interactions
pane or definitions pane.)
At this point, we hope you’re wondering what other useful and interesting procedures are built into Scheme. Section 6.2.5 of the Revised report on the algorithmic language Scheme contains a list of the ones that are mainly about numbers, and that’s only one section of the full roster of standard Scheme procedures. Fortunately, most of the primitive procedures perform small, simple jobs and are easily learned.
What do you expect the value of the following expressions to be?
(square 4) (* (+ 4 2) 2) (- 1 (/ 1 2)) (/ (- (+ 2 3) 1) 2) (expt 2 3)
At the beginning of the next class, compare your answers to your lab partner’s.