...recipes.
Readers whose experience is exclusively based on programming languages such as C/C++, Basic, and Pascal should read ``procedure'' or ``method'' where the preface mentions ``program.'' 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...difficulty.
Our design recipes were inspired by work with Daniel P. Friedman on structural recursion, with Robert Harper on type theory, and by Michael A. Jackson's design method. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...site.
Scheme has an official definition-the Revised Report on Scheme, edited by Richard Kelsey, William Clinger, and Jonathan Rees-and many implementations. For a copy of the report and for a list of alternative Scheme implementations, visit www.schemers.org on the Web. Note, however, that the language of this book extends that of the report and is tailored to beginners. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...afterwards.
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. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...area
It is common to speak of the area of a circle, but mathematically speaking, the circle is only the disk's outer edge. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Fahrenheit->Celsius,
An arrow is keyed in as - followed by >. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Errors:
We will find out in section [cross-reference] why such errors are called syntax errors. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...behavior.
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. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...order
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. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...programs:
An arrow is keyed in as - followed by >. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...size=-1>PARAMETERS.
Others also call them FORMAL ARGUMENTS or INPUT VARIABLES. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...system:
See The World Book Encyclopedia 1993, Weights and Measurements. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...true.
In truth, the operations and and or are different from not, which is why they are typeset in different fonts. We ignore this minor difference for now. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...holds.
The use of brackets, that is, [ and ], in place of parentheses is optional, but it sets apart the conditional clauses from other expressions and helps people read functions. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...expression.
If the cond-expression has no else clause and all conditions evaluate to false, an error is signaled in Beginning Student Scheme. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...characters
Not all keyboard characters are legal in symbols. For example, a blank space or a comma are illegal. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...game.
MasterMind, the commercial version of this game, is played in a different manner. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...structures.
An alternative terminology is ``to access the fields of a record.'' We prefer to think of structure values as containers from which we can extract other values. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...canvas.
For more documentation, see DrScheme's Help Desk. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...computations.
DrScheme provides an optional tool that permits programmers to check whether users and programmers respect the data definition for a particular structure. To do so, a programmer must state data definitions in a special language. Although checking the adherence to data definitions is important for large programs, an introductory course can avoid this topic. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...programs.
This series of sections was inspired by Ms. Karen Buras and her son. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...three-letter
In reality, we would want to play the game with words of arbitrary length, but a game based on three-letter words is easier to implement for now. We return to the problem in exercise [cross-reference]. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...stages.
Thanks to Mr. John Clements for the artistic version of draw-next-part. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...data:
We have also discussed images and strings, but we ignore these for now. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...definitions:
The posn structure is automatically provided in DrScheme's teaching languages and should never be defined. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...radius.
The perimeter of a circle is also known as circumference. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...language.
We use different fonts to distinguish the words of different categories. Constants and primitive operations are type set in sans serif, variables in italics, and keywords in boldface. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...HREF="node43.htm#figsynbeginner">[cross-reference].
This grammar describes only that portion of Scheme we have used so far (minus variable and structure definitions), which still covers a large subset of the full language. Scheme is a bit larger, and we will get to know more of it in the remaining parts of the book. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...rest.
The traditional names are car and cdr, but we will not use these nonsensical names. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...elements.
It is common that a data definition describes a class of data that contains more than the intended elements. This limitation is inherent and is just one of the many symptoms of the limits of computing. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...part.
Numbers also seem to be arbitrarily large. For inexact numbers, this is an illusion. For precise integers, this is indeed the case, and we will discuss them later in this part. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...example,
Since we don't know yet how to compare two lists with a function, we use the old style of specifying examples and tests. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...HREF="node58.htm#figtoytable">[cross-reference].
Thanks to Mr. John Clements for drawing these pictures. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...etc.
It is important to start counting at 0 so that we can use the natural numbers for counting the number of items on a list or the members of a family tree. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...rigorous,
For that, we need to defer to a course on mathematical sets. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...functions.
The term ``wish list'' in this context is due to Dr. John Stone. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...corners.
Mr. Paul C. Fisher inspired this section. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...arrangements.
The mathematical term is permutation. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...NAME=15201>convention,
The convention is due to LISP, an early but highly advanced programming language designed in 1958. Scheme inherited many ideas from LISP, but it is a different language. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...NAME=18231>directories.
On some computers, a directory is called a folder. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...tree.
The picture explains why computer scientists call such directories trees. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...sketch:
We discuss this form of recursion in detail in part [cross-reference]. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...atoms:
Some people also include empty and keyboard characters (chars). 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...expected.
As we evaluate expressions in this manner, our list of definitions grows longer and longer. Fortunately, DrScheme knows how to manage such growing lists. Indeed, it occasionally throws out definitions that will never be used again. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...symbol.
Computing borrows the term ``abstract'' from mathematics. A mathematician refers to ``6'' as an abstract number because it only represents all different ways of naming six things. In contrast, ``6 inches'' or ``6 eggs'' are concrete instances of ``6'' because they express a measurement and a count. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...size=-1>POLYMORPHIC
The word ``poly'' means ``many'' and ``morphic'' means shape. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...preparation.
A currently popular method of abstraction is INHERITANCE in class-based object-oriented programming languages. Inheritance is quite similar to functional abstraction, though it emphasizes those aspects that change over those that stay the same. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...button.
The program has also cleared the result field to avoid any misunderstanding. Similarly, the user could also just hit the enter key instead of clicking the button. We ignore such subtleties here. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...structures
More precisely, we construct an object, but we do not need to understand the distinction between a structure and an object here. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...provides.
The gui-items aren't really structures, which explains the font of the operations' names. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...one.
In some cases, an infinite sequence may also have a sum. Specifically, adding up more and more of the terms of a sequence produces numbers that are closer and closer to some number, which we call the sum. For example, the sum of the sequence

