Revised
3
Report on the Algorithmic Language
Scheme
JONATHAN REES AND WILLIAM CLINGER (Editors)
H. ABELSON R. K. DYBVIG C. T. HAYNES G. J. ROZAS
N. I. ADAMS IV D. P. FRIEDMAN E. KOHLBECKER G. J. SUSSMAN
D. H. BARTLEY R. HALSTEAD D. OXLEY M. WAND
G. BROOKS C. HANSON K. M. PITMAN
Dedicated to the Memory of ALGOL 60
SUMMARY
The report gives a defining description of the program-
ming language Scheme. Scheme is a statically scoped and
properly tail-recursive dialect of the Lisp programming
language invented by Guy Lewis Steele Jr. and Gerald
Jay Sussman. It was designed to have an exceptionally
clear and simple semantics and few different ways to form
expressions. A wide variety of programming paradigms, in-
cluding imperative, functional, and message passing styles,
find conven ient expression in Scheme.
The introduction offers a brief history of the language and
of the report.
The first three chapters present the fundamental ideas of
the language and describe the notational conventions used
for describing the language and for writing programs in the
language.
Chapters 4 and 5 describe the syntax and semantics of
expressions, programs, and defini tion s.
Chapter 6 describes Scheme’s built-in procedures, which
include all of the language’s data manipulation and in-
put/output primitives.
Chapter 7 provides a formal syntax for Scheme written in
extended BNF, along with a formal denotational semantics.
The report concludes with an example of the use of the
language and an alphabetic index.
CONTENTS
Introduction . . . . . . . . . . . . . . . . . . . . . . 2
1. Overview of Scheme . . . . . . . . . . . . . . . . . 3
1.1. Semantics . . . . . . . . . . . . . . . . . . . 3
1.2. Syntax . . . . . . . . . . . . . . . . . . . . . 3
1.3. Notation and terminology . . . . . . . . . . 3
2. Lexical conventions . . . . . . . . . . . . . . . . . 4
2.1. Identifiers . . . . . . . . . . . . . . . . . . . 4
2.2. Whitespace and comments . . . . . . . . . . 5
2.3. Other notations . . . . . . . . . . . . . . . . 5
3. Basic concepts . . . . . . . . . . . . . . . . . . . . 5
3.1. Variables and regions . . . . . . . . . . . . . 5
3.2. True and false . . . . . . . . . . . . . . . . . 6
3.3. External representations . . . . . . . . . . . 6
4. Expressions . . . . . . . . . . . . . . . . . . . . . 6
4.1. Primitive expression types . . . . . . . . . . 6
4.2. Derived expression types . . . . . . . . . . . 8
5. Program structure . . . . . . . . . . . . . . . . . . 11
5.1. Programs . . . . . . . . . . . . . . . . . . . 11
5.2. Definitions . . . . . . . . . . . . . . . . . . . 11
6. Standard procedures . . . . . . . . . . . . . . . . 12
6.1. Booleans . . . . . . . . . . . . . . . . . . . . 12
6.2. Equivalence predicates . . . . . . . . . . . . 13
6.3. Pairs and lists . . . . . . . . . . . . . . . . . 14
6.4. Symbols . . . . . . . . . . . . . . . . . . . . 17
6.5. Numbers . . . . . . . . . . . . . . . . . . . . 17
6.6. Characters . . . . . . . . . . . . . . . . . . . 23
6.7. Strings . . . . . . . . . . . . . . . . . . . . . 24
6.8. Vectors . . . . . . . . . . . . . . . . . . . . 25
6.9. Control features . . . . . . . . . . . . . . . . 26
6.10. Input and output . . . . . . . . . . . . . . . 28
7. Formal syntax and semantics . . . . . . . . . . . . 30
7.1. Formal syntax . . . . . . . . . . . . . . . . . 30
7.2. Formal semantics . . . . . . . . . . . . . . . 32
7.3. Derived expression types . . . . . . . . . . . 35
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Example . . . . . . . . . . . . . . . . . . . . . . . . . 37
Bibliography and references . . . . . . . . . . . . . . 38
Alphabetic index of definitions of concept s ,
keywords, and procedures . . . . . . . . . . 41
2 Revised
3
Scheme
INTRODUCTION
Programming languages should be designed not by piling
feature on top of feature, but by removing the weaknesses
and restrictions that make additional features appear nec-
essary. Scheme demonstrates that a very small number of
rules for forming expressions, with no restrictions on how
they are composed, suffice to form a practical and efficient
programming language that is flexible enough to support
most of the major programming paradigms in use today.
Scheme has i nfl ue n ced the evolution of Lisp. Scheme was
one of the first programming languages to incorporate firs t
class procedures as in the lambda calculus, thereby proving
the usefulness of static scope rules and block structure in
a dynamically typed language. Scheme was the first major
dialect of Lisp to distinguish procedu r e s from lambda ex-
pressions and symbols, to use a single lexical environment
for all variables, and to evaluate the operator position of
a proce du r e call in the same way as an operand p osi tion.
By relying entirely on procedure calls to express iteration,
Scheme emph asiz ed the fact that tail-recursive procedure
calls are essentially goto’s that pass arguments. Scheme
was th e first widely used programming language to em-
brace first class escape procedures, from which all known
sequential control struct ur e s can be synthesized. A few
of these inn ovations have recently been incorporated into
Common Lisp, while others remain to be adopted.
Background
The first descripti on of Scheme was written in 1975 [48 ]. A
revised report [44] appeared in 1978, which described the
evolution of the language as its MIT implementation was
upgraded to support an innovative compiler [41]. Three
distinct projects began in 1981 and 1982 to use variants
of Scheme for courses at MIT, Yale, and Indiana Univer-
sity [30, 23, 10]. An introductory computer science text-
bo ok using Scheme was published in 1984 [1].
As might be expected of a language used primarily for ed-
ucation and research, Scheme has always evolved rapidly.
This was no problem when Scheme was used only within
MIT, but as Scheme became more widespread, local di-
alects b egan to diverge until students and researchers oc-
casionally found it difficult to und er s t and code written at
other sites.
Fifteen repres entatives of the major implementations of
Scheme therefore met in October 1984 to work toward
a better and more widely accepted standard for Scheme.
Participating in this workshop were Hal Abelson, Nor-
man Adams, David Bartley, Gar y Brooks, William Clinger,
Daniel Friedman, Robert Halstead, Chris Hanson, Christo-
pher Haynes, Eugene Kohlbecker, Don Oxley, Jonathan
Rees, Guillermo Rozas, Gerald Jay Sussman, and Mitchell
Wand. Kent Pitman made valuable contributions to the
agenda for the workshop but was unable to attend the ses-
sions.
Subsequent electronic mail discussions and committee work
completed the definition of the language. Gerry Su s sman
drafted the section on numbers, Chris Hanson drafted the
sections on characters and strings, and Gary Brooks and
William Clinger drafted the sections on inp ut and output.
William Clinger recorded the decisions of the workshop and
compiled the pieces into a coherent document. The “Re-
vised revised re port on Scheme” [4] was publish ed at MIT
and Indiana University in the summer of 1985. Another
round of revision in the spring of 1986, again accomplished
almost entirely by electronic mail, resulted in the present
report.
We intend this report to belong to the entire Scheme com-
munity, and so we grant permission to copy it in whole or in
part without fee. In particular, we encourage implementors
of Scheme to use this report as a starting point for manuals
and other documentation, modifying it as necessary.
Acknowledgements
We would like to thank the following people for their
comments and criticisms: Alan Bawden, George Carrette,
Andy Cromarty, Andy Freeman, Richard Gabriel, Yekta
G¨ursel, Ken Haase, Paul Hudak, Richard Kelsey, Chris
Lindblad, Mark Meyer, Jim Miller, Jim Philbin, John
Ramsdell, Guy Lewis Steele Jr., Julie Sussman, Perry Wa-
gle, Daniel Weise, and Henry Wu. We thank Carol Fes-
senden, Daniel Friedman, and Christopher Haynes for per-
mission to use text from the Scheme 311 version 4 reference
manual. We thank Texas Instruments, Inc. for permission
to use text from the TI Scheme Language Reference M an-
ual. We gladly acknowledge the influen c e of manuals for
MIT Scheme, T, Scheme 84, Common Lisp, and Algol 60.
We also thank Betty Dexter for the extreme effort she put
into setting this report in T
E
X, and Donald Knuth for de-
signing the program that caused her troubles.
The Artificial Intelligence Laboratory of the M as sachusetts
Institute of Techn ology and the Computer S cie nc e Depart-
ment of Ind iana University supported the preparation of
this report. Support for the MIT work was provided in
part by the Advanc ed Research Projects Agency of the
Department of Defense under Office of Naval Research con-
tract N00014-80-C-0505. Support for the Indi ana Univer-
sity work was provided by NSF grants NCS 83-04567 and
NCS 83-03325.
1. Overview of Scheme 3
DESCRIPTION OF THE LANGUAGE
1. Overview of Scheme
1.1. Semantics
This section gives an overview of Scheme’s semantics. A
detailed informal semantics is the subject of chapters 3
through 6. For r ef er en c e purposes, section 7.2 provides a
formal semantics of Scheme.
Following Algol, Scheme is a statically scoped program-
ming language. Each use of a variable is associated with a
lexically apparent binding of that variable.
Scheme has latent as opposed to manifest types. Types
are associated with values (also called objects) rather than
with var iabl es . (Some authors refer to languages with
latent types as weakly typed or dynamically typed lan-
guages.) Other languages with latent types are APL,
Snobol, and other dialects of Lisp. Languages with mani-
fest types (sometimes referred to as strongly typed or s tat-
ically typed languages) include Algol 60, Pascal, and C.
All objects created in the c our s e of a S cheme computation,
including procedures and continuations, have unlimi te d ex-
tent. No Scheme object is ever de st r oyed. The reason that
implementations of Scheme do not (usually!) run out of
storage is that they are permitted to reclaim the storage
occupied by an object if they can prove that the object
cannot possibly matter to any future computation. Other
languages in which most objects have unli mite d extent in-
clude APL and other Lisp dialects.
Implementations of Scheme are required to be properly
tail-recursive. This allows the execu tion of an iterative
computation in constant space, even if the iterative compu-
tation is described by a syntactically recursive procedure.
Thus with a tail-recursive implementation, iteration can be
expressed using the ordinary procedure-call mechanics, so
that special iteration constructs are usefu l only as syntactic
sugar.
Scheme procedures are objects in their own right. Pro-
cedures can be created dynamically, stor ed in data struc-
tures, returned as results of procedures, and so on. Other
languages with these p r opertie s include Common Lisp and
ML.
One distinguishing fe atur e of Scheme is that continuations ,
which in most other languages only operate behin d t he
scenes, also have “first-class” status. Continuations are
useful for implementing a wide variety of advanced control
constructs, including non-local exits, backtracking, and
coroutines. See section 6.9.
Arguments to Scheme procedures are always passed by
value, which means that the actual argument expr e ss i ons
are evaluated before the procedu r e gains control, whether
the procedure needs the result of the evaluation or not.
ML, C, and APL are three oth er languages that always
pass arguments by value. This is distinct from the lazy-
evaluation semantics of SASL, or the call-by-name se man-
tics of Algol 60, where an argument expression is not eval-
uated unless its value is needed by the procedure .
1.2. Syntax
Scheme employs a pare nthesized-list Polish notation to de-
scribe programs and (other) data. The syntax of Scheme,
like that of most Lisp dialects, provides for great expressive
power, largely due to its simplicity. An important conse-
quence of this simplicity is the susceptibility of Scheme
programs and data to uniform treatment by other Scheme
programs. As with other Lisp dialects, the read primitive
parses its input; that is, it per for ms syntactic as well as
lexical decomposition of what it reads.
1.3. Notation and terminology
1.3.1. Essential and non-essential features
It is required that every implementation of Scheme support
features that are marked as b ei ng essential. Features not
explicitly marked as essential are not essential. Implemen-
tations are free to omit non-essential features of Scheme
or to add extensions, provided the extensions are not in
conflict with the language reported here .
1.3.2. Error situ ati on s and unspecified b eh avior
When speaking of an error situation, this report uses the
phrase “an error is signalled” to indicate that implemen-
tations must detect and report the error. If such wording
does not appear in the discussion of an error, then imple-
mentations are not required to detect or report the error,
though they are encouraged to do so. An err or situation
that implementations are not required to de te ct is usually
referred to simply as “an error.”
For example, it is an er r or for a procedure to be passed an
argument that the procedure is not explicitly specified to
handle, even t hough such domain errors are s e ld om men-
tioned in this report. Implementations may extend a pro-
cedure’s domain of definition to inclu de other arguments.
If the value of an expression is said to be “unspecified,”
then the expression must evaluate to some object without
signalling an error, but the value depends on the imple-
mentation; this report explicitly does not say what value
should be returned.
1.3.3. Entry format
Chapters 4 and 6 are organized into entries. Each entry de-
scribes one language feature or a group of related features,
4 Revised
3
Scheme
where a feature is either a syntactic construct or a built-in
procedure. An entry b e gins with one or more header lines
of the form
template essential category
if the feature is an essential feature, or simply
template category
if the feature is not an essential feature.
If category is “syntax”, the entry describes an expression
type, and th e header line gives the syntax of the expression
type. Components of expressions are designated by syn-
tactic variables, which are written using angle brackets,
for example, hexpressioni, hvariablei. Syntactic variables
should be understood to denote segments of program text;
for example, hexpr es s ioni stands for any string of charac-
ters which is a syntactically valid expression. The notation
hthing
1
i . . .
indicates zero or more occurrences of a hthingi, and
hthing
1
i hthing
2
i . . .
indicates one or more occurrences of a hthingi.
If category is “procedure”, then the entry describes a pro-
cedure, and the header line gives a template for a call t o the
procedure. Argument names in the template are italicized .
Thus the header line
(vector-ref vector k ) essential procedure
indicates that the essential built-in procedure vector-ref
takes two arguments, a vector vector and an exact non-
negative integer k (see below). The header lines
(append list
1
list
2
) essential procedure
(append list . . . ) procedure
indicate that in all implementations, the append procedure
must be defined to take two arguments, and s ome imple-
mentations will extend it to take zero or more arguments.
It is an error for an operation to b e presented with an ar-
gument that it is not specified to handle. For succinctness,
we follow the convention that if an argument name is also
the name of a type, then this implies a restriction on the
type of that argument to the procedure. For example, the
header line for vector-ref given above dictates that first
argument to vector-ref must be a vector. The following
naming conve ntions also imply type restrictions:
obj any object
z, z
1
, . . . z
j
, . . . complex, real, rational, integer
x, x
1
, . . . x
j
, . . . real, rational, integer
y, y
1
, . . . y
j
, . . . real, rational, integer
q, q
1
, . . . q
j
, . . . rational, integer
n, n
1
, . . . n
j
, . . . integer
k, k
1
, . . . k
j
, . . . exact non-negative integer
1.3.4. Evaluation examples
The symbol “=⇒” used in program examples should be
read “evaluate s to.” For example,
(* 5 8) =⇒ 40
means that the expression (* 5 8) evaluates to the ob-
ject 40. Or, more precisely: the expression given by the
sequence of characters “(* 5 8)” evaluates, in the initial
environment, to an object that may be repre se nted exter-
nally by the sequence of characters “40”. See section 3.3
for a discussion of external repres entations of obje ct s.
2. Lexical conventions
This section gives an informal account of some of the lexical
conventions used in wri tin g Scheme programs. For a formal
syntax of Scheme, see section 7.1.
Upper and lower case forms of a letter are never distin-
guished except within character and string constants. For
example, Foo is the same identifier as FOO, and #x1AB is
the same number as #X1ab.
2.1. Identifiers
Most identifiers allowed by oth er programming languages
are also acceptable to Scheme. The pre ci se rules for form-
ing identifiers vary among implementations of Scheme, bu t
in all implementations a sequence of letters, digits, and “ex-
tended alphabetic characters” that begins with a character
that cannot begin a number is an identifier. I n addition, +
and - (which can begin numbers) are identifiers. Here are
some examples of identifiers:
lambda q
list->vector soup
+ V17a
<=? a34kTMNs
the-word-recursion-has-many-meanings
Extended alphabetic characters may be used in identifiers
exactly as if they were letters. The following are extended
alphabetic characters:
* / < = > ! ? : $ % _ & ~ ^
See section 7.1.1 for a formal syntax of identifiers.
Identifiers have several uses within Scheme programs:
• Certain identifiers are reserved for use as syntactic
keywords (see below).
• Any identifier that is not a syntactic keyword may be
used as a variable (see section 3.1).
• When an identifier appears as a literal or within a
literal (see section 4.1.2), it is being used to denote a
symbol (see section 6.4).
3. Basic concepts 5
The following identifiers are syntactic keywords, and
should not be used as var iabl es :
=> do or
and else quasiquote
begin if quote
case lambda set!
cond let unquote
define let* unquote-splicing
delay letrec
Some implementations allow all identifiers, including syn-
tactic keywords, to be used as variables. This is a com-
patible exten s ion to the language, but ambiguities in the
language result when the restriction is relaxed, and the
ways in which these ambiguities are resolved vary between
implementations.
The characters ? and ! have no special properties—they
are extended alphabetic characters. By convention, how-
ever, most predicate procedures (those that return boolean
values) are named by identifiers that end in ?, and most
data mutation procedures are named by identifiers that end
in !.
2.2. Whitespace and comments
Whitespace characters are spaces and newlines. (Imple-
mentations typically provide additional whitespace char-
acters such as tab or page break.) Whitespace is used for
improved readability and as necessary to separate tokens
from each other, a token being an indivisible lexical unit
such as an identifier or number, b u t is otherwise insignifi-
cant. Whitespace may occur between any two tokens, but
not within a token. Whitespace may also occur inside a
string, where it is significant.
A semicolon (;) indicates the start of a comment. The
comment continues to the end of the li ne on which the
semicolon appears. Comments are invisible to Scheme, but
the end of the line is visible as whitespace. This prevents a
comment from appearing in the middle of an identifier or
number.
;;; The FACT procedure computes the factorial
;;; of a non-negative integer.
(define fact
(lambda (n)
(if (= n 0)
1 ;Base case: return 1
(* n (fact (- n 1))))))
2.3. Other notations
For a description of the notations used for numbers, see
section 6.5.
. + - These are used in numbers, and may also occur any-
where in an identifier except as the first character. A
delimited plus or minus sign by itself is also an identi-
fier. A deli mite d period (not occurring within a num-
ber or identifier) is used in the notation for pairs (sec-
tion 6.3), and to indicate a rest-parameter in a formal
parameter list (section 4.1.4).
( ) Parentheses are used for group in g and to notate lists
(section 6.3).
’ The single quote character is used to indicate literal data
(section 4.1.2).
` The back qu ote character is used to indicate almost-
constant data (section 4.2.6).
, ,@ The character comma and the sequence comma at-
sign are used in conjunction with backquote (sec-
tion 4.2.6).
" The double quote character is used to delimit strings
(section 6.7).
\ Backslash is used in the syntax for character constants
and as an escape character within string constants
(section 6.7).
[ ] { } Left and right square brackets and curly braces
are reserved for possible future extens i ons to the lan-
guage.
# Sharp sign is used for a variety of purposes depending
on the character that immediately follows it:
#t #f These are the boolean constants (section 6.1).
#\ This intro d uc es a character constant (section 6.6).
#( This introduces a vector constant (section 6.8). Vector
constants are terminated by ) .
#e #i #l #s #b #o #d #x These are used in the nota-
tion for numbers (section 6.5.3).
3. Basic concepts
3.1. Variables and regions
Any identifier that is not a syntactic keyword (see sec-
tion 2.1) may b e used as a variable. A variable may name
a location where a value can be stored. A variable that
does so is said to be bound to the location. The set of all
such bindings in effect at some point in a program is known
as the environm ent in effect at that point. Th e value stored
in the lo c ation to which a variable is bound is called the
variable’s value. By abuse of terminology, the variable is
sometimes said to name the value or to be bound to the
value. This is not quite accurate, but confusion rarely r e-
sults from this practice.
6 Revised
3
Scheme
Certain expr e s si on types are used to create new locations
and to bind variables to those l ocations. The most funda-
mental of these binding constructs is the lambda expres-
sion, because all other bindi ng constructs can be explained
in terms of lambda expressions. The other binding con-
structs are let, let*, letrec, and do expressi ons (see sec-
tions 4.1.4, 4.2.2, and 4.2.4).
Like Algol and Pascal, and unlike most other dialects of
Lisp except for Common Lisp, Scheme is a statically scoped
language with block structure. To each place where a vari-
able is bound in a program there corresponds a region of the
program text within which the binding is effective. The r e-
gion is determined by the particular binding construct that
establishes the binding; if the binding is established by a
lambda expression, for example, then its region is the en-
tire lambda expression. Every reference to or assignment
of a variable refers to the bind ing of the variable that es-
tablished the innermost of the regions containing the use.
If there is no binding of the variable whose region c ontains
the use, then the use refers to the binding for the variable
in the top level environment, if any (section 6); if there is
no binding for the identifier, it is s aid to b e unbound.
3.2. True and false
Any Scheme value can be used as a boolean value for the
purpose of a conditional test. As explained in section 6.1,
all values count as true in such a test except for #f and
the empty list, which count as false. This report uses the
word “true” to refer to any Scheme value that counts as
true, and the word “false” to refer to any Scheme value
that counts as false.
3.3. External representations
An important concept in Scheme (and Lisp) is that of the
external representation of an object as a sequence of char-
acters. For example, an exter nal representation of the inte-
ger 28 is the sequence of characters “28”, and an exte r nal
representation of a list consisting of the integers 8 and 13
is the sequence of characters “(8 13)”.
The external representation of an object is not necessarily
unique. The integer 28 also has representations “28.000”
and “#x1c”, and the list in the previous paragraph also has
the representations “( 08 13 )” and “(8 . (13 . ()))”
(see section 6.3).
Many objects have stan dar d external representations, but
some, such as procedures, do not have standard represen-
tations (although particular implementations may define
representations for them).
An external representation may be wr it te n in a program to
obtain t he corresponding objec t (see quote, section 4.1.2).
External representations can also be used for input and
output. The procedure read (section 6.10.2) parses ex-
ternal representations, and the procedure write (s e c-
tion 6.10.3) generates them. Together, they provide an
elegant and powerful input/output facility.
Note that the sequence of characters “(+ 2 6)” i s not an
external representation of the integer 8, even though it is an
expression evaluating to the integer 8; rather, it is an exter-
nal representation of a three-element list, the elements of
which are the symbol + and the integers 2 and 6. Scheme’s
syntax has the proper ty that any sequence of characters
which is an expression is also the ext er n al representation
of some object. This can lead to confusion, since it may
not be obvious out of context whether a given sequence of
characters is intended to denote data or program, but it is
also a s our c e of power, since it facilitates writing programs
such as interpreters and compilers which treat programs as
data (or vice versa).
The syntax of external representations of various kinds of
objects accompanies the description of the primitives for
manipulating the objects in the appropriate sections of
chapter 6.
4. Expressions
A Scheme expression is a construct that returns a value,
such as a variable reference, liter al, procedure call, or con-
ditional.
Expression types are categorized as primitive or derived.
Primitive expression types include variables and procedure
calls. Derived expression types are not semantically primi-
tive, but can instead be explained in terms of the p r imit ive
constructs as in section 7.3. They are redundant in the
strict sense of the word, but they capture common pat-
terns of usage, and are therefore provided as convenient
abbreviations.
4.1. Primitive expression types
4.1.1. Variable references
hvariablei essential syntax
An expression c ons is tin g of a variable (section 3.1) is a
variable reference. The value of the variable reference is
the value stored in the location to which the variable is
bound. It is an error to reference an unbound variable.
(define x 28)
x =⇒ 28
4. Expressions 7
4.1.2. Literal express i ons
(quote hdatumi) essential syntax
’hdatumi essential syntax
hconstanti essential syntax
(quote hdatumi) evaluates to hdatumi. hDatumi may be
any external representation of a Scheme object (see sec-
tion 3.3). This notation is used to includ e literal constants
in Scheme code.
(quote a) =⇒ a
(quote #(a b c)) =⇒ #(a b c)
(quote (+ 1 2)) =⇒ (+ 1 2)
(quote hdatumi) may be abbreviated as ’hdatumi. The
two notations are equivalent in all respects.
’a =⇒ a
’#(a b c) =⇒ #(a b c)
’(+ 1 2) =⇒ (+ 1 2)
’(quote a) =⇒ (quote a)
’’a =⇒ (quote a)
Numeric cons tants, string constants, character constants,
and boolean constants evaluate “to themselves”; they need
not be quoted.
’"abc" =⇒ "abc"
"abc" =⇒ "abc"
’145932 =⇒ 145932
145932 =⇒ 145932
’#t =⇒ #t
#t =⇒ #t
It is an error to alter a constant (i.e. the value of a literal
expression) using a mutation procedure like set-car! or
string-set!.
4.1.3. Procedure calls
(hoperatori hoperand
1
i . . . ) essential syntax
A procedure call is written by simply enclosing in parenthe-
ses expressions for the procedure to be called and the ar-
guments to be passed to it. The operator and operand ex-
pressions are evaluated (in an indeterminate order) and the
resulting procedure is passed the res ult in g arguments.
(+ 3 4) =⇒ 7
((if #f + *) 3 4) =⇒ 12
A number of procedures are available as the values of vari-
ables in the initial environment; for example, the addition
and multiplication procedur es in the above examples are
the values of the variabl es + and *. New procedures are cre-
ated by evaluating lambda expressions (see section 4.1.4).
Procedure calls are also called combinations.
Note: In contrast to ot h er dialects of Lisp, the order o f
evaluation is un specified, and the operator expression and the
operand expressions are always evaluated with the same evalu-
ation rules.
Note: In many dialects of Lisp, the empty combination, (),
is a legitimate expression. In Scheme, combinations must have
at least one subexpression, so () is not a syntactically valid
expression.
4.1.4. Lambda exp res si ons
(lambda hformalsi hbodyi ) essential syntax
Syntax: hFormalsi should be a formal arguments list as
described below, an d hbodyi should be a sequence of one
or more expressions.
Semantics: A lambda expression evaluates t o a procedure.
The environment in effect when the lambda expression was
evaluated is remembered as part of the procedure. When
the procedure is l ater called with some actual arguments,
the environment in which the lambda expression was evalu-
ated will be extended by binding the variables in the formal
argument list to fresh locations, the corresponding actual
argument values will be stored in those locations, and the
expressions in the body of the lambda expression will be
evaluated sequentially in the extended environment. The
result of the last expression in the body will be returned
as the result of the procedure call.
(lambda (x) (+ x x)) =⇒ a procedure
((lambda (x) (+ x x)) 4) =⇒ 8
(define reverse-subtract
(lambda (x y) (- y x)))
(reverse-subtract 7 10) =⇒ 3
(define foo
(let ((x 4))
(lambda (y) (+ x y))))
(foo 6) =⇒ 10
hFormalsi should have one of the following f orms :
• (hvariable
1
i . . . ): The procedure takes a fixed num-
ber of arguments; when the procedure is called, the
arguments will be stored in the bin d in gs of the corre-
sponding variab les .
• hvariablei: The procedure takes any number of ar-
guments; when the procedure is called, the sequence
of actual arguments is converted into a newly allo-
cated list , and the list is stored in the binding of the
hvariablei.
• (hvariable
1
i . . . hvariable
n−1
i . hvariable
n
i): If a
space-delimited period precedes the last variable, then
the value stored in the binding of the last variable will
be a newly allocated list of the actual arguments left
over after all the other actual arguments have been
matched up against the other formal arguments.
((lambda x x) 3 4 5 6) =⇒ (3 4 5 6)
((lambda (x y . z) z)
3 4 5 6) =⇒ (5 6)
8 Revised
3
Scheme
4.1.5. Conditionals
(if htesti hconsequenti halternatei) essential syntax
(if htesti hconsequenti) syntax
Syntax: hTesti, h cons e qu enti, and halternatei may be arbi-
trary expressions.
Semantics: An if expression is evaluated as follows: first,
htesti is evaluated. If it yields a true value (see section 6.1),
then hconsequenti is evaluated and its value is returned.
Otherwise halternatei is evalu ated and its value is returned.
If htesti yields a false value and no h alte r nate i is specified,
then the result of the expressi on is uns pecifie d.
(if (> 3 2) ’yes ’no) =⇒ yes
(if (> 2 3) ’yes ’no) =⇒ no
(if (> 3 2)
(- 3 2)
(+ 3 2)) =⇒ 1
4.1.6. Assignments
(set! hvariablei hexpressioni) essential syntax
hExpressioni is evaluated, and the resulting value is stored
in the location to which hvariablei is bound. hVariablei
must be bound either in some region enclosing the set!
expression or at top level. The result of the set! expression
is unspecified.
(define x 2)
(+ x 1) =⇒ 3
(set! x 4) =⇒ unspecified
(+ x 1) =⇒ 5
4.2. Derived expression types
For reference purposes, section 7.3 gives rewrite rules that
will convert constructs describ e d in this section into the
primitive constructs described in the previous section.
4.2.1. Conditionals
(cond hclause
1
i hclause
2
i . . . ) essential syntax
Syntax: Each hclausei should be of the form
(htesti hexpressioni . . . )
where htesti is any expression. The last hclausei may be
an “else clause,” which has the form
(else hexpression
1
i hexpression
2
i . . . ).
Semantics: A cond expression is evaluated by evaluating
the htesti expressions of successive hclauseis in order until
one of them evaluates to a true value (see section 6.1).
When a htesti evaluates to a true value, then the remaining
hexpressionis in its hclausei are evaluated in order, and the
result of the last hex pr e ss i oni in the hclausei is returned
as the result of t he entire cond expres si on. If the selected
hclausei c ontains only the htesti and no hex pressionis, then
the value of the htesti is returned as the result. If all htestis
evaluate to false valu es , and ther e is no else clause, then
the result of the conditional expression is unspecified; if
there is an else clause, then its hexpressionis are evaluated,
and the value of the last one is returned.
(cond ((> 3 2) ’greater)
((< 3 2) ’less)) =⇒ greater
(cond ((> 3 3) ’greater)
((< 3 3) ’less)
(else ’equal)) =⇒ equal
Some implementations support an alternative hclausei syn-
tax, (htesti => hrecipienti), where hrecipienti is an expres-
sion. If h te st i evaluates to a true value, then hrec ipi enti is
evaluated. Its value must be a procedure of one argument;
this procedure is then invoked on the value of the htesti.
(cond ((assv ’b ’((a 1) (b 2))) => cadr)
(else #f)) =⇒ 2
(case hkeyi hclause
1
i hclause
2
i . . . ) syntax
Syntax: hKeyi may be any expression. Each hclausei
should have the form
((hdatum
1
i . . . ) hexpression
1
i hexpression
2
i . . . ),
where each hdatumi is an external representation of some
object. All the hdatumis must be distinct. The last
hclausei may be an “else clause,” which has the form
(else hexpression
1
i hexpression
2
i . . . ).
Semantics: A case expression is evaluated as follows.
hKeyi is evaluated and its result is compared against each
hdatumi. If the result of evaluating hkeyi is equivalent
(in the sense of eqv?; see section 6.2) to a hdatumi, then
the expr e s si ons in the corresponding hclausei are evaluated
from left to right and the result of the last expression in
the hclausei is returned as the result of the case expres-
sion. If the result of evaluating hkeyi is different from every
hdatumi, then if there is an else clause its expressions are
evaluated and the result of the last is the result of the case
expression; otherwise the result of the case expression is
unspecified.
(case (* 2 3)
((2 3 5 7) ’prime)
((1 4 6 8 9) ’composite)) =⇒ composite
(case (car ’(c d))
((a) ’a)
((b) ’b)) =⇒ unspecified
(case (car ’(c d))
((a e i o u) ’vowel)
((w y) ’semivowel)
(else ’consonant)) =⇒ consonant
4. Expressions 9
(and htest
1
i . . . ) syntax
The htesti expressions are evaluated from left to right, and
the value of the first expr es s ion that evaluates to a false
value (see section 6.1) is returned. Any remaining expres-
sions are not evaluated. If all the expressions evaluate to
true values, the value of t he last expression is returned. If
there are no expressions then #t is retur n ed .
(and (= 2 2) (> 2 1)) =⇒ #t
(and (= 2 2) (< 2 1)) =⇒ #f
(and 1 2 ’c ’(f g)) =⇒ (f g)
(and) =⇒ #t
(or htest
1
i . . . ) syntax
The htesti expressions are evaluated from left to right, and
the value of the first expression that evaluates to a true
value (see section 6.1) is returned. Any remaining expres-
sions are not evaluated. If all expressions evalu ate to false
values, the value of the last expression is returned. If there
are no expressions then #f is returned.
(or (= 2 2) (> 2 1)) =⇒ #t
(or (= 2 2) (< 2 1)) =⇒ #t
(or #f #f #f) =⇒ #f
(or (memq ’b ’(a b c))
(/ 3 0)) =⇒ (b c)
4.2.2. Binding constructs
The three binding constructs let, let*, and letrec give
Scheme a blo ck structure, like Algol 60. The syntax of the
three constructs is identical, but they differ in the regions
they establish for their vari able bindings. In a let ex-
pression, the initial values are computed before any of the
variables become bound; in a let* expression, the bind-
ings and evaluations are performed sequentially; while in
a letrec expr e s si on, t he bind in gs are in effect while their
initial values are being computed, thus allowing mutually
recursive definitions.
(let hbindingsi hbo dy i) essential syntax
Syntax: hBindingsi sh ould have the form
((hvariable
1
i hinit
1
i) . . . ),
where each hiniti is an expression , and hbodyi should be a
sequence of one or more expressions.
Semantics: The hinitis are evaluated in the current envi-
ronment (in some unspecified order), the hvariableis are
bound to fresh loc ations holding the results, the hbodyi is
evaluated in the extended environment, and the value of
the last expression of hbodyi is returned. Each binding of
a hvariablei has hbo dy i as it s region.
(let ((x 2) (y 3))
(* x y)) =⇒ 6
(let ((x 2) (y 3))
(let ((foo (lambda (z) (+ x y z)))
(x 7))
(foo 4))) =⇒ 9
See also named let, section 4.2.4.
(let* hbindingsi hbod y i) syntax
Syntax: hBindingsi sh ould have the form
((hvariable
1
i hinit
1
i) . . . ),
and hbodyi should be a sequence of one or more expres-
sions.
Semantics: Let* is similar to let, but th e bindings are
performed sequentially fr om left to right, and the region of
a binding indicated by (hvariablei hiniti) is that part of
the let* expression to the right of the binding. Thus the
second binding is d one in an environment in which the first
binding is visible, and so on.
(let* ((x 1) (y (+ x 1)))
y) =⇒ 2
(letrec hbindingsi hbo d yi ) ess ential syntax
Syntax: hBindingsi sh ould have the form
((hvariable
1
i hinit
1
i) . . . ),
and hbodyi should be a sequence of one or more expres-
sions.
Semantics: The hvariableis are bound to fresh locations
holding undefined values, the hinitis are evaluated in the
resulting environment (in some unspecified order), each
hvariablei is assigned to the result of the corresponding
hiniti, the hbodyi is evaluated in the resulting environment,
and the value of the last expression in hbodyi is returned.
Each binding of a hvariablei has the entire letrec expr es -
sion as its region, making it possible to define mutually
recursive procedures.
(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? 88))
=⇒ #t
10 Revised
3
Scheme
One restriction on letrec is very important: it must be
possible to evaluate each hiniti without referring to the
value of any hvariablei. If this restriction is violated, then
the effect is u n de fin ed , and an error may be signalle d dur-
ing evaluation of the hinitis. The restriction is necessary
because Scheme passes arguments by value rather than by
name. In the most common uses of letrec, all the hinitis
are lambda expressions and the restriction is satisfied au-
tomatically.
4.2.3. Sequencing
(begin hexpression
1
i hexpression
2
i . . . ) essential syntax
The hexpressionis are evaluated s e qu entially from left to
right, and the value of the last hexpressioni is returned.
This expression type is used to sequence side effects such
as input and output.
(begin (set! x 5)
(+ x 1)) =⇒ 6
(begin (display "4 plus 1 equals ")
(display (+ 4 1))) =⇒ unspecified
and prints 4 plus 1 equals 5
Note: [1] uses the keyword sequence instead of begin.
4.2.4. Iteration
(do ((hvariable
1
i hinit
1
i hstep
1
i) syntax
. . . )
(htesti hexpressioni . . . )
hcommandi . . . )
Do is an iteration construct. It specifies a set of variabl es
to be bound , how they are to be initialized at the start,
and how they are to be updated on each iteration. When a
termination condition is met, the loop exits with a specified
result value.
Do expressions are evaluated as follows: The hiniti ex-
pressions are evaluated (in some unspecified order), the
hvariableis are bound to fresh locations, the results of
the hiniti expressions are stored in the bindings of the
hvariableis, and then the iteration phase begins.
Each iteration begins by evaluating htesti; if the result is
false (see section 6.1), then the hcommandi expressions are
evaluated in order for e ffe ct, the hstepi expre ss i ons are eval-
uated in some unspecified order, the hvariable is are bound
to fresh locations, the results of the hstepis are stored in the
bindings of the hvariableis, and the next iteration begins.
If h te s ti evaluates to a true value, then the hexpressionis
are evaluated from left to right and the value of the last
hexpressioni is return ed as the value of the do express ion.
If no hexpressionis are present, then the value of the do
expression is unspecified.
The region of the binding of a hvariablei consists of the
entire do expression except for the hinitis.
A hstepi may be omitted, in which case th e effect is the
same as if (hvariablei hiniti hvariablei) had been written
instead of (hvariablei hiniti).
(do ((vec (make-vector 5))
(i 0 (+ i 1)))
((= i 5) vec)
(vector-set! vec i i)) =⇒ #(0 1 2 3 4)
(let ((x ’(1 3 5 7 9)))
(do ((x x (cdr x))
(sum 0 (+ sum (car x))))
((null? x) sum))) =⇒ 25
(let hvariablei hbindingsi hbodyi) syntax
Some implementations of Scheme permit a variant on the
syntax of let called “named let” which provides a more
general looping construct than do, and may also be used
to express recursions.
Named let has the same syntax and semantics as ordi-
nary let except that hvariablei is bound within hbodyi to
a procedure whose formal arguments are the bound vari-
ables and whose body is hbodyi. Thus the execution of
hbodyi may be repeated by invoking the procedure named
by hvariablei.
(let loop ((numbers ’(3 -2 1 6 -5))
(nonneg ’())
(neg ’()))
(cond ((null? numbers) (list nonneg neg))
((>= (car numbers) 0)
(loop (cdr numbers)
(cons (car numbers) nonneg)
neg))
((< (car numbers) 0)
(loop (cdr numbers)
nonneg
(cons (car numbers) neg)))))
=⇒ ((6 1 3) (-5 -2))
4.2.5. Delayed evaluation
(delay hexpressioni) syntax
The delay construct is used together with the proced ure
force t o impl eme nt l az y evaluation or call by need. (delay
hexpressioni) returns an object called a promise which at
some point in the future may be asked (by the force pro-
cedure) to evaluate hexpressioni and deliver the resulting
value.
See the desc r ipt ion of force (section 6.9) for a complete
description of delay.
5. Program structure 11
4.2.6. Quasiquotation
(quasiquote htemplatei) syntax
`htemplatei syntax
“Backquote” or “quasiquote” expressions are useful for
constructing a list or vector structure when most but not
all of the desired structure is known in advance. If no
commas appear within the htemplatei, the result of evalu-
ating `htemplatei is equivalent to the result of evaluating
’htemplatei. If a comma appears wit hi n the htemplatei,
however, the expression following the comma is evaluated
(“unquoted”) and its result is inserted into the structure
instead of the comma and the expression. If a comma ap-
pears followed immediately by an at-sign (@), then the fol-
lowing expres si on must evaluate to a list; the opening and
closing parentheses of the list are then “stripped away” and
the elements of the list are insert ed in place of the comma
at-sign expression sequence.
`(list ,(+ 1 2) 4) =⇒ (list 3 4)
(let ((name ’a)) `(list ,name ’,name))
=⇒ (list a (quote a))
`(a ,(+ 1 2) ,@(map abs ’(4 -5 6)) b)
=⇒ (a 3 4 5 6 b)
`((foo ,(- 10 3)) ,@(cdr ’(c)) . ,(car ’(cons)))
=⇒ ((foo 7) . cons)
`#(10 5 ,(sqrt 4) ,@(map sqrt ’(16 9)) 8)
=⇒ #(10 5 2 4 3 8)
Quasiquote forms may be nested. Substitutions are made
only for unquoted components appearing at the same nest-
ing level as the outermost backquote. The nesting level in-
creases by one inside each successive quasiquotation, and
decreases by one inside each unquotation.
`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)
=⇒ (a `(b ,(+ 1 2) ,(foo 4 d) e) f)
(let ((name1 ’x)
(name2 ’y))
`(a `(b ,,name1 ,’,name2 d) e))
=⇒ (a `(b ,x ,’y d) e)
The notations `htemplatei and (quasiquote htemplatei)
are identical in all respects. ,hexpressioni is id entical to
(unquote hexpressioni), and ,@hexpressioni is identical to
(unquote-splicing hexpressioni). The external syntax
generated by write for two-element lists whose car is one
of these symbols may vary between implementations.
(quasiquote (list (unquote (+ 1 2)) 4))
=⇒ (list 3 4)
’(quasiquote (list (unquote (+ 1 2)) 4))
=⇒ `(list ,(+ 1 2) 4)
i.e., (quasiquote (list (unquote (+ 1 2)) 4))
Unpredictable behavior can result if any of the symbols
quasiquote, unquote, or unquote-splicing appear in
positions within a htemplatei otherwise than as described
above.
5. Program structure
5.1. Programs
A Scheme program consists of a sequence of expressions
and definitions. Expressions are described in chapter 4;
definitions are the subject of the rest of the present chapt er .
Programs are typically stor ed in fi le s or entered inter-
actively to a running Scheme system, although other
paradigms are possible; questions of user interface lie out-
side the scope of this report. (Indeed, Scheme would still be
useful as a notation for expressing computational metho d s
even in the absence of a mechanical implementation.)
Definitions occurring at the top level of a program are inter-
preted declaratively. They cause bindings to be created in
the top level environment. Expressions occurring at the top
level of a program are interpreted imperatively; they are
executed in order when the p r ogram is invoked or loaded,
and typically perform some kind of initialization.
5.2. Definitions
Definitions are valid in some, but not all, contexts where
expressions are allowed. They are valid only at the top
level of a hprogrami and, in some implementations, at the
beginning of a hbodyi.
A definition should have one of the following forms:
• (define hvariablei hexpressioni)
This syntax is essential.
• (define (hvariablei hformalsi) hbodyi)
This syntax is not essent ial. hFormalsi should be ei-
ther a sequence of zero or more variables, or a sequence
of one or more variables followed by a space-delimited
period and another variable (as in a lambda expres-
sion). This form is equivalent to
(define hvariablei
(lambda (hformalsi) hbodyi)).
• (define (hvariablei . hformali) hbodyi)
This syntax is not essential. hFormali should be a
single variable. This form is equivalent to
(define hvariablei
(lambda hformali hb odyi)).
5.2.1. Top level definitions
At t he top level of a progr am, a defi ni tion
(define hvariablei hexpressioni)
has essentially the same effect as the assignment expres-
sion
(set! hvariablei hexpressioni)
12 Revised
3
Scheme
if hvariablei is bound. If hvariablei is not bound, however,
then the definition will bind hvariablei to a new location
before performing the assignment, whereas it would be an
error to perform a set! on an unbound variable.
(define add3
(lambda (x) (+ x 3)))
(add3 3) =⇒ 6
(define first car)
(first ’(1 2)) =⇒ 1
All Scheme implementations must support top level defini-
tions.
Some implementations of Scheme use an initial environ-
ment in which all possible variables are bound to locations,
most of which contain undefined values. Top level defin i-
tions in s uch an implementation are truly equivalent to
assignments.
5.2.2. Internal definitions
Some implementations of Scheme permit definitions to oc-
cur at the beginning of a hbo d yi (that is, the body of a
lambda, let, let*, letrec, or define expression). Such
definitions are known as internal definitions as opposed to
the top level definitions described above. The variable de-
fined by an internal defin iti on is local t o the hbodyi. That
is, hvariable i is bound r ath er than assigned , and the region
of the binding is the entire hbodyi. For example,
(let ((x 5))
(define foo (lambda (y) (bar x y)))
(define bar (lambda (a b) (+ (* a b) a)))
(foo (+ x 3))) =⇒ 45
A hbodyi containing internal definitions can always be con-
verted into a completely equivalent letrec expression. For
example, the let expression in the above example is equiv-
alent to
(let ((x 5))
(letrec ((foo (lambda (y) (bar x y)))
(bar (lambda (a b) (+ (* a b) a))))
(foo (+ x 3))))
6. Standard procedures
This chapter describes Scheme’s built-in procedures. The
initial (or “top level”) Scheme environment starts out with
a number of variables bound to locations containing u se fu l
values, most of which are primitive procedures that manip-
ulate data. For example, the variable abs is bound to (a
location initiall y containing) a procedure of one argument
that computes the absolute value of a number, and the
variable + is bound to a procedure th at computes sums.
6.1. Booleans
The standard boolean objects for true and false are written
as #t and #f. What re ally matters, though, are the objects
that the Scheme conditional express ions ( if, cond, and,
or, do) treat as true or false. The phrase “a true value”
(or sometimes just “true”) means any object treated as
true by the conditional expressions, and the phrase “a fals e
value” (or “false”) means any object treated as false by the
conditional expressions.
Of all the standard Scheme values, only #f and the empty
list count as false in conditional expressions. Everything
else, including #t, pairs, symbols, numbers, strings , vec-
tors, and procedures, counts as true.
The empty list counts as false for compatibility with exist-
ing programs and implementations that assume this to be
the case.
Programmers accustomed to other dialects of Lisp should
beware that Scheme distinguishes false and the empty list
from the symbol nil.
Boolean constants evaluate to themselves, so they don’t
need to be quoted in programs.
#t =⇒ #t
#f =⇒ #f
’#f =⇒ #f
(not obj ) essential procedure
Not returns #t if obj is false, and returns #f otherwise.
(not #t) =⇒ #f
(not 3) =⇒ #f
(not (list 3)) =⇒ #f
(not #f) =⇒ #t
(not ’()) =⇒ #t
(not (list)) =⇒ #t
(boolean? obj ) essential procedure
Boolean? returns #t if obj is either #t or #f and returns
#f otherwise.
(boolean? #f) =⇒ #t
(boolean? 0) =⇒ #f
nil variable
t variable
Some implementations provide variables nil and t whose
values in the initial environment are #f and #t respectively.
t =⇒ #t
nil =⇒ #f
’nil =⇒ nil
6. Standard procedures 13
6.2. Equivalence predicates
A predicate is a procedure t hat always returns a boolean
value (#t or #f). An equivalence predicate is the compu -
tational analogue of a mathematical equivalence relation
(it is symmetric, reflexive, and transitive). Of the equiva-
lence predicates described in thi s section, eq? is the finest
or most discriminating, and equal? is the coarsest. Eqv?
is slightly less discriminatin g than eq?.
Two objects are operationally equivalent if and only if there
is no way that they can be d is ti ngui sh e d, us in g S cheme
primitives other than eqv? or eq? or those like memq and
assv whose meaning is defined explicitly in terms of eqv?
or eq?. It is guaranteed that objects maintain their opera-
tional identity despite being named by variables or fetched
from or stored into data structure s.
This definition can be interpreted in the following ways for
various k in ds of objects:
• The two boolean values, #t and #f, are operationally
distinct because they behave in opposite ways in con-
ditionals.
• Two symbols are operationally equivalent if they print
the same way.
• Two numbers are operationally equivalent if they are
numerically equal (see =, section 6.5.4) and are either
both exact or both inexact (see section 6.5.2).
• Two characters are operationally equivalent if they are
the same character accord in g to char=? (section 6.6).
• Two structured mutable objects—pairs, vectors, or
strings—are operationally equivalent if they have op-
erationally equivale nt values in corresponding posi-
tions, and applying a mutation procedur e to one
causes the other to change as well. (A mutation pro-
cedure is one like set-car! which alters a data struc-
ture.) For example, two pairs are not operationally
equivalent if a set-car! operation on one does not
change the car field of the other.
• There is only one empty list, and it is operationally
equivalent to itself. All empty vectors are opera-
tionally equivalent to each other. All empty strings
are operationally equivalent to each other. Whether
there is more than one empty vector or string is
implementation-dependent.
• Two procedures are operationally equivalent if, when
called on operationally equivalent arguments, they re-
turn the same value and perform the same side effects.
(eqv? obj
1
obj
2
) essential procedure
The eqv? procedure implements an approximation to the
relation of operational equivalence. It returns #t if it can
prove that obj
1
and obj
2
are operationally equivalent. If it
can’t, it always errs on the conservative side and returns
#f.
The only situation in which it might fail to prove is when
obj
1
and obj
2
are operationally equivalent procedures that
were created at different times. In general, operational
equivalence of procedur es is uncomputable, but it is guar-
anteed that eqv? can recognize a procedure created at a
given time by a given lambda expression as “being itself.”
This is useful for applications in which procedures are be-
ing used to implement objects with lo cal state.
(eqv? ’a ’a) =⇒ #t
(eqv? ’a ’b) =⇒ #f
(eqv? 2 2) =⇒ #t
(eqv? ’() ’()) =⇒ #t
(eqv? "" "") =⇒ #t
(eqv? 100000000 100000000) =⇒ #t
(eqv? (cons 1 2) (cons 1 2))=⇒ #f
(eqv? (lambda () 1)
(lambda () 2)) =⇒ #f
(eqv? #f ’nil) =⇒ #f
(let ((p (lambda (x) x)))
(eqv? p p)) =⇒ #t
The following examples illustrate cases in which eqv? is
permitted to fail to pr ove operational equivalence, depend-
ing on the implementation. (In every case, it will return
either #t or #f, but which one it returns is implementation-
dependent.) Compare with the last example in the previ-
ous set.
(eqv? (lambda (x) x)
(lambda (x) x)) =⇒ unspecified
(eqv? (lambda (x) x)
(lambda (y) y)) =⇒ unspecified
The next set of examples shows the use of eqv? with pro-
cedures that have local state. Gen-counter must return a
distinct pr ocedur e every time, since each procedure has its
own internal counter. Gen-loser, however, returns equiv-
alent procedures each time, since the local state does not
affect the value or side effects of the procedures.
(define gen-counter
(lambda ()
(let ((n 0))
(lambda () (set! n (+ n 1)) n))))
(let ((g (gen-counter)))
(eqv? g g)) =⇒ #t
(eqv? (gen-counter) (gen-counter))
=⇒ #f
(define gen-loser
(lambda ()
(let ((n 0))
(lambda () (set! n (+ n 1)) 27))))
(let ((g (gen-loser)))
(eqv? g g)) =⇒ #t
(eqv? (gen-loser) (gen-loser))
=⇒ unspecified
14 Revised
3
Scheme
Objects of distinct types are never operationally equiva-
lent, except that false and the empty list are permitted to
be identical, and the character type need not be disjoint
from other types.
(eqv? ’() #f) =⇒ unspecified
(eqv? 57 #\A) =⇒ unspecified
Since it is an er r or to modify constant objects (those re-
turned by literal expressions), implementations are per-
mitted, though not required, to share structure between
constants where appropriate. Thus the value of eqv? on
constants is sometimes implementation-dependent.
(let ((x ’(a)))
(eqv? x x)) =⇒ #t
(eqv? ’(a) ’(a)) =⇒ unspecified
(eqv? "a" "a") =⇒ unspecified
(eqv? ’(b) (cdr ’(a b))) =⇒ uns pecified
Note: The above definition of eqv? allows implementations
latitude in their treatment of p rocedures and literals: imple-
mentations are free to either detec t or fail to detect that two
procedures or two literals are operation a lly equivalent to each
other, and can decide whether or not to merge representations
of equivalent objects by using the same pointer or bit pattern
to represent both.
(eq? obj
1
obj
2
) essential procedure
Eq? is similar to eqv? except that in some cases it is capable
of discerning distinctions finer than thos e detectable by
eqv?.
Eq? and eqv? are guaranteed to have the same behavior
on symbols, booleans, the empty list, pairs, and non-empty
strings and vectors. Eq?’s behavior on numbers and charac-
ters is implementation-dependent, but it will always return
either true or false, and will return true only when eqv?
would also return true. Eq? may also behave differently
from eqv? on empty vectors and empty strings.
(eq? ’a ’a) =⇒ #t
(eq? ’(a) ’(a)) =⇒ unspecified
(eq? (list ’a) (list ’a)) =⇒ #f
(eq? "a" "a") =⇒ unspecified
(eq? "" "") =⇒ unspecified
(eq? ’() ’()) =⇒ #t
(eq? 2 2) =⇒ unspecified
(eq? #\A #\A) =⇒ unspecified
(eq? car car) =⇒ #t
(let ((n (+ 2 3)))
(eq? n n)) =⇒ unspecified
(let ((x ’(a)))
(eq? x x)) =⇒ #t
(let ((x ’#()))
(eq? x x)) =⇒ #t
(let ((p (lambda (x) x)))
(eq? p p)) =⇒ #t
Note: It will usually be possible to implement eq? much more
efficiently than eqv?, for example, as a simple pointer compari-
son instead of as some more complicated operation. One reason
is that it may not be possible to compute eqv? of two numbers
in constant time, whereas eq? implemented as pointer compar-
ison will always finish in constant time. Eq? may be used like
eqv? in applicatio n s using pro c edures to implement objects with
state since it obeys the same constraints as eqv?.
(equal? obj
1
obj
2
) essential procedure
Equal? recursively compares the contents of pairs, vectors,
and strings, applying eqv? on other objects such as num-
bers and symbols. A rule of thumb is that objects are
generally equal? if they print the same. Equal? may fail
to terminate if its arguments are circular data structures.
(equal? ’a ’a) =⇒ #t
(equal? ’(a) ’(a)) =⇒ #t
(equal? ’(a (b) c)
’(a (b) c)) =⇒ #t
(equal? "abc" "abc") =⇒ #t
(equal? 2 2) =⇒ #t
(equal? (make-vector 5 ’a)
(make-vector 5 ’a)) =⇒ #t
(equal? (lambda (x) x)
(lambda (y) y)) =⇒ unspecified
6.3. Pairs and lists
A pair (sometimes called a dotted pair) is a record structure
with two fields called the car and cdr fields (for historical
reasons). Pairs are created by the procedure cons. The
car and cdr fields are accessed by the procedur e s car and
cdr. The car and cdr fields are assigned by the procedures
set-car! and set-cdr!.
Pairs are used primarily to represent lists. A list can be
defined recursively as either the empty list or a pair whose
cdr is a list. The objects in the car fields of successive
pairs of a li st are the elements of the list. For example,
a two-element list is a pair whose car is the first element
and whose cdr is a pair whose car is the second element
and whose cdr is the empty list. The length of a list is the
number of elements , which is the same as the number of
pairs.
The empty list is a special object of its own type (it is not
a pair); it has no elements and its length is zero.
The most general notation (external representation) for
Scheme pairs is the “dotted” notation (c
1
. c
2
) where c
1
is the value of the car field and c
2
is the value of the cdr
field. For exampl e (4 . 5) is a pair whose car is 4 and
whose cdr is 5. Note that (4 . 5) is the external repre-
sentation of a pair, not an expression that evaluates to a
pair.
6. Standard procedures 15
A more streamlined notation can be used for lists: the
elements of the list are simply enclosed in parentheses and
separated by spaces. The empty list is written () . For
example,
(a b c d e)
and
(a . (b . (c . (d . (e . ())))))
are both representations of the same list of symbols.
A chain of pairs not ending in the empty list is called an
improper list. Note that an improper list is not a list.
The list and dotted notations can be combined to represent
improper lists:
(a b c . d)
is equivalent to
(a . (b . (c . d)))
Whether a given pair is a list depends upon what is s tor ed
in the cdr field. When t he set-cdr! procedure is used, an
object can be a list one moment and not the next:
(define x (list ’a ’b ’c))
(define y x)
y =⇒ (a b c)
(set-cdr! x 4) =⇒ unspecified
x =⇒ (a . 4)
(eqv? x y) =⇒ #t
y =⇒ (a . 4)
It is often convenient to speak of a homogeneous list of ob-
jects of some particular data type, as for example (1 2 3)
is a list of integers. To be more precise, suppose D is some
data type. (Any predicate defines a data ty pe consisting
of those objects of which the predicate is true.) The n
• The empty list is a list of D.
• If list is a list of D, then any pair whose cdr is list and
whose car is an element of the data type D is also a
list of D.
• There are no other lists of D.
Within literal expressions and representations of ob-
jects read by the read procedur e, the forms ’hdatumi,
`hdatumi, ,hdatumi, and ,@hdatumi denote two-ele-
ment lists whose first elements are the symbols quote,
quasiquote, unquote, and unquote-splicing, respec-
tively. The second element in each case is hdatumi. This
convention is supported so that arbitrary Scheme pro-
grams may be represented as lists. That is, according
to Scheme’s grammar, every hexpres s ioni is also a hdatumi
(see section 7.1.2). Among other things, this permits the
use of the read procedure to parse Scheme programs. See
section 3.3.
(pair? obj ) essential procedure
Pair? returns #t if obj is a pair, and otherwise returns #f.
(pair? ’(a . b)) =⇒ #t
(pair? ’(a b c)) =⇒ #t
(pair? ’()) =⇒ #f
(pair? ’#(a b)) =⇒ #f
(cons obj
1
obj
2
) essential procedure
Returns a newly allocated pair whose car is obj
1
and whose
cdr is obj
2
. The pair is guaranteed to be different (in the
sense of eqv?) from every existing object.
(cons ’a ’()) =⇒ (a)
(cons ’(a) ’(b c d)) =⇒ ((a) b c d)
(cons "a" ’(b c)) =⇒ ("a" b c)
(cons ’a 3) =⇒ (a . 3)
(cons ’(a b) ’c) =⇒ ((a b) . c)
(car pair ) essential procedure
Returns the contents of the car field of pair . Note that it
is an error to take the car of the empty list.
(car ’(a b c)) =⇒ a
(car ’((a) b c d)) =⇒ (a)
(car ’(1 . 2)) =⇒ 1
(car ’()) =⇒ error
(cdr pair ) essential procedure
Returns the contents of the cdr fi el d of pair . Note that it
is an error to take the cdr of the empty list.
(cdr ’((a) b c d)) =⇒ (b c d)
(cdr ’(1 . 2)) =⇒ 2
(cdr ’()) =⇒ error
(set-car! pair obj ) essential procedure
Stores obj in the car field of pair . The value returned by
set-car! is unspecified.
(set-cdr! pair obj ) essential procedure
Stores obj in th e cdr field of pair . The value returned by
set-cdr! is unspecified.
(caar pair ) essential procedure
(cadr pair ) essential procedure
.
.
.
.
.
.
(cdddar pair ) essential procedure
(cddddr pair ) essential procedure
These procedures are compositions of car and cdr, where
for example caddr could be defined by
16 Revised
3
Scheme
(define caddr (lambda (x) (car (cdr (cdr x))))).
Arbitrary compositions, up to four deep, are provided.
There are twenty-eight of these procedures in all.
(null? obj ) essential procedure
Returns #t if obj is the empty list, other wis e returns #f.
(In implementations in which the empty list is the same as
#f, null? will return #t if obj is #f.)
(list obj . . . ) essential procedure
Returns a list of its arguments.
(list ’a (+ 3 4) ’c) =⇒ (a 7 c)
(list) =⇒ ()
(length list) essential procedure
Returns the length of list.
(length ’(a b c)) =⇒ 3
(length ’(a (b) (c d e))) =⇒ 3
(length ’()) =⇒ 0
(append list
1
list
2
) essential procedure
(append list . . . ) procedure
Returns a list consisting of the elements of the fir s t list
followed by th e elements of the other lists.
(append ’(x) ’(y)) =⇒ (x y)
(append ’(a) ’(b c d)) =⇒ (a b c d)
(append ’(a (b)) ’((c))) =⇒ (a (b) (c))
The resulting list is always newly allocated, except that
it shares structure with the last list argument. The last
argument may actuall y be any object; an improper list
results if it is not a proper list.
(append ’(a b) ’(c . d)) =⇒ (a b c . d)
(append ’() ’a) =⇒ a
(reverse list) procedure
Returns a newly allocated list consisting of the elements of
list in reverse order.
(reverse ’(a b c)) =⇒ (c b a)
(reverse ’(a (b c) d (e (f))))
=⇒ ((e (f)) d (b c) a)
(list-tail list k) procedure
Returns the sublist of list obtained by omitting the first k
elements. List-tail could be defined by
(define list-tail
(lambda (x k)
(if (zero? k)
x
(list-tail (cdr x) (- k 1)))))
(list-ref list k) procedure
Returns the kth element of list. (This is the same as the
car of (list-tail list k).)
(list-ref ’(a b c d) 2) =⇒ c
(last-pair list) procedure
Returns the last pair in the nonempty, possibly improper,
list list. Last-pair could be defined by
(define last-pair
(lambda (x)
(if (pair? (cdr x))
(last-pair (cdr x))
x)))
(memq obj list) essential procedure
(memv obj list) essential procedure
(member obj list) essential procedure
These procedures return the first sublist of list whose car
is obj . If obj does not occur in list, #f (n.b.: not the empty
list) is returned. Memq uses eq? to compare o bj with the
elements of lis t , while memv uses eqv? and member uses
equal?.
(memq ’a ’(a b c)) =⇒ (a b c)
(memq ’b ’(a b c)) =⇒ (b c)
(memq ’a ’(b c d)) =⇒ #f
(memq (list ’a) ’(b (a) c)) =⇒ #f
(member (list ’a)
’(b (a) c)) =⇒ ((a) c)
(memq 101 ’(100 101 102)) =⇒ unspecified
(memv 101 ’(100 101 102)) =⇒ (101 102)
(assq obj alist) essential procedure
(assv obj alist) essential procedure
(assoc obj alist) essential procedure
Alist (for “association list”) must be a list of pairs. These
procedures find the first pair in alist whose car field is obj ,
and returns that pair . If no pair in alist has obj as its car,
#f is returned. Assq uses eq? to compare obj with the car
fields of the pairs in alist, while assv uses eqv? and assoc
uses equal?.
(define e ’((a 1) (b 2) (c 3)))
(assq ’a e) =⇒ (a 1)
(assq ’b e) =⇒ (b 2)
(assq ’d e) =⇒ #f
(assq (list ’a) ’(((a)) ((b)) ((c))))
6. Standard procedures 17
=⇒ #f
(assoc (list ’a) ’(((a)) ((b)) ((c))))
=⇒ ((a))
(assq 5 ’((2 3) (5 7) (11 13)))
=⇒ unspecified
(assv 5 ’((2 3) (5 7) (11 13)))
=⇒ (5 7)
Note: Although t h ey are ordina r ily used as predicates, memq,
memv, member, assq, assv, and assoc do not have question
marks in their names because they return useful values rather
than just #t or #f.
6.4. Symbols
Symbols are objects whose usefulness rests on th e fact that
two symbols are identical (in the sense of eqv?) if and only
if their names are spelled the same way. This is exactly the
property needed to represent identifiers in programs, and
so most implementations of Scheme use them internally for
that purpose. Symbols are useful for many other applica-
tions; for instance, they may be used the way enumerated
values ar e used in Pascal.
The rules for writing a symbol are exactly the same as the
rules for writing an identifier; see sections 2.1 and 7.1.1.
It is guaranteed that any symbol that has been returned as
part of a literal expression, or read using the read proce-
dure, and subsequently written out using the write proce-
dure, will read back in as the identical symbol (in the sense
of eqv?). The string->symbol procedure, however, can
create symbols for which this write/read invariance may
not hold because their names contain special characters or
letters in the non-standard case.
Note: Some implementations of Scheme have a feature known
as “slashification” in order to guarantee write/ rea d inva ria n c e
for all symbols, but historically the most important use of this
feature has been to compen sa t e for the lack of a string data
type.
Some implementations also have “uninterned symbols”, which
defeat write/read invariance even in implementations with
slashification, and also generate exceptions to the rule that two
symbols a r e the same if and only if their names are spelled the
same.
(symbol? obj ) essential procedure
Returns #t if obj is a symbol, otherwise returns #f.
(symbol? ’foo) =⇒ #t
(symbol? (car ’(a b))) =⇒ #t
(symbol? "bar") =⇒ #f
(symbol->string symbol) essential procedure
Returns the name of symbol as a string. If the symbol was
part of an object returned as the value of a literal expres-
sion (section 4.1.2) or by a call to the read procedure, and
its name contains alphabetic characters, then the string
returned will contain characters in the implementation’s
preferred standard c ase —some implementations will prefer
upper case, others lower case. If the symbol was returned
by string->symbol, the case of characters in the strin g
returned will be the same as the case in the string that
was passed to string->symbol. It is an error to apply
mutation procedures like string-set! to strings returned
by this procedure.
The following examples assume that the implementation’s
standard case is lower case:
(symbol->string ’flying-fish)
=⇒ "flying-fish"
(symbol->string ’Martin) =⇒ "martin"
(symbol->string
(string->symbol "Malvina"))
=⇒ "Malvina"
(string->symbol string) essential procedure
Returns the symbol whose name is string. This procedure
can create symbols with names containing special charac-
ters or letters in the non-standard case, b ut it is usually
a bad idea to create such sy mbols be caus e in some imple-
mentations of Scheme they cannot be read as themselves.
See symbol->string.
The following examples assume that the implementation’s
standard case is lower case:
(eq? ’mISSISSIppi ’mississippi)
=⇒ #t
(string->symbol "mISSISSIppi")
=⇒ the symbol with name "mISSISSIppi"
(eq? ’bitBlt (string->symbol "bitBlt"))
=⇒ #f
(eq? ’JollyWog
(string->symbol
(symbol->string ’JollyWog)))
=⇒ #t
(string=? "K. Harper, M.D."
(symbol->string
(string->symbol "K. Harper, M.D.")))
=⇒ #t
6.5. Numbers
Numerical computation has traditionally been neglected by
the Lisp communi ty. Until Common Lisp there has been
no carefully thought out strategy for organizing numeri-
cal computation, and with the exception of the MacLisp
system [28] there has been little effort to exe cu te numeri-
cal code efficiently. We applaud the excellent work of the
Common Lisp committee and we accept many of their rec-
ommendations. In some ways we simplify and generalize
their proposals in a manner consistent with the purposes
of Scheme.
18 Revised
3
Scheme
Scheme’s numerical operations treat number s as abstract
data, as independent of their representation as is possible.
Thus, the casual user should be able to write simple pro-
grams without having to know that the implementation
may use fixed-point, floating-point, and perhaps other rep-
resentations for his data. Unfortunately, this illusion of
uniformity can be sustained only approximately—the im-
plementation of numbers will leak out of its abstraction
whenever the user must be in control of precision, or accu-
racy, or when he must construct especially efficient com-
putations. Thus the language must also provide escape
mechanisms s o that a sophisticated programmer can exer-
cise more control over the execution of his code and the
representation of his data when nece ss ar y.
It is important to distinguish betwee n the abstract num-
bers, their machine representations, and their written rep-
resentations. We will use mathematical terms number,
complex, real, rational, and integer for properties of
the abstract numbers, th e names fixnum, bignum, ratnum,
and flonum for machine rep r es e ntations, and the names
int, fix, flo, sci, rat, polar, and rect for input/output
formats.
6.5.1. Numbers
A Scheme system provides data of type number, which is
the most general numerical type supported by that sys-
tem. Number is likely to be a complicated union type im-
plemented in terms of fixnums, bignums, flonums, and so
forth, but this should not be apparent to a naive user.
What the user should see is that t he usual operations
on numbers produce the mathematically expected results,
within the limits of the implementation. Thus if the user
divides the exact number 3 by the exact number 2, he
should get something like 1.5 (or the exact fraction 3/2).
If he adds that result to itself, and the imple mentation is
good enough, he should get an exact 3.
Mathematically, numbers may be arranged into a tower of
subtypes with projections and injections relati ng adjacent
levels of the tower:
number
complex
real
rational
integer
We impose a uniform rule of downward coercion—a num-
ber of one type is also of a lower type if the injection (up)
of the projection (down) of a number leaves the number
unchanged. Since this tower is a genuine mathematical
structure, Scheme provides predicates and procedures to
access the tower.
Not all implementations of Scheme must provide the whole
tower, but they must implement a coherent subset consis-
tent with both the purposes of the implementation and the
spirit of the Scheme language.
6.5.2. Exactness
Numbers are either exact or inexact. A number is exact
if it was derived fr om exact numbers usin g only exact
operations. A nu mbe r is inexact if it models a quantity
(e.g., a measurement) known only approximately, if it was
derived using inexact ingredients, or if it was derived us-
ing inexact operations. Thus inexactness is a contagious
property of a number. Some operations, su ch as the square
root (of non-square numbers), must be inexact because of
the finite precision of our representations. Other opera-
tions are inexact because of implementation requirements.
We emphasize that exactness is independent of the posi-
tion of the number on the tower . It is perfectly possible to
have an inexact integer or an exact real; 355/113 may
be an exact rational or it may be an inexact rational
approximation to pi, depending on the application.
Operationally, it is the system’s responsibility to combine
exact numbers using exact methods, such as infinite pr e-
cision integer and rational arithmetic, where possible. An
implementation may not b e able to do this (if it does not
use infinite precision integers and rationals), but if a num-
ber becomes inexact for implementation reasons there is
likely to be an important error condition, such as integer
overflow, to be reported. Arithmetic on inexact numbers
is not so constrained. The system may use floating point
and other ill-behaved representation strategies for inexact
numbers. This is not to say that implementors need not
use the best known algorithms for inexact computations—
only that approximate methods of high quality are allowed.
In a system that cannot explicitly distinguish exact from
inexact numbers th e system must do its best to main-
tain precision. Scheme systems must not burden u se r s
with numerical operations described in terms of hard ware
and operating-syste m dependent representations such as
fixnum and flonum, however, because these representation
issues are hardly ever germane to the us er’s problems.
We highly recommend that the IEEE 32-bit and 64-bit
floating-point standards be adopted for implementations
that us e floating-point representations internally. To min-
imize loss of precision we adopt the following rules: If an
implementation uses several different sizes of floatin g-point
formats, the resu lt s of any operation with a floating-point
result must be expressed in the largest format used to ex-
press any of the floating-point arguments to that operation.
It is des ir abl e (but not required) for potentially irrational
operations such as sqrt, when applied to exact arguments,
to produce exact answers whenever possible (for example
the square root of an exact 4 ought to be an exact 2). If
an exact number (or an inexact number repr es ented as
6. Standard procedures 19
a fixnum, a bignum, or a ratnum) is operated upon so as
to produce an inexact result (as by sqrt), and if the re-
sult is represented as a flonum, then the largest available
flonum format must be used; but if the result is expressed
as a ratnum then the rational approximation mu st have at
least as much precision as the largest available flonum.
6.5.3. Number syntax
Scheme allows the traditional ways of writing numerical
constants, though any particular implementation may sup-
port only some of them. These syntaxes are intended to
be purely notational; any kind of number may be written
in any form that the user deems convenient. Of course,
writing 1/7 as a limited-precision decimal fraction will not
express the number exactly, but this app r oximate form of
expression may be just what the user wants to see.
The syntax of numbers is described formally in sec-
tion 7.1.1. See se cti on 6.5.6 for many examples of rep-
resentations of numbers.
A numerical constant may be repres e nted in binary, octal,
decimal, or hex by the use of a radix prefix. The radix
prefixes are #b (binary), #o (octal), #d (decimal), and #x
(hex). With no radix prefix, a number is assumed to be
expressed in decimal.
A numerical const ant may be specified to be either exact
or inexact by a prefix. The prefixes are #e for exact, and
#i for inexact. An exac tn es s prefix may appear before or
after any radix prefix that is used. If the representation of
a numerical constant has no exactness prefix, the constant
may be assumed to be exact or inexact at the discretion of
the implementation, except that integers ex pr e s se d without
decimal points and without use of exponential notation are
assumed exact.
In systems with both single and double pre cis ion flonums
we may want to specify which size we want to use to rep-
resent a constant internally. For example, we may want
a constant that has the value of pi rounded to the single
precision length, or we might want a long number that has
the value 6/10. In either case, we are specifying an explicit
way to represent an inexact number. For this purpose, we
may express a number with a prefix that indicates short or
long flonum representation:
#S3.14159265358979
Round to short — 3.141593
#L.6
Extend to long — .600000000000000
6.5.4. Numerical operations
The reader is referred to section 1.3.3 for a summary of
the naming conventions us e d to specify restriction s on the
types of arguments to numerical routines.
(number? obj ) essential procedure
(complex? obj ) essential procedure
(real? obj ) essential procedure
(rational? obj ) essential procedure
(integer? obj ) essential procedure
These numerical type predicates can be applied to any kind
of argument, including non-numbers. They retur n true if
the object is of the named type. In general, if a type pred-
icate is true of a number then all higher type predicates
are also true of that number. Not every system supports
all of these types; for example, it is entirely possible to
have a Scheme system that has only integers. Nonethe-
less e very implementation of Scheme must have all of these
predicates.
(zero? z) essential procedure
(positive? x) essential procedure
(negative? x) essential procedure
(odd? n) essential procedure
(even? n) essential procedure
(exact? z) essential procedure
(inexact? z) essential procedure
These numerical predicates test a number for a particular
property, returning #t or #f.
(= z
1
z
2
) essential procedure
(< x
1
x
2
) essential procedure
(> x
1
x
2
) essential procedure
(<= x
1
x
2
) essential procedure
(>= x
1
x
2
) essential procedure
Some implementations allow these procedures to take many
arguments, to facilitate range checks. These procedures
return #t if their arguments are (respectively): numeri-
cally equal, monotonically increasing, monotonically de-
creasing, monotonically nondecreasing, or monotonically
nonincreasing. Warning: on inexact numbers the eq ual-
ity tests will give unreliable resu lt s , and the other numer-
ical comparisons will be useful only heuristically; when in
doubt, consult a numerical analyst.
(max x
1
x
2
) essential procedure
(max x
1
x
2
. . . ) procedure
(min x
1
x
2
) essential procedure
(min x
1
x
2
. . . ) procedure
These proce du r es return the maximum or minimum of their
arguments.
(+ z
1
z
2
) essential procedure
(+ z
1
. . . ) procedure
(* z
1
z
2
) essential procedure
(* z
1
. . . ) procedure
These procedures return the sum or product of their argu-
ments.
20 Revised
3
Scheme
(+ 3 4) =⇒ 7
(+ 3) =⇒ 3
(+) =⇒ 0
(* 4) =⇒ 4
(*) =⇒ 1
(- z
1
z
2
) essential procedure
(- z
1
z
2
. . . ) procedure
(/ z
1
z
2
) essential procedure
(/ z
1
z
2
. . . ) procedure
With two or more arguments, these procedures return th e
difference or quotie nt of their arguments, associating to the
left. With one argument, however, they return the additive
or multiplicative inverse of their argument.
(- 3 4) =⇒ -1
(- 3 4 5) =⇒ -6
(- 3) =⇒ -3
(/ 3 4 5) =⇒ 3/20
(/ 3) =⇒ 1/3
(abs z ) essential procedure
Abs returns the magnitude of its argument.
(abs -7) =⇒ 7
(abs -3+4i) =⇒ 5
(quotient n
1
n
2
) essential procedure
(remainder n
1
n
2
) essential procedure
(modulo n
1
n
2
) procedure
These are intended to implement number-theoretic (inte-
ger) division: For positive integers n
1
and n
2
, if n
3
and n
4
are integers such that n
1
= n
2
n
3
+ n
4
and 0 ≤ n
4
< n
2
,
then
(quotient n
1
n
2
) =⇒ n
3
(remainder n
1
n
2
) =⇒ n
4
(modulo n
1
n
2
) =⇒ n
4
For all integers n
1
and n
2
with n
2
not equal to 0,
(= n
1
(+ (* n
2
(quotient n
1
n
2
))
(remainder n
1
n
2
)))
=⇒ #t
The value returned by quotient always has the sign of the
product of its arguments. Remainder and modulo differ on
negative arguments—the remainder always has the sign of
the dividend, the modulo always h as the sign of the divisor:
(modulo 13 4) =⇒ 1
(remainder 13 4) =⇒ 1
(modulo -13 4) =⇒ 3
(remainder -13 4) =⇒ -1
(modulo 13 -4) =⇒ -3
(remainder 13 -4) =⇒ 1
(modulo -13 -4) =⇒ -1
(remainder -13 -4) =⇒ -1
(numerator q) procedure
(denominator q) procedure
These procedures return the numerator or denominator of
their argument.
(numerator (/ 6 4)) =⇒ 3
(denominator (/ 6 4)) =⇒ 2
(gcd n
1
. . . ) procedure
(lcm n
1
. . . ) procedure
These procedures return the greatest common divisor or
least common multiple of their arguments. The result is
always non-negative.
(gcd 32 -36) =⇒ 4
(gcd) =⇒ 0
(lcm 32 -36) =⇒ 288
(lcm) =⇒ 1
(floor x ) procedure
(ceiling x ) procedure
(truncate x ) procedure
(round x ) procedure
(rationalize x y) procedure
(rationalize x ) procedure
These procedures create integers and rationals. Their re-
sults are exact if and only if their arguments are exact.
Floor returns the largest integer not larger than x.
Ceiling returns the s malles t integer not smaller than x.
Truncate returns the integer of maximal absolute value
not larger than the absolute value of x. Round returns the
closest integer t o x, rounding to even when x is halfway
between two integers. With two arguments, rationalize
produces the rational number with smallest denominator
differing from x by n o more than y. With one argument,
rationalize produces the best rational approximation to
x, preserving all of the precision in i ts representation.
Note: Round ro u n d s to even f o r consistency with the rounding
modes required by the IEEE floating point standard.
(exp z) procedure
(log z) procedure
(sin z) procedure
(cos z) procedure
(tan z) procedure
(asin z) procedure
(acos z) procedure
(atan z) procedure
(atan y x) procedure
These procedures are part of every impleme ntation that
supports real numbers; they compute t he usual transcen-
dental functions. Log computes the natural logarithm of
z (not the base 10 logarithm). Asin, acos, and atan
6. Standard procedures 21
compute arcs in e (sin
−1
), arccosine (cos
−1
), and ar ct an-
gent (tan
−1
), respectively. The two-argument variant of
atan computes (angle (make-rectangular x y)) (see
below), even in i mple mentations that don’t support com-
plex numbers.
In general, the mathematical functions log, arcsine, arcco-
sine, and arctangent are multiply defined. For nonzero real
x, the value of log x is defined to be t he one whose imagi-
nary part lies in the range −π (exclusive) to π ( in cl us ive).
log 0 is undefined. The value of log z when z is complex is
defined according to the formula
log z = log magnitud e(z) + i angle(z)
With log defined this way, the values of sin
−1
z, cos
−1
z,
and tan
−1
z are according to the following formulae:
sin
−1
z = − i log(iz +
p
1 − z
2
)
cos
−1
z = −i log (z + i
p
1 − z
2
)
tan
−1
z = −i log (( 1 + iz)
p
1/(1 + z
2
))
The above specification follows [43], which in turn fol-
lows [26]; refer to these sources for more detailed discussion
of branch cuts, boundary conditions, and implementation
of these functions.
(sqrt z) procedure
Returns the principal square root of z. The res ul t will have
either positive real part, or zero real part and non-negative
imaginary part.
(expt z
1
z
2
) procedure
Returns z
1
raised to the power z
2
:
z
1
z
2
= e
z
2
log z
1
0
0
is defined to be equal to 1.
(make-rectangular x
1
x
2
) procedure
(make-polar x
3
x
4
) procedure
(real-part z) procedure
(imag-part z) procedure
(magnitude z) procedure
(angle z) procedure
These procedures are part of every impleme ntation that
supports complex numbers. Suppose x
1
, x
2
, x
3
, and x
4
are real numbers and z is a complex number such that
z = x
1
+ x
2
i = x
3
· e
ix
4
Then make-rectangular and make-polar return z,
real-part returns x
1
, imag-part returns x
2
, magnitude
returns x
3
, and angle re tu r n s x
4
. In th e c ase of angle,
whose value is not uniquely determined by the preceding
rule, the value returned will be the one in the range −π
(exclusive) to π (inclusive).
Note: Magnitude is the same as abs, but abs must be present
in all implementations, whereas magnitude will only be present
in implementations that support complex numbers.
(exact->inexact z) procedure
(inexact->exact z) procedure
Exact->inexact returns an inexact representation of z,
which i s a fairly harmless thing to do. Inexact->exact
returns an exact representation of z. Since the law of
“garbage in, garbage out” remains in force, inexact->
exact should not be used casually.
6.5.5. Numerical input and output
(number->string number format) procedure
The conventions used to produce the printed representation
of a number can be specified by a format, as described
in section 6.5.6. The procedure number->string takes a
number and a format and returns as a string the printed
representation of the given number in the given format.
This procedure will mostly be used by sophisticated users
and in system programs. In general, a naive u se r will need
to know nothing about the formats because the system
printer will have reasonable default formats for all types of
numbers.
(string->number string exactness radix ) procedure
The system reader will construct reasonable default numer-
ical types for numbers expressed in each of the formats it
recognizes. A user who needs control of the coercion from
strings to numbers will use string->number. Exactness
must be a symbol, either E (for exact) or I (for inexact).
Radix must also be a symbol: B for bin ary, O for octal, D for
decimal, and X for hexadecimal. Ret ur n s a number of the
maximally precise representation ex pr e s se d by the given
string. It is an error if string does not express a number
according to the grammar in section 7.1.1.
6.5.6. Formats
A format is a list beginning with a format descriptor, which
is a symbol such as sci. Following the descriptor are pa-
rameters used by th at descriptor, such as the number of
significant digits to be used. Default values are supplied
for any parameters that are omitted. Modifiers may appear
after the parameters, s u ch as the radix and exactness for-
mats described below, which themselves take par amete r s .
Details of particular formats such as sci and fix are given
in section 6.5.7.
For example , the format (sci 5 2 (exactness s)) spec-
ifies that a number is to be expresse d in Fortran scien-
tific format with 5 significant p lace s and two places after
22 Revised
3
Scheme
the radix point, and that its exactness prefix is to be sup-
pressed.
In the following examples, the comment shows the format
that was used to produce the output shown:
123 +123 -123 ; (int)
123456789012345678901234567 ; (int)
355/113 +355/113 -355/113 ; (rat)
+123.45 -123.45 ; (fix 2)
3.14159265358979 ; (fix 14)
3.14159265358979 ; (flo 15)
123.450 ; (flo 6)
-123.45e-1 ; (sci 5 2)
123e3 123e-3 -123e-3 ; (sci 3 0)
-1+2i ; (rect (int) (int))
; (flo 7))
A format may specify that a number should be expressed
in a particular radix. The radix prefix may also be sup-
pressed. For example, one may express a complex number
in polar form with the magnitude in octal and the angle in
decimal as follows:
#o1.2@#d1.570796327 ; (polar (flo 2 (radix o))
; (flo (radix d)))
; (flo (radix d s)))
A format may specify that a number should be expressed
with an explicit exactness prefix ((exactness e)), or it
may force the exactness to be suppressed ((exactness
s)). For example, the following are ways to express an
inexact value for pi:
#i355/113 ; (rat (exactness e))
355/113 ; (rat (exactness s))
#i3.1416 ; (fix 4 (exactness e))
An attempt to produce more digits than are available in
the internal machine representation of a number will be
marked with a “#” filling the extra digits. This is not a
statement that the implementation knows or keeps track
of the significance of a number, just that the machine will
flag attempts to produce 20 digits of a number that has
only 15 digits of machine representation:
3.14158265358979##### ; (flo 20 (exactness s))
6.5.7. Details of formats
The format descriptors are:
(int) format
Express as an integer. The radix point is implicit. If
there are not enough s ignifi cant places then insignificant
digits will be flagged. For example , an inexact integer
6.0238 · 10
23
(represented internally as a 7 digit flonum)
would be printed as
6023800#################
(rat n) format
Express as a rational fraction. n specifi es the largest de-
nominator to be used in constructing a rational approxi-
mation to the number being expressed. If n is omitted it
defaults to infinity.
(fix n) format
Express with a fix ed radix point. n specifies the number of
places to the right of the radix point. n defaults to the size
of a single-precision flonum. If there are not enough signi f-
icant places, then insignificant digits will be flagged. For
example, an inexact 6.0238 · 10
23
(represented internally as
a 7 digit flonum) would be printed with a (fix 2) format
as
6023800#################.##
(flo n) format
Express with a floating radix point. n specifies the total
number of places to be displayed. n defaults to the size of
a single- pr e ci si on flonum. If the number is out of range,
it is converte d to (sci). (flo h) expresses n in floating
point f ormat heuristically for human consumption.
(sci n m) format
Express in exponential notation. n specifies the total num-
ber of places to be displayed. n defaults to the size of a
single-precision flonum. m specifies the number of places
to the right of the radix point. m defaults to n − 1. (sci
h) does heuristic expression.
(rect r i) format
Express as a rectangular form complex number. r and i
are formats for the real and imaginary parts respectively.
They default to (heur).
(polar m a) format
Express as a polar form comple x number. m and a are
formats for the magnitude and angle respectively. m and
a default to (heur).
(heur) format
Express he ur is t ic ally using the minimum number of digits
required to get an expression that when coerced back to
a number produces the original machine repre s entation.
Exact numbers are exp r es s ed as (int) or (rat). Inexact
numbers are expressed as (flo h) or (sci h) depending
6. Standard procedures 23
on their range. Complex numbers are expressed in (rect).
This is the normal default of the system printer.
The following modifiers may be added to a numerical for-
mat specification:
(exactness s) format
This controls the expression of the exactness prefix of a
number. s must be a symbol, either E or S, indicating
whether the exactness is to be expressed or suppr es s ed , re-
spectively. If no exactness modifier is specified for a format
then the exactness is by default suppressed.
(radix r s) format
This forces a number to be expressed in the radix r. r may
be th e symbol B (binary), O (octal), D ( de ci mal), or X (hex).
s must be a symbol, either E or S, indicating whether the
radix prefix is t o be expressed or suppressed, respectively.
s defaults to E (expre s se d) . If no radix modifier is specified
then the default is decimal and the pre fi x is su pp r es s e d.
6.6. Characters
Characters are objects that represent printed characters
such as letters and digits. There is no requirement that the
data type of characters be di s joint from other data types;
implementations are encouraged to have a separate char-
acter data type, but may choose to represent characters as
integers, strings, or some other type.
Characters are written using t he notation #\hcharacteri or
#\hcharacter namei. For example:
#\a ; lower case let te r
#\A ; upper case letter
#\( ; left parenthesis
#\ ; the space character
#\space ; the preferred way to write a space
#\newline ; the n ewli ne character
Case is significant in #\hcharacteri, bu t not in #\hcharacter
namei. If hcharacteri in #\hcharacteri is alphabetic, then
the character following hcharacteri must be a deli mite r
character such as a space or parenthesis. This rule resolves
the ambiguous case where, for example, the sequence of
characters “#\space” could be taken to be either a repre-
sentation of the space character or a representation of the
character “#\s” followed by a representation of the symbol
“pace.”
Characters written in the #\ notation are self -e valuating.
That is, they do not have to be quoted in programs. The #\
notation is not an essential part of Scheme, however. Even
implementations that suppor t the #\ notation for input do
not have to su pport it for output.
Some of the pr ocedur es that oper ate on characters ignore
the difference between upper case and lower case. The pr o-
cedures that ignore case have the suffix “-ci” (for “case in-
sensitive”). If the operation is a predicate, then the “-ci”
suffix precedes the “?” at the end of the name.
(char? obj ) essential procedure
Returns #t if obj is a character, otherwise returns #f.
(char=? char
1
char
2
) essential procedure
(char<? char
1
char
2
) essential procedure
(char>? char
1
char
2
) essential procedure
(char<=? char
1
char
2
) essential procedure
(char>=? char
1
char
2
) essential procedure
These procedures impose a total ordering on the set of
characters. It is guaranteed that under t hi s ordering:
• The upper case characters are in order. For example,
(char<? #\A #\B) returns #t.
• The lower case characters are in order. For example,
(char<? #\a #\b) returns #t.
• The digits are in order. For example, (char<? #\0
#\9) returns #t.
• Either all the digits precede all the upper case letters,
or vice versa.
• Either all the digits precede all the lower case letters,
or vice versa.
Some implementations may generalize these procedures to
take more than two arguments, as with the corresponding
numeric predicates.
(char-ci=? char
1
char
2
) procedure
(char-ci<? char
1
char
2
) procedure
(char-ci>? char
1
char
2
) procedure
(char-ci<=? char
1
char
2
) procedure
(char-ci>=? char
1
char
2
) procedure
These procedures are similar to char=? et cetera, but they
treat upper case and lower case letters as the same. For
example, (char-ci=? #\A #\a) return s #t. Some imple-
mentations may generalize these procedures to take more
than two arguments, as with the corresponding numeric
predicates.
(char-alphabetic? char) procedure
(char-numeric? char) procedure
(char-whitespace? char) procedure
These procedures retur n #t if their arguments are alpha-
betic, numeric, or whitespace characters, respectively, oth-
erwise they return #f. The following remarks, which are
24 Revised
3
Scheme
specific to the ASCII character set, are intended only as
a guide: The alphabetic ch ar acte r s are the 52 upper and
lower case letters. The numeric characters are the ten dec-
imal digits. The whitespace characters are space, tab, line
feed, form feed, and carriage return.
(char-upper-case? letter) procedure
(char-lower-case? letter) procedure
Letter must be an alphabetic character. These procedures
return #t if their arguments are upper case or lower c ase
characters, respectively, otherwise they return #f.
(char->integer char) essential procedure
(integer->char n) essential procedure
Given a character, char->integer returns an integer rep-
resentation of the character. Given an integer that is the
image of a character under char->integer, integer->
char returns a character. These procedures implement or-
der isomorphisms betwe en the set of characters under the
char<=? ordering and s ome subset of the integers under
the <= ordering. That is, if
(char<=? a b) =⇒ #t and (<= x y) =⇒ #t
and x and y are in the range of char->integer, then
(<= (char->integer a)
(char->integer b)) =⇒ #t
(char<=? (integer->char x)
(integer->char y)) =⇒ #t
(char-upcase char) procedure
(char-downcase char) procedure
These pro ce du r e s return a character char
2
such that
(char-ci=? char char
2
). In addition, if cha r is alpha-
betic, then the result of char-upcase is upper case and
the result of char-downcase is lower case.
6.7. Strings
Strings are sequence s of characters. In some implemen-
tations of Scheme they are immutable; oth er implementa-
tions provide destructive procedur e s such as string-set!
that alter string objects.
Strings are written as sequences of characters enclosed
within doublequotes ("). A doublequote can be writt en
inside a string only by escaping it with a backslash (\), as
in
"The word \"recursion\" has many meanings."
A backslash can be written inside a string only by escaping
it with another backslash. Scheme does not specify the
effect of a backslash within a string that is not followed by
a doublequote or backslash.
A string may continue from one line to the next, but this is
usually a bad idea because the exact effect may vary from
one computer system to another.
The length of a string is the number of characters that
it contains. This number is a non-negative integer that
is fixed when the string is created. The valid indexes of
a string are the exact non-negative integers less than the
length of the string. The first character of a string has
index 0, the second has index 1, and so on.
In phrases such as “the characters of string beginning with
index start and ending with index end ,” it is un de r s tood
that the index start is inclusive and the index end is ex-
clusive. Thus if start and end are the same index, a null
substring is re fe r r ed to, and if start is zero and end is the
length of string, then the entire string is referred to.
Some of the procedures that op e r ate on strings ignore the
difference between upper and lower case. The versions that
ignore case have the su ffix “-ci” (for “case insensitive”). If
the operation is a predicate, then the “-ci” suffix precedes
the “?” at the end of the name.
(string? obj ) essential procedure
Returns #t if obj is a string, otherwise returns #f.
(make-string k) procedure
(make-string k char ) procedure
k must be a non-negative integer, and char must be a char-
acter. Make-string returns a newly allocated string of
length k. If char is given, then all elements of the string
are initialized to char , otherwise the contents of the string
are unspecified.
(string-length string) essential procedure
Returns the number of characters in the given string.
(string-ref string k) essential procedure
k must be a valid index of string. String-ref returns
character k of string using zero-origin indexing.
(string-set! string k char) procedure
k must be a valid index of s tr ing. String-set! stores char
in element k of string and r et ur n s an unspecifie d value.
(string=? string
1
string
2
) essential procedure
(string-ci=? string
1
string
2
) procedure
Returns #t if the two strings are the same length and con-
tain the same characters in the same positions, otherwise
6. Standard procedures 25
returns #f. String-ci=? treats upper and lower case let-
ters as though they were the s ame character, but string=?
treats upper and lower case as distinct characters.
(string<? string
1
string
2
) essential procedure
(string>? string
1
string
2
) essential procedure
(string<=? string
1
string
2
) essential procedure
(string>=? string
1
string
2
) essential procedure
(string-ci<? string
1
string
2
) procedure
(string-ci>? string
1
string
2
) procedure
(string-ci<=? string
1
string
2
) procedure
(string-ci>=? string
1
string
2
) procedure
These procedures are the lexicographic e xt en si ons to
strings of the corresponding orderings on characters. For
example, string<? is the lex icogr aphi c ordering on strings
induced by the ordering char<? on characters. If two
strings differ in length but are the same up to the length
of the shorter string, the shorter string is considered to be
lexicographically less than th e longer string.
Implementations may generalize these and the string=?
and string-ci=? procedures to take more than two argu-
ments, as with the corresponding numeric predicates.
(substring string start end) essential procedure
String must be a string, and start and end must be exact
integers satisfying
0 ≤ start ≤ end ≤ (string-length string).
Substring returns a newly allocated string formed from
the characters of string beginning with index start (inclu-
sive) and ending with index end (exclusive).
(string-append string
1
string
2
) essential procedure
(string-append string . . . ) procedure
Returns a new string whose characters form the concate-
nation of the given strings.
(string->list string) essential procedure
(list->string chars) essential procedure
String->list returns a newly allocated list of the char-
acters that make up the given string. List->string re-
turns a string formed from the characters in the list chars.
String->list and list->string are inverses so far as
equal? is concerned. Implementations that provide de-
structive operations on strings should ensure that the re-
sult of list->string is newly allocated.
(string-copy string) procedure
Returns a newly allocated copy of the given string.
(string-fill! string char) procedure
Stores char in every element of the given string and returns
an unspecified value.
6.8. Vectors
Vectors are heterogenous mutable structures whose ele-
ments are indexed by integers.
The length of a vector is the number of elements that it
contains. This number is a non-negative integer that is
fixed when the vector is cr e ated . The valid indexes of a
vector are the exact non-ne gative integers less than the
length of the vector. The first element in a vector is indexed
by zero, and the last element is indexed by one less than
the length of the vector.
Vectors are written using the notation #(obj . . . ). For
example, a vector of length 3 containing the number zero
in element 0, the list (2 2 2 2) in element 1, and the
string "Anna" in element 2 can be written as following:
#(0 (2 2 2 2) "Anna")
Note that this is the external representation of a vector, not
an ex pression evaluating to a vector. Like list constants,
vector constants must be quoted:
’#(0 (2 2 2 2) "Anna")
=⇒ #(0 (2 2 2 2) "Anna")
(vector? obj ) essential procedure
Returns #t if obj is a vector, otherwise returns #f.
(make-vector k) essential pr ocedur e
(make-vector k fill ) procedure
Returns a newly allocated vector of k elements. If a second
argument is given, then each element is initialized to fill.
Otherwise the initial contents of each element is unspeci-
fied.
(vector obj . . . ) essential procedure
Returns a newly allocated vector whose elements contain
the given arguments. Analogous to list.
(vector ’a ’b ’c) =⇒ #(a b c)
(vector-length vector ) essential procedure
Returns the number of elements in vector.
(vector-ref vector k) essential procedur e
k must be a valid index of vector . Vector-ref returns the
contents of element k of vector .
(vector-ref ’#(1 1 2 3 5 8 13 21) 5) =⇒ 8
(vector-set! vector k obj ) essential procedure
k must be a valid index of vector . Vector-set! stores obj
in element k of vector . The value retur n ed by vector-set!
is unspecified.
26 Revised
3
Scheme
(let ((vec (vector 0 ’(2 2 2 2) "Anna")))
(vector-set! vec 1 ’("Sue" "Sue"))
vec)
=⇒ #(0 ("Sue" "Sue") "Anna")
(vector->list vector ) essential procedur e
(list->vector list) essential procedure
Vector->list returns a newly created list of the objects
contained i n the elements of vector. List->vector returns
a newly created vector initialized to the ele ments of the list
list.
(vector->list ’#(dah dah didah))
=⇒ (dah dah didah)
(list->vector ’(dididit dah))
=⇒ #(dididit dah)
(vector-fill! vector fill) procedure
Stores fill in every element of vector . The value returned
by vector-fill! is un s pecifie d.
6.9. Control features
This chapter describes various primitive procedures which
control the flow of program execution in special ways. Th e
procedure? predicate is also described here.
(procedure? obj ) essential procedure
Returns #t if obj is a procedure, otherwise returns #f.
(procedure? car) =⇒ #t
(procedure? ’car) =⇒ #f
(procedure? (lambda (x) (* x x)))
=⇒ #t
(procedure? ’(lambda (x) (* x x)))
=⇒ #f
(call-with-current-continuation procedure?)
=⇒ #t
(apply proc args) essential procedure
(apply proc arg
1
. . . args) procedure
Proc must be a procedure and args must be a list. The
first (essential) form calls proc with the elements of args as
the actual arguments. The second form is a generalization
of the first that calls proc with the elements of the list
(append (list arg
1
. . . ) args) as the actual arguments.
(apply + (list 3 4)) =⇒ 7
(define compose
(lambda (f g)
(lambda args
(f (apply g args)))))
((compose sqrt *) 12 75) =⇒ 30
(map proc list ) essential procedure
(map proc list
1
list
2
. . . ) procedure
The lists must be lists, and proc must be a proced u r e taking
as many arguments as there are lists. If more than one list
is given, then they must all be the same length. Map applies
proc element-wise to the ele ments of the lists and returns
a list of the r es u lt s. The order in which proc is appl ied to
the elements of the lists is unspecified.
(map cadr ’((a b) (d e) (g h)))
=⇒ (b e h)
(map (lambda (n) (expt n n))
’(1 2 3 4 5))
=⇒ (1 4 27 256 3125)
(map + ’(1 2 3) ’(4 5 6)) =⇒ (5 7 9)
(let ((count 0))
(map (lambda (ignored)
(set! count (+ count 1))
count)
’(a b c))) =⇒ unspecified
(for-each proc list ) essential pr ocedur e
(for-each proc list
1
list
2
. . . ) pr ocedur e
The arguments to for-each are like the arguments to map,
but for-each calls proc for its side effects r ath er than for
its values. Unlike map, for-each is guar anteed to call proc
on the elements of the lists in order from the first element to
the last, and the value returned by for-each is unspecified .
(let ((v (make-vector 5)))
(for-each (lambda (i)
(vector-set! v i (* i i)))
’(0 1 2 3 4))
v) =⇒ #(0 1 4 9 16)
(force promise) procedure
Forces the value of promise (see delay, section 4.2.5). If
no value has been computed for the promise, then a value
is computed and returned. The value of the promise is
cached (or “memoized ”) so that if it is forced a second
time, the previously computed value is returned without
any recomputation.
(force (delay (+ 1 2))) =⇒ 3
(let ((p (delay (+ 1 2))))
(list (force p) (force p)))
=⇒ (3 3)
(define a-stream
(letrec ((next
(lambda (n)
(cons n (delay (next (+ n 1)))))))
(next 0)))
6. Standard procedures 27
(define head car)
(define tail
(lambda (stream) (force (cdr stream))))
(head (tail (tail a-stream)))
=⇒ 2
Force and delay are mainly intended for programs writ-
ten in functional style. The following examples should not
be considered to illustrate good programming style, but
they illustrate the property t hat the value of a promise is
computed at most once.
(define count 0)
(define p (delay (begin (set! count (+ count 1))
(* x 3))))
(define x 5)
count =⇒ 0
p =⇒ a promise
(force p) =⇒ 15
p =⇒ a promise, still
count =⇒ 1
(force p) =⇒ 15
count =⇒ 1
Here is a possible implementation of delay and force. We
define the expression
(delay hexpressioni)
to have the s ame meaning as the procedure call
(make-promise (lambda () hexpressioni)),
where make-promise is defined as follows:
(define make-promise
(lambda (proc)
(let ((already-run? #f) (result #f))
(lambda ()
(cond ((not already-run?)
(set! result (proc))
(set! already-run? #t)))
result))))
Promises are implemented here as procedures of no argu-
ments, and force simply calls its argument.
(define force
(lambda (object)
(object)))
Various extensions to t hi s semantics of delay and force
are supported in some implementations:
• Calling force on an object that is not a promise may
simply return the object.
• It may be the case that there is no means by which
a promise can be operationally distinguished from its
forced value. That is, expres s ions like the following
may evaluate to either #t or to #f, depending on the
implementation:
(eqv? (delay 1) 1) =⇒ unspecified
(pair? (delay (cons 1 2))) =⇒ unspecified
• Some implementations will implement “implicit forc-
ing,” where the value of a promise is forced by primi-
tive procedures like cdr and +:
(+ (delay (* 3 7)) 13) =⇒ 34
(call-with-current-continuation proc)
essential procedure
Proc must be a procedure of one argument. The procedure
call-with-current-continuation packages up the cur-
rent continuation (see the rationale below) as an “escape
procedure” and p ass es it as an argument to proc. The
escape procedure is a Scheme procedure of one argument
that, if it is later passed a value, will ignore whatever con-
tinuation is in effect at that later time and will give the
value instead to the continuation that was in effect when
the escape procedure was created.
The escape procedure created by
call-with-current-continuation has unlimited extent
just like any other procedure in Scheme. It may be stored
in variables or data structures and may be called as many
times as desired.
The following examples show only the most common
uses of call-with-current-continuation. If all real
programs were as simple as these examples, there
would be no need for a procedure with the power of
call-with-current-continuation.
(call-with-current-continuation
(lambda (exit)
(for-each (lambda (x)
(if (negative? x)
(exit x)))
’(54 0 37 -3 245 19))
#t)) =⇒ -3
(define list-length
(lambda (obj)
(call-with-current-continuation
(lambda (return)
(letrec ((r
(lambda (obj)
(cond ((null? obj) 0)
((pair? obj)
(+ (r (cdr obj)) 1))
(else (return #f))))))
(r obj))))))
(list-length ’(1 2 3 4)) =⇒ 4
(list-length ’(a b . c)) =⇒ #f
Rationale: A
common use of call-with-current-continuation is for struc-
tured, non-local exits from loops or procedure bodies, but in
28 Revised
3
Scheme
fact call-with-current-continuation is extremely useful for
implementing a wide variety of advanced control structures.
Whenever a Scheme expr essio n is evaluated there is a contin-
uation wanting the result of the expression. The continuation
represents an entire (default) future for the computation. If
the expression is evaluated at top level, for example, then the
continuation will take the result, print it on the screen, prompt
for the next input, evalu a te it, and so on forever. Most of the
time the continuation includes actions specified by user code,
as in a continuatio n that will take the result, multiply it by
the value stored in a local variable, add seven, and give the
answer to the top level continuation to be printed. Normally
these ubiquitous continuations are hid d en behind the scenes and
programmers don’t think much about them. On rare occasions,
however, a programmer may need to deal with continuations ex-
plicitly. Call-with-current-continuation allows Scheme pro-
grammers to do that by creating a procedure that acts just like
the current continuation.
Most programming languages incorporate one or more special-
purpose escape constructs with names like exit, return, o r
even goto. In 1965, however, Peter Landin [21] invented a
general purpose escape operator called the J-operator. John
Reynolds [32] described a simpler but equa lly powerful con-
struct in 1972. T h e catch s pecial form d es cr ibed by Sussman
and Steele in the 1975 report on Scheme is exactly the same as
Reynolds’s construct, though its name came fro m a less general
construct in Ma c Lis p . Several Scheme implementors noticed
that the full power of the catch construct could be provided by
a procedure instead of by a special s yntactic c o n st ruct, and the
name call-with-current-continuation was coined in 198 2.
This name is descriptive, but opinions differ on the merits of
such a long name, and some people use the name call/cc in-
stead.
6.10. Input and output
6.10.1. Ports
Ports represent input and output devices. To Scheme, an
input device is a Scheme object th at can deliver characters
upon command, whil e an output device is a Scheme object
that can accept characters.
(call-with-input-file string proc)
essential procedure
(call-with-output-file string proc)
essential procedure
Proc should be a procedure of one argument, and
string should be a string naming a file. For
call-with-input-file, the file must already exist; for
call-with-output-file, the effec t is unspecified if the
file already exis ts . These procedures call proc with one ar-
gument: the port obtained by opening the named file for
input or output. If the file cannot be opened, an error is
signalled. If the procedure returns, then the port is closed
automatically and the value yielde d by the procedure is
returned. If the pro c ed ure does not return, then Scheme
will not close the port unless it can prove that the port will
never again be used for a read or write operation.
Rationale: Because Scheme’s escape procedures have un-
limited extent, it is possible to escape from the current con-
tinuation but later to escape b a ck in. If implementations
were permitted to close the port on any escape from the
current co ntinuation, then it would be impossible to write
portable code using both call-with-current-continuation
and call-with-input-file or call-with-output-file.
(input-port? obj ) essential procedure
(output-port? obj ) essential procedure
Returns #t if obj is an input port or output port res pec-
tively, otherwise returns #f.
(current-input-port) essential p r ocedur e
(current-output-port) essential procedure
Returns the current default input or output port.
(with-input-from-file string thunk) procedure
(with-output-to-file string thunk) procedure
Thunk must be a procedure of no arguments, and
string must be a string naming a file. For
with-input-from-file, the file must already exist; for
with-output-to-file, the effect is unspecified if the file
already exists. The file is op en ed for input or out-
put, an in pu t or output port c onne ct ed to it is made
the default value returned by current-input-port or
current-output-port, and the thunk is called with no ar-
guments. When the thunk returns, the port is closed and
the previous default is restored. With-input-from-file
and with-output-to-file return the value yielded by
thunk. If an escape procedure is used to escape from the
continuation of these procedures, their behavior is imple-
mentation dependent.
(open-input-file filename) procedure
Takes a string naming an exi st in g file and returns an input
port capable of delivering character s from the fi le . If the
file cannot be opened, an error is signalled.
(open-output-file filename) procedure
Takes a string naming an output file to be created and
returns an output port capable of writ in g characters to a
new file by that name. If the file cannot be opened, an
error is signalled. If a file with the given name already
exists, the effect is unspecified.
6. Standard procedures 29
(close-input-port port) procedure
(close-output-port port) p r ocedur e
Closes the file associated with po r t , rendering the port in-
capable of delivering or accepting characters. These rou-
tines have no effect if the file has already been closed. The
value r e tu r ne d is uns pecified .
6.10.2. Input
(read) essential procedure
(read port) essential procedure
Read converts written representations of Scheme objects
into the objects themselves. That is, it is a parser for the
nonterminal hdatumi (see section 7.1.2). Read returns the
next object parsable from the given input port, updating
port to point to the first character past the end of the
written representation of the object.
If an end of file is encountered in the input before any char-
acters are found that can begin an object, then an end of
file obje ct is re tu r ne d. The port remains open, and fur-
ther attempts to read will also return an end of file object.
If an end of file is encountered after the beginning of an
object’s written representation, but the written repr es en -
tation is incomplete and therefore not parsable, an error is
signalled.
The port argument may be omitted, in which case it de-
faults to the value returned by current-input-port. It is
an error to read from a closed port.
(read-char) essential procedure
(read-char port) essential procedure
Returns the next character available from the input port,
updating the port to point to the following character. If
no more characters are available, an end of file object is
returned. Port may be omitted, in which case it defaults
to the value returned by current-input-port.
(char-ready?) procedure
(char-ready? port) procedure
Returns #t if a character is ready on the input port and
returns #f otherwise. If char-ready returns #t then the
next read-char operation on the given port is guaranteed
not to h ang. If the port is at end of file then char-ready?
returns #t. Port may be omitted, in which case it defaults
to the value returned by current-input-port.
Rationale: Char-ready? exists to make it possible for a pro-
gram to accept characters from interactive ports without getting
stuck waiting for input. A ny input editors associated with such
ports must ensure that characters whose existence has been as-
serted by char-ready? cannot be rubbed out. If char-ready?
were t o return #f at end of file, a port at end of file would
be indistinguishable from an i nteractive port that has no ready
characters.
(eof-object? obj ) essential procedure
Returns #t if obj is an end of file object, otherwise returns
#f. The precise set of end of file objec ts will vary among
implementations, but in any case no end of file object will
ever be a character or an object that can be read in using
read.
6.10.3. Output
(write obj ) essential procedure
(write obj port) essenti al procedure
Writes a representation of obj to the given port . Strings
that appear in the written representation ar e enclosed in
doublequotes, and within those strings backslash and dou-
blequote characters are escaped by backslashes. Write re-
turns an unspecified value. The port argument may be
omitted, in which case it defaults to the value returned by
current-output-port.
(display obj ) essential procedure
(display obj port) essential procedure
Writes a representation of obj to the given port . Strings
that appear in the writ te n representation are not enclosed
in doublequotes, and no characters are escaped within
those strings. In those implementations th at have a dis-
tinct character type, character objects appear in the repre-
sentation as if written by write-char instead of by write.
Display retur n s an unspecified value. The port argument
may be omitted, in which case it defaults to the value re-
turned by current-output-port.
Rationale: Write is intended for producing machine-readable
output and display is for producing human-readable output.
Implementations that allow “slashification” within symbols will
probably want write but not display to slashify funny charac-
ters in symbols.
(newline) essential procedure
(newline port) essential procedure
Writes an end of line to port. Exactly how this is done
differs from one operating system to another. Returns
an unspecified value. The port argument may be omit-
ted, in which case it defaults to the value returned by
current-output-port.
(write-char char) essential procedure
(write-char char port) essential procedure
Writes the character char (not a written rep r es e ntation of
the character) to the given port and return s an unspecified
value. The port argument may be omitted, in which case it
defaults to the value returned by current-output-port.
30 Revised
3
Scheme
6.10.4. User interface
Questions of user interface generally fall outside of the do-
main of this report. However, the following operations are
important enough to deserve description here.
(load filename) essential procedure
Filename should be a string naming an existing file con-
taining Scheme source code. The load procedure reads ex-
pressions and definitions from the file and evaluates them
sequentially. It is unspecified whether the results of the
expressions are printed. The load procedure does not
affect the values returned by current-input-port and
current-output-port. Load r et ur n s an unspecified value.
Note: For portability, load must operate on source files. Its
operation on other kinds of files necessarily varies among im-
plementations.
(transcript-on filename) procedure
(transcript-off) procedure
Filename must be a string naming an output file to be cre-
ated. The effect of transcript-on is to open the named
file for output, and to cause a transc r ip t of subsequent
interaction between the user and the Scheme s ys t em to
be written to the file. The transcript is ended by a call
to transcript-off, which closes the transcript file. Only
one transcript may be in progress at any time, though some
implementations may relax this restrict ion. The values re-
turned by these procedures are unspecified.
7. Formal syntax and semantics
This chapter provides formal descriptions of what has al-
ready been described informally in previous chapters of this
report.
7.1. Formal syntax
This section provides a formal syntax for Scheme writt en
in an extended BNF. The syntax for the entire language,
including features which are not es s ential, is given here.
All spaces in the grammar are for legibility. Case is insignif-
icant; for example, #x1A and #X1a are equivalent. hemptyi
stands for the empty string.
The following extensions to BNF ar e used to make the de-
scription more concise: hthingi* means zer o or more occur-
rences of hthingi; and hthingi
+
means at least one hthingi.
7.1.1. Lexical structure
This section de sc r ibes how individual tokens (identifiers,
numbers, etc.) are formed from sequences of characters.
The following sec ti ons describe how expressions and pro-
grams are formed from sequences of tokens.
hIntertoken spacei may occur on either side of any token,
but not within a token.
Tokens which require implicit termination (identifiers,
numbers, characters, and dot) may be terminated by any
hdelimiteri, but not nece s sar il y by anything e ls e.
htokeni −→ hidentifieri | hbooleani | hnumberi
| hcharacteri | hstringi
| ( | ) | #( | ’ | ` | , | ,@ | .
hdelimiteri −→ hwhitespacei | ( | ) | " | ;
hwhitespacei −→ hspace or newlinei
hcommenti −→ ; hall subsequent characters up to a
line breaki
hatmospherei −→ hwhitespacei | hcommenti
hintertoken spacei −→ hatmospherei*
hidentifieri −→ hinitiali hsubsequenti*
| hp ec ul iar identifieri
hinitiali −→ hletteri | hspecial initiali
hletteri −→ a | b | c | ... | z
hspecial initiali −→ ! | $ | % | & | * | / | : | < | =
| > | ? | ~ | _ | ^
hsubsequenti −→ hinitiali | hdigiti
| hspecial subsequenti
hdigiti −→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
hspecial subsequenti −→ . | + | -
hpeculiar identifieri −→ + | -
hsyntactic keywordi −→ hexpression keywordi
| else | => | define
| unquote | unquote-splicing
hexpression keywordi −→ quote | lambda | if
7. Formal syntax and semantics 31
| set! | begin | cond | and | or | case
| let | let* | letrec | do | delay
| quasiquote
hvariablei −→ hany hi de ntifieri which isn’t
also a hsyntactic keywordii
hbooleani −→ #t | #f
hcharacteri −→ #\ hany characteri
| #\ hcharacter namei
hcharacter namei −→ space | newline
hstringi −→ " hstr ing elementi* "
hstring elementi −→ hany character other than " or \i
| \" | \\
hnumberi −→ hreali | hreali + hureali i
| hreali - hureali i | hr eali @ hreali
hreali −→ hs igni hur eali
hureali −→ h ur e al 2i | hureal 8i | hureal 10i | hureal 16i
The following rules for hureal Ri, huinteger R i , and hprefix
Ri should be replic ated for R = 2, 8, 10, and 16:
hureal R i −→ hprefix Ri huinteger Ri hsuffixi
| hprefix Ri huinteger Ri / huinteger Ri hsuffixi
| hprefix Ri . hdigit Ri
+
#* hsuffixi
| hprefix Ri hdigit Ri
+
. hdigit Ri* #* hsuffixi
| hprefix Ri hdigit Ri
+
#* . #* hsuffixi
hprefix R i −→ hradix Ri hexactnessi hprecisioni
| hradix Ri hprecisioni hexactnes s i
| hexactnessi hradix R i hprecisi oni
| hexactnessi hprecisioni hradix Ri
| hprecisioni hradix R i hexactness i
| hprecisioni hexactnessi hradix Ri
huinteger Ri −→ hdigit Ri
+
#*
hsigni −→ hemp tyi | + | -
hsuffixi −→ he mptyi | e hsigni hdigiti
+
hexactnessi −→ hemptyi | #i | #e
hprecisioni −→ hemptyi | #s | #l
hradix 2i −→ #b
hradix 8i −→ #o
hradix 10i −→ hemptyi | #d
hradix 16i −→ #x
hdigit 2i −→ 0 | 1
hdigit 8i −→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
hdigit 10i −→ hdigiti
hdigit 16i −→ hdigiti | a | b | c | d | e | f
7.1.2. External representations
hDatumi is what the read procedure (section 6.10.2) suc-
cessfully parses. Note that any string which parses as an
hexpressioni will also parse as a hdatumi.
hdatumi −→ h si mple datumi | hcompound datumi
hsimple datumi −→ hbooleani | hnumberi
| hcharacteri | hstringi | hsymboli
hsymboli −→ hidentifieri
hcompound datumi −→ hlisti | hvectori
hlisti −→ (hdatumi*) | (hdatumi
+
. hdatumi)
| habbreviationi
habbreviationi −→ habbrev prefixi hdatumi
habbrev prefixi −→ ’ | ` | , | ,@
hvectori −→ #(hdatumi*)
7.1.3. Expressions
hexpressioni −→ hvariablei
| hliterali
| hprocedure calli
| hlambda expres s ioni
| hconditionali
| hassignmenti
| hderived expressioni
hliterali −→ hquotationi | hself-evaluatingi
hself-evaluatingi −→ hbooleani | hnumberi
| hcharacteri | hstringi
hquotationi −→ ’hdatumi | (quote hdatumi)
hprocedure calli −→ (hoperatori hoperandi*)
hoperatori −→ hex pr e s si oni
hoperandi −→ hexpr e s s ioni
hlambda expressioni −→ (lambda hformalsi hbodyi)
hformalsi −→ (hvariablei*) | hvariablei
| (hvariablei
+
. hvariablei)
hbodyi −→ hdefinitioni* hse qu en ce i
hsequencei −→ hcommandi* hexpressioni
hcommandi −→ h ex p r es s ioni
hconditionali −→ (if ht es ti hcons eq ue nti halternatei)
htesti −→ hexpressioni
hconsequenti −→ hexpressioni
halternatei −→ hexpressioni | hemptyi
hassignmenti −→ (set! hvariablei hexpressioni)
hderived expressioni −→
(cond hcond clausei
+
)
| (cond hcond clausei* (else hsequencei))
| (case hexpressioni
hcase clausei
+
)
| (case hexpressioni
hcase clausei*
(else hsequencei))
| (and htesti*)
| (or htesti*)
| (let (hbinding speci*) hbodyi)
| (let hvariablei (hbinding speci*) hbodyi)
| (let* (hbinding speci*) hbodyi)
| (letrec (hbinding speci*) hbodyi)
32 Revised
3
Scheme
| (begin hsequencei)
| (do (hiteration speci*)
(htesti hsequencei)
hcommandi*)
| (delay hexpressioni)
| hquasiquotationi
hcond clausei −→ (htesti hsequencei)
| (else hsequencei)
| (htesti)
| (htesti => hrecipienti)
hrecipienti −→ hexpressioni
hcase clausei −→ ((hdatumi*) hsequencei)
| (else hsequencei)
hbinding speci −→ (hvariablei hexpressioni)
hiteration speci −→ (hvariablei hiniti hstepi)
| (hvariablei hiniti)
hiniti −→ hexpressioni
hstepi −→ h ex pr e s si oni
7.1.4. Quasiquotations
The following grammar for quasiquote expressions is not
context-free. It is presented as a recipe for generating an
infinite number of production rules. Imagine a copy of the
following rules for D = 1, 2, 3, . . .. D keeps track of the
nesting depth.
hquasiquotationi −→ hquasiquotation 1i
htemplate 0i −→ hexpressioni
hquasiquotation Di −→ `htemplate Di
| (quasiquote htemplate Di)
htemplate Di −→ hsimple datumi
| hlist template Di
| hvector template Di
| hunquotation Di
hlist template Di −→ (htemplate or splice Di*)
| (htemplate or splice Di
+
. htemplate Di)
| ’hquasiquotation Di
| hquasiquotation D + 1i
hvector template Di −→ #(htemplate or splice Di*)
hunquotation Di −→ ,htemplate D − 1i
| (unquote htemplate D − 1i)
htemplate or splice Di −→ htemplate Di
| hsplicing unquotation Di
hsplicing unquotation Di −→ ,@htemplate D − 1i
| (unquote-splicing htemplate D − 1i)
In hquasiq u otationis , a hlist template Di can sometimes be
confused with an hun qu otation Di or hsplicing unquotation
Di. The interpretation as an hunquotationi or hsplicing
unquotation Di takes precedence.
7.1.5. Programs and definitions
hprogrami −→ h command or definitioni*
hcommand or definitioni −→ hcommandi | hdefinitioni
hdefinitioni −→ (define hvariablei hexpressioni)
| (define (hvariablei hdef formalsi) hbodyi)
hdef formalsi −→ hvariablei*
| hvariablei* . hvariablei
7.2. Formal semantics
This section provides a formal denotational semantics for
the primitive expressions of Scheme and selected built-in
procedures. The concepts and notation used here are de-
scribed in [50]; the notation is summarized below:
h . . . i sequence formation
s ↓ k kth member of the sequence s (1-based)
#s length of sequence s
s § t concatenation of sequences s and t
s † k drop the first k members of sequence s
t → a, b McCarthy conditional “if t then a else b”
ρ[x/i] substitution “ρ with x for i”
x in D injection of x into domain D
x | D projection of x to domain D
To avoid special treatment for a top-level environment, the
semantics assumes that environment s assign locations to all
variables.
The reason that expression continuations take sequences
of values instead of single values is to simplify the formal
treatment of procedure calls and to make it easy to add
multiple return values.
The order of evaluation within a call is unspecifie d. We
mimic that here by applying arbitrary permutations per-
mute and unpermute, which must be inverses, to the ar-
guments in a call before and after th ey are evaluated.
This still requires that the order of evaluation be con-
stant throughout a program (for any given number of ar-
guments), but it is a closer approximation to the intended
semantics than a left-to-right evaluation would be.
The storage allocator new is implementation-dep e nd ent,
but it must obey the following axiom: if new σ
∈
L, then
σ (new σ | L) ↓ 2 = false.
The semantics in this section was translated by machine
from an executable version of the semantics written in
Scheme itself.
7.2.1. Abstract syntax
K
∈
Con constants, including quotations
I
∈
Ide i de ntifiers (variabl es )
E
∈
Exp expressions
Γ
∈
Com = Exp commands
Exp −→ K | I | (E
0
E*)
| (lambda (I*) Γ* E
0
)
| (lambda (I* . I) Γ* E
0
)
7. Formal s y ntax and semantics 33
| (lambda I Γ* E
0
)
| (if E
0
E
1
E
2
) | (if E
0
E
1
)
| (set! I E)
7.2.2. Domain equations
α
∈
L locations
ν
∈
N natural numbers
T = {false, true} bo ole ans
Q symbols
H characters
R numbers
E
p
= L × L pairs
E
v
= L* vectors
E
s
= L* strings
M = {false, true, null, undefined, unspecified}
miscellaneous
φ
∈
F = L × (E* → K → C) procedure values
ǫ
∈
E = Q + H + R + E
p
+ E
v
+ E
s
+ M + F
expressed values
σ
∈
S = L → (E × T) stores
ρ
∈
U = Ide → L environments
θ
∈
C = S → A command continuations
κ
∈
K = E* → C expression continuations
A answers
X errors
7.2.3. Semantic functions
K : Con → E
E : Exp → U → K → C
E* : Exp* → U → K → C
C : Com* → U → C → C
Definition of K deliberately omitted.
E[[K]] = λρκ . send ( K[[K]]) κ
E[[I]] = λρκ . hold (lookup ρ I)
(single(λǫ . ǫ = undefined →
wrong “undefined variable”,
send ǫ κ))
E[[(E
0
E*)]] =
λρκ . E*(permute(hE
0
i § E*))
ρ
(λǫ* . ((λǫ* . applica te (ǫ* ↓ 1) (ǫ* † 1) κ)
(unpermute ǫ*)))
E[[(lambda (I*) Γ* E
0
)]] =
λρκ . λσ .
new σ
∈
L →
send (hnew σ | L,
λǫ*κ
′
. #ǫ* = #I* →
tievals(λα* . (λρ
′
. C[[Γ*]]ρ
′
(E[[E
0
]]ρ
′
κ
′
))
(extends ρ I* α*))
ǫ*,
wrong “wrong number of argu ments”i
in E)
κ
(update (new σ | L) unspecified σ),
wrong “out of memory” σ
E[[(lambda (I* . I) Γ* E
0
)]] =
λρκ . λσ .
new σ
∈
L →
send (hnew σ | L,
λǫ*κ
′
. #ǫ* ≥ #I* →
tievalsrest
(λα* . (λρ
′
. C[[Γ*]]ρ
′
(E[[E
0
]]ρ
′
κ
′
))
(extends ρ (I* § hI
′
i) α*))
ǫ*
(#I*),
wrong “too few arguments”i in E)
κ
(update (new σ | L) unspecified σ),
wrong “out of memory” σ
E[[(lambda I Γ* E
0
)]] = E[[(lambda (. I ) Γ* E
0
)]]
E[[(if E
0
E
1
E
2
)]] =
λρκ . E[[E
0
]] ρ (single (λǫ . truish ǫ → E[[E
1
]]ρκ,
E[[E
2
]]ρκ))
E[[(if E
0
E
1
)]] =
λρκ . E[[E
0
]] ρ (single (λǫ . truish ǫ → E[[E
1
]]ρκ,
send unspecified κ))
Here and elsewhere, any expressed value other than undefined
may be used in place of unspecified.
E[[(set! I E)]] =
λρκ . E[[E]] ρ (single(λǫ . assi gn (lookup ρ I)
ǫ
(send unspecified κ)))
E*[[ ]] = λρκ . κh i
E*[[E
0
E*]] =
λρκ . E[[E
0
]] ρ (single(λǫ
0
. E*[[E*]] ρ (λǫ* . κ (hǫ
0
i § ǫ*))))
C[[ ]] = λρθ . θ
C[[Γ
0
Γ*]] = λρθ . E[[Γ
0
]] ρ (λǫ* . C[[Γ*]]ρθ)
7.2.4. Auxiliary functions
lookup : U → Id e → L
lookup = λρI . ρI
extends : U → Ide* → L* → U
extends =
λρI*α* . #I* = 0 → ρ,
extends (ρ[(α* ↓ 1)/(I* ↓ 1)]) (I* † 1) (α* † 1)
wrong : X → C [implementation-dependent]
send : E → K → C
send = λǫκ . κhǫi
single : (E → C) → K
single =
λψǫ* . #ǫ* = 1 → ψ(ǫ* ↓ 1),
wrong “wrong number of retur n values”
34 Revised
3
Scheme
new : S → (L + {error}) [implementation -d ependent]
hold : L → K → C
hold = λακσ . send (σα ↓ 1)κσ
assign : L → E → C → C
assign = λαǫθσ . θ(update αǫσ)
update : L → E → S → S
update = λαǫσ . σ[hǫ, truei/α]
tievals : (L* → C) → E* → C
tievals =
λψǫ*σ . #ǫ* = 0 → ψh iσ,
new σ
∈
L → tievals (λα* . ψ(hnew σ | Li § α*))
(ǫ* † 1)
(update(new σ | L)(ǫ* ↓ 1)σ),
wrong “out of memory”σ
tievalsrest : (L* → C) → E* → N → C
tievalsrest =
λψǫ*ν . list (dropfirst ǫ*ν)
(single(λǫ . tievals ψ ((takefirst ǫ*ν) § hǫi)))
dropfirst = λln . n = 0 → l, dropfirst ( l † 1)(n − 1)
takefirst = λln . n = 0 → h i, hl ↓ 1i § (takefirs t (l † 1)(n − 1))
truish : E → T
truish = λǫ . (ǫ = false ∨ ǫ = null) → false, tru e
permute : Exp* → Exp* [implementation-dependent]
unpermute : E* → E* [inverse of permute]
applicate : E → E* → K → C
applicate =
λǫǫ*κ . ǫ
∈
F → (ǫ | F ↓ 2)ǫ*κ, wrong “bad procedure”
onearg : (E → K → C) → (E* → K → C)
onearg =
λζǫ*κ . #ǫ* = 1 → ζ(ǫ* ↓ 1)κ,
wrong “wrong number of argu ments”
twoarg : (E → E → K → C) → (E* → K → C)
twoarg =
λζǫ*κ . #ǫ* = 2 → ζ(ǫ* ↓ 1)(ǫ* ↓ 2)κ,
wrong “wrong number of argu ments”
list : E* → K → C
list =
λǫ*κ . #ǫ* = 0 → send null κ,
list (ǫ* † 1)(single(λǫ . conshǫ* ↓ 1, ǫiκ))
cons : E* → K → C
cons =
twoarg (λǫ
1
ǫ
2
κσ . new σ
∈
L →
(λσ
′
. new σ
′
∈
L →
send (hnew σ | L, new σ
′
| Li in E)
κ
(update(new σ
′
| L) ǫ
2
σ
′
),
wrong “out of memory”σ
′
)
(update(new σ | L)ǫ
1
σ),
wrong “out of memory”σ)
less : E* → K → C
less =
twoarg (λǫ
1
ǫ
2
κ . (ǫ
1
∈
R ∧ ǫ
2
∈
R) →
send (ǫ
1
| R < ǫ
2
| R → true, false)κ,
wrong “non-numeric argument to <”)
add : E* → K → C
add =
twoarg (λǫ
1
ǫ
2
κ . (ǫ
1
∈
R ∧ ǫ
2
∈
R) →
send ((ǫ
1
| R + ǫ
2
| R) in E)κ,
wrong “non-numeric argument to +”)
car : E* → K → C
car =
onearg (λǫκ . ǫ
∈
E
p
→ hold (ǫ | E
p
↓ 1)κ,
wrong “non-pair argument to car”)
cdr : E* → K → C [similar to car]
setcar : E* → K → C
setcar =
twoarg (λǫ
1
ǫ
2
κ . ǫ
1
∈
E
p
→ assign (ǫ
1
| E
p
↓ 1)
ǫ
2
(send unspecified κ),
wrong “non-pair argument to set-car!”)
eqv : E* → K → C
eqv =
twoarg (λǫ
1
ǫ
2
κ . (ǫ
1
∈
M ∧ ǫ
2
∈
M) →
send (ǫ
1
| M = ǫ
2
| M → true, false)κ,
(ǫ
1
∈
Q ∧ ǫ
2
∈
Q) →
send (ǫ
1
| Q = ǫ
2
| Q → true, false)κ,
(ǫ
1
∈
H ∧ ǫ
2
∈
H) →
send (ǫ
1
| H = ǫ
2
| H → true, false)κ,
(ǫ
1
∈
R ∧ ǫ
2
∈
R) →
send (ǫ
1
| R = ǫ
2
| R → true, false)κ,
(ǫ
1
∈
E
p
∧ ǫ
2
∈
E
p
) →
send ((λp
1
p
2
. ((p
1
↓ 1) = (p
2
↓ 1)∧
(p
1
↓ 2) = (p
2
↓ 2)) → true,
false)
(ǫ
1
| E
p
)
(ǫ
2
| E
p
))
κ,
(ǫ
1
∈
E
v
∧ ǫ
2
∈
E
v
) → . . . ,
(ǫ
1
∈
E
s
∧ ǫ
2
∈
E
s
) → . . . ,
(ǫ
1
∈
F ∧ ǫ
2
∈
F) →
send ((ǫ
1
| F ↓ 1) = (ǫ
2
| F ↓ 1) → true, false)
κ,
send false κ)
apply : E* → K → C
apply =
twoarg (λǫ
1
ǫ
2
κ . ǫ
1
∈
F → valueslist hǫ
2
i(λǫ* . applicate ǫ
1
ǫ*κ),
wrong “bad procedure argument to apply”)
valueslist : E* → K → C
valueslist =
onearg (λǫκ . ǫ
∈
E
p
→
cdrhǫi
(λǫ* . valueslist
ǫ*
(λǫ* . carhǫi(single(λǫ . κ(hǫi § ǫ*))))),
ǫ = null → κh i,
wrong “non-list argument to values-list”)
7. Formal syntax and semantics 35
cwcc : E* → K → C [call-with-current-continuation]
cwcc =
onearg (λǫκ . ǫ
∈
F →
(λσ . new σ
∈
L →
applicate ǫ
hhnew σ | L, λǫ*κ
′
. κǫ*i in Ei
κ
(update (new σ | L)
unspecified
σ),
wrong “out of memory” σ),
wrong “bad procedure argument”)
7.3. Derived expression types
This sec tion gives rewrite rules for the derived expression
types. By the application of these r ul es , any expression
can be reduced to a semantically equivalent expression in
which only the primitive expression types (literal, variable,
call, lambda, if, set!) occur.
(cond (htesti hsequencei)
hclause
2
i . . . )
≡ (if htesti
(begin hsequencei)
(cond hclause
2
i . . . ))
(cond (htesti)
hclause
2
i . . . )
≡ (or htesti (cond hclause
2
i . . . ))
(cond (htesti => hrecipienti)
hclause
2
i . . . )
≡ (let ((test-result htesti)
(thunk2 (lambda () hrecipienti))
(thunk3 (lambda () (cond hc la u se
2
i . . . ))))
(if test-result
((thunk2) test-result)
(thunk3)))
(cond (else hsequencei))
≡ (begin hsequencei)
(cond)
≡ hsome expression returnin g an unspecified valuei
(case hkeyi
((d1 . . . ) hsequencei)
. . . )
≡ (let ((key hkeyi)
(thunk1 (lambda () hsequencei))
. . . )
(cond ((hmemvi key ’(d1 . . . )) (thunk1))
. . . ))
(case hkeyi
((d1 . . . ) hsequencei)
. . .
(else f1 f2 . . . ))
≡ (let ((key hkeyi)
(thunk1 (lambda () hsequencei))
. . .
(elsethunk (lambda () . . . )))
(cond ((hmemvi key ’(d1 . . . )) (thunk1))
. . .
(else (elsethunk))))
where hmemvi is an expr es s ion evaluating to the memv pro-
cedure.
(and) ≡ #t
(and htesti) ≡ htesti
(and htest
1
i htest
2
i . . . )
≡ (let ((x htest
1
i)
(thunk (lambda () (and htest
2
i . . . ))))
(if x (thunk) x))
(or) ≡ #f
(or htesti) ≡ htesti
(or htest
1
i htest
2
i . . . )
≡ (let ((x htest
1
i)
(thunk (lambda () (or htest
2
i . . . ))))
(if x x (thunk)))
(let ((hvariable
1
i hinit
1
i) . . . )
hbodyi)
≡ ((lambda (hvariable
1
i . . . ) hbodyi) hinit
1
i . . . )
(let* () hbodyi)
≡ ((lambda () hbodyi))
(let* ((hvariable
1
i hinit
1
i)
(hvariable
2
i hinit
2
i)
. . . )
hbodyi)
≡ (let ((hvariable
1
i hinit
1
i))
(let* ((hvariable
2
i hinit
2
i)
. . . )
hbodyi))
(letrec ((hvariable
1
i hinit
1
i)
. . . )
hbodyi)
≡ (let ((hvariable
1
i hundefinedi)
. . . )
(let ((htemp
1
i hinit
1
i)
. . . )
(set! hvariable
1
i htemp
1
i)
. . . )
hbodyi)
where htemp
1
i, htemp
2
i, . . . are variables, distinct from
hvariable
1
i, . . . , which do not free occur in the original
hiniti expressions, and hundefinedi is an expression which
returns something which when stored in a location makes
it an error to try to obtain the value stored in the location.
(No such expression is define d, but one is assumed to ex-
ist for the purposes of this rewrite rule .) The second let
expression in the ex pans ion is not strictly necessary, but it
serves to preserve the property that the hiniti expressions
are evaluate d in an arbitrary order.
36 Revised
3
Scheme
(begin hsequencei)
≡ ((lambda () hsequencei))
The following alternative expansion for begin does not
make use of the ability to write more than one expres-
sion in the body of a lambda expression. In any case, note
that these rules apply only if hsequencei contains no defi-
nitions.
(begin hexpressioni) ≡ hexpressioni
(begin hcommandi hsequencei)
≡ ((lambda (ignore thunk) (thunk))
hcommandi
(lambda () (begin hsequencei)))
(do ((hvariable
1
i hinit
1
i hstep
1
i)
. . . )
(htesti hsequencei)
hcommand
1
i . . . )
≡ (letrec ((hloopi
(lambda (hvariable
1
i . . . )
(if htesti
(begin hsequencei)
(begin hcommand
1
i
. . .
(hloopi hstep
1
i . . . ))))))
(hloopi hinit
1
i . . . ))
where hloopi is any variable which is distinct from
hvariable
1
i, . . . , and which does not occu r free in the do
expression.
(let hvariable
0
i ((hvariable
1
i hinit
1
i) . . . )
hbodyi)
≡ ((letrec ((hvariable
0
i (lambda (hvariable
1
i . . . )
hbodyi)))
hvariable
0
i)
hinit
1
i . . . )
(delay hexpressioni)
≡ (hmake-promisei (lambda () hexpressioni))
where hmake-promisei is an expre s si on evaluating to some
procedure which behaves appropriately with re s pect to t he
force procedure; see section 6.9.
NOTES
Language changes
This section enumerates the changes that have been made
to Scheme since the “Revised revised report” [4] was pub-
lished.
• The character ^ (circumfle x) is n ow an extended al-
phabetic character
• The objects returned by literal expression s are permit-
ted to be immutable
• The list to which a rest-argument becomes bound must
be newly allocated
• Do variables are u pdated by rebinding rather than by
assignment
• New expre ss ion type: delay
• Quasiquote ( backquote) has been improved in several
ways: vectors are allowed; nesting is allowed ; and an
external syntax for quasiquote expressions (analogous
to that for quote) has been defined
• The semantics of definitions of the form (define
(hvariablei hformalsi) hbodyi) no longer involves an
implicit rec or letrec
• The “curr ie d” definition syntax has been removed
• The boolean constants are now written #t and #f in-
stead of #!true and #!false
• The syntax #!null (for the empty list) has been re-
moved
• New procedures : boolean?, procedure?, and force
• The value of eq? on numbers and characters is now
unspecified
• Eq? and eqv? now explicitly permit operationally
equivalent procedures to be identified
• Eqv? distin guis h es exact numbers from inexact ones,
even if they are equal according to =
• List, string, and vector indexes must be exact integers
• Atan now admits eith er one or two arguments
• Expression types removed: named-lambda, rec,
sequence
• Procedures
removed: append!, string-null?, substring-fill!,
substring-move-left!, substring-move-right!,
object-hash, object-unhash, 1+, -1+
• Redundant procedur e names removed: <?, <=?, =?,
>?, and >=?
Example 37
Keywords as variable names
Some implementations allow arbitr ary syntactic keywords
to be used as variable names, instead of reser v in g them,
as this report would have it. But this creates ambiguities
in the interpretation of expressions: for example, in the
following, i t’s not clear whether the expression (if 1 2 3)
should be treated as a procedure call or as a conditional.
(define if list)
(if 1 2 3) =⇒ 2 or (1 2 3)
These ambiguities are u s ually resolved in some consistent
way within any given implementation, but no particular
treatment stands out as being clearly superior to any other,
so these situations were excluded for th e purposes of this
report.
Macros
Scheme does not have any st andar d facility for defining
new kinds of expressions.
The ability to alter the syntax of the language c r eate s nu-
merous problems. All current implementations of Scheme
have macro facilities that solve those proble ms to one de-
gree or another, but the solutions are quite different and
it isn’t clear at this ti me which solution is best, or indeed
whether any of the solutions are truly adequate. Rather
than standardize, we are encouraging implementations to
continue to experiment with different solutions.
The main problems with traditional macros are: They
must be defined to the system before any code using them
is loaded; this is a common source of obscure bugs . They
are usually global; macros can be made to follow lexical
scope rules , but many people find the resulting scope rules
confusing. Unless they are written very carefully, macros
are vulnerable to inadvertant capture of free variables; to
get around this, for example, macros may have to generate
code in which procedure values appear as quoted constants.
There is a similar problem wit h syntactic keywords if the
keywords of special forms are not reserved. If keywords are
reserved, then either macros introduce new reserved words,
invalidating old code, or else special forms defined by the
programmer do not have the same status as special forms
defined by the system.
EXAMPLE
Integrate-system integrates the system
y
′
k
= f
k
(y
1
, y
2
, . . . , y
n
), k = 1, . . . , n
of differential equations with the method of Runge-Kutta.
The parameter system-derivative is a function that
takes a sys te m state (a vector of values for the state vari-
ables y
1
, . . . , y
n
) and produces a system derivative (the val-
ues y
′
1
, . . . , y
′
n
). The parameter initial-state provides
an initial system state, and h is an initial guess for the
length of the integration step.
The value returned by integrate-system is an infinite
stream of system states.
(define integrate-system
(lambda (system-derivative initial-state h)
(let ((next (runge-kutta-4 system-derivative h)))
(letrec ((states
(cons initial-state
(delay (map-streams next
states)))))
states))))
Runge-Kutta-4 takes a function, f, that produces a system
derivative from a system state. Runge-Kutta-4 produces
a function that takes a system state and produces a new
system state.
(define runge-kutta-4
(lambda (f h)
(let ((*h (scale-vector h))
(*2 (scale-vector 2))
(*1/2 (scale-vector (/ 1 2)))
(*1/6 (scale-vector (/ 1 6))))
(lambda (y)
;; y is a system state
(let* ((k0 (*h (f y)))
(k1 (*h (f (add-vectors y (*1/2 k0)))))
(k2 (*h (f (add-vectors y (*1/2 k1)))))
(k3 (*h (f (add-vectors y k2)))))
(add-vectors y
(*1/6 (add-vectors k0
(*2 k1)
(*2 k2)
k3))))))))
(define elementwise
(lambda (f)
(lambda vectors
(generate-vector
(vector-length (car vectors))
(lambda (i)
(apply f
(map (lambda (v) (vector-ref v i))
vectors)))))))
(define generate-vector
(lambda (size proc)
38 Revised
3
Scheme
(let ((ans (make-vector size)))
(letrec ((loop
(lambda (i)
(cond ((= i size) ans)
(else
(vector-set! ans i (proc i))
(loop (+ i 1)))))))
(loop 0)))))
(define add-vectors (elementwise +))
(define scale-vector
(lambda (s)
(elementwise (lambda (x) (* x s)))))
Map-streams is analogous to map: it applies its first argu-
ment (a procedure) to all the elements of its second argu-
ment (a stream).
(define map-streams
(lambda (f s)
(cons (f (head s))
(delay (map-streams f (tail s))))))
Infinite streams are implemented as pairs whose car holds
the first element of the s tr e am and whose cdr holds a
promise to deliver the rest of the st r eam.
(define head car)
(define tail
(lambda (stream) (force (cdr stream))))
The following illustrates t he use of integrate-system in
integrating the system
C
dv
C
dt
= −i
L
−
v
C
R
L
di
L
dt
= v
C
which mo d els a damped oscillator.
(define damped-oscillator
(lambda (R L C)
(lambda (state)
(let ((Vc (vector-ref state 0))
(Il (vector-ref state 1)))
(vector (- 0 (+ (/ Vc (* R C)) (/ Il C)))
(/ Vc L))))))
(define the-states
(integrate-system
(damped-oscillator 10000 1000 .001)
’#(1 0)
.01))
BIBLIOGRAPHY AND REFERENCES
[1] Harold Abelson and G e r ald Jay Sussman with Jul ie
Sussman. Structure and Interpretation of Computer
Programs. MIT Press, Cambridge, 1985.
[2] David H. Bartley and John C. Jensen. The imple-
mentation of PC Scheme. In Proceedings of the 1986
ACM Conference on Lisp and Functional Program-
ming, pages 86–93.
[3] John Batali, Edmund Goodhue, Chris Hanson, Howie
Shrobe, Richard M. Stallman, and Ger ald Jay Suss-
man. The Scheme-81 architecture—system and chip.
In Proceedings, Conference on Advanced Research in
VLSI, pages 69–77. Paul Penfield, Jr., editor. Artech
House, 610 Washington Street, Dedham MA, 1982.
[4] William Clinger, editor. The revise d revised report on
Scheme, or an unc ommon Lisp. MIT Artific ial Intel-
ligence Memo 848, August 1985. Also published as
Computer Science Department Technical Report 174,
Indiana University, June 1985.
[5] William Clinger. The Scheme 311 compiler: An exer-
cise in denotational semantics. In Conference Record
of the 1984 ACM Symposium on Lisp and Functional
Programming, pages 356–364.
[6] R. Kent Dybvig, Daniel P. Friedman, and Christopher
T. Haynes. Exp ansi on-p ass in g style: Beyond conven-
tional macros. In Proceedings of the 1986 ACM Con-
ference on Lisp and Functional Programming, pages
143–150.
[7] Michael A. Eisenberg. Bochser: an integrated Scheme
programming system. MIT Laboratory for Computer
Science Technical Report 349, O c tober 1985.
[8] Marc Feeley. Deux appro ches `a l’implantation
du language Scheme. M.Sc. thesis, D´epartement
d’Informatique e t de Recherche Op´erationelle, Univer-
sity of Montreal, May 1986.
[9] Matthias Felleisen, Daniel P. Friedman, Eugene
Kohlbecker, and Bruce Duba. Reasoning with con-
tinuations. In Proceedings of the Symposium on Logic
in Computer Science, pages 131–141. IEEE Computer
Society P r es s , Washigton DC, 1986.
[10] Carol Fessenden, William Clinger, Daniel P. Fried-
man, and Christopher Haynes. Scheme 311 version
4 reference manual. Indiana University Computer
Science Technical Report 137, February 1983. Su-
perceded by [13].
[11] Daniel P. Friedman and Matthias Felleisen. The Little
LISPer. Science Research Associates, second edition
1986.
Bibliography 39
[12] Daniel P. Friedman, Christopher T. Haynes, and Eu-
gene Kohlbecker. Programming with continuations. In
Program Transformation and Programming Environ-
ments, pages 263–274. P. Pepper, editor. Springer-
Verlag, 1984.
[13] D. Friedman, C. Haynes, E. Kohlbecker, and
M. Wand. Scheme 84 interim reference manual. In-
diana University Comput er Science Technic al Report
153, January 1985.
[14] Daniel P. Friedman and Christopher T. Hay n es . Con-
straining control. In Proceedings of the Twel ft h Annual
Symposium on Principles of Programming Languages ,
pages 245–254. ACM, January 1985.
[15] Christopher T. Haynes, Daniel P. Friedman, and
Mitchell Wand. Continuations and coroutine s . In Con-
ference Record of the 1984 ACM Symposium on Lisp
and Functional Programming, pages 293–298.
[16] Christopher T. Hayne s. Logic continuations. In Pro-
ceedings of the Third International Conference on
Logic Programming, pages 671–685. Springer-Verlag,
July 1986.
[17] Christopher T. Haynes and Daniel P. Friedman. En-
gines build process abstracions. In Conference Record
of the 1984 ACM Symposium on Lisp and Functional
Programming, pages 18–24.
[18] Peter Henderson. Functional Geometry. In Confer-
ence Record of the 19 82 ACM Symposium on Lisp and
Functional Programming, pages 179–187.
[19] Eugene Edmund Kohlbecker Jr. Syntactic Extensions
in the Programming Language Lisp. PhD thesis, Indi-
ana University, August 1986.
[20] David Kranz, Richard Kelsey, Jonathan Rees, Paul
Hudak, James Philbin, and Norman Adams. Orbit:
An optimizing compiler for Scheme. In Proceedings of
the SIGPLAN ’86 Symposium on Compiler Construc-
tion, pages 219–233. ACM, June 1986. Proceedings
published as SIGPLAN Notices 21(7), July 1986.
[21] Peter Landin. A correspondence between Algol 60 and
Church’s lambda notation: Part I. Communica tio ns of
the ACM 8(2):89–101, February 1965.
[22] Drew McDe r mott. An efficient environment allocation
scheme in an interpreter for a lexically-scoped lisp.
In Conference Record of the 1980 Lisp Conference,
pages 154–162. The Lisp Conference, P.O. Box 487,
Redwood Estates CA, 1980. Proceedings reprinted by
ACM.
[23] MIT Departme nt of Electri cal Engineering and Com-
puter Science. Scheme manual, seventh edition.
September 1984.
[24] Steven S. Muchnick and Uwe F. Pleban . A semantic
comparison of Lisp and Scheme. In Conference Record
of the 1980 Lisp Conference, pages 56–64. The Lisp
Conference, 1980.
[25] Peter Naur et al. Revised report on the algorith-
mic language Algol 60. Communications of the ACM
6(1):1–17, January 1963.
[26] Paul Penfield, Jr. Principal values and branch cuts
in complex APL. In APL ’81 Conference Proceed-
ings, pages 248–256. ACM SIGAPL, San Francisco,
September 1981. Proceedings published as APL Qu ot e
Quad 12(1), ACM, September 1981.
[27] Kent M. Pitman. Excep ti onal situations in Lisp. MIT
Artificial Intelligence Laboratory Working Paper 268,
February 1985.
[28] Kent M. Pitman. The revised MacLisp manual ( s atur -
day evening edition). MIT Artificial Intelligence Lab-
oratory Technical R eport 295, May 1983.
[29] Kent M. Pitman. Special forms in Lisp. In Conference
Record of the 1980 Lisp Conference, pages 179–187.
The Lisp Conference, 1980.
[30] Jonathan A. Rees and Norman I. Adams IV. T: A
dialect of Lisp or, lambda: The ultimate software tool.
In Conference Record of the 1982 ACM Symposium on
Lisp and Functional Programming, pages 114–122.
[31] Jonathan A. Rees, Norman I. Adams IV, and James
R. Meehan. The T manual, fourth edition. Yale Uni-
versity Computer Science Department, January 1984.
[32] John Reynolds. Definitional interpreters for higher or-
der programming languages. In ACM Conference Pro-
ceedings, pages 717–740. ACM, 1972.
[33] Guillermo J. Rozas. Liar, an Algol-like compiler for
Scheme. S. B. thesis, MIT Department of Electrical
Engineering and Computer Science, January 1984.
[34] Brian C. Smith. Reflection and semantics in a pro-
cedural language. MIT Laboratory for Computer Sci-
ence Technical Report 272, January 1982.
[35] Amitabh Srivastava, Don Oxley, and Aditya Srivas-
tava. An(other) integration of logic and functional pro-
gramming. In Proceedings of the Symposium on Logic
Programming, pages 254–260. IEEE, 1985.
[36] Richard M. Stallman. Phantom stacks—if you look
too hard, they aren’t the r e. MIT Artificial Intelligence
Memo 556, July 1980.
[37] Guy Lewis Steele Jr. and Gerald Jay Sussman.
Lambda, the ultimate imperative. MIT Artificial In-
telligence Memo 353, March 1976.
40 Revised
3
Scheme
[38] Guy Lewis Steele Jr. Lambda, the ultimate declara-
tive. MIT Artificial Intelligence Memo 379, November
1976.
[39] Guy Lewis Steele Jr. Debunking the “expensive pro-
cedure call” myth, or procedure call implementa-
tions considered harmful, or lambda, the u lt imate
GOTO. In ACM Conference Proceedings, pages 153–
162. ACM, 1977.
[40] Guy Lewis Steele Jr. Macaroni is better t han
spaghetti. In Proceedings of the Symposium on Arti-
ficial Intelligence and Programming Languages, pages
60–66. These proceedings were published as a special
joint issue of SIGPLAN Notices 12(8) and SIGART
Newsletter 64, August 1977.
[41] Guy Lewis Steele Jr . Rabbit: a compiler for Scheme.
MIT Artificial Intelligence Laboratory Technical Re-
port 474, May 1978.
[42] Guy Lewis Steele Jr. An overview of Common Lisp.
In Conference Record of the 1982 ACM Symposium on
Lisp and Functional Programming, pages 98–107.
[43] Guy Lewis Steele, Jr. Common Lisp: The Language.
Digital Press, Burlington M A, 1984.
[44] Guy Lewis Steele, Jr. and Gerald Jay Sussman. The
revised report on Scheme, a dialect of Lisp. MIT Ar-
tificial Intelligence Memo 452, January 1978.
[45] Guy Lewis Steele, Jr. and Gerald Jay Sussman. The
art of the interpreter, or the modularity complex
(parts zero, one, and two). MIT Artificial Intelligence
Memo 453, May 1978.
[46] Guy Lewis Steele, Jr. and Gerald Jay Suss man. De-
sign of a Lisp-based processor. Communications of the
ACM 23(11):628–645, November 1980.
[47] Guy Lewis Steele, Jr. and Gerald Jay Sussman. The
dream of a lifetime: a lazy variable extent mechanism.
In Conference Record of the 1980 Lisp Conference,
pages 163–172. The Lisp Conference, 1980.
[48] Gerald Jay Sussman and Guy Lewis Steele, Jr.
Scheme: an interpreter for extended lambda calcu-
lus. MIT Artificial Intelligence Memo 349, December
1975.
[49] Gerald Jay Sussman, Jack Holloway, Guy Lewis
Steele, Jr., and Alan Bel l. Scheme-79—Lisp on a chip.
IEEE Computer 14(7):10–21, July 1981.
[50] Joseph E. Stoy. Denotational Semantics: The Scott-
Strachey Approach to Programming Language Theory.
MIT Press, Cambridge, 1977.
[51] Texas Ins tr u ments, Inc. TI Scheme Language Refer-
ence Manual. Preliminary version 1.0, November 1985.
[52] Mitchell Wand. Continuation-based program transfor-
mation strategies. Journal of the ACM 27(1):174–180,
1978.
[53] Mitchell Wand. Continuation-based multiprocessing.
In Conference Record of the 1980 Lisp Conference,
pages 19–28. The Lisp Conference, 1980.
Index 41
ALPHABETIC INDEX OF DEFINITIONS OF CONC EP TS,
KEYWORDS, AND PROCEDURES
The principal entry for each term, procedure, or keyword is
listed first, separated from the other entries by a semicolon.
! 5
’ 7; 15
* 19; 7
+ 19; 4, 7, 12, 27, 34
, 11; 15
- 20; 4
/ 20
; 5
< 19; 34
<= 19; 24
= 19; 13, 36
=> 8
> 19
>= 19
? 5
abs 20; 12, 21
acos 20
and 9; 12
angle 21
append 16
apply 26; 34
asin 20
assoc 16; 17
assq 16; 17
assv 16; 13, 17
at-sign 11
atan 20; 21, 36
#b 19, 31
backquote 11
begin 10; 36
binding 5
binding construct 6
boolean? 12; 36
bound 6
caar 15
caddr 15
cadr 15
call 7
call by need 10
call-with-current-continuation 27; 28, 34
call-with-input-file 28
call-with-output-file 28
call/cc 28
car 15; 14, 34
case 8
catch 28
cdddar 15
cddddr 15
cdr 15; 14, 27
ceiling 20
char->integer 24
char-alphabetic? 23
char-ci<=? 23
char-ci<? 23
char-ci=? 23
char-ci>=? 23
char-ci>? 23
char-downcase 24
char-lower-case? 24
char-numeric? 23
char-ready 29
char-ready? 29
char-upcase 24
char-upper-case? 24
char-whitespace? 23
char<=? 23; 24
char<? 23; 25
char=? 23; 13
char>=? 23
char>? 23
char? 23
close-input-port 29
close-output-port 29
combination 7
comma 11
comment 5; 30
complex? 19
cond 8; 12
cons 15; 14
cos 20
current-input-port 28; 29, 30
current-output-port 28; 29, 30
#d 19
define 11; 12
delay 10; 26, 27, 36
denominator 20
display 29
do 10; 6, 12, 36
dotted pair 14
#e 19, 31
else 8
empty list 14; 12, 13, 15, 16, 36
eof-object? 29
eq? 14; 13, 16, 36
equal? 14; 13, 16, 25
equivalence predicate 13
eqv? 13; 8, 14, 15, 16, 17, 36
42 Revised
3
Scheme
error 3
escape procedure 27
essential 3
even? 19
exact->inexact 21
exact? 19
exactness 18
exactness 23
exp 20
expt 21
#f 12
false 6; 12
fix 22
flo 22
floor 20
foo 4, 11
for-each 26
force 26; 10, 27, 36
gcd 20
gen-counter 13
gen-loser 13
heur 22
#i 19, 22, 31
identifier 4; 5, 17, 30
if 8; 12, 33, 35
imag-part 21
improper list 15
inexact->exact 21
inexact? 19
initial environment 12
input-port? 28
int 22
integer->char 24
integer? 19
integrate-system 37, 38
internal definition 12
keyword 4, 5, 30, 37
#l 19, 31
lambda 7; 12, 33, 35
lambda exp r e ss ion 6
last-pair 16
lazy evalu ation 10
lcm 20
length 16
let 9, 10; 6, 12, 35
let* 9; 6, 12
letrec 9; 6, 10, 12
list 16; 25
list->string 25
list->vector 26
list-ref 16
list-tail 16
load 30
log 20
macros 37
magnitude 21
make-polar 21
make-promise 27
make-rectangular 21
make-string 24
make-vector 25
map 26; 38
map-streams 38
max 19
member 16; 17
memq 16; 13, 17
memv 16; 17, 35
min 19
modulo 20
mutation procedure 13
negative? 19
newline 29
nil 12
not 12
null? 16
number 17
number->string 21
number? 19
numerator 20
#o 19, 22, 31
odd? 19
open-input-file 28
open-output-file 28
operationally equivalent 13
or 9; 12
output-port? 28
pair 14
pair? 15
polar 22
positive? 19
predicate 13
procedure call 7
procedure? 26; 36
promise 10; 26
quasiquote 11; 15
quote 7; 6, 15, 36
quotient 20
radix 23
rat 22
rational? 19
Index 43
rationalize 20
read 29; 3, 6, 15, 17, 31
read-char 29
real-part 21
real? 19
rect 22
region 6; 8, 9, 10
remainder 20
return 28
reverse 16
round 20
runge-kutta-4 37
#s 19, 31
sci 22
sequence 10
set! 8; 11, 12, 33, 35
set-car! 15; 7, 13, 14, 34
set-cdr! 15; 14
sin 20
sqrt 21; 18, 19
string->list 25
string->number 21
string->symbol 17
string-append 25
string-ci<=? 25
string-ci<? 25
string-ci=? 24; 25
string-ci>=? 25
string-ci>? 25
string-copy 25
string-fill! 25
string-length 24
string-ref 24
string-set! 24; 7, 17
string<=? 25
string<? 25
string=? 24; 25
string>=? 25
string>? 25
string? 24
substring 25
symbol->string 17
symbol? 17
syntactic keyword 4, 5, 30, 37
#t 12
t 12
tan 20
token 30
top level environment 12; 6
transcript-off 30
transcript-on 30
true 6; 8, 12
truncate 20
unbound 6; 12
unquote 11, 15
unquote-splicing 11, 15
valid in de xe s 24; 25
values-list 34
variable 5; 4, 6, 31, 37
vector 25
vector->list 26
vector-fill! 26
vector-length 25
vector-ref 25
vector-set! 25
vector? 25
whitespace 5
with-input-from-file 28
with-output-to-file 28
write 29; 6, 11, 17
write-char 29
#x 19, 31
zero? 19
