% Initial environment

%\vfill\eject
\chapter{Standard procedures}
\label{initialenv}
\label{builtinchapter}

\mainindex{initial environment}
\mainindex{top level environment}

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 useful values, most of which are primitive
procedures that manipulate data.  For example, the variable \ide{abs} is
bound to (a location initially containing) a procedure of one argument
that computes the absolute value of a number, and the variable \ide{+}
is bound to a procedure that computes sums.


\section{Booleans}
\label{booleansection}

The standard boolean objects for true and false are written as
\schtrue{} and \schfalse.\sharpindex{t}\sharpindex{f}  What really
matters, though, are the objects that the Scheme conditional expressions
(\ide{if}, \ide{cond}, \ide{and}, \ide{or}, \ide{do}) 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 The empty list counts as false for compatibility with existing programs
and implementations that assume this to be the case.

\vest Programmers accustomed to other dialects of Lisp should beware that
Scheme distinguishes false and the empty list from the symbol \ide{nil}.

\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}{%
\proto{not}{ obj}{essential procedure}}

\ide{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{boolean?}{ obj}{essential procedure}}

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

\begin{scheme}
(boolean? \schfalse)  \ev  \schtrue
(boolean? 0)          \ev  \schfalse%
\end{scheme}

\end{entry}


\begin{entry}{%
\vproto{nil}{variable}
\vproto{t}{variable}}

Some implementations provide variables \ide{nil} and \ide{t} whose
values in the initial environment are \schfalse{} and \schtrue{}
respectively.

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

\end{entry}

 
\section{Equivalence predicates}
\label{equivalencesection}

A \defining{predicate} is a procedure that always returns a boolean
value (\schtrue{} or \schfalse).  An \defining{equivalence predicate} is
the computational analogue of a mathematical equivalence relation (it is
symmetric, reflexive, and transitive).  Of the equivalence predicates
described in this section, \ide{eq?}\ is the finest or most
discriminating, and \ide{equal?}\ is the coarsest.  \ide{Eqv?}\ is
slightly less discriminating than \ide{eq?}.  \todo{Pitman doesn't like
this paragraph.  Lift the discussion from the Maclisp manual.  Explain
why there's more than one predicate.}

\vest Two objects are \defining{operationally equivalent} if and only if
there is no way that they can be distinguished, using Scheme primitives
other than \ide{eqv?} or \ide{eq?} or those like \ide{memq} and
\ide{assv} whose meaning is defined explicitly in terms of \ide{eqv?} or
\ide{eq?}.  It is guaranteed that objects maintain their operational
identity despite being named by variables or fetched from or stored into
data structures.

\vest This definition can be interpreted in the following ways for various
kinds of objects:

\begin{itemize}
\item The two boolean values, \schtrue{} and
\schfalse{}, are operationally distinct because they behave in
opposite ways in conditionals.

\item Two symbols are operationally equivalent if they print
the same way.

\item Two numbers are operationally equivalent if they are numerically
equal (see \ide{=}, section~\ref{=}) and are either both exact or both
inexact (see section~\ref{exactly}).

\item Two characters are operationally equivalent if they are the same
character according to \ide{char=?} (section~\ref{char=?}).

\item Two structured mutable objects---pairs, vectors, or strings---are
operationally equivalent if they have operationally equivalent values in
corresponding positions, and applying a mutation procedure to one causes
the other to change as well.  (A mutation procedure is one like
\ide{set-car!} which alters a data structure.)\index{mutation
procedure} For example, two pairs are not operationally equivalent if a
\ide{set-car!}\ operation on one does not change the car field of the
other.

\item There is only one empty list\index{empty list}, and it is
operationally equivalent to itself.  All empty vectors are operationally
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.

\item Two procedures are operationally equivalent if, when called on
operationally equivalent arguments, they return the same value and
perform the same side effects.

\end{itemize}


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

The \ide{eqv?} procedure implements an approximation to the relation of
operational equivalence.
It returns \schtrue{} if it can prove that \vari{obj} and \varii{obj}
are operationally equivalent.  If it can't, it always errs on the
conservative side and returns \schfalse.

The only situation in which it might fail to prove is when \vari{obj}
and \varii{obj} are operationally equivalent procedures that were
created at different times.  In general, operational equivalence of
procedures is uncomputable, but it is guaranteed that \ide{eqv?}\ can
recognize a procedure created at a given time by a given \lambdaexp{} as
``being itself.''  This is useful for applications in which procedures
are being used to implement objects with local state.

\begin{scheme}
(eqv? 'a 'a)                     \ev  \schtrue
(eqv? 'a 'b)                     \ev  \schfalse
(eqv? 2 2)                       \ev  \schtrue
(eqv? '() '())                   \ev  \schtrue
(eqv? "" "")                     \ev  \schtrue
(eqv? 100000000 100000000)       \ev  \schtrue
(eqv? (cons 1 2) (cons 1 2))     \ev  \schfalse
(eqv? (lambda () 1)
      (lambda () 2))             \ev  \schfalse
(eqv? \#f 'nil)                  \ev  \schfalse
(let ((p (lambda (x) x)))
  (eqv? p p))		         \ev  \schtrue%
\end{scheme}

The following examples illustrate cases in which \ide{eqv?}\ is
permitted to fail to prove operational equivalence, depending on the
implementation.  (In every case, it will return either \schtrue{} or
\schfalse{}, but which one it returns is implementation-dependent.)
Compare with the last example in the previous set.

\begin{scheme}
(eqv? (lambda (x) x)
      (lambda (x) x))    \ev  \unspecified
(eqv? (lambda (x) x)
      (lambda (y) y))    \ev  \unspecified%
\end{scheme}

The next set of examples shows the use of \ide{eqv?}\ with procedures
that have local state.  \ide{Gen-counter} must return a distinct
procedure every time, since each procedure has its own internal counter.
\ide{Gen-loser}, however, returns equivalent procedures each time, since
the local state does not affect the value or side effects of the
procedures.

\begin{scheme}
(define gen-counter
  (lambda ()
    (let ((n 0))
      (lambda () (set! n (+ n 1)) n))))
(let ((g (gen-counter)))
  (eqv? g g))           \ev  \schtrue
(eqv? (gen-counter) (gen-counter))
                        \ev  \schfalse
(define gen-loser
  (lambda ()
    (let ((n 0))
      (lambda () (set! n (+ n 1)) 27))))
(let ((g (gen-loser)))
  (eqv? g g))           \ev  \schtrue
(eqv? (gen-loser) (gen-loser))
                        \ev  \unspecified%
\end{scheme}

Objects of distinct types are never operationally equivalent, except
that false and the empty list\index{empty list} are permitted to be identical, and the
character type need not be disjoint from other types.

\begin{scheme}
(eqv? '() \schfalse)    \ev  \unspecified
(eqv? 57 \#\backwhack{}A)  \ev  \unspecified%
\end{scheme}

Since it is an error to modify constant objects (those returned by
literal expressions), implementations are permitted, though not
required, to share structure between constants where appropriate.  Thus
the value of \ide{eqv?} on constants is sometimes
implementation-dependent.

\begin{scheme}
(let ((x '(a)))
  (eqv? x x))                    \ev  \schtrue
(eqv? '(a) '(a))                 \ev  \unspecified
(eqv? "a" "a")                   \ev  \unspecified
(eqv? '(b) (cdr '(a b)))	 \ev  \unspecified%
\end{scheme}

\begin{note} 
The above definition of \ide{eqv?} allows implementations latitude in
their treatment of procedures and literals:  implementations are free
to either detect or fail to detect that two procedures or two literals
are operationally 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.
\end{note}

\end{entry}


\begin{entry}{%
\proto{eq?}{ \vari{obj} \varii{obj}}{essential 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?}.

\vest \ide{Eq?}\ and \ide{eqv?}\ are guaranteed to have the same
behavior on symbols, booleans, the empty list, pairs, and non-empty
strings and vectors.  \ide{Eq?}'s behavior on numbers and characters is
implementation-dependent, but it will always return either true or
false, and will return true only when \ide{eqv?}\ would also return
true.  \ide{Eq?} may also behave differently from \ide{eqv?} on empty
vectors and empty strings.

\begin{scheme}
(eq? 'a 'a)                     \ev  \schtrue
(eq? '(a) '(a))                 \ev  \unspecified
(eq? (list 'a) (list '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
(eq? car car)                   \ev  \schtrue
(let ((n (+ 2 3)))
  (eq? n n))      \ev  \unspecified
(let ((x '(a)))
  (eq? x x))      \ev  \schtrue
(let ((x '\#()))
  (eq? x x))      \ev  \schtrue
(let ((p (lambda (x) x)))
  (eq? p p))      \ev  \schtrue%
\end{scheme}

\todo{Needs to be explained better above.  How can this be made to be
not confusing?  A table maybe?}

\begin{note} It will usually be possible to implement \ide{eq?}\ much
more efficiently than \ide{eqv?}, for example, as a simple pointer
comparison instead of as some more complicated operation.  One reason is
that it may not be possible to compute \ide{eqv?}\ of two numbers in
constant time, whereas \ide{eq?}\ implemented as pointer comparison will
always finish in constant time.  \ide{Eq?}\ may be used like \ide{eqv?}\
in applications using procedures to implement objects with state since
it obeys the same constraints as \ide{eqv?}.  \end{note}

\end{entry}


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

\ide{Equal?} recursively compares the contents of pairs, vectors, and
strings, applying \ide{eqv?} on other objects such as numbers and symbols.
A rule of thumb is that objects are generally \ide{equal?} if they print
the same.  \ide{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}


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

A \defining{pair} (sometimes called a \defining{dotted pair}) is a
record 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 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 the same 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}

It is often convenient to speak of a homogeneous list of objects
of some particular data type, as for example \hbox{\cf (1 2 3)} is a list of
integers.  To be more precise, suppose \var{D} is some data type.  (Any
predicate defines a data type consisting of those objects of which the
predicate is true.)  Then

\begin{itemize}
\item The empty list is a list of \var{D}.
\item If \var{list} is a list of \var{D}, then any pair whose cdr is
      \var{list} and whose car is an element of the data type \var{D} is also a
      list of \var{D}.
\item There are no other lists of \var{D}.
\end{itemize}

Within literal expressions and representations of objects read by the
\ide{read} procedure, the forms \singlequote\hyper{datum}\schindex{'},
\backquote\hyper{datum}, {\tt,}\hyper{datum}\schindex{,}, and
{\tt,@}\hyper{datum} denote two-ele\-ment lists whose first elements are
the symbols \ide{quote}, \ide{quasiquote}, \hbox{\ide{unquote}}, and
\ide{unquote-splicing}, respectively.  The second element in each case
is \hyper{datum}.  This convention is supported so that arbitrary Scheme
programs may be represented as lists.  \todo{Can or need this be stated
more carefully?} That is, according to Scheme's grammar, every
\meta{expression} is also a \meta{datum} (see section~\ref{datum}).
Among other things, this permits the use of the \ide{read} procedure to
parse Scheme programs.  See section~\ref{externalreps}. 
 

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

\ide{Pair?} returns \schtrue{} if \var{obj} is a pair, and 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}}{essential 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{car}{ pair}{essential 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}{essential 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}{essential 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.  % <!>
%This procedure can be very confusing if used indiscriminately.

\end{entry}


\begin{entry}{%
\proto{set-cdr!}{ pair obj}{essential 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{essential procedure}


\begin{entry}{%
\proto{caar}{ pair}{essential procedure}
\proto{cadr}{ pair}{essential procedure}
\pproto{\hbox to 1\wd0 {\hfil$\vdots$\hfil}}{\hbox to 1\wd1 {\hfil$\vdots$\hfil}}
\proto{cdddar}{ pair}{essential procedure}
\proto{cddddr}{ pair}{essential 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}{essential procedure}}

Returns \schtrue{} if \var{obj} is the empty list\index{empty list},
otherwise returns \schfalse.  (In implementations in which the empty
list is the same as \schfalse{}, \ide{null?} will return \schtrue{}
if \var{obj} is \schfalse{}.) 
 
\end{entry}


\begin{entry}{%
\proto{list}{ \var{obj} \dotsfoo}{essential 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}{essential 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}}{essential 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}.
\ide{Last-pair} 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}{essential procedure}
\proto{memv}{ obj list}{essential procedure}
\proto{member}{ obj list}{essential procedure}}

%Finds the first occurrence of \var{obj} in the list \var{list} and
These procedures return the first sublist of \var{list} whose car is
\var{obj}.  If \var{obj} does not occur in \var{list}, \schfalse{}
(n.b.:~not the empty list) is returned.  \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}{essential procedure}
\proto{assv}{ obj alist}{essential procedure}
\proto{assoc}{ obj alist}{essential procedure}}

\domain{\var{Alist} (for ``association list'') must be a list of
pairs.}  These procedures find 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, \schfalse{} is returned.  \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
(assoc (list 'a) '(((a)) ((b)) ((c))))   
                           \ev  ((a))
(assq 5 '((2 3) (5 7) (11 13)))    
                           \ev  \unspecified
(assv 5 '((2 3) (5 7) (11 13)))    
                           \ev  (5 7)%
\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.  This is exactly the property needed to
represent identifiers\index{identifier} in programs, and so most
implementations of Scheme use them internally for that purpose.  Symbols
are useful for many other applications; for instance, they may be used
the way enumerated values are used in Pascal.

\vest The rules for writing a symbol are exactly the same as the rules for
writing an identifier; see sections~\ref{syntaxsection}
and~\ref{identifiersyntax}.

\vest It is guaranteed that any symbol that has been returned as part of
a literal expression, or read using the \ide{read} procedure, and
subsequently written out using the \ide{write} procedure, will read back
in as the identical symbol (in the sense of \ide{eqv?}).  The
\ide{string\coerce{}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.

\begin{note}
Some implementations of Scheme have a feature known as ``slashification''
in order to guarantee write/read invariance for all symbols, but
historically the most important use of this feature has been to
compensate for the lack of a string data type.

\vest 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 are the same
if and only if their names are spelled the same.
\end{note}


\begin{entry}{%
\proto{symbol?}{ obj}{essential 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{symbol->string}{ symbol}{essential procedure}}

Returns the name of \var{symbol} as a string.  If the symbol was part of
an object returned as the value of a literal expression
(section~\ref{literalsection}) or by a call to the \ide{read} procedure,
and its name contains alphabetic characters, then the string returned
will contain characters in the implementation's preferred standard
case---some implementations will prefer upper case, others lower case.
If the symbol was returned by \ide{string\coerce{}symbol}, the case of
characters in the string returned will be the same as the case in the
string that was passed to \ide{string\coerce{}symbol}.  It is an error
to apply mutation procedures like \ide{string-set!} to strings returned
by this procedure.

The following examples assume that the implementation's standard case is
lower case:

\begin{scheme}
(symbol->string 'flying-fish)     
                                  \ev  "flying-fish"
(symbol->string 'Martin)          \ev  "martin"
(symbol->string
   (string->symbol "Malvina"))     
                                  \ev  "Malvina"%
\end{scheme}
\end{entry}


\begin{entry}{%
\proto{string->symbol}{ string}{essential procedure}}

Returns the symbol whose name is \var{string}.  This procedure can
create symbols with names containing special characters or letters in
the non-standard case, but it is usually a bad idea to create such
symbols because in some implementations of Scheme they cannot be read as
themselves.  See \ide{symbol\coerce{}string}.

The following examples assume that the implementation's standard case is
lower case:

\begin{scheme}
(eq? 'mISSISSIppi 'mississippi)  \lev  \schtrue
(string->symbol "mISSISSIppi")  \lev%
  {\rm{}the symbol with name} "mISSISSIppi"
(eq? 'bitBlt (string->symbol "bitBlt"))     \lev  \schfalse
(eq? 'JollyWog
     (string->symbol
       (symbol->string 'JollyWog)))  \lev  \schtrue
(string=? "K. Harper, M.D."
          (symbol->string
            (string->symbol "K. Harper, M.D.")))  \lev  \schtrue%
\end{scheme}

\end{entry}


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

Numerical computation has traditionally been neglected by the Lisp
community.  Until Common Lisp there has been no carefully thought out
strategy for organizing numerical computation, and with the exception of
the MacLisp system \cite{Pitman83} there has been little effort to
execute numerical code efficiently.  We applaud the excellent work of
the Common Lisp committee and we accept many of their recommendations.
In some ways we simplify and generalize their proposals in a manner
consistent with the purposes of Scheme.

\vest Scheme's numerical operations treat numbers as abstract data, as
independent of their representation as is possible.  Thus, the casual user
should be able to write simple programs without having to know that the
implementation may use fixed-point, floating-point, and perhaps other
representations for his data.  Unfortunately, this illusion of uniformity
can be sustained only approximately---the implementation of numbers will
leak out of its abstraction whenever the user must be in control of
precision, or accuracy, or when he must construct especially efficient
computations.  Thus the language must also provide escape mechanisms so
that a sophisticated programmer can exercise more control over the
execution of his code and the representation of his data when necessary.

\newcommand{\type}[1]{{\tt#1}}

\vest It is important to distinguish between the abstract numbers, their
machine representations, and their written representations.  We will use
mathematical terms \type{number}, \type{complex}, \type{real},
\type{rational}, and \type{integer} for properties of the abstract
numbers, the names \type{fixnum}, \type{bignum}, \type{ratnum}, and
\type{flonum} for machine representations, and the names
\type{int}, \type{fix}, \type{flo}, \type{sci}, \type{rat},
\type{polar}, and \type{rect} for input/output formats. 

\todo{Bartley says it's confusing to use the same typeface for these as
for Scheme identifiers.}

 
\subsection{Numbers}

A Scheme system provides data of type \type{number}, which is the most
general numerical type supported by that system.  \type{Number} is likely
to be a complicated union type implemented in terms of \type{fixnum}s,
\type{bignum}s, \type{flonum}s, and so forth, but this should not be
apparent to a naive user.  What the user should see is that the 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
implementation is good enough, he should get an exact 3.

\vest Mathematically, numbers may be arranged into a tower of subtypes with 
projections and injections relating adjacent levels of the tower:

$$\begin{tabular}{l}
\type{number} \\
\type{complex} \\
\type{real} \\
\type{rational} \\
\type{integer} 
\end{tabular} $$

\todo{I don't like this}
We impose a uniform rule of downward coercion---a number 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.

\vest Not all implementations of Scheme must provide the whole tower,
but they must implement a coherent subset consistent with both the
purposes of the implementation and the spirit of the Scheme language. 
 
 
\subsection{Exactness}

\mainindex{exactness} \label{exactly}
Numbers are either \type{exact} or \type{inexact}.  A number is
\type{exact} if it was derived from \type{exact} numbers using only
\type{exact} operations.  A number is \type{inexact} if it models a
quantity (e.g., a measurement) known only approximately, if it was
derived using \type{inexact} ingredients, or if it was derived using
\type{inexact} operations.
Thus \type{inexact}ness is a contagious property of a number.  Some
operations, such as the square root (of non-square numbers), must be
\type{inexact} because of the finite precision of our representations.
\todo{This is obviously wrong, or else there is a big chain of reasoning
involved.  Fix.}
Other operations are inexact because of implementation requirements.  We
emphasize that exactness is independent of the position of the number on
the tower.  It is perfectly possible to have an \type{inexact}
\type{integer} or an \type{exact} \type{real}; 355/113 may be an
\type{exact} \type{rational} or it may be an \type{inexact}
\type{rational} approximation to pi, depending on the application.

\vest Operationally, it is the system's responsibility to combine \type{exact}
numbers using exact methods, such as infinite precision integer and
rational arithmetic, where possible.  An implementation may not be able to
do this (if it does not use infinite precision integers and rationals), but
if a number becomes \type{inexact} for implementation reasons there is
likely to be an important error condition, such as integer overflow, to be
reported.  Arithmetic on \type{inexact} numbers is not so constrained.  The
system may use floating point and other ill-behaved representation
strategies for \type{inexact} numbers.  This is not to say that
implementors need not use the best known algorithms for \type{inexact}
computations---only that approximate methods of high quality are allowed.
In a system that cannot explicitly distinguish exact from \type{inexact}
numbers the system must do its best to maintain precision.  Scheme systems
must not burden users with numerical operations described in terms of
hardware and operating-system dependent representations such as
\type{fixnum} and \type{flonum}, however, because these representation
issues are hardly ever germane to the user's problems.

\vest We highly recommend that the IEEE 32-bit and 64-bit floating-point
standards be adopted for implementations that use floating-point
representations internally.  To minimize loss of precision we adopt the
following rules: If an implementation uses several different sizes of
floating-point formats, the results of any operation with a floating-point
result must be expressed in the largest format used to express any of the
floating-point arguments to that operation.  It is desirable (but not
required) for potentially irrational operations such as \ide{sqrt}, when
applied to \type{exact} arguments, to produce \type{exact} answers whenever
possible (for example the square root of an exact 4 ought to be an exact
2).  If an \type{exact} number (or an \type{inexact} number represented as
a \type{fixnum}, a \type{bignum}, or a \type{ratnum}) is operated upon so
as to produce an \type{inexact} result (as by \ide{sqrt}), and if the
result is represented as a \type{flonum}, then the largest available
\type{flonum} format must be used; but if the result is expressed as a
\type{ratnum} then the rational approximation must have at least as much
precision as the largest available \type{flonum}.


\subsection{Number syntax}
\label{numbernotations}

%@@@@LOSE@@@@

Scheme allows the traditional ways of writing numerical constants,
though any particular implementation may support 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 approximate form of expression may be just what
the user wants to see.

The syntax of numbers is described formally in
section~\ref{numbersyntax}.  See section~\ref{numberformats} for
many examples of representations of numbers.

A numerical constant may be represented in binary, octal, decimal, or
hex by the use of a radix prefix.  The radix prefixes are {\cf
\#b}\sharpindex{b} (binary), {\cf \#o}\sharpindex{o} (octal), {\cf
\#d}\sharpindex{d} (decimal), and {\cf \#x}\sharpindex{x} (hex).  With
no radix prefix, a number is assumed to be expressed in decimal.

A numerical constant may be specified to be either \type{exact} or
\type{inexact} by a prefix.  The prefixes are {\cf \#e}\sharpindex{e}
for exact, and {\cf \#i}\sharpindex{i} for inexact.  An exactness 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 expressed without decimal points
and without use of exponential notation are assumed exact.

In systems with both single and double precision \type{flonum}s we may
want to specify which size we want to use to represent 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 \type{inexact} number.  For this purpose,
we may express a number with a prefix that indicates short or long
\type{flonum} representation:\sharpindex{s}\sharpindex{l}

\begin{scheme}
\#S3.14159265358979
       {\rm Round to short ---} 3.141593
\#L.6
       {\rm Extend to long ---} .600000000000000%
\end{scheme}


\subsection{Numerical operations}

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

\todo{Scheme provides the usual set of operations for manipulating
numbers, etc.}

\begin{entry}{%
\proto{number?}{ obj}{essential procedure}
\proto{complex?}{ obj}{essential procedure}
\proto{real?}{ obj}{essential procedure}
\proto{rational?}{ obj}{essential procedure}
\proto{integer?}{ obj}{essential 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.  Not every system supports all of these types; for example,
it is entirely possible to have a Scheme system that has only
\type{integer}s.  Nonetheless every implementation of Scheme must have all
of these predicates.

\end{entry}


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

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

\end{entry}


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

Some implementations allow these procedures to take many arguments, to
facilitate range checks.  These procedures return \schtrue{} if their
arguments are (respectively): numerically equal, monotonically
increasing, monotonically decreasing, monotonically nondecreasing, or
monotonically nonincreasing.  Warning: on \type{inexact} numbers the
equality tests will give unreliable results, and the other numerical
comparisons will be useful only heuristically; when in doubt, consult a
numerical analyst.

\end{entry}


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

These procedures return the maximum or minimum of their arguments.
\todo{Kelsey: Is there a better way to say that only the 2-arg case is essential?}
\end{entry}


\begin{entry}{%
\proto{+}{ \vri{z} \vrii{z}}{essential procedure}
\proto{+}{ \vri{z} \dotsfoo}{procedure}
\proto{*}{ \vri{z} \vrii{z}}{essential 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}}{essential procedure}
\proto{-}{ \vri{z} \vrii{z} \dotsfoo}{procedure}
\proto{/}{ \vri{z} \vrii{z}}{essential 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}{essential 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}}{essential procedure}
\proto{remainder}{ \vri{n} \vrii{n}}{essential 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}
\proto{rationalize}{ x y}{procedure}
\proto{rationalize}{ x}{procedure}}

These procedures create integers and rationals.  Their results are
\type{exact} if and only if their arguments are \type{exact}.

%Their results are not
%\type{exact}---in fact, their results are clearly \type{inexact}, though
%they can be made \type{exact} with an explicit exactness coercion.

\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.  With two arguments, \ide{rationalize} produces the rational
number with smallest denominator differing from \vr{x} by no more than
\vr{y}.  With one argument, \ide{rationalize} produces the best rational
approximation to \vr{x}, preserving all of the precision in its
representation.

\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}}

These procedures are part of every implementation that supports real
numbers; they compute the usual transcendental functions.  \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), even in implementations
that don't support complex numbers.

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}}

These procedures are part of every implementation that supports complex
numbers.  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}, and \ide{angle} returns \vriv{x}.
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}, but \ide{abs}
must be present in all implementations, whereas \ide{magnitude} will
only be present in implementations that support complex numbers.
\end{note}

\end{entry}


\begin{entry}{%
\proto{exact->inexact}{ \vr{z}}{procedure}
\proto{inexact->exact}{ \vr{z}}{procedure}}

\ide{Exact\coerce{}inexact} returns an \type{inexact} representation of \vr{z},
which is a fairly harmless thing to do.  \ide{Inexact\coerce{}exact} returns an
\type{exact} representation of \vr{z}.  Since the law of ``garbage in,
garbage out'' remains in force, \ide{inexact\coerce{}exact} should not be used
casually.

\end{entry}

\medskip

\subsection{Numerical input and output}


\begin{entry}{%
\proto{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~\ref{numberformats}.
The procedure \ide{number\coerce{}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
user will need to know nothing about the formats because the system
printer will have reasonable default formats for all types of
\type{number}s.

\end{entry}


\begin{entry}{%
\proto{string->number}{ string exactness radix}{procedure}}

The system reader will construct reasonable default numerical 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
\ide{string\coerce{}number}.
\var{Exactness} must be a symbol, either {\cf E} (for \type{exact}) or {\cf
I} (for \type{inexact}).  \var{Radix} must also be a symbol: {\cf B} for
binary, {\cf O} for octal, {\cf D} for decimal, and {\cf X} for
hexadecimal.  Returns a number of the maximally precise representation
expressed by the given \var{string}.  It is an error if \var{string} does
not express a number according to the grammar in section~\ref{numbersyntax}.
 
\end{entry}

 
\subsection{Formats}
\label{numberformats}

%@@@@LOSE@@@@

A {\em format} is a list beginning with a {\em format descriptor}, which
is a symbol such as {\cf sci}.  Following the descriptor are parameters
used by that 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, such as the {\cf radix} and
{\cf exactness} formats described below, which themselves take
parameters.

Details of particular formats such as {\tt sci} and {\tt fix} are given
in section~\ref{formatdetails}.

For example, the format {\cf (sci 5 2 (exactness s))} specifies that a
number is to be expressed in Fortran scientific format with 5
significant places and two places after the radix point, and that its
exactness prefix is to be suppressed.

In the following examples, the comment shows the format that was
used to produce the output shown:

\begin{scheme}
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))
1.2@1.570796                 ; (polar (fix 1)
                             ;        (flo 7))%
\end{scheme}

A format may specify that a number should be expressed in a particular
radix.  The radix prefix may also be suppressed.  For example, one may
express a complex number in polar form with the magnitude in octal and
the angle in decimal as follows:

\begin{scheme}
\#o1.2@\#d1.570796327 ; (polar (flo 2 (radix o))\sharpindex{o}
                    ;        (flo (radix d)))
\#o1.2@1.570796327   ; (polar (flo 2 (radix o))
                    ;        (flo (radix d s)))%
\end{scheme}

A format may specify that a number should be expressed with an explicit
exactness prefix ({\tt (exactness e)}), or it may force the exactness to
be suppressed ({\tt (exactness s)}).  For example, the following are
ways to express an inexact value for pi:

\begin{scheme}
\#i355/113           ; (rat (exactness e))\sharpindex{i}
355/113             ; (rat (exactness s))
\#i3.1416            ; (fix 4 (exactness e))%
\end{scheme}


An attempt to produce more digits than are available in the internal
machine representation of a number will be marked with a ``\sharpsign''
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:

\begin{scheme}
3.14158265358979\#\#\#\#\#   ; (flo 20 (exactness s))%
\end{scheme}

 
\subsection{Details of formats}
\label{formatdetails}

The format descriptors are:


\begin{entry}{\rproto{int}{}{format}}

Express as an integer.  The radix point is implicit.  If there are not
enough significant places then insignificant digits will be flagged.  For
example, an inexact integer \hbox{$6.0238\cdot10^{23}$} (represented internally as a 7 digit
\type{flonum}) would be printed as

\nobreak
\begin{scheme}
6023800\verb"#################"%
\end{scheme}

\end{entry}

 
\begin{entry}{\rproto{rat}{ \vr{n}}{format}}

Express as a rational fraction.  \vr{n} specifies the largest denominator
to be used in constructing a rational approximation to the number being
expressed.  If \vr{n} is omitted it defaults to infinity.

\end{entry}


\begin{entry}{\rproto{fix}{ \vr{n}}{format}}

Express with a fixed radix point.  \vr{n} specifies the number of places
to the right of the radix point.  \vr{n} defaults to the size of a
single-precision \type{flonum}.  If there are not enough significant
places, then insignificant digits will be flagged.  For example,
an inexact \hbox{$6.0238\cdot10^{23}$} (represented internally as a 7 digit \type{flonum})
would be printed with a {\tt (fix 2)} format as

\begin{scheme}
6023800\verb"#################.##"%
\end{scheme}

\end{entry}


\begin{entry}{\rproto{flo}{ \vr{n}}{format}}

Express with a floating radix point.  \vr{n} specifies the total number
of places to be displayed.  \vr{n} defaults to the size of a
single-precision \type{flonum}.  If the number is out of range, it is
converted to {\tt (sci)}.  {\tt (flo h)} expresses \vr{n} in floating
point format heuristically for human consumption. 
 
\end{entry}


\begin{entry}{\rproto{sci}{ \vr{n} \vr{m}}{format}}

Express in exponential notation.  \vr{n} specifies the total number of
places to be displayed.  \vr{n} defaults to the size of a single-precision
\type{flonum}.  \vr{m} specifies the number of places to the right of the
radix point.  \vr{m} defaults to $\vr{n}-1$.  {\tt (sci h)} does heuristic
expression.
 
\end{entry}


\begin{entry}{\rproto{rect}{ \vr{r} \vr{i}}{format}}

Express as a rectangular form complex number.  \vr{r} and \vr{i} are
formats for the real and imaginary parts respectively.  They default to
{\tt (heur)}.
 
\end{entry}


\begin{entry}{\rproto{polar}{ \vr{m} \vr{a}}{format}}

Express as a polar form complex number.  \vr{m} and \vr{a} are formats
for the magnitude and angle respectively.  \vr{m} and \vr{a} default to
{\tt (heur)}.

\end{entry}


\begin{entry}{\rproto{heur}{}{format}}

Express heuristically using the minimum number of digits required to get an
expression that when coerced back to a number produces the original machine
representation.  \type{Exact} numbers are expressed as {\tt (int)} or {\tt
(rat)}.  \type{Inexact} numbers are expressed as {\tt (flo h)} or {\tt (sci
h)} depending on their range.  Complex numbers are expressed in {\tt
(rect)}.  This is the normal default of the system printer.

\end{entry}

\bigskip

The following modifiers may be added to a numerical format specification:

\begin{entry}{\rproto{exactness}{ \vr{s}}{format}}

This controls the expression of the exactness prefix of a number.  \vr{s}
must be a symbol, either {\tt E} or {\tt S}, indicating whether the
exactness is to be expressed or suppressed, respectively.  If no
exactness modifier is specified for a format then the exactness is by
default suppressed.  \todo{Use something besides \vr{s}.  Also: allow
spelled out versions?}

\end{entry}


\begin{entry}{\rproto{radix}{ \vr{r} \vr{s}}{format}}

This forces a number to be expressed in the radix \vr{r}.  \vr{r} may be
the symbol {\tt B} (binary), {\tt O} (octal), {\tt D} (decimal), or {\tt X}
(hex).
\vr{s} must be a symbol, either {\tt E} or {\tt S}, indicating whether
the radix prefix is to be expressed or suppressed, respectively.
\vr{s} defaults to \hbox{\tt E} (expressed).  If no
radix modifier is specified then the default is decimal and the prefix is
suppressed.
\todo{How to spell these out??}

\end{entry}


\section{Characters}
\label{charactersection}

Characters are objects that represent printed characters such as
letters and digits.  There is no requirement that the data type of
characters be disjoint from other data types; implementations are
encouraged to have a separate character data type, but may choose to
represent characters as integers, strings, or some other type.

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{} }&; the space character\\
{\tt \#\backwhack{}space}&; the preferred way to write a space\\
{\tt \#\backwhack{}newline}&; the newline character\\
\end{tabular}
$$

Case is significant in \sharpsign\backwhack\hyper{character}, but not in
\sharpsign\backwhack\hyper{character name}.  If \hyper{character} in
\sharpsign\backwhack\hyper{character} is alphabetic, then the character
following \hyper{character} must be a delimiter character such as a
space or parenthesis.  This rule resolves the ambiguous case where, for
example, the sequence of characters ``{\tt\sharpsign\backwhack space}''
could be taken to be either a representation of the space character or a
representation of the character ``{\tt\sharpsign\backwhack s}'' followed
by a representation of the symbol ``{\tt pace}.''

\todo{Fix}
Characters written in the \sharpsign\backwhack{} notation are self-evaluating.
That is, they do not have to be quoted in programs.  The \sharpsign\backwhack{}
notation is not an essential part of Scheme, however.  Even implementations
that support the \sharpsign\backwhack{} notation for input do not have to support
it for output.

\vest Some of the procedures that operate on characters ignore the
difference between upper case and lower case.  The procedures that
ignore case have the suffix \hbox{``{\tt -ci}''} (for ``case
insensitive'').  If the operation is a predicate, then the \hbox{``{\tt
-ci}''} suffix precedes the \hbox{``{\tt ?}''} at the end of the name.


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

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

\end{entry}


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

\label{characterequality}
\nodomain{Both \vari{char} and \varii{char} must be characters.}
These procedures impose a total ordering on the set of characters.  It
is guaranteed that under this ordering:

\begin{itemize}
\item The upper case characters are in order.  For example, {\cf 
   (char<?\ \#\backwhack{}A \#\backwhack{}B)} returns \schtrue.
\item The lower case characters are in order.  For example, {\cf 
   (char<?\ \#\backwhack{}a \#\backwhack{}b)} returns \schtrue.
\item The digits are in order.  For example, {\cf 
   (char<?\ \#\backwhack{}0 \#\backwhack{}9)} returns \schtrue.
\item Either all the digits precede all the upper case letters, or vice versa.
\item Either all the digits precede all the lower case letters, or vice versa.
\end{itemize}

Some implementations may generalize these procedures to take more than
two arguments, as with the corresponding numeric predicates.

\end{entry}


\begin{entry}{%
\proto{char-ci=?}{ \vari{char} \varii{char}}{procedure}
\proto{char-ci<?}{ \vari{char} \varii{char}}{procedure}
\proto{char-ci>?}{ \vari{char} \varii{char}}{procedure}
\proto{char-ci<=?}{ \vari{char} \varii{char}}{procedure}
\proto{char-ci>=?}{ \vari{char} \varii{char}}{procedure}}

\nodomain{Both \vari{char} and \varii{char} must be characters.}
These procedures are similar to \ide{char=?}\ et cetera, but they treat
upper case and lower case letters as the same.  For example, {\cf
(char-ci=?\ \#\backwhack{}A \#\backwhack{}a)} returns \schtrue.  Some
implementations may generalize these procedures to take more than two
arguments, as with the corresponding numeric predicates.

\end{entry}


\begin{entry}{%
\proto{char-alphabetic?}{ char}{procedure}
\proto{char-numeric?}{ char}{procedure}
\proto{char-whitespace?}{ char}{procedure}}

These procedures return \schtrue{} if their arguments are alphabetic,
numeric, or whitespace characters, respectively, otherwise they return
\schfalse.  The following remarks, which are specific to the ASCII
character set, are intended only as a guide:  The alphabetic characters
are the 52 upper and lower case letters.  The numeric characters are the
ten decimal digits.  The whitespace characters are space, tab, line
feed, form feed, and carriage return.
\end{entry}


\begin{entry}{%
\proto{char-upper-case?}{ letter}{procedure}
\proto{char-lower-case?}{ letter}{procedure}}

\domain{\var{Letter} must be an alphabetic character.}
These procedures return \schtrue{} if their arguments are upper case or
lower case characters, respectively, otherwise they return \schfalse.
\end{entry}


\begin{entry}{%
\proto{char->integer}{ char}{essential procedure}
\proto{integer->char}{ \vr{n}}{essential procedure}}

Given a character, \ide{char\coerce{}integer} returns an integer
representation of the character.  Given an integer that is the image of
a character under \ide{char\coerce{}integer}, \ide{integer\coerce{}char}
returns a character.  These procedures implement order isomorphisms
between the set of characters under the \ide{char<=?}\ ordering and some
subset of the integers under the \ide{<=}\ ordering.  That is, if

\begin{scheme}
(char<=? \vr{a} \vr{b}) \evalsto \schtrue  {\rm{}and}  %
(<= \vr{x} \vr{y}) \evalsto \schtrue%
\end{scheme}

\noindent and \vr{x} and \vr{y} are in the range of \ide{char\coerce{}integer},
then

\begin{scheme}
(<= (char\coerce{}integer \vr{a})
    (char\coerce{}integer \vr{b}))         \ev  \schtrue

(char<=? (integer\coerce{}char \vr{x})
         (integer\coerce{}char \vr{y}))     \ev  \schtrue%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{char-upcase}{ char}{procedure}
\proto{char-downcase}{ char}{procedure}}

\nodomain{\var{Char} must be a character.}
These procedures return a character \varii{char} such that {\cf
(char-ci=? \var{char} \varii{char})}.  In addition, if \var{char} is
alphabetic, then the result of \ide{char-upcase} is upper case and the
result of \ide{char-downcase} is lower case.

\end{entry}


\section{Strings}
\label{stringsection}

Strings are sequences of characters.  In some implementations of Scheme
they are immutable; other implementations provide destructive procedures
such as \ide{string-set!}\ that alter string objects.

\vest 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.

\vest 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.

\vest The {\em 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 \defining{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.

\vest In phrases such as ``the characters of \var{string} beginning with
index \var{start} and ending with index \var{end},'' it is understood
that the index \var{start} is inclusive and the index \var{end} is
exclusive.  Thus if \var{start} and \var{end} are the same index, a null
substring is referred to, and if \var{start} is zero and \var{end} is
the length of \var{string}, then the entire string is referred to.

\vest Some of the procedures that operate on strings ignore the
difference between upper and lower case.  The versions that ignore case
have the suffix \hbox{``{\cf -ci}''} (for ``case insensitive'').  If the
operation is a predicate, then the \hbox{``{\cf -ci}''} suffix precedes the
\hbox{``{\cf ?}''} at the end of the name.


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

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


\begin{entry}{%
\proto{make-string}{ \vr{k}}{procedure}
\proto{make-string}{ \vr{k} char}{procedure}}

\domain{\vr{k} must be a non-negative integer, and \var{char} must be
a character.}  \ide{Make-string} returns a newly allocated string of
length \vr{k}.  If \var{char} is given, then all elements of the string
are initialized to \var{char}, otherwise the contents of the
\var{string} are unspecified.

\end{entry}

\begin{entry}{%
\proto{string-length}{ string}{essential procedure}}

Returns the number of characters in the given \var{string}.
\end{entry}


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

\domain{\vr{k} must be a valid index of \var{string}.}
\ide{String-ref} returns character \vr{k} of \var{string} using zero-origin indexing.
\end{entry}


\begin{entry}{%
\proto{string-set!}{ string k char}{procedure}}

\domain{%\var{String} must be a string, 
\vr{k} must be a valid index of \var{string}%, and \var{char} must be a character
.}
\ide{String-set!} stores \var{char} in element \vr{k} of \var{string}
and returns an unspecified value.  % <!>

\end{entry}


\begin{entry}{%
\proto{string=?}{ \vari{string} \varii{string}}{essential procedure}
\proto{string-ci=?}{ \vari{string} \varii{string}}{procedure}}

Returns \schtrue{} if the two strings are the same length and contain the same
characters in the same positions, otherwise returns \schfalse.
\ide{String-ci=?}\ treats
upper and lower case letters as though they were the same character, but
\ide{string=?}\ treats upper and lower case as distinct characters.

\end{entry}


\begin{entry}{%
\proto{string<?}{ \vari{string} \varii{string}}{essential procedure}
\proto{string>?}{ \vari{string} \varii{string}}{essential procedure}
\proto{string<=?}{ \vari{string} \varii{string}}{essential procedure}
\proto{string>=?}{ \vari{string} \varii{string}}{essential procedure}
\proto{string-ci<?}{ \vari{string} \varii{string}}{procedure}
\proto{string-ci>?}{ \vari{string} \varii{string}}{procedure}
\proto{string-ci<=?}{ \vari{string} \varii{string}}{procedure}
\proto{string-ci>=?}{ \vari{string} \varii{string}}{procedure}}

These procedures are the lexicographic extensions to strings of the
corresponding orderings on characters.  For example, \ide{string<?}\ is
the lexicographic ordering on strings induced by the ordering
\ide{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 the longer string.

Implementations may generalize these and the \ide{string=?}\ and
\ide{string-ci=?} procedures to take more than two arguments, as with
the corresponding numeric predicates.

\end{entry}


\begin{entry}{%
\proto{substring}{ string start end}{essential procedure}}

\domain{\var{String} must be a string, and \var{start} and \var{end}
must be exact integers satisfying
$$0 \leq \var{start} \leq \var{end} \leq \hbox{\tt(string-length \var{string})\rm.}$$}
\ide{Substring} returns a newly allocated string formed from the characters of
\var{string} beginning with index \var{start} (inclusive) and ending with index
\var{end} (exclusive).
\end{entry}


\begin{entry}{%
\proto{string-append}{ \vari{string} \varii{string}}{essential procedure}
\proto{string-append}{ \var{string} \dotsfoo}{procedure}}

Returns a new string whose characters form the concatenation of the
given strings.

\end{entry}


\begin{entry}{%
\proto{string->list}{ string}{essential procedure}
\proto{list->string}{ chars}{essential procedure}}

\ide{String\coerce{}list} returns a newly allocated list of the
characters that make up the given string.  \ide{List\coerce{}string}
returns a string formed from the characters in the list \var{chars}.
\ide{String\coerce{}list} and \ide{list\coerce{}string} are inverses so
far as \ide{equal?}\ is concerned.  Implementations that provide
destructive operations on strings should ensure that the result of
\ide{list\coerce{}string} is newly allocated.

\end{entry}


\begin{entry}{%
\proto{string-copy}{ string}{procedure}}

Returns a newly allocated copy of the given \var{string}.

\end{entry}


\begin{entry}{%
\proto{string-fill!}{ string char}{procedure}}

Stores \var{char} in every element of the given \var{string} and returns an
unspecified value.  % <!>

\end{entry}


\section{Vectors}
\label{vectorsection}

Vectors are heterogenous mutable structures whose elements are indexed
by integers.

\vest The {\em 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 created.  The {\em valid indexes}\index{valid indexes} of a
vector are the exact non-negative 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 {\tt\#(\var{obj} \dotsfoo)}.
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 of a vector, not an
expression evaluating to a vector.  Like list constants, vector
constants must be quoted:

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

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


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


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

Returns a newly allocated vector of \var{k} 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}{essential 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}{essential procedure}}

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


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

\domain{\vr{k} must be a valid index of \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}{essential procedure}}

\domain{\vr{k} must be a valid index of \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}{essential procedure}
\proto{list->vector}{ list}{essential 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}
\label{proceduresection}
 
% Intro flushed; not very a propos any more.
% Procedures should be discussed somewhere, however.

This chapter describes various primitive procedures which control the
flow of program execution in special ways.
The \ide{procedure?}\ predicate is also described here.

\todo{{\tt Procedure?} doesn't belong in a section with the name
``control features.''  What to do?}

\begin{entry}{%
\proto{procedure?}{ obj}{essential 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
(call-with-current-continuation procedure?)
                            \ev  \schtrue%
\end{scheme}

\end{entry}


\begin{entry}{%
\proto{apply}{ proc args}{essential procedure}
\proto{apply}{ proc \vari{arg} $\ldots$ args}{procedure}}

\domain{\var{Proc} must be a procedure and \var{args} must be a list.}
The first (essential) 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 the list
{\cf(append (list \vari{arg} \dotsfoo) \var{args})} as the actual
arguments.

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

(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}{essential procedure}
\proto{map}{ proc \vari{list} \varii{list} \dotsfoo}{procedure}}

\domain{The \var{list}s must be lists, and \var{proc} must be a
procedure taking as many arguments as there are {\it list}s.  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}{essential 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}


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

Forces the value of \var{promise} (see \ide{delay},
section~\ref{delay}).\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 in
functional style.  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}

Here is a possible implementation of \ide{delay} and \ide{force}.  We
define the expression

\begin{scheme}
(delay \hyper{expression})%
\end{scheme}

to have the same meaning as the procedure call

\begin{scheme}
(make-promise (lambda () \hyper{expression}))\rm,%
\end{scheme}

where \ide{make-promise} is defined as follows:

\begin{scheme}
(define make-promise
  (lambda (proc)
    (let ((already-run? \schfalse) (result \schfalse))
      (lambda ()
        (cond ((not already-run?)
               (set! result (proc))
               (set! already-run? \schtrue)))
        result))))%
\end{scheme}

Promises are implemented here as procedures of no arguments,
and \ide{force} simply calls its argument.

\begin{scheme}
(define force
  (lambda (object)
    (object)))%
\end{scheme}

Various extensions to this semantics of \ide{delay} and \ide{force}
are supported in some implementations:

\begin{itemize}
\item Calling \ide{force} on an object that is not a promise may simply
return the object.

\item It may be the case that there is no means by which a promise can be
operationally distinguished from its forced value.  That is, expressions
like the following may evaluate to either \schtrue{} or to \schfalse{},
depending on the implementation:

\begin{scheme}
(eqv? (delay 1) 1)          \ev  \unspecified
(pair? (delay (cons 1 2)))  \ev  \unspecified%
\end{scheme}

\item Some implementations will implement ``implicit forcing,'' where
the value of a promise is forced by primitive procedures like \ide{cdr}
and \ide{+}:

\begin{scheme}
(+ (delay (* 3 7)) 13)  \ev  34%
\end{scheme}
\end{itemize}
\end{entry}


\begin{entry}{%
\proto{call-with-current-continuation}{ proc}{essential procedure}}

\label{continuations} \domain{\var{Proc} must be a procedure of one
argument.} The procedure \ide{call-with-current-continuation} packages
up the current continuation (see the rationale below) as an ``escape
procedure''\mainindex{escape procedure} and passes it as an argument to
\var{proc}.  The escape procedure is a Scheme procedure of one
argument that, if it is later passed a value, will ignore whatever
continuation 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.

\vest The escape procedure created by \ide{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.

\vest The following examples show only the most common uses of
\ide{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 \ide{call-with-current-continuation}.

\begin{scheme}
(call-with-current-continuation
  (lambda (exit)
    (for-each (lambda (x)
                (if (negative? x)
                    (exit x)))
              '(54 0 37 -3 245 19))
    \schtrue))                        \ev  -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 \schfalse))))))
          (r obj))))))

(list-length '(1 2 3 4))            \ev  4

(list-length '(a b . c))            \ev  \schfalse%
\end{scheme}

\begin{rationale}
A common use of \ide{call-with-current-continuation} is for
structured, non-local exits from loops or procedure bodies, but in fact
\ide{call-with-current-continuation} is extremely useful for implementing a
wide variety of advanced control structures.

\vest Whenever a Scheme expression is evaluated there is a {\em continuation}
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, evaluate it, and
so on forever.  Most of the time the continuation includes actions
specified by user code, as in a continuation 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 hidden behind the scenes and programmers don't
think much about them.  On rare occasions, however, a programmer may
need to deal with continuations explicitly.
\ide{Call-with-current-continuation} allows Scheme programmers to do
that by creating a procedure that acts just like the current
continuation.

\vest Most programming languages incorporate one or more special-purpose
escape constructs with names like {\tt exit}, \hbox{\ide{return}}, or
even {\tt goto}.  In 1965, however, Peter Landin~\cite{Landin65}
invented a general purpose escape operator called the J-operator.  John
Reynolds~\cite{Reynolds72} described a simpler but equally powerful
construct in 1972.  The \ide{catch} special form described by Sussman
and Steele in the 1975 report on Scheme is exactly the same as
Reynolds's construct, though its name came from a less general construct
in MacLisp.  Several Scheme implementors noticed that the full power of the
\ide{catch} construct could be provided by a procedure instead of by a
special syntactic construct, and the name
\ide{call-with-current-continuation} was coined in 1982.  This name is
descriptive, but opinions differ on the merits of such a long name, and
some people use the name \ide{call/cc} instead.
\end{rationale}

\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.

\todo{Haase: Mention that there are alternatives to files?}

\begin{entry}{%
\proto{call-with-input-file}{ string proc}{essential procedure}
\proto{call-with-output-file}{ string proc}{essential 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.  If the procedure 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.

\begin{rationale}
Because Scheme's escape procedures have unlimited extent, it  is
possible to escape from the current continuation but later to escape back in. 
If implementations were permitted to close the port on any escape from the
current continuation, then it would be impossible to write portable code using
both \ide{call-with-current-continuation} and \ide{call-with-input-file} or
\ide{call-with-output-file}.
\todo{Pitman wants more said here; maybe encourage users to call
{\tt close-foo-port}; maybe talk about process switches (?).}
\end{rationale} 
\end{entry}


\begin{entry}{%
\proto{input-port?}{ obj}{essential procedure}
\proto{output-port?}{ obj}{essential 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}{}{essential procedure}
\proto{current-output-port}{}{essential 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}.
If an escape procedure
is used to escape from the continuation of these procedures, their
behavior is implementation dependent.

\todo{Kelsey sez he'd hate to try to implement this.}
\todo{OK this with authors??}
%current continuation changes in such a way
%as to make it doubtful that the \var{thunk} will ever return.

\todo{Freeman:
Throughout this section I wanted to see ``the value of {\tt(current-input-port)}''
instead of ``the value returned by {\tt current-input-port}''.  (Same for
{\tt current-output-port}.)}


\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.  If a file with the given name
already exists, the effect is unspecified.

\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.

\todo{Ramsdell:  Some note is needed explaining why there are two
different close procedures.}

\todo{A port isn't necessarily still a port after it has been closed?}

\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}{}{essential procedure}
\proto{read}{ port}{essential procedure}}

\ide{Read} converts written representations of Scheme objects into the
objects themselves.  That is, it is a parser for the nonterminal
\meta{datum} (see section~\ref{datum}).  \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.

\vest 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.  \todo{} 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}{}{essential procedure}
\proto{read-char}{ port}{essential 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{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}.

\begin{rationale}
\ide{Char-ready?}\ exists to make it possible for a program to
accept characters from interactive ports without getting stuck waiting for
input.  Any input editors associated with such ports must ensure that
characters whose existence has been asserted by \ide{char-ready?}\ cannot
be rubbed out.  If \ide{char-ready?}\ were to return \schfalse{} at end of
file, a port at end of file would be indistinguishable from an interactive
port that has no ready characters.
\end{rationale}
\end{entry}


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

Returns \schtrue{} if \var{obj} is an end of file object, otherwise returns
\schfalse.  The precise set of end of file objects 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 \ide{read}.

\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}{essential procedure}
\proto{write}{ obj port}{essential 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}{essential procedure}
\proto{display}{ obj port}{essential 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 appear in the representation as if written by \ide{write-char}
instead of by \ide{write}.  \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.  Implementations that allow ``slashification''
within symbols will probably want \ide{write} but not \ide{display} to
slashify funny characters in symbols.
\end{rationale}
\end{entry}


\begin{entry}{%
\proto{newline}{}{essential procedure}
\proto{newline}{ port}{essential 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}{essential procedure}
\proto{write-char}{ char port}{essential 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}


\subsection{User interface}

Questions of user interface generally fall outside of the domain of this
report.  However, the following operations are important enough to
deserve description here.


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

\todo{Fix}

\domain{\var{Filename} should be a string naming an existing file
containing Scheme source code.} The \ide{load} procedure reads
expressions and definitions from the file and evaluates them
sequentially.  It is unspecified whether the results of the expressions
are printed.  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.

\begin{note}
For portability, \ide{load} must operate on source files.
Its operation on other kinds of files necessarily varies among
implementations.
\end{note}
\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,
though some implementations may relax this restriction.  The values
returned by these procedures are unspecified.

%\begin{note}
%These procedures are redundant in some systems, but
%systems that need them should provide them.
%\end{note}
\end{entry}