134#134

is 2. In contrast, the sequence

135#135

does not have a sum. 

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...slope.
The process of decreasing 169#169 to 0 is a convergence (or limit) process. It does not always succeed, that is, for some function graphs, the process does not end properly. We ignore those cases, but they are common and require special attention. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...fprime:
If x is a number, then adding or subtracting 169#169 yields a number. If, by accident, we apply fprime to something else, both expressions signal an error. It is therefore acceptable to act as if the expressions were values. In general, this is not true. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...size=-1>SOLVABLE
For this part of the book, trivial is a technical term. It will be explained in section [cross-reference]. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...N).
Of course, we could have just argued that the sorted version of a one-item list is the list, which is the basis of exercise [cross-reference]. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...equivalent.
The concept of observably equivalent functions and expressions plays a central role in the study of programming languages and their meaning. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...numbers.
The material on the greatest common divisor was suggested by John Stone. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Bezier.
Ms. Geraldine Morin suggested this exercise. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...computers,
The tradition of breaking a file into lines is due to the use of punch cards with early mechanical computers, dating back to the 1890 census. It is meaningless for file storage in modern computing. Unfortunately, this historical accident continues to affect the development of computing and software technology in a negative manner. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...cube.
If the equation is originally presented as g(x) = h(x), we set f(x) = g(x) - h(x) to transform the equation into the standard form. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...r0.
The tangent of a function f at 204#204 is the linear function

205#205

The function f' is the derivative of f, and f'(r0) is the slope of f at r0. Furthermore, the root of a linear function is the intersection of a straight line with the x axis. In general, if the line's equation is

206#206

then its root is -b/a. In our case, the root of f's tangent is

207#207

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...evaluation.
We speak of an abstract running time because the measure ignores the details of how much time primitive steps take and how much time the overall evaluation takes. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...maximum.
More precisely, the evaluation consists of 243#243 steps, but

244#244

which shows that we ignore a (small) constant when we say on the order of 245#245. 

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...definition:
The most convenient way to construct this list is to evaluate (build-list (add1 N) identity). 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...faster:
The time of evaluation will differ from computer to computer. These measurements were conducted on a Pentium 166Mhz running Linux. Measuring timings is also difficult. At a minimum, each evaluation should be repeated several times, and the time reported should be the average of those measurements. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...numbers;
We can force Full Scheme to interpret numbers with a dot as exact by prefixing the numbers with #e. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...set!
This keyword is pronounced set-bang. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...V.
We have already encountered several kinds of effects: drawing to a canvas, changing the text field in a GUI, the creating of files by teachpacks, and so on. These effects aren't as complex as those of set! because they don't affect the program proper. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...substitution:
Because the calculation does not affect the function definitions, we do not include them in the calculation here. This convention saves space and time, but it should be used carefully. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...up.
A device should also go into the least harmful state when it detects an internal failure. Unfortunately, many software engineers don't follow this rule. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...language.
The grammar misses and-expression and or-expression, and a few other short-cuts. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...value.
We also evaluate the right-hand side of definitions if they are not values, but we can safely ignore this minor issue here. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...values,
It lacks a specification of structural values, but they play no role in this discussion. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...logicians
Logic is to computing what mathematics is to physics. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...definition.
For simplicity, we use this simple approximation. When a program also uses set!-expression, we must rely on the refinement of intermezzo 8.3 to understand its behavior completely. Also see the note on this topic on page [cross-reference]. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...outline:
The notation (vectorof X) is analogous to (listof X). 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...field.
Scheme proper provides list mutators, and a Scheme programmer would use them to represent a hand as a list of cards. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...kind
A program could set up an entirely new board for every new stage in the algorithm and search for solutions in parallel. The additional work is, however, prohibitive for a human being, which is why humans shy away from such simulations. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...extraction.
An object in a language such as Java is a function with many different bodies. Each method represents a different way of extracting data from an object. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

PLT