% This file contains the documentation of the part of the
%Scheme student system that is not specific to 6.003, so that we can
% include this in other manuals.

\section{Notation and terminology}

This section describes the notation used in this chapter.  It also
discusses the lexical conventions for writing Scheme programs.

\subsection{Format of entries}
\label{typeconventions}

The sections below are organized into entries.  Each entry describes
one language feature or a group of related features, where a feature
is either a syntactic construct or a built-in procedure.  An entry
begins with one or more header lines of the form

\noindent\pproto{\var{template}}{\var{category}}\unpenalty

If \var{category} is ``\exprtype'', the entry describes an expression
type, and the header line gives the syntax of the expression type.
Components of expressions are designated by syntactic variables, which
are written using angle brackets, for example, \hyper{expression},
\hyper{variable}.  Syntactic variables should be understood to denote segments of
program text; for example, \hyper{expression} stands for any string of
characters which is a syntactically valid expression.  The notation
\begin{tabbing}
\qquad \hyperi{thing} $\ldots$
\end{tabbing}
indicates zero or more occurrences of a \hyper{thing}, and
\begin{tabbing}
\qquad \hyperi{thing} \hyperii{thing} $\ldots$
\end{tabbing}
indicates one or more occurrences of a \hyper{thing}.

If \var{category} is ``procedure'', then the entry describes a procedure, and
the header line gives a template for a call to the procedure.  Argument
names in the template are \var{italicized}.  Thus the header line

\noindent\pproto{(vector-ref \var{vector} \var{k})}{procedure}\unpenalty

indicates that the procedure {\tt vector-ref} takes
two arguments, a vector \var{vector} and an integer \var{k}.  The
header line

\noindent%
\pproto{(append \var{list} \dotsfoo)}{procedure}\unpenalty

indicates that the {\tt append} procedure takes zero or more
arguments.

It is an error for an operation to be presented with an argument 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 {\tt vector-ref} given above dictates that first
argument to {\tt vector-ref} must be a vector.  The following naming
conventions also imply type restrictions:
\newcommand{\foo}[1]{\vr{#1}, \vri{#1}, $\ldots$ \vrj{#1}, $\ldots$}
$$
\begin{tabular}{ll}
\var{obj}&any object\\
\foo{x}&real nnumber\\
\foo{y}&real number\\
\foo{z}&complex number\\
\foo{n}&integer\\
\foo{k}&nonnegative integer\\
\end{tabular}
$$

\subsection{Evaluation examples}

The symbol ``\evalsto'' used in program examples should be read
``evaluates to.''  For example,

\begin{scheme}
(* 5 8)      \ev  40%
\end{scheme}

means that the expression {\tt(* 5 8)} evaluates to {\tt 40}.

\subsection{Unspecified values}

\vest If the value of an expression is said to be ``unspecified,'' then
the Scheme implementation makes no commitment as to what the value may
be.  For example

\begin{scheme}
(set! x 3)    \ev  \unspecified
\end{scheme}

Feel free to experiment and determine what Scheme returns in any
particular case, but be warned that there is no guarantee that the
behavior will not change when there is a system update.  On no account
should you write programs that rely on a value that has been
advertised to be unspecified.

\subsection{Identifiers}
\label{identifiersyntax}

An identifier\mainindex{identifier} in Scheme is a
sequence of letters, digits, and ``extended alphabetic
characters'' that begins with a character that cannot begin a number is
an identifier.  In addition, \ide{+} and \ide{-} %, \ide{1+}, and \ide{-1+}
are identifiers.  Here are some examples of identifiers:

\begin{scheme}
lambda                   q
list->vector             soup
{+}                        V17a
<=?                      a34kTMNs
the-word-recursion-has-many-meanings%
\end{scheme}

\vest Upper and lower case forms of a letter are never distinguished
except within character and string constants.  For example, {\tt Foo}
is the same identifier as {\tt FOO}, and {\tt\#x1AB} is the same
number as {\tt\#X1ab}.\footnote{Be aware, however, that Unix
distinguishes between upper and lower case letters in file and
directory names.}

\vest Identifiers have several uses within Scheme programs:
\begin{itemize}
\item Certain identifiers are reserved for use as syntactic keywords
(see below).\index{syntactic keyword}\index{keyword}

\item Any identifier that is not a syntactic keyword may be used as a
variable\index{variable} (see section~\ref{variablesection}).

\item When an identifier appears as a quoted constant or within a quoted
constant, it is being used to denote a {\em symbol}
(see section~\ref{symbolsection}).

\end{itemize}

\label{keywordsection}
The following identifiers are syntactic keywords, and should not be used
as variables:

\begin{scheme}
and          else             quasiquote
begin        if               quote
or           lambda           set!
cond         let              unquote
sequence     letrec           cons-stream
define       let*             unquote-splicing
delay        the-environment  make-environment
error        bkpt
\end{scheme}


\subsection{Syntax of numbers}
\index{number}

A number is expressed as a sequence of digits, followed optionally by
a decimal point and more digits, preceded optionally by a
{\tt +} or {\tt -} sign.  Scientific (power of 10) notation is
indicated by following the number by the letter {\tt e} followed
optionally by a {\tt +} or {\tt -} sign, followed by a sequence of
digits.  Scheme also supports the conventional notation for complex
constants of the form $a+b\imag$.
Here are some examples of numbers:

\begin{scheme}
123      +123       -123
12345668450450945095289203
3.14159265358979
123e10
-123.45e-1
37.4+1.5j   37.4-1.5j   0+3.5j
\end{scheme}
\noindent
Note that complex constants {\em must} have a real part and a
numerical imaginary part---{\tt 1.2j} and {\tt 3.5+j} are not
legitimate complex constants.

\subsection{Whitespace and comments}

\defining{Whitespace} characters are spaces and newlines.
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, but is
otherwise insignificant.  Whitespace may occur between any two tokens,
but not within a token.  Whitespace may also occur inside of a string,
where it is significant.

A semicolon indicates the start of a comment.\mainindex{comment} The
comment continues to the end of the line 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.

\begin{scheme}
;;; The FACT procedure computes the factorial
;;; of a nonnegative integer.
(define fact
  (lambda (n)
    (if (= n 0)
        1        ;Base case: return 1
        (* n (fact (- n 1))))))%
\end{scheme}


\subsection{Other notations}

\begin{description}{}{}

%  _ = 5F   & = 26   ~ = 7E   ^ = 5E
\setbox0\hbox{\tt * / < = > !\ ?\ :\ \$ \% \char"5F{} \char"26{} \char"7E{} \char"5E}
\item[\copy0]
These are extended alphabetic characters, and may be used
in identifiers exactly as if they were letters.

\item[{\tt.\ + -}]
These are used in numbers, and may also occur anywhere in an identifier.
A delimited plus or minus sign by itself
is also an identifier.
A delimited period (not occurring within a number or identifier) is used
in the notation for pairs (section~\ref{listsection}), and to indicate a
rest-parameter in a  formal parameter list (section~\ref{lambda}).

\item[\tt( )]
Parentheses are used for grouping and to notate lists
(section~\ref{listsection}).

\item[\singlequote]
The single quote character is used to indicate literal data (section~\ref{quote}).

\item[\backquote]
The backquote character is used to indicate almost-constant
data (section~\ref{quasiquote}).

\item[\tt, ,@]
The character comma and the sequence comma at-sign are used in conjunction
with backquote (section~\ref{quasiquote}).

\item[\tt"]
The double quote character is used to delimit strings (section~\ref{stringsection}).

\item[\backwhack]
Backslash is used in the syntax for character constants and as an escape
character within string constants (section~\ref{stringsection}).

\setbox0\hbox{\tt \char"5B{} \char"5D{} \char"7B{} \char"7D}
\item[\copy0]
Left and right square brackets and curly braces
are reserved for possible future extensions to the language.

\item[\sharpsign] Sharp sign is used for a variety of purposes depending on
the character that immediately follows it:

\item[\schtrue{} \schfalse{}]
These are the boolean constants (section~\ref{booleansection}).

\item[\sharpsign\backwhack]
Introduces a character constant (section~\ref{charactersection}).

\item[\sharpsign\tt(]
Introduces a vector constant (section~\ref{vectorsection}).

\end{description}

\section{Variables and bindings}
\label{variablesection}

\vest Any identifier that is not a syntactic keyword\index{keyword} (see
section~\ref{keywordsection}) may be used as a variable.\index{syntactic
keyword}\index{identifier}\mainindex{variable}  A variable may name a
location where a value can be stored.  A variable that does so is said
to be {\em bound} to the location.  The set of all such
bindings\mainindex{binding} in effect at some point in a program is
known as the {\em environment} in effect at that point.  The value
stored in the location 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 results from this practice.

\vest Certain expression types are used to create new locations and to
bind variables to those locations.  The most fundamental of these {\em
binding constructs}\mainindex{binding construct} is the
\lambdaexp{}\index{\lambdaexp{}}, because all other binding constructs
can be explained in terms of \lambdaexp{}s.  See
section~\ref{bindingconstructs}.

\vest 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 variable is bound in a program
there corresponds a \defining{region} of the program text within which
the binding is effective.  The region is determined by the particular
binding construct that establishes the binding; if the binding is
established by a \lambdaexp{}, for example, then its region is the
entire \lambdaexp{}.  Every reference to or assignment of a variable
refers to the binding of the variable that established the innermost
of the regions containing the use.  If there is no binding of the
variable whose region contains the use, then the use refers to the
binding for the variable in the top level environment; if there is no
binding for the identifier, it is said to be
\defining{unbound}.\mainindex{bound}\index{top level environment}

\section{Expressions}
\label{expressionchapter}

\newcommand{\syntax}{{\em Syntax: }}
\newcommand{\semantics}{{\em Semantics: }}

A Scheme expression is a construct that returns a value.  Types of
expressions include variable references, literals, procedure calls,
and constructs specified by syntactic keywords (see
section~\ref{keywordsection}).  This section describes all of Scheme's
expression types, except for those dealing with conditionals and
logical operations, which are described in section~\ref{booleansection}.

\subsection{Variable references}\unsection

\begin{entry}{%
\pproto{\hyper{variable}}{ \exprtype}}

An expression consisting of a variable\index{variable}
(section~\ref{variablesection}) 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\index{unbound} variable.

\begin{scheme}
(define x 28)
x   \ev  28%
\end{scheme}
\end{entry}

\subsection{Literals}\unsection
\label{literalsection}

\begin{entry}{%
\proto{quote}{ \hyper{datum}}{ \exprtype}
\pproto{\singlequote\hyper{datum}}{ \exprtype}
\pproto{\hyper{constant}}{ \exprtype}}

{\cf (quote \hyper{datum})} evaluates to \hyper{datum}.  \hyper{Datum}
may be any printed representation of a Scheme object.  This notation
is used to include literal constants in Scheme code.

\begin{scheme}%
(quote a)                     \ev  a
(quote \sharpsign(a b c))     \ev  \#(a b c)
(quote (+ 1 2))               \ev  (+ 1 2)%
\end{scheme}

{\cf (quote \hyper{datum})} may be abbreviated as
\singlequote\hyper{datum}.  The two notations are equivalent in all
respects.

\begin{scheme}
'a                   \ev  a
'\#(a b c)           \ev  \#(a b c)
'(+ 1 2)             \ev  (+ 1 2)
'(quote a)           \ev  (quote a)
''a                  \ev  (quote a)%
\end{scheme}

Numeric constants, string constants, character constants, and boolean
constants evaluate ``to themselves''; they need not be quoted.

\begin{scheme}
'"abc"     \ev  "abc"
"abc"      \ev  "abc"
'145932    \ev  145932
145932     \ev  145932
'\schtrue  \ev  \schtrue
\schtrue   \ev  \schtrue%
\end{scheme}

\end{entry}


\subsection{Procedure calls}\unsection

\begin{entry}{%
\pproto{(\hyper{operator} \hyperi{operand} \dotsfoo)}{ \exprtype}}

A procedure call is written by enclosing in parentheses
expressions for the procedure to be called and the arguments to be
passed to it.  The operator and operand expressions are evaluated (in an
indeterminate order) and the resulting procedure is passed the resulting
arguments.\mainindex{call}\mainindex{procedure call}
\begin{scheme}%
(+ 3 4)                          \ev  7
((if \schfalse + *) 3 4)         \ev  12%
\end{scheme}


Procedure calls are also called {\em combinations}.
\mainindex{combination}

\end{entry}


\subsection{Lambda expressions}\unsection
\label{lambda}

\begin{entry}{%
\proto{lambda}{ \hyper{formals} \hyper{body}}{ \exprtype}}

\syntax
\hyper{Formals} should be a formal arguments list as described below,
and \hyper{body} should be a sequence of one or more expressions.

\semantics
\vest A \lambdaexp{} evaluates to a procedure.  The environment in
effect when the \lambdaexp{} was evaluated is remembered as part of the
procedure.  When the procedure is later called with some actual
arguments, the environment in which the \lambdaexp{} was evaluated 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 \lambdaexp{}
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.

\begin{scheme}
(lambda (x) (+ x x))      \ev  {\em{}a procedure}
((lambda (x) (+ x x)) 4)  \ev  8

(define reverse-subtract
  (lambda (x y) (- y x)))
(reverse-subtract 7 10)         \ev  3

(define foo
  (let ((x 4))
    (lambda (y) (+ x y))))
(foo 6)                         \ev  10%
\end{scheme}

\hyper{Formals} should have one of the following forms:

\begin{itemize}
\item {\tt(\hyperi{variable} \dotsfoo)}:
The procedure takes a fixed number of arguments; when the procedure is
called, the arguments will be stored in the bindings of the
corresponding variables.

\item \hyper{variable}:
The procedure takes any number of arguments; when the procedure is
called, the sequence of actual arguments is converted into a newly
allocated list, and the list is stored in the binding of the
\hyper{variable}.

\item {\tt(\hyperi{variable} \dotsfoo{} \hyper{variable$_{n-1}$} {\bf.}\ \hypern{variable})}:
If a space-delimited period precedes the last variable, then
the value stored in the binding of the last variable will be a
list of the actual arguments left over after all the other actual
arguments have been matched up against the formal arguments.
\end{itemize}

\begin{scheme}
((lambda x x) 3 4 5 6)          \ev  (3 4 5 6)
((lambda (x y . z) z)
 3 4 5 6)                       \ev  (5 6)%
\end{scheme}

\end{entry}

\subsection{Binding constructs}
\label{bindingconstructs}

The three binding constructs \ide{let}, \ide{let*}, and \ide{letrec}
give Scheme a block structure, like Algol 60.  The syntax of the three
constructs is identical, but they differ in the regions\index{region} they establish
for their variable bindings.  In a {\tt let} expression, the initial
values are computed before any of the variables become bound; in a
{\tt let*} expression, the bindings and evaluations are performed
sequentially; while in a {\tt letrec} expression, the bindings are in
effect while their initial values are being computed, thus allowing
mutually recursive definitions.

\begin{entry}{%
\proto{let}{ \hyper{bindings} \hyper{body}}{\exprtype}}

\syntax
\hyper{Bindings} should have the form
\begin{scheme}
((\hyperi{variable} \hyperi{init}) \dotsfoo)\rm,%
\end{scheme}
where each \hyper{init} is an expression, and \hyper{body} should be a
sequence of one or more expressions.

\semantics
The \hyper{init}s are evaluated in the current environment (in some
unspecified order), the \hyper{variable}s are bound to fresh locations
holding the results, the \hyper{body} is evaluated in the extended
environment, and the value of the last expression of \hyper{body} is
returned.  Each binding of a \hyper{variable} has \hyper{body} as its
region.\index{region}

\begin{scheme}
(let ((x 2) (y 3))
  (* x y))                      \ev  6

(let ((x 2) (y 3))
  (let ((foo (lambda (z) (+ x y z)))
        (x 7))
    (foo 4)))                   \ev  9%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{let}{ \hyper{variable} \hyper{bindings} \hyper{body}}{\exprtype}}

\label{namedlet}
This is an extension of the syntax of {\tt let}, called ``named
{\tt let}'' which provides a general looping construct and which may
also be used to express recursions.\index{named {\tt let}}

Named {\tt let} has the same syntax and semantics as ordinary {\tt let}
except that \hyper{variable} is bound within \hyper{body} to a procedure
whose formal arguments are the bound variables and whose body is
\hyper{body}.  Thus the execution of \hyper{body} may be repeated by
invoking the procedure named by \hyper{variable}.

%                                              |  <-- right margin
\begin{scheme}
(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))))) %
  \lev  ((6 1 3) (-5 -2))%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{let*}{ \hyper{bindings} \hyper{body}}{\exprtype}}\nobreak

\nobreak
\syntax
\hyper{Bindings} should have the form
\begin{scheme}
((\hyperi{variable} \hyperi{init}) \dotsfoo)\rm,%
\end{scheme}
and \hyper{body} should be a sequence of one or more expressions.

\semantics
{\tt Let*} is similar to {\tt let}, but the bindings are performed
sequentially from left to right, and the region\index{region} of a binding indicated
by {\cf(\hyper{variable} \hyper{init})} is that part of the {\tt let*}
expression to the right of the binding.  Thus the second binding is done
in an environment in which the first binding is visible, and so on.

\begin{scheme}
(let* ((x 1) (y (+ x 1)))
  y)                      \ev  2%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{letrec}{ \hyper{bindings} \hyper{body}}{ \exprtype}}

\syntax
\hyper{Bindings} should have the form
\begin{scheme}
((\hyperi{variable} \hyperi{init}) \dotsfoo)\rm,%
\end{scheme}
and \hyper{body} should be a sequence of one or more expressions.

\semantics
The \hyper{variable}s are bound to fresh locations holding undefined
values; the \hyper{init}s are evaluated in the resulting environment (in
some unspecified order); each \hyper{variable} is assigned to the result
of the corresponding \hyper{init}; the \hyper{body} is evaluated in the
resulting environment; and the value of the last expression in
\hyper{body} is returned.  Each binding of a \hyper{variable} has the
entire {\tt letrec} expression as its region\index{region}, making it possible to
define mutually recursive procedures.

\begin{scheme}
(letrec ((even?
          (lambda (n)
            (if (zero? n)
                \schtrue
                (odd? (- n 1)))))
         (odd?
          (lambda (n)
            (if (zero? n)
                \schfalse
                (even? (- n 1))))))
  (even? 88))   \lev  \schtrue%
\end{scheme}

One restriction on {\tt letrec} is very important: it must be possible
to evaluate each \hyper{init} without referring to the value of any
\hyper{variable}.  If this restriction is violated, then the effect is
undefined, and an error may be signalled during evaluation of the
\hyper{init}s.  The restriction is necessary because Scheme passes
arguments by value rather than by name.  In the most common uses of
{\tt letrec}, all the \hyper{init}s are \lambdaexp{}s and the
restriction is satisfied automatically.

\end{entry}


\subsection{Assignments}\unsection

\begin{entry}{%
\proto{set!}{ \hyper{variable} \hyper{expression}}{ \exprtype}}

\hyper{Expression} is evaluated, and the resulting value is stored in
the location to which \hyper{variable} is bound.  \hyper{Variable} must
be bound in some region\index{region} or at top level.  The result of
the {\tt set!} expression is unspecified.

\begin{scheme}
(define x 2)            \ev  \unspecified
(+ x 1)                 \ev  3
(set! x 4)              \ev  \unspecified
(+ x 1)                 \ev  5%
\end{scheme}

\end{entry}


\subsection{Sequencing}\unsection

\begin{entry}{%
\proto{begin}{ \hyperi{expression} \hyperii{expression} \dotsfoo}{ \exprtype}
\proto{sequence}{ \hyperi{expression} \hyperii{expression} \dotsfoo}{ \exprtype}}

The \hyper{expression}s are evaluated sequentially from left to right,
and the value of the last \hyper{expression} is returned.  This
expression type is used to sequence side effects such as input and
output.

\begin{scheme}
(begin (set! x 5)
       (+ x 1))                  \ev  6

(begin (display "4 plus 1 equals ")
       (display (+ 4 1)))      \ev  \unspecified
 \>{\em and prints}  4 plus 1 equals 5%
\end{scheme}

\begin{note}
{\tt Begin} is the sequencing construct in the Scheme standard.
{\tt Sequence} is a synonym provided for compatibility with~\cite{SICP}.
\end{note}

\end{entry}

\subsection{Quasiquotation}\unsection

\begin{entry}{%
\proto{quasiquote}{ \hyper{template}}{\exprtype} \nopagebreak
\pproto{\backquote\hyper{template}}{\exprtype}}

``Backquote'' or ``quasiquote''\index{backquote} 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\index{comma}
appear within the \hyper{template}, the result of evaluating
\backquote\hyper{template} is equivalent to the result of evaluating
\singlequote\hyper{template}.  If a comma appears within the
\hyper{template}, 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 appears followed
immediately by an at-sign (\atsign),\index{at-sign} then the following
expression must evaluate to a list; the opening and closing parentheses
of the list are then ``stripped away'' and the elements of the list are
inserted in place of the comma at-sign expression sequence.

\begin{scheme}
`(list ,(+ 1 2) 4)  \ev  (list 3 4)
(let ((name 'a)) `(list ,name ',name)) %
          \lev  (list a (quote a))
`(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b) %
          \lev  (a 3 4 5 6 b)
`(({\tt foo} ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons))) %
          \lev  ((foo 7) . cons)
`\#(10 5 ,(sqrt 4) ,@(map sqrt '(16 9)) 8) %
          \lev  \#(10 5 2 4 3 8)%
\end{scheme}

Quasiquote forms may be nested.  Substitutions are made only for
unquoted components appearing at the same nesting level
as the outermost backquote.  The nesting level increases by one inside
each successive quasiquotation, and decreases by one inside each
unquotation.

\begin{scheme}
`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f) %
          \lev  (a `(b ,(+ 1 2) ,(foo 4 d) e) f)
(let ((name1 'x)
      (name2 'y))
  `(a `(b ,,name1 ,',name2 d) e)) %
          \lev  (a `(b ,x ,'y d) e)%
\end{scheme}

The notations
 \backquote\hyper{template} and {\tt (quasiquote \hyper{template})}
 are identical in all respects.
 {\cf,\hyper{expression}} is identical to {\cf (unquote \hyper{expression})},
 and
 {\cf,@\hyper{expression}} is identical to {\cf (unquote-splicing \hyper{expression})}.

\begin{scheme}
(quasiquote (list (unquote (+ 1 2)) 4)) %
          \lev  (list 3 4)
'(quasiquote (list (unquote (+ 1 2)) 4)) %
          \lev  `(list ,(+ 1 2) 4)
     {\em{}i.e.,} (quasiquote (list (unquote (+ 1 2)) 4))%
\end{scheme}

Unpredictable behavior can result if any of the symbols
{\tt quasiquote}, {\tt unquote}, or {\tt unquote-splicing} appear in
positions within a \hyper{template} otherwise than as described above.

\end{entry}

\section{Definitions}

Definitions are used to establish bindings.  Definitions are not valid
in all contexts where expressions are allowed.  They are valid only at
the top level of a \hyper{program} and at the beginning of a
\hyper{body}.

A definition should have one of the following forms:\mainschindex{define}

\begin{itemize}

\item {\tt(define \hyper{variable} \hyper{expression})} \\

\item{\tt(define (\hyper{variable} \hyper{formals}) \hyper{body})} \\
\hyper{Formals} should be either 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 expression).  This form is equivalent to
\begin{scheme}
(define \hyper{variable}
  (lambda (\hyper{formals}) \hyper{body}))\rm.%
\end{scheme}

\item{\tt(define (\hyper{variable} . \hyper{formal}) \hyper{body})} \\
\hyper{Formal} should be a single
variable.  This form is equivalent to
\begin{scheme}
(define \hyper{variable}
  (lambda \hyper{formal} \hyper{body}))\rm.%
\end{scheme}

\end{itemize}

\subsection{Top level definitions}

At the top level of a program, a definition
\begin{scheme}
(define \hyper{variable} \hyper{expression})%
\end{scheme}
\noindent
has essentially the same effect as the assignment expression
\begin{scheme}
(set! \hyper{variable} \hyper{expression})%
\end{scheme}
\noindent
if \hyper{variable} is bound.  If \hyper{variable} is not bound,
however, then the definition will bind \hyper{variable} to a new
location before performing the assignment, whereas it would be an error
to perform a {\tt set!}\ on an unbound\index{unbound} variable.

\begin{scheme}
(define add3
  (lambda (x) (+ x 3)))
(add3 3)                            \ev  6
(define first car)
(first '(1 2))                      \ev  1%
\end{scheme}

\subsection{Internal definitions}
\label{internaldefines}

Definitions are also permitted at the
beginning of a \hyper{body} (that is, the body of a {\tt lambda},
{\tt let}, {\tt let*}, {\tt letrec}, or {\tt define} expression).  Such
definitions are known as {\em internal definitions} \mainindex{internal
definition} as opposed to the top level definitions described above.
The variable defined by an internal definition is local to the
\hyper{body}.  That is, \hyper{variable} is bound rather than assigned,
and the region of the binding is the entire \hyper{body}.  For example,

\begin{scheme}
(let ((x 5))
  (define foo (lambda (y) (bar x y)))
  (define bar (lambda (a b) (+ (* a b) a)))
  (foo (+ x 3)))                \ev  45%
\end{scheme}

A \hyper{body} containing internal definitions can always be converted
into a completely equivalent {\tt letrec} expression.  For example, the
{\tt let} expression in the above example is equivalent to

\begin{scheme}
(let ((x 5))
  (letrec ((foo (lambda (y) (bar x y)))
           (bar (lambda (a b) (+ (* a b) a))))
    (foo (+ x 3))))%
\end{scheme}


\section{Booleans and conditionals}
\label{booleansection}

The standard boolean objects for true and false are written as
\schtrue{} and \schfalse.\sharpindex{true}\sharpindex{false}  What really
matters, though, are the objects that the Scheme conditional expressions
({\tt if}, {\tt cond}, {\tt and}, {\tt or}) treat as
true\index{true} or false\index{false}.  The phrase ``a true value'' (or
sometimes just ``true'') means any object treated as true by the
conditional expressions, and the phrase ``a false value'' (or ``false'')
means any object treated as false by the conditional expressions.

\vest Of all the standard Scheme values, only \schfalse{} and the
empty list\index{empty list} count as false in conditional
expressions.  Everything else, including \schtrue, pairs, symbols,
numbers, strings, vectors, and procedures, counts as true.

\vest Boolean constants evaluate to themselves, so they don't need to be quoted
in programs.

\begin{scheme}
\schtrue         \ev  \schtrue
\schfalse        \ev  \schfalse
'\schfalse       \ev  \schfalse%
\end{scheme}

\begin{entry}{%
\vproto{true}{variable}
\vproto{false}{variable}}

The variables {\tt true} and {\tt false} are initially bound to the
values \schtrue{} and \schfalse{} respectively.  Note that these are
ordinary variables, whereas {\tt true} and {\tt false} are constants.

\begin{scheme}
true             \ev  \schtrue
false            \ev  \schfalse
'false           \ev  false
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{boolean?}{ obj}{procedure}}

{\tt Boolean?} returns \schtrue{} if \var{obj} is either \schtrue{} or
\schfalse{} and returns \schfalse{} otherwise.

\end{entry}

\subsection{Boolean operations}

\begin{entry}{%
\proto{not}{ obj}{procedure}}

{\tt Not} returns \schtrue{} if \var{obj} is false, and returns
\schfalse{} otherwise.

\begin{scheme}
(not \schtrue)   \ev  \schfalse
(not 3)          \ev  \schfalse
(not (list 3))   \ev  \schfalse
(not \schfalse)  \ev  \schtrue
(not '())        \ev  \schtrue
(not (list))     \ev  \schtrue
\end{scheme}

\end{entry}



\begin{entry}{%
\proto{and}{ \hyperi{test} \dotsfoo}{\exprtype}}

The \hyper{test} expressions are evaluated from left to right, and the
value of the first expression that evaluates to a false value is
returned.  Any remaining expressions are not evaluated.  If all the
expressions evaluate to true values, the value of the last expression
is returned.  If there are no expressions then \schtrue{} is returned.

\begin{scheme}
(and (= 2 2) (> 2 1))           \ev  \schtrue
(and (= 2 2) (< 2 1))           \ev  \schfalse
(and 1 2 'c '(f g))             \ev  (f g)
(and)                           \ev  \schtrue%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{or}{ \hyperi{test} \dotsfoo}{\exprtype}}

The \hyper{test} expressions are evaluated from left to right, and the
value of the first expression that evaluates to a true value is
returned.  Any remaining expressions are not evaluated.  If all
expressions evaluate to false values, the (false) value of the last
expression is returned.  If there are no expressions then \schfalse{}
is returned.

\begin{scheme}
(or (= 2 2) (> 2 1))            \ev  \schtrue
(or (= 2 2) (< 2 1))            \ev  \schtrue
(or \schfalse \schfalse \schfalse) \ev  \schfalse
(or (memq 'b '(a b c)) 
    (/ 3 0))                    \ev  (b c)%
\end{scheme}

\end{entry}

\subsection{Conditionals}\unsection

\begin{entry}{%
\proto{if}{ \hyper{test} \hyper{consequent} \hyper{alternate}}{ \exprtype}
\proto{if}{ \hyper{test} \hyper{consequent}}{\exprtype}}  %\/ if hyper = italic

\syntax
\hyper{Test}, \hyper{consequent}, and \hyper{alternate} may be arbitrary
expressions.

\semantics
An {\tt if} expression is evaluated as follows: first,
\hyper{test} is evaluated.  If it yields a true value\index{true} (see
section~\ref{booleansection}), then \hyper{consequent} is evaluated and
its value is returned.  Otherwise \hyper{alternate} is evaluated and its
value is returned.  If \hyper{test} yields a false value and no
\hyper{alternate} is specified, then the result of the expression is
unspecified.

\begin{scheme}
(if (> 3 2) 'yes 'no)           \ev  yes
(if (> 2 3) 'yes 'no)           \ev  no
(if (> 3 2)
    (- 3 2)
    (+ 3 2))                    \ev  1%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{cond}{ \hyperi{clause} \hyperii{clause} \dotsfoo}{ \exprtype}}

\syntax
Each \hyper{clause} should be of the form
\begin{scheme}
(\hyper{test} \hyper{expression} \dotsfoo)%
\end{scheme}
where \hyper{test} is any expression.  The last \hyper{clause} may be
an ``else clause,'' which has the form
\begin{scheme}
(else \hyperi{expression} \hyperii{expression} \dotsfoo)\rm.%
\end{scheme}
\mainschindex{else}
\mainschindex{=>}

\semantics
A {\tt cond} expression is evaluated by evaluating the \hyper{test}
expressions of successive \hyper{clause}s in order until one of them
evaluates to a true value\index{true} (see
section~\ref{booleansection}).  When a \hyper{test} evaluates to a true
value, then the remaining \hyper{expression}s in its \hyper{clause} are
evaluated in order, and the result of the last \hyper{expression} in the
\hyper{clause} is returned as the result of the entire {\tt cond}
expression.  If the selected \hyper{clause} contains only the
\hyper{test} and no \hyper{expression}s, then the value of the
\hyper{test} is returned as the result.  If all \hyper{test}s evaluate
to false values, and there is no else clause, then the result of
the conditional expression is unspecified; if there is an else
clause, then its \hyper{expression}s are evaluated, and the value of
the last one is returned.

\begin{scheme}
(cond ((> 3 2) 'greater)
      ((< 3 2) 'less))         \ev  greater%

(cond ((> 3 3) 'greater)
      ((< 3 3) 'less)
      (else 'equal))            \ev  equal%
\end{scheme}

\end{entry}


\subsection{Testing for equivalence}
\label{equivalencesection}

The three predicates described in this section are used to test
whether objects are ``the same''.  Of the three predicates, {\tt eq?}\
is the finest or most discriminating while {\tt equal?}\ is the
coarsest. {\tt Eqv?}\ is slightly less discriminating than {\tt eq?}.
In general, you should use {\tt equal?} to test the equivalence of
structures and {\tt eqv?} to test the equivalence of atomic objects.
See~\cite{RRRS} for a careful description of the rationale for these
three different predicates.

\begin{entry}{%
\proto{eqv?}{ \vari{obj} \varii{obj}}{procedure}}

{\tt Eqv?} is the predicate that you should generally used to test the
identity of atomic objects. {\tt Eqv?} returns \schtrue{} if \vari{obj}
and \varii{obj} are two symbols that print the same or two numbers
that are numerically $=$.  Two procedures are {\tt eqv?} only if they
were created by the same evaluation of the same expression.  Two
structures (two lists, two vectors, or two character strings) are
{\tt eqv?} if any attempt to modify one of them modifies the other in
the same way.  In particular, two structures might not be {\tt eqv?}
even if their respective components are {\tt eqv?}.


\begin{scheme}
(eqv? 17.945 17.945)             \ev  \schtrue
(eqv? 'a 'a)                     \ev  \schtrue
(eqv? 'a 'b)                     \ev  \schfalse
(eqv? '(a) '(a))                 \ev  \schfalse
(eqv? '() '())                   \ev  \schtrue
(eqv? (cons 1 2) (cons 1 2))     \ev  \schfalse

(let ((a '(1 2 3)))
  (let ((b (cons a a)))
    (eqv? (car b) (cdr b))))     \ev  \schtrue

(eqv? (lambda () 1)
      (lambda () 1))              \ev  \schfalse

(let ((p (lambda () 1)))
  (eqv? p p))                     \ev  \schtrue%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{equal?}{ \vari{obj} \varii{obj}}{procedure}}

{\tt Equal?} recursively compares the contents of pairs, vectors, and
strings, applying {\tt eqv?} on atomic objects like numbers and symbols.
A rule of thumb is that objects are generally {\tt equal?} if they print
the same.  {\tt Equal?}\ may fail to terminate if its arguments are
circular data structures.

\begin{scheme}
(equal? 'a 'a)                  \ev  \schtrue
(equal? '(a) '(a))              \ev  \schtrue
(equal? '(a (b) c) '(a (b) c))  
                                \ev  \schtrue
(equal? "abc" "abc")            \ev  \schtrue
(equal? 2 2)                    \ev  \schtrue
(equal? (make-vector 5 'a)
        (make-vector 5 'a))     \ev  \schtrue
(equal? (lambda (x) x)
        (lambda (y) y))  \ev  \unspecified%
\end{scheme}

\end{entry}

\begin{entry}{%
\proto{eq?}{ \vari{obj} \varii{obj}}{procedure}}

\ide{Eq?}\ is similar to \ide{eqv?}\ except that in some cases it is
capable of discerning distinctions finer than those detectable by
\ide{eqv?}.  From an implementation point of view, two objects are
\ide{eq?} if they share the same location in memory.  In particular,
whether or not two numbers are \ide{eq?} is highly
implementation-dependent.

\begin{scheme}
(eq? 'a 'a)                     \ev  \schtrue
(eq? '(a) '(a))                 \ev  \schfalse
(eq? "a" "a")                   \ev  \unspecified
(eq? "" "")                     \ev  \unspecified
(eq? '() '())                   \ev  \schtrue
(eq? 2 2)                       \ev  \unspecified
(eq? \#\backwhack{}A \#\backwhack{}A) \ev  \unspecified%
\end{scheme}

\end{entry}



\section{Pairs and lists}
\label{listsection}

A \defining{pair} (sometimes called a \defining{dotted pair}) is a
structure with two fields called the car and cdr fields (for
historical reasons).  Pairs are created by the procedure \ide{cons}.
The car and cdr fields are accessed by the procedures \ide{car} and
\ide{cdr}.  The car and cdr fields are assigned by the procedures
\ide{set-car!}\ and \ide{set-cdr!}.

Pairs are used primarily to represent lists.  A \defining{list} can be
defined recursively as either the empty list\index{empty list} or a
pair whose cdr is a list.  The objects in the car fields of successive
pairs of a list 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\mainindex{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 \hbox{\cf (\vari{c} .\ \varii{c})} where
\vari{c} is the value of the car field and \varii{c} is the value of the
cdr field.  For example {\cf (4 .\ 5)} is a pair whose car is 4 and whose
cdr is 5.  Note that {\cf (4 .\ 5)} is the external representation of a
pair, not an expression that evaluates to a pair.

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\index{empty list} is written {\tt()} .  For example,

\begin{scheme}
(a b c d e)%
\end{scheme}

and

\begin{scheme}
(a . (b . (c . (d . (e . ())))))%
\end{scheme}

are both representations of a list of symbols.

A chain of pairs not ending in the empty list is called an
\defining{improper list}.  Note that an improper list is not a list.
The list and dotted notations can be combined to represent improper
lists:

\begin{scheme}
(a b c . d)%
\end{scheme}

is equivalent to

\begin{scheme}
(a . (b . (c . d)))%
\end{scheme}

Whether a given pair is a list depends upon what is stored in the cdr
field.  When the \ide{set-cdr!} procedure is used, an object can be a
list one moment and not the next:

\begin{scheme}
(define x (list 'a 'b 'c))
(define y x)
y                       \ev  (a b c)
(set-cdr! x 4)          \ev  \unspecified
x                       \ev  (a . 4)
(eqv? x y)              \ev  \schtrue
y                       \ev  (a . 4)%
\end{scheme}


\begin{entry}{%
\proto{pair?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is a pair, otherwise returns \schfalse.

\begin{scheme}
(pair? '(a . b))        \ev  \schtrue
(pair? '(a b c))        \ev  \schtrue
(pair? '())             \ev  \schfalse
(pair? '\#(a b))         \ev  \schfalse%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{cons}{ \vari{obj} \varii{obj}}{procedure}}

Returns a newly allocated pair whose car is \vari{obj} and whose cdr is
\varii{obj}.  The pair is guaranteed to be different (in the sense of
\ide{eqv?}) from every existing object.

\begin{scheme}
(cons 'a '())           \ev  (a)
(cons '(a) '(b c d))    \ev  ((a) b c d)
(cons "a" '(b c))       \ev  ("a" b c)
(cons 'a 3)             \ev  (a . 3)
(cons '(a b) 'c)        \ev  ((a b) . c)%
\end{scheme}
\end{entry}

\begin{entry}{%
\proto{cons*}{ \vari{obj} \varii{obj} \dotsfoo}{procedure}}

Constructs a pair whose \ide{car} is \vari{obj} and whose \ide{cdr} is
{\tt (cons* \varii{obj} \dotsfoo)}.  When there are only two
arguments, \ide{cons*} behaves like \ide{cons}.  With a single
argument, \ide{cons*} returns its argument (by convention).

\begin{scheme}
(cons* 'a 'b 'c)            \ev   (a b . c)
(cons* '(a b) 'c '(d e))    \ev  ((a b) c d e)
(cons* 'a 'b)               \ev  (a . b)
(cons* 'a)                  \ev   a
\end{scheme}
\end{entry}

\begin{entry}{%
\proto{car}{ pair}{procedure}}

\nodomain{\var{Pair} must be a pair.}
Returns the contents of the car field of \var{pair}.  Note that it is an
error to take the car of the empty list\index{empty list}.

\begin{scheme}
(car '(a b c))          \ev  a
(car '((a) b c d))      \ev  (a)
(car '(1 . 2))          \ev  1
(car '())               \ev  \scherror%
\end{scheme}
 
\end{entry}


\begin{entry}{%
\proto{cdr}{ pair}{procedure}}

\nodomain{\var{Pair} must be a pair.}
Returns the contents of the cdr field of \var{pair}.
Note that it is an error to take the cdr of the empty list.


\begin{scheme}
(cdr '((a) b c d))      \ev  (b c d)
(cdr '(1 . 2))          \ev  2
(cdr '())               \ev  \scherror%
\end{scheme}
 
\end{entry}

\begin{entry}{%
\proto{set-car!}{ pair obj}{procedure}}

\nodomain{\var{Pair} must be a pair.}  
Stores \var{obj} in the car field of \var{pair}.
The value returned by \ide{set-car!}\ is unspecified.

\end{entry}


\begin{entry}{%
\proto{set-cdr!}{ pair obj}{procedure}}

\nodomain{\var{Pair} must be a pair.}
Stores \var{obj} in the cdr field of \var{pair}.
The value returned by \ide{set-cdr!}\ is unspecified.  % <!>
%This procedure can be very confusing if used indiscriminately.

\end{entry}

\setbox0\hbox{\tt(cadr \var{pair})}
\setbox1\hbox{procedure}


\begin{entry}{%
\proto{caar}{ pair}{procedure}
\proto{cadr}{ pair}{procedure}
\pproto{\hbox to 1\wd0 {\hfil$\vdots$\hfil}}{\hbox to 1\wd1 {\hfil$\vdots$\hfil}}
\proto{cdddar}{ pair}{procedure}
\proto{cddddr}{ pair}{procedure}}

These procedures are compositions of \ide{car} and \ide{cdr}, where
for example \ide{caddr} could be defined by

\begin{scheme}
(define caddr (lambda (x) (car (cdr (cdr x))))){\rm.}%
\end{scheme}

Arbitrary compositions, up to four deep, are provided.  There are
twenty-eight of these procedures in all.

\end{entry}

\begin{entry}{%
\proto{null?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is the empty list\index{empty list},
otherwise returns \schfalse.
 
\end{entry}


\begin{entry}{%
\proto{list}{ \vari{obj} \dotsfoo}{procedure}}

Returns a list of its arguments.

\begin{scheme}
(list 'a (+ 3 4) 'c)            \ev  (a 7 c)
(list)                          \ev  ()%
\end{scheme}
\end{entry}




\begin{entry}{%
\proto{length}{ list}{procedure}}

\nodomain{\var{List} must be a list.}
Returns the length of \var{list}.

\begin{scheme}
(length '(a b c))               \ev  3
(length '(a (b) (c d e)))       \ev  3
(length '())                    \ev  0%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{append}{ \vari{list} \varii{list}}{procedure}
\proto{append}{ list \dotsfoo}{procedure}}

\nodomain{All \var{list}s should be lists.}
Returns a list consisting of the elements of the first \var{list}
followed by the elements of the other \var{list}s.

\begin{scheme}
(append '(x) '(y))              \ev  (x y)
(append '(a) '(b c d))          \ev  (a b c d)
(append '(a (b)) '((c)))        \ev  (a (b) (c))%
\end{scheme}

The resulting list is always newly allocated, except that it shares
structure with the last \var{list} argument.  The last argument may
actually be any object; an improper list results if it is not a proper
list.  \todo{This is pretty awkward.  I should get Bartley to fix this.}

\begin{scheme}
(append '(a b) '(c . d))        \ev  (a b c . d)
(append '() 'a)                 \ev  a%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{reverse}{ list}{procedure}}

\nodomain{\var{List} must be a list.}
Returns a newly allocated list consisting of the elements of \var{list}
in reverse order.

\begin{scheme}
(reverse '(a b c))              \ev  (c b a)
(reverse '(a (b c) d (e (f))))  \lev  ((e (f)) d (b c) a)%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{list-tail}{ list \vr{k}}{procedure}}

Returns the sublist of \var{list} obtained by omitting the first \vr{k}
elements.
\ide{List-tail} could be defined by

\begin{scheme}
(define list-tail
  (lambda (x k)
    (if (zero? k)
        x
        (list-tail (cdr x) (- k 1)))))%
\end{scheme} 
\end{entry}


\begin{entry}{%
\proto{list-ref}{ list \vr{k}}{procedure}}

Returns the \vr{k}th element of \var{list}.  (This is the same
as the car of {\tt(list-tail \var{list} \vr{k})}.)

\begin{scheme}
(list-ref '(a b c d) 2)              \ev  c%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{last-pair}{ list}{procedure}}

Returns the last pair in the nonempty, possibly improper, list \var{list}.
Could be defined by

\begin{scheme}
(define last-pair
  (lambda (x)
    (if (pair? (cdr x))
        (last-pair (cdr x))
        x)))%
\end{scheme} 
 
\end{entry}


\begin{entry}{%
\proto{memq}{ obj list}{procedure}
\proto{memv}{ obj list}{procedure}
\proto{member}{ obj list}{procedure}}

%Finds the first occurrence of \var{obj} in the list \var{list} and
Returns the first sublist of \var{list} whose car is \var{obj}.
If \var{obj} does not occur in \var{list}, returns \schfalse.
\ide{Memq} uses \ide{eq?}\ to compare \var{obj} with the elements of
\var{list}, while \ide{memv} uses \ide{eqv?}\ and \ide{member} uses
\ide{equal?}.

\begin{scheme}
(memq 'a '(a b c))              \ev  (a b c)
(memq 'b '(a b c))              \ev  (b c)
(memq 'a '(b c d))              \ev  \schfalse
(memq (list 'a) '(b (a) c))     \ev  \schfalse
(member (list 'a)
        '(b (a) c))             \ev  ((a) c)
(memq 101 '(100 101 102))       \ev  \unspecified
(memv 101 '(100 101 102))       \ev  (101 102)%
\end{scheme} 
 
\end{entry}


\begin{entry}{%
\proto{assq}{ obj alist}{procedure}
\proto{assv}{ obj alist}{procedure}
\proto{assoc}{ obj alist}{procedure}}

\domain{\var{Alist} (for ``association list'') must be a list of
pairs.}  Finds the first pair in \var{alist} whose car field is \var{obj}
and returns that pair.  If no pair in \var{alist} has \var{obj} as its
car, returns \schfalse.  \ide{Assq} uses \ide{eq?}\ to compare \var{obj}
with the car fields of the pairs in \var{alist}, while \ide{assv} uses
\ide{eqv?}\ and \ide{assoc} uses \ide{equal?}.

\begin{scheme}
(define e '((a 1) (b 2) (c 3)))
(assq 'a e)     \ev  (a 1)
(assq 'b e)     \ev  (b 2)
(assq 'd e)     \ev  \schfalse
(assq (list 'a) '(((a)) ((b)) ((c))))
                \ev  \schfalse
(assq 5 '((2 3) (5 7) (11 13)))    
                           \ev  \unspecified
(assv 5 '((2 3) (5 7) (11 13)))    
                           \ev  (5 7)
(assoc (list 'a) '(((a)) ((b)) ((c))))   
                           \ev  ((a))%
\end{scheme}


\begin{note}
Although they are ordinarily used as predicates,
\ide{memq}, \ide{memv}, \ide{member}, \ide{assq}, \ide{assv}, and \ide{assoc} do not
have question marks in their names because they return useful values rather
than just \schtrue{} or \schfalse{}.
\end{note}
\end{entry}


\section{Symbols}
\label{symbolsection}

Symbols are objects whose usefulness rests on the fact that two
symbols are identical (in the sense of \ide{eqv?}) if and only if
their names are spelled the same way.  The rules for writing a symbol
are exactly the same as the rules for writing an identifier; see
section~\ref{identifiersyntax}.

\begin{entry}{%
\proto{symbol?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is a symbol, otherwise returns \schfalse.

\begin{scheme}
(symbol? 'foo)          \ev  \schtrue
(symbol? (car '(a b)))  \ev  \schtrue
(symbol? "bar")         \ev  \schfalse%
\end{scheme}
\end{entry}

\begin{entry}{%
\proto{alphaless?}{\vari{symbol} \varii{symbol} }{procedure}}

Returns \schtrue{ } or \schfalse{ } according to whether the name of
\vari{symbol} alphabetically precedes the name of \varii{symbol}.

\begin{scheme}
(alphaless? 'ab 'b)      \ev     \schtrue
(alphaless? 'a 'a)      \ev     \schfalse
\end{scheme}
\end{entry}

\begin{entry}{%
\proto{explode}{ \var{symbol}}{procedure}}

Returns a list of one-character symbols or digits that are the letters
in the name of \var{symbol}.

\begin{scheme}
(explode 'gleep35)      \ev     (G L E E P 3 5)
\end{scheme}
\end{entry}

\begin{entry}{%
\proto{implode}{ \var{list}}{procedure}}

The argument must be a list of one-character symbols or numbers.
\ide{Implode} returns a symbol whose name is the concatenation of the
elements in the list.

\begin{scheme}
(implode '(g l e e p 3 5))       \ev     GLEEP35
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{generate-uninterned-symbol}{}{procedure}
\proto{generate-uninterned-symbol}{ \var{symbol}}{procedure}}

Returns a symbol that is guaranteed to be different (not \ide{eqv?})
from any other symbol.  If an argument \hyper{symbol} is specified,
then the printed representation of the new symbol will begin with the
characters of \hyper{symbol}.

\begin{note}
The ``name'' of an uninterned symbol is convenience for the human
reader.  You cannot reference an uninterned symbol by quoting its
name.
\end{note}

\begin{scheme}
(define s (generate-uninterned-symbol 'fact)) 
                                      \ev   \unspecified
s                                     \ev          FACT342
(eqv? s s)                       \ev  \schtrue
(eqv? s 'FACT342)                \ev  \schfalse
\end{scheme}
\end{entry}

\section{Numbers}
\label{numbersection}
\index{number}

Refer to section~\ref{typeconventions} for a summary of
the naming conventions used to specify restrictions on the types of
arguments to numerical routines.


\begin{entry}{%
\proto{number?}{ obj}{procedure}
\proto{complex?}{ obj}{procedure}
\proto{real?}{ obj}{procedure}
\proto{integer?}{ obj}{procedure}}

These numerical type predicates can be applied to any kind of argument,
including non-numbers.
They return true if the object is of the named type.  In general, if a type
predicate is true of a number then all higher type predicates are also true
of that number.

\end{entry}


\begin{entry}{%
\proto{zero?}{ \vr{z}}{procedure}
\proto{positive?}{ \vr{x}}{procedure}
\proto{negative?}{ \vr{x}}{procedure}
\proto{odd?}{ \vr{n}}{procedure}
\proto{even?}{ \vr{n}}{procedure}}

These numerical predicates test a number for a particular property, returning
\schtrue{} or \schfalse.

\end{entry}


\begin{entry}{%
\proto{=}{ \vri{z} \vrii{z}}{procedure}
\proto{<}{ \vri{x} \vrii{x}}{procedure}
\proto{>}{ \vri{x} \vrii{x}}{procedure}
\proto{<=}{ \vri{x} \vrii{x}}{procedure}
\proto{>=}{ \vri{x} \vrii{x}}{procedure}}

These procedures return \schtrue{} if their
arguments are (respectively): numerically equal, monotonically
increasing, monotonically decreasing, monotonically nondecreasing, or
monotonically nonincreasing.

\end{entry}


\begin{entry}{%
\proto{max}{ \vri{x} \vrii{x}}{procedure}
\proto{max}{ \vri{x} \vrii{x} \dotsfoo}{procedure}
\proto{min}{ \vri{x} \vrii{x}}{procedure}
\proto{min}{ \vri{x} \vrii{x} \dotsfoo}{procedure}}

These procedures return the maximum or minimum of their arguments.
\end{entry}


\begin{entry}{%
\proto{+}{ \vri{z} \vrii{z}}{procedure}
\proto{+}{ \vri{z} \dotsfoo}{procedure}
\proto{*}{ \vri{z} \vrii{z}}{procedure}
\proto{*}{ \vri{z} \dotsfoo}{procedure}}

These procedures return the sum or product of their arguments.

\begin{scheme}
(+ 3 4)                 \ev  7
(+ 3)                   \ev  3
(+)                     \ev  0
(* 4)                   \ev  4
(*)                     \ev  1%
\end{scheme} 
 
\end{entry}


\begin{entry}{%
\proto{-}{ \vri{z} \vrii{z}}{procedure}
\proto{-}{ \vri{z} \vrii{z} \dotsfoo}{procedure}
\proto{/}{ \vri{z} \vrii{z}}{procedure}
\proto{/}{ \vri{z} \vrii{z} \dotsfoo}{procedure}}

With two or more arguments, these procedures return the difference or
quotient of their arguments, associating to the left.  With one argument,
however, they return the additive or multiplicative inverse of their argument.

\begin{scheme}
(- 3 4)                 \ev  -1
(- 3 4 5)               \ev  -6
(- 3)                   \ev  -3
(/ 3 4 5)               \ev  3/20
(/ 3)                   \ev  1/3%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{abs}{ z}{procedure}}

\ide{Abs} returns the magnitude of its argument.  
\begin{scheme}
(abs -7)                \ev  7
(abs -3+4i)             \ev  5%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{quotient}{ \vri{n} \vrii{n}}{procedure}
\proto{remainder}{ \vri{n} \vrii{n}}{procedure}
\proto{modulo}{ \vri{n} \vrii{n}}{procedure}}

These are intended to implement number-theoretic (integer)
division: For positive integers \vri{n} and \vrii{n}, if \vriii{n} and
\vriv{n} are integers such that $\vri{n}=\vrii{n}\vriii{n}+\vriv{n}$ and
$0\leq \vriv{n}<\vrii{n}$, then

\begin{scheme}
(quotient \vri{n} \vrii{n})        \ev  \vriii{n}
(remainder \vri{n} \vrii{n})       \ev  \vriv{n}
(modulo \vri{n} \vrii{n})          \ev  \vriv{n}%
\end{scheme}

For all integers \vri{n} and \vrii{n} with \vrii{n} not equal to 0,

\begin{scheme}
(= \vri{n} (+ \=(* \vrii{n} (quotient \vri{n} \vrii{n}))
              \>(remainder \vri{n} \vrii{n})))
                                   \ev  \schtrue%
\end{scheme}


The value returned by \ide{quotient} always has the sign of the product of
its arguments.  \ide{Remainder} and \ide{modulo} differ on negative arguments---the
\ide{remainder} always has the sign of the dividend, the \ide{modulo}
always has the sign of the divisor:

\begin{scheme}
(modulo 13 4)           \ev  1
(remainder 13 4)        \ev  1

(modulo -13 4)          \ev  3
(remainder -13 4)       \ev  -1

(modulo 13 -4)          \ev  -3
(remainder 13 -4)       \ev  1

(modulo -13 -4)         \ev  -1
(remainder -13 -4)      \ev  -1%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{numerator}{ \vr{q}}{procedure}
\proto{denominator}{ \vr{q}}{procedure}}

These procedures return the numerator or denominator of their argument.
\todo{More description and examples needed.  The denominator is always positive.
What to do in the case of zero?}
\begin{scheme}
(numerator (/ 6 4))  \ev  3
(denominator (/ 6 4))  \ev  2%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{gcd}{ \vri{n} \dotsfoo}{procedure}
\proto{lcm}{ \vri{n} \dotsfoo}{procedure}}

These procedures return the greatest common divisor or least common
multiple of their arguments. The result is always non-negative.

\begin{scheme}
(gcd 32 -36)            \ev  4
(gcd)                   \ev  0
(lcm 32 -36)            \ev  288
(lcm)                   \ev  1%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{floor}{ x}{procedure}
\proto{ceiling}{ x}{procedure}
\proto{truncate}{ x}{procedure}
\proto{round}{ x}{procedure}}

These procedures create integers and rationals.


\vest \ide{Floor} returns the largest integer not larger than \vr{x}.
\ide{Ceiling} returns the smallest integer not smaller than~\vr{x}.
\ide{Truncate} returns the integer of maximal absolute value not larger
than the absolute value of \vr{x}.  \ide{Round} returns the closest
integer to \vr{x}, rounding to even when \vr{x} is halfway between two
integers. 

\begin{note}
\ide{Round} rounds to even for consistency with the rounding
modes required by the IEEE floating point standard.
\end{note}

\end{entry}


\begin{entry}{%
\proto{exp}{ \vr{z}}{procedure}
\proto{log}{ \vr{z}}{procedure}
\proto{sin}{ \vr{z}}{procedure}
\proto{cos}{ \vr{z}}{procedure}
\proto{tan}{ \vr{z}}{procedure}
\proto{asin}{ \vr{z}}{procedure}
\proto{acos}{ \vr{z}}{procedure}
\proto{atan}{ \vr{z}}{procedure}
\proto{atan}{ \vr{y} \vr{x}}{procedure}}

\ide{Log}
computes the natural logarithm of \vr{z} (not the base 10 logarithm).
\ide{Asin}, \ide{acos}, and \ide{atan} compute arcsine ($\sin^{-1}$),
arccosine ($\cos^{-1}$), and arctangent ($\tan^{-1}$), respectively.
The two-argument variant of \ide{atan} computes {\tt (angle
(make-rectangular \vr{x} \vr{y}))} (see below).

In general, the mathematical functions log, arcsine, arccosine, and
arctangent are multiply defined.
For nonzero real $x$, the value of $\log x$ is defined to be
the one whose imaginary part lies in the range $-\pi$ (exclusive) to
$\pi$ (inclusive).  $\log 0$ is undefined.  The value of $\log z$ when
\vr{z} is complex is defined according to the formula
$$\log z = \log {\rm magnitude}(z) + i \: {\rm 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 (i z + \sqrt{1 - z^2})$$
$$\cos^{-1} z = -i \log (z + i \sqrt{1 - z^2})$$
$$\tan^{-1} z = -i \log ( (1 + i z) \sqrt{1/(1 + z^2)} )$$

The above specification follows~\cite{CLtL}, which in turn
follows~\cite{Penfield81}; refer to these sources for more detailed
discussion of branch cuts, boundary conditions, and implementation of
these functions.

\end{entry}


\begin{entry}{%
\proto{sqrt}{ \vr{z}}{procedure}}

Returns the principal square root of \vr{z}.  The result will have
either positive real part, or zero real part and non-negative imaginary
part.
\end{entry}


\begin{entry}{%
\proto{expt}{ \vri{z} \vrii{z}}{procedure}}

Returns \vri{z} raised to the power \vrii{z}:
$${z_1}^{z_2} = e^{z_2 \log {z_1}}$$
$0^0$ is defined to be equal to 1.
\end{entry}


\begin{entry}{%
\proto{make-rectangular}{ \vri{x} \vrii{x}}{procedure}
\proto{make-polar}{ \vriii{x} \vriv{x}}{procedure}
\proto{real-part}{ \vr{z}}{procedure}
\proto{imag-part}{ \vr{z}}{procedure}
\proto{magnitude}{ \vr{z}}{procedure}
\proto{angle}{ \vr{z}}{procedure}
\proto{conjugate}{ \vr{z}}{procedure}}

Suppose \vri{x}, \vrii{x}, \vriii{x}, and \vriv{x} are
real numbers and \vr{z} is a complex number such that
 $$ \vr{z} = \vri{x} + \vrii{x}\hbox{$i$}
 = \vriii{x} \cdot e^{{\displaystyle{\hbox{$i$}} \vriv{x}}}$$
Then \ide{make-rectangular} and \ide{make-polar} return \vr{z},
\ide{real-part} returns \vri{x}, \ide{imag-part} returns \vrii{x},
\ide{magnitude} returns \vriii{x}, \ide{angle} returns \vriv{x}, and
\ide{conjugate} returns the complex  conjugate of \vr{z}.
In the case of \ide{angle}, whose value is not uniquely determined by
the preceding rule, the value returned will be the one in the range
$-\pi$ (exclusive) to $\pi$ (inclusive).

\begin{note} \ide{Magnitude} is the same as \ide{abs}.
\end{note}

\end{entry}

\begin{entry}{%
\proto{random}{ \vr{k}}{procedure}}

Returns an integer chosen at random between 0 and $k-1$, inclusive.
The argument $k$ must be a positive integer.
\end{entry}

\section{Characters}
\label{charactersection}

Characters are atomic objects that represent printed characters such
as letters and digits.  Characters are written using the notation
\sharpsign\backwhack\hyper{character} or
\sharpsign\backwhack\hyper{character name}.  For example:

$$
\begin{tabular}{ll}
{\tt \#\backwhack{}a}&; lower case letter\\
{\tt \#\backwhack{}A}&; upper case letter\\
{\tt \#\backwhack{}(}&; left parenthesis\\
{\tt \#\backwhack{}space}&; the space character\\
{\tt \#\backwhack{}newline}&; the newline character\\
\end{tabular}
$$

Characters written in the \sharpsign\backwhack{} notation are self-evaluating.
That is, they do not have to be quoted in programs.

\begin{entry}{%
\proto{char?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is a character, otherwise returns \schfalse.

\end{entry}


\begin{entry}{%
\proto{char=?}{ \vari{char} \varii{char}}{procedure}}

\label{characterequality}
Returns \schtrue{} if \vari{char} and \varii{char} are the same
character.  Case is significant, that is,  {\cf 
(char=?\ \#\backwhack{}A \#\backwhack{}a)} returns \schfalse.
Both \vari{char} and \varii{char} must be characters.
\end{entry}

\section{Strings}
\label{stringsection}

Strings are sequences of characters.  
Strings are written as sequences of characters enclosed within doublequotes
({\cf "}).  A doublequote can be written inside a string only by escaping
it with a backslash (\backwhack{}), as in

\begin{scheme}
"The word \backwhack{}"recursion\backwhack{}" has many meanings."%
\end{scheme}

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.


\begin{entry}{%
\proto{string?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is a string, otherwise returns \schfalse.
\end{entry}


\section{Vectors}
\label{vectorsection}

Vectors are structures whose elements are indexed by integers.  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.  The printed
representation for vectors is a \verb|#| followed by the sequence
of elements, enclosed in parentheses.  For example, a vector of length
3 containing the number zero in element 0, the list {\cf(2 2 2 2)} in
element 1, and the string {\cf "Anna"} in element 2 can be written as
following:

\begin{scheme}
\#(0 (2 2 2 2) "Anna")%
\end{scheme}

Note that this is the external representation, not an expression evaluating to
a vector.  Like lists, vector constants must be quoted:

\begin{scheme}
'\#(0 (2 2 2 2) "Anna")  \lev  \#(0 (2 2 2 2) "Anna")%
\end{scheme}

Vectors are created by the constructor procedure \ide{make-vector}.  The
elements are accessed and assigned by the procedures \ide{vector-ref}
and \ide{vector-set!}.

\todo{Pitman sez: The visual similarity to lists is bound to be confusing
to some.  Elaborate on the distinction.}


\begin{entry}{%
\proto{vector?}{ obj}{procedure}}
 
Returns \schtrue{} if \var{obj} is a vector, otherwise returns \schfalse.
\end{entry}


\begin{entry}{%
\proto{make-vector}{ size}{procedure}
\proto{make-vector}{ size fill}{procedure}}

Returns a newly allocated vector of \var{size} elements.  If a second
argument is given, then each element is initialized to \var{fill}.
Otherwise the initial contents of each element is unspecified.

\end{entry}


\begin{entry}{%
\proto{vector}{ obj \dotsfoo}{procedure}}

Returns a newly allocated vector whose elements contain the given
arguments.  Analogous to \ide{list}.

\begin{scheme}
(vector 'a 'b 'c)               \ev  \#(a b c)%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{vector-length}{ vector}{procedure}}

Returns the number of elements in \var{vector}.
\end{entry}


\begin{entry}{%
\proto{vector-ref}{ vector k}{procedure}}

\domain{\vr{k} must be a nonnegative integer less than
{\cf(vector-length \var{vector})}.}
\ide{Vector-ref} returns the contents of element \vr{k} of
\var{vector}.

\begin{scheme}
(vector-ref '\#(1 1 2 3 5 8 13 21) 5)  \evalsto  8%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{vector-set!}{ vector k obj}{procedure}}

\domain{\vr{k} must be a nonnegative integer less than
{\cf(vector-length \var{vector})}.}
\ide{Vector-set!} stores \var{obj} in element \vr{k} of \var{vector}.
The value returned by \ide{vector-set!}\ is unspecified.  % <!>

\begin{scheme}
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
  (vector-set! vec 1 '("Sue" "Sue"))
  vec)      \lev  \#(0 ("Sue" "Sue") "Anna")%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{vector->list}{ vector}{procedure}
\proto{list->vector}{ list}{procedure}}

\ide{Vector->list} returns a newly created list of the objects contained
in the elements of \var{vector}.  \ide{List->vector} returns a newly
created vector initialized to the elements of the list \var{list}.

\begin{scheme}
(vector->list '\#(dah dah didah))  \lev  (dah dah didah)
(list->vector '(dididit dah))   \lev  \#(dididit dah)%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{vector-fill!}{ vector fill}{procedure}}

Stores \var{fill} in every element of \var{vector}.
The value returned by \ide{vector-fill!}\ is unspecified.  % <!>

\end{entry}


\section{Control features}
 
This chapter describes various primitive procedures that control the
flow of program execution in special ways.

\begin{entry}{%
\proto{apply}{ proc args}{procedure}
\proto{apply}{ proc \vari{arg} \dotsfoo args}{procedure}}

\domain{\var{Proc} must be a procedure and \var{args} must be a list.}
The first form calls \var{proc} with the elements of
\var{args} as the actual arguments.  The second form is a generalization
of the first that calls \var{proc} with the elements of {\cf(append
(list \vari{arg} \dotsfoo) \var{args})} as the actual arguments.

\begin{scheme}
(apply + (list 3 4))              \ev  7
(apply + 1 2 (list 3 4))          \ev 10

(define compose
  (lambda (f g)
    (lambda args
      (f (apply g args)))))

((compose sqrt *) 12 75)              \ev  30%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{map}{ proc list}{procedure}
\proto{map}{ proc \vari{list} \varii{list} \dotsfoo}{procedure}}

\domain{\var{Proc} must be a procedure of one argument and the \var{list}s must
be lists.  If more than one \var{list} is given, then they must
all be the same length.}
\ide{Map} applies \var{proc} element-wise to the elements of the
\var{list}s and returns a list of the results.  The order in which
\var{proc} is applied to the elements of the \var{list}s is unspecified.

\begin{scheme}
(map cadr '((a b) (d e) (g h)))   \lev  (b e h)

(map (lambda (n) (expt n n))
     '(1 2 3 4 5))                \lev  (1 4 27 256 3125)

(map + '(1 2 3) '(4 5 6))         \ev  (5 7 9)

(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1))
         count)
       '(a b c)))                 \ev  \unspecified%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{for-each}{ proc list}{procedure}
\proto{for-each}{ proc \vari{list} \varii{list} \dotsfoo}{procedure}}

The arguments to \ide{for-each} are like the arguments to \ide{map}, but
\ide{for-each} calls \var{proc} for its side effects rather than for its
values.  Unlike \ide{map}, \ide{for-each} is guaranteed to call \var{proc} on
the elements of the \var{list}s in order from the first element to the
last, and the value returned by \ide{for-each} is unspecified.

\begin{scheme}
(let ((v (make-vector 5)))
  (for-each (lambda (i)
              (vector-set! v i (* i i)))
            '(0 1 2 3 4))
  v)                                \ev  \#(0 1 4 9 16)%
\end{scheme}

\end{entry}


\section{Streams and delayed evaluation}

A \defining{stream} is a structure with two fields called the head and
the tail.  Streams are created by \ide{cons-stream}.  The head and
tail are accessed using the procedures \ide{head} and
\ide{tail}.  Streams are used for representing sequences of elements,
which are retrieved as the heads of successive tails of the stream.
In this way, a stream is like a list.  The difference is that the
items in the stream are {\em delayed}, that is, they are computed when
they are accessed rather than when the stream is constructed.  The
empty stream\mainindex{empty stream} is stream that has no elements.
See chapter 3 of~\cite{SICP} for information on programming with
streams.

\begin{entry}{%
\proto{cons-stream}{ \vari{obj} \varii{obj}}{\exprtype}}

Returns a stream whose head is \vari{obj} and whose tail is
\varii{obj}.  \ide{Cons-stream} is syntax rather than a procedure
because it does not evaluate its second argument.
\end{entry}

\begin{entry}{%
\proto{head}{ \var{stream}}{procedure}}

Returns the head of the given \var{stream}.
\end{entry}


\begin{entry}{%
\proto{tail}{ \var{stream}}{procedure}}

Returns the tail of the given \var{stream}.
\end{entry}

\begin{entry}{%
\vproto{the-empty-stream}{variable}}

A variable initially bound to the empty stream.
\end{entry}

\begin{entry}{%
\proto{empty-stream?}{ \var{obj}}{procedure}}

Returns \schtrue{ } or \schfalse{ } depending on whether \var{obj} is
the empty steam.
\end{entry}

\begin{entry}{%
\proto{delay}{ \hyper{expression}}{\exprtype}}

The \ide{delay} construct, together with the procedure \ide{force},
implement \defining{lazy evaluation} or \defining{call by need}.
{\tt(delay \hyper{expression})} returns an object called a
\defining{promise} which at some point in the future may be asked (by
the \ide{force} procedure) to evaluate
\hyper{expression} and deliver the resulting value.

\end{entry}


\begin{entry}{%
\proto{force}{ promise}{procedure}}

Forces the value of \var{promise} (see \ide{delay}
above).\index{promise} 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.

\begin{scheme}
(force (delay (+ 1 2)))   \ev  3
(let ((p (delay (+ 1 2))))
  (list (force p) (force p)))  
                               \ev  (3 3)

(define a-stream
  (letrec ((next
            (lambda (n)
              (cons n (delay (next (+ n 1)))))))
    (next 0)))
(define head car)
(define tail
  (lambda (stream) (force (cdr stream))))

(head (tail (tail a-stream)))  
                               \ev  2%
\end{scheme}

\ide{Force} and \ide{delay} are mainly intended for programs written
using streams.  The following examples should not be considered to
illustrate good programming style, but they illustrate the property that
the value of a promise is computed at most once.

\begin{scheme}
(define count 0)
(define p (delay (begin (set! count (+ count 1))
                        (* x 3))))
(define x 5)
count      \ev  0
p          \ev  {\it{}a promise}
(force p)  \ev  15
p          \ev  {\it{}a promise, still}
count      \ev  1
(force p)  \ev  15
count      \ev  1%
\end{scheme}

\end{entry}



\section{Input and output}

\subsection{Ports}
\label{portsection}

Ports represent input and output devices.  To Scheme, an input device is a
Scheme object that can deliver characters upon command, while an output device
is a Scheme object that can accept characters.

\begin{entry}{%
\vproto{console-input-port}{variable}
\vproto{console-output-port}{variable}}

These variables are initially bound to the ports for input and output
to the console.
\end{entry}


\begin{entry}{%
\proto{open-input-file}{ filename}{procedure}}
 
Takes a string naming an existing file and returns an input port capable of
delivering characters from the file.  If the file cannot be opened, an error is
signalled.

\end{entry}


\begin{entry}{%
\proto{open-output-file}{ filename}{procedure}}

Takes a string naming an output file to be created and returns an output
port capable of writing characters to a new file by that name.  If the file
cannot be opened, an error is signalled.

\end{entry}


\begin{entry}{%
\proto{close-input-port}{ port}{procedure}
\proto{close-output-port}{ port}{procedure}}

Closes the file associated with \var{port}, rendering the \var{port}
incapable of delivering or accepting characters.  \todo{But maybe a no-op
on some ports, e.g. terminals or editor buffers.}
These routines have no effect if the file has already been closed.
The value returned is unspecified.

\end{entry}



\begin{entry}{%
\proto{call-with-input-file}{ string proc}{procedure}
\proto{call-with-output-file}{ string proc}{procedure}}

\domain{\var{Proc} should be a procedure of one argument, and
\var{string} should be a string naming a file.  For
\ide{call-with-input-file}, the file must already exist; for
\ide{call-with-output-file}, the effect is unspecified if the file
already exists.} These procedures call \var{proc} with one argument: 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 yielded by the
procedure is returned.  
\end{entry}


\begin{entry}{%
\proto{input-port?}{ obj}{procedure}
\proto{output-port?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is an input port or output port
respectively, otherwise returns \schfalse.

\todo{Won't necessarily return true after port is closed.}

\end{entry}


\begin{entry}{%
\proto{current-input-port}{}{procedure}
\proto{current-output-port}{}{procedure}}
 
Returns the current default input or output port.

\end{entry}


\begin{entry}{%
\proto{with-input-from-file}{ string thunk}{procedure}
\proto{with-output-to-file}{ string thunk}{procedure}}

\domain{\var{Thunk} must be a procedure of no arguments, and
\var{string} must be a string naming a file.  For
\ide{with-input-from-file}, the file must already exist; for
\ide{with-output-to-file}, the effect is unspecified if the file already
exists.} The file is opened for input or output, an input or output port
connected to it is made the default value returned by
\ide{current-input-port} or \ide{current-output-port}, and the
\var{thunk} is called with no arguments.  When the \var{thunk} returns,
the port is closed and the previous default is restored.
\ide{With-input-from-file} and \ide{with-output-to-file} return the
value yielded by \var{thunk}.
Furthermore, when these procedures return, they close the
default port and restore the previous default.
\end{entry}


\subsection{Input}
\label{inputsection}

\noindent \hbox{ }  %???
\vspace{-5ex}
\todo{The input routines have some things in common, maybe explain here.}

\begin{entry}{%
\proto{read}{}{procedure}
\proto{read}{ port}{procedure}}

\ide{Read} returns the next
object parsable from the given input \var{port}, updating \var{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 characters are found that can begin an object, then
an end of file object is returned.  The port remains open, and
further 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 representation is incomplete
and therefore not parsable, an error is signalled.

The \var{port} argument may be omitted, in which case it defaults to the
value returned by \ide{current-input-port}.  It is an error to read from
a closed port.
\end{entry}

\begin{entry}{%
\proto{read-char}{}{procedure}
\proto{read-char}{ port}{procedure}}

Returns the next character available from the input \var{port}, updating
the \var{port} to point to the following character.  If no more characters
are available, an end of file object is returned.  \var{Port} may be
omitted, in which case it defaults to the value returned by \ide{current-input-port}.

\end{entry}

\begin{entry}{%
\proto{load}{ filename}{procedure}}

\var{Filename} should be a string naming an existing file
containing Scheme code. The \ide{load} procedure reads
expressions and definitions from the file and evaluates them
sequentially.  The \ide{load} procedure does not affect the values
returned by \ide{current-input-port} and \ide{current-output-port}.
\ide{Load} returns an unspecified value.
\end{entry}


\begin{entry}{%
\proto{char-ready?}{}{procedure}
\proto{char-ready?}{ port}{procedure}}

Returns \schtrue{} if a character is ready on the input \var{port} and
returns \schfalse{} otherwise.  If \ide{char-ready} returns \schtrue{} then
the next \ide{read-char} operation on the given \var{port} is guaranteed
not to hang.  If the \var{port} is at end of file then \ide{char-ready?}\
returns \schtrue.  \var{Port} may be omitted, in which case it defaults to
the value returned by \ide{current-input-port}.
\ide{Char-ready?}\ exists to make it possible for a program to
accept characters from interactive ports without getting stuck waiting for
input.
\end{entry}


\begin{entry}{%
\proto{eof-object?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is an end of file object, otherwise returns
\schfalse.

\end{entry}


\subsection{Output}
\label{outputsection}

% We've got to put something here to fix the indentation!!
\noindent \hbox{}
\vspace{-5ex}

\begin{entry}{%
\proto{write}{ obj}{procedure}
\proto{write}{ obj port}{procedure}}

Writes a representation of \var{obj} to the given \var{port}.  Strings that
appear in the written representation are enclosed in doublequotes, and
within those strings backslash and doublequote characters are
escaped by backslashes.  \ide{Write} returns an unspecified value.  The
\var{port} argument may be omitted, in which case it defaults to the value
returned by \ide{current-output-port}.

\end{entry}


\begin{entry}{%
\proto{display}{ obj}{procedure}
\proto{display}{ obj port}{procedure}}

Writes a representation of \var{obj} to the given \var{port}.  Strings
that appear in the written representation are not enclosed in
doublequotes, and no characters are escaped within those strings.  In
those implementations that have a distinct character type, character
objects in the representation appear as if written by \ide{write-char}.
\ide{Display} returns an unspecified value.  The \var{port} argument may
be omitted, in which case it defaults to the value returned by
\ide{current-output-port}.

\begin{rationale}
\ide{Write} is intended
for producing mach\-ine-readable output and \ide{display} is for producing
human-readable output.
\end{rationale}
\end{entry}

\begin{entry}{%
\proto{pp}{ obj}{procedure}}

\mainindex{pretty print}
``Pretty prints'' \var{obj} to the current output port.  That is,
\ide{pp} displays \var{obj} formatted so as to clearly show its
structure.  For example, if \var{obj} is a long list, then the
displayed representation will be broken over a number of lines and
indented.  If \var{obj} is a procedure then the text of \var{obj} will
displayed.
\end{entry}

\begin{entry}{%
\proto{newline}{}{procedure}
\proto{newline}{ port}{procedure}}

Writes an end of line to \var{port}.  Exactly how this is done differs
from one operating system to another.  Returns an unspecified value.
The \var{port} argument may be omitted, in which case it defaults to the
value returned by \ide{current-output-port}.

\end{entry}


\begin{entry}{%
\proto{write-char}{ char}{procedure}
\proto{write-char}{ char port}{procedure}}

Writes the character \var{char} (not a written representation of the
character) to the given \var{port} and returns an unspecified value.  The
\var{port} argument may be omitted, in which case it defaults to the value
returned by \ide{current-output-port}.

\end{entry}

\begin{entry}{%
\proto{transcript-on}{ filename}{procedure}\nopagebreak{}
\proto{transcript-off}{}{procedure}}

\domain{\var{Filename} must be a string naming an output file to be
created.} The effect of \ide{transcript-on} is to open the named file
for output, and to cause a transcript of subsequent interaction between
the user and the Scheme system to be written to the file.  The
transcript is ended by a call to \ide{transcript-off}, which closes the
transcript file.  Only one transcript may be in progress at any time.
The values
returned by these procedures are unspecified.
\end{entry}

\section{Environments and evaluation}

An \defining{environment} is the set of bindings for variables that is
in effect at some point in a program.  (See
section~\ref{variablesection}.)  Environments in Scheme are
first-class objects.  That is, they may be named by variables, passed
as arguments to procedures, and returned as the values of procedures.
Scheme includes operations for capturing the environment in effect at
any point and for specifying that an expression should be evaluated
relative to a particular environment.

\begin{entry}{%
\proto{eval}{ exp env}{procedure}}

Returns the result of evaluating \var{exp} in the environment
\var{env}.
\end{entry}

\begin{entry}{%
\proto{the-environment}{}{\exprtype}}

Evaluating the form \ide{the-environment} returns the environment in
which the form is evaluated.

\begin{note}
Scheme's static-scoping semantics imply that \ide{the-environment} is
not a procedure.
\end{note}
\end{entry}

\begin{entry}{%
\proto{environment?}{ obj}{procedure}}

Returns \schtrue{} or \schfalse{} depending on whether \var{obj} is an
environment.
\end{entry}


\begin{entry}{%
\proto{make-environment}{ \vari{exp} \varii{exp} \dotsfoo}{\exprtype}}

\ide{Make-environment} constructs a new environment that is contained
in the environment in which this form is evaluated.  The expressions
\vari{exp}, \varii{exp}, \dotsfoo are evaluated sequentially in this
new environment, and the environment is returned.  The \var{exp$_i$}
are typically \ide{define} expressions.  A \ide{make-environment}
form is alternate syntax for
\begin{scheme}
(let () \vari{exp} \varii{exp} \dotsfoo (the-environment))
\end{scheme}
\end{entry}

\begin{entry}{%
\vproto{user-initial-environment}{variable}}

A variable that is initially bound to the environment in which
expressions entered from the console are evaluated when Scheme is
first run.
\end{entry}

\section{Errors, breakpoints, and debugging}
\label{errorcommands}

When Scheme encounters an error, it enters an {\em error
read-eval-print loop}
\index{error read-eval-print loop} which accepts expressions to be
evaluated in the environment of the error.  One error level can be
nested inside another and the user can move between error levels, or
return to the top level.  {\em Breakpoints}, which are similar to
error breaks, can also be triggered by executing {\tt bkpt}
expressions.  There are also special subsystems called {\tt debug} and
{\tt where} to aid in debugging.  This section lists Scheme's
debugging commands, but refer to chapter~\ref{errorsystem} for a more
extended description of errors and breakpoints.

\begin{entry}{%
\proto{error}{ \vari{exp} \varii{exp} \dotsfoo}{\exprtype}}

Signals an error.  Displays all the expressions and creates a
debugging breakpoint.  See section~\ref{errorrep}.
\end{entry}

\begin{entry}{%
\proto{bkpt}{ \var{message} \var{object}}{\exprtype}}

Sets a breakpoint .  Displays \var{message} and \var{object} and
enters a breakpoint read-eval-print loop in the current environment.
To proceed from a breakpoint, use the {\tt proceed} procedure.
See section~\ref{errorrep}.
\end{entry}

\begin{entry}{%
\proto{proceed}{}{procedure}}

Continues evaluation that was interrupted by a breakpoint.
See section~\ref{errorrep}.
\end{entry}

\begin{entry}{%
\proto{debug}{}{procedure}}

Enters the history examination system, which allows the user to
examine the history of the execution of an expression by issuing
one-letter commands.  See
section~\ref{debugsection}.

\end{entry}


\begin{entry}{%
\proto{where}{}{procedure}
\proto{where}{ \var{procedure}}{procedure}}

Enters the environment examination system, which allows the user to
examine and modify variables and bindings by issuing one-letter commands.
With no argument, the environment examined is the one in which {\tt
where} was evaluated.  If \var{procedure} is supplied as an argument,
then the environment examined is the one in which \var{procedure} was
defined. See section~\ref{wheresection}.

\end{entry}

\begin{entry}{%
\proto{trace-entry}{ procedure}{procedure}
\proto{trace-exit}{ procedure}{procedure}
\proto{trace-both}{ procedure}{procedure}
\proto{trace}{ procedure}{procedure}}

{\tt Trace-entry} causes Scheme to
display a message whenever \var{procedure} is entered.  {\tt
Trace-exit} displays a message whenever \var{procedure} returns.  {\tt
Trace-both} performs both {\tt trace-entry} and {\tt trace-exit}.
{\tt Trace} is the same as {\tt trace-entry}.  See section~\ref{trace}
for examples of tracing procedures.
\end{entry}

\begin{entry}{%
\proto{break-entry}{ procedure}{procedure}
\proto{break-exit}{ procedure}{procedure}
\proto{break-both}{ procedure}{procedure}
\proto{break}{ procedure}{procedure}}

{\tt Break-entry} causes Scheme to enter a breakpoint
whenever \var{procedure} is entered.  {\tt
Break-exit} enters a breakpoint \var{procedure} returns.  {\tt
Break-both} performs both {\tt break-entry} and {\tt break-exit}.
{\tt Break} is the same as {\tt break-entry}.  See section~\ref{break}
for examples of setting breakpoints on procedures.
\end{entry}

\begin{entry}{%
\proto{*proc*}{}{procedure}
\proto{*result*}{}{procedure}
\proto{*args*}{}{procedure}}

These three procedures are used only at a breakpoint.  \ide{*Proc*}
returns the ``broken'' procedure, \ide{*args*} returns a list of the
arguments supplied to the ``broken'' procedure, and \ide{*result*}
returns the result about to be returned by the "broken" procedure.
\ide{*Result*} is used only at exit breaks.  See section~\ref{break} for
examples of how these are used.
\end{entry}

\begin{entry}{%
\proto{untrace}{ }{procedure}
\proto{untrace}{ \var{procedure}}{procedure}}

Removes any breakpoints and trace messages set for \var{procedure}.
With no argument, removes traces and breakpoints for all procedures.
\end{entry}

\section{Miscellaneous}

% We've got to put something here to fix the indentation!!
\noindent \hbox{}
\vspace{-5ex}

\begin{entry}{%
\proto{procedure?}{ obj}{procedure}}

Returns \schtrue{} if \var{obj} is a procedure, otherwise returns \schfalse.

\begin{scheme}
(procedure? car)            \ev  \schtrue
(procedure? 'car)           \ev  \schfalse
(procedure? (lambda (x) (* x x)))   
                            \ev  \schtrue
(procedure? '(lambda (x) (* x x)))  
                            \ev  \schfalse
\end{scheme}

\end{entry}

\begin{entry}{%
\proto{runtime}{}{procedure}}

Returns the amount of time (in milliseconds) that the system has been
running.
\end{entry}

\begin{entry}{%
\proto{object-type}{ obj}{procedure}}

Returns the primitive datatype of the object \var{obj}.  The
following are the datatypes that would be encountered in user code:
\ide{character}, \ide{string}, \ide{interned-symbol},
\ide{uninterned-symbol}, \ide{environment}, \ide{pair}, \ide{vector},
\ide{number}, \ide{procedure}, \ide{primitive-procedure}, \ide{true},
\ide{null}, \ide{delayed}.
\end{entry}

\begin{entry}{%
\proto{enable-language-features}{}{procedure}}

The Scheme system includes many more built-in procedures than are
documented in this manual.  Most of these are of value for system
programming only.  When Scheme is initially loaded, only the
procedures in this manual are accessible from the initial user
environment.  Evaluating \ide{enable-language-features} makes the
additional procedures accessible.
\end{entry}
