procs.tex

% Initial environment

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

\mainindex{initial environment}
\mainindex{global environment}
\mainindex{procedure}

This chapter describes Scheme's built-in procedures.


A program can use a global variable definition to bind any variable.
These operations do not modify the behavior of
any procedure defined in this report.
%Altering any global binding that has
%not been introduced by a definition has an unspecified effect on the
%behavior of the procedures defined in this chapter.

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


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

The {\cf eqv?}\ procedure can determine if symbols, numbers and
booleans are equivalent. The empty list is only equivalent to another empty
list. Two different types are never equivalent, and other comparisons
are unspecified.

The {\cf eqv?} procedure returns \schtrue{} if:

\begin{itemize}
\item \vari{obj} and \varii{obj} are both \schtrue{} or both \schfalse.

\item \vari{obj} and \varii{obj} are both symbols and are the same
symbol (section~\ref{symbolsection}).

\item \vari{obj} and \varii{obj} are both numbers and
are numerically equal (in the sense of {\cf =}).

\item \vari{obj} and \varii{obj} are both the empty list.
\end{itemize}

The {\cf eqv?} procedure returns \schfalse{} if:

\begin{itemize}
\item \vari{obj} and \varii{obj} are of different types
(section~\ref{disjointness}).

\item one of \vari{obj} and \varii{obj} is \schtrue{} but the other is
\schfalse{}.

\item \vari{obj} and \varii{obj} are symbols but are not the same
symbol (section~\ref{symbolsection}).

\item \vari{obj} and \varii{obj} are both numbers and
are numerically unequal (in the sense of {\cf =}).

\item one of \vari{obj} and \varii{obj} is the empty list but the other
is not.

\end{itemize}


\begin{scheme}
(eqv? 'a 'a)                     \ev  \schtrue
(eqv? 'a 'b)                     \ev  \schfalse
(eqv? '(a) '(a))                 \ev  \unspecified
(eqv? (list 'a) (list 'a))       \ev  \unspecified
(eqv? '() '())                   \ev  \schtrue
(eqv? 2 2)                       \ev  \schtrue
(eqv? car car)                   \ev  \unspecified
(let ((n (+ 2 3)))
  (eqv? n n))      \ev  \schtrue
(let ((x '(a)))
  (eqv? x x))      \ev  \unspecified
(let ((x '()))
  (eqv? x x))      \ev  \schtrue
(let ((p (lambda (x) x)))
  (eqv? p p))      \ev  \unspecified
(eqv? \#f 'nil)                  \ev  \schfalse%
\end{scheme}

\begin{rationale} {\cf eqv?}\ can be used to compare simple values, and
most other uses are left unspecified.
\end{rationale}

\end{entry}

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

\newcommand{\type}[1]{{\it#1}}
\newcommand{\tupe}[1]{{#1}}

It is important to distinguish between mathematical numbers, the
Scheme numbers that attempt to model them, the machine representations
used to implement the Scheme numbers, and notations used to write
numbers.  This report uses the types \type{number}, and \type{integer}
to refer to both mathematical numbers and Scheme numbers.

Pico Scheme implementations should support signed integers with a
range that includes the longest possible list length.

\begin{note}
Pico Scheme implementations may support integers of practically
unlimited size, or they may support integers with a limited range.  If
using limited range integers some operations may overflow. Pico Scheme
implementations should document integer range restrictions and how
they are handled. Pico Scheme implementations may either return the
wrapped around number, or return a miscellaneous value (such as {\it
  false} or {\it undefined}) for overflow (which can be checked with
{\cf number?} which will return \schfalse\ for a miscellaneous value).
\end{note}

\subsection{Syntax of numerical constants}
\label{numbernotations}

The syntax of the written representations for numbers is described formally in
section~\ref{numbersyntax}. Numbers are written in decimal.

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

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

This numerical type predicate can be applied to any kind of
argument, including non-numbers.  It returns \schtrue{} if the object is
a number, and otherwise it returns \schfalse{}.

\begin{scheme}
(number? 3)         \ev  \schtrue
(number? '(1))      \ev  \schfalse%
\end{scheme}

\end{entry}

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

These procedures return \schtrue{} if their arguments are (respectively):
equal, monotonically increasing, monotonically decreasing,
and \schfalse{} otherwise.

These predicates are required to be transitive.

\end{entry}

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

These procedures return the sum or product of their arguments.

\begin{scheme}
(+ 3 4)                 \ev  7
(* 4 5)                 \ev  20%
\end{scheme}

\end{entry}

\begin{entry}{%
\proto{-}{ \vr{n}}{procedure}
\rproto{-}{ \vri{n} \vrii{n}}{procedure}}

With two arguments, this procedure returns the difference of its arguments, associating to the left.  With one argument,
however, it returns the additive inverse of its argument.

\begin{scheme}
(- 3 4)                 \ev  -1
(- 3)                   \ev  -3%
\end{scheme}

\end{entry}

\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
({\cf if}, {\cf cond}, {\cf and}, {\cf or}) treat as
true\mainindex{true} or false\mainindex{false}.  The phrase ``a true value''\mainindex{true}
(or sometimes just ``true'') means any object treated as true by the
conditional expressions, and the phrase ``a false value''\mainindex{false} (or
``false'') means any object treated as false by the conditional expressions.

\vest Of all the Scheme values, only \schfalse{}
counts as false in conditional expressions.
All other Scheme values, including \schtrue,
count as true.

\begin{note}
Unlike some other dialects of Lisp,
Scheme distinguishes \schfalse{} and the empty list \mainindex{empty list}
from each other and from the symbol {\cf nil}.
\end{note}

\vest Boolean constants evaluate to themselves, so they do not need to be quoted
in programs.

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


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

The {\cf not} procedure returns \schtrue{} if \var{obj} is false, and returns
\schfalse{} otherwise.

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

\end{entry}


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

The {\cf boolean?} predicate returns \schtrue{} if \var{obj} is either \schtrue{} or
\schfalse{} and returns \schfalse{} otherwise.

\begin{scheme}
(boolean? \schfalse)  \ev  \schtrue
(boolean? 0)          \ev  \schfalse
(boolean? '())        \ev  \schfalse%
\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 {\cf cons}.
The car and cdr fields are accessed by the procedures {\cf car} and
{\cf cdr}.

Pairs are used primarily to represent lists.  A \defining{list} can
be defined recursively as either the empty list\mainindex{empty list} or a pair whose
cdr is a list.  More precisely, the set of lists is defined as the smallest
set \var{X} such that

\begin{itemize}
\item The empty list is in \var{X}.
\item If \var{list} is in \var{X}, then any pair whose cdr field contains
      \var{list} is also in \var{X}.
\end{itemize}

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.

\begin{note}
The above definitions imply that all lists have finite length and are
terminated by the empty list.
\end{note}

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\mainindex{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 equivalent notations for a list of symbols.

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

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

is equivalent to

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

Whether a given pair is a list depends upon what is stored in the cdr
field.

Within literal expressions and representations of objects the form \singlequote\hyper{datum}\schindex{'} denotes a two-ele\-ment list whose first elements is
the symbols \ide{quote}.  The second element in each case
is \hyper{datum}.  This convention is supported so that arbitrary Scheme
programs can be represented as lists.  
That is, according to Scheme's grammar, every
\meta{expression} is also a \meta{datum} (see section~\ref{datum}).
See section~\ref{externalreps}. 


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

The {\cf pair?} predicate 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
\end{scheme}
\end{entry}


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

Returns a pair whose car is \vari{obj} and whose cdr is
\varii{obj}. 

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


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

Returns the contents of the car field of \var{pair}.  Note that it is an
error to take the car of the empty list\mainindex{empty list}.

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


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

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{null?}{ obj}{procedure}}

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

\end{entry}

\section{Symbols}
\label{symbolsection}

Symbols are objects whose usefulness rests on the fact that two
symbols are identical (in the sense of {\cf eqv?}) if and only if their
names are spelled the same way.  For instance, they can be used
the way enumerated values are used in other languages.

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

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

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

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

\section{Control features}
\label{proceduresection}

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

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

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

\end{entry}

\begin{entry}{%
\proto{apply}{ proc args}{procedure}}

The {\cf apply} procedure calls \var{proc} with the elements of the list
\var{args} as the actual
arguments.

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

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

((compose - *) 3 4)              \ev  -12%
\end{scheme}
\end{entry}

\section{Input and output}

Pico Scheme allows output to a character device. Input is not
specified in this report but an implementation may be extended to
support input. Since expressions are side-effect free, standard Pico
Scheme programs should not perform input or output from expressions
and implementations may require that input or output from them is an
error.  Output is only required to be allowed at the outermost level
of a program.

\begin{rationale}
  Implementations may choose to allow input and output (IO) from
  expressions (like \rsevenrs\ allows) or choose to forbid it.  An
  implementation that forbids IO side-effects in expressions but
  wishes to allow IO in places besides the outermost level would
  likely need to extend Scheme in a way that is not compatible with
  \rsevenrs.

  For example, an implementation could add a command type that allowed
  IO, and syntax to create it and then allow {\cf (define displayline
    (delta (x) (display x) (newline)))} to define a new command {\cf
    displayline}.

  Implementations could add a non-expression {\cf do} that allows
  IO inside it, similar to \rsevenrs's {\cf do} to support more
  flexible IO while remaining a subset of \rsevenrs.

  Besides {\cf display} and {\cf newline}, implementations could add
  {\cf write-u8}, {\cf (define} \hyper{indentifier} {\cf (read))}, and
  {\cf (define} \hyper{identifier} {\cf (read-u8))} to the outermost
  level to support more IO. Other IO from \rsevenrs{} can be added if
  string, char or port types are added.
\end{rationale}

\subsection{Output}
\label{outputsection}

\begin{entry}{%
\proto{display}{ obj}{input or output}
}

Writes a representation of \var{obj} to the textual output.  For
booleans, nulls, numbers and symbols, and pairs containing these, this
should be an external representation of the object.  Returns an
unspecified value.

\end{entry}

\begin{entry}{%
\proto{newline}{}{input or output}
}

Writes an end of line to textual output.  Exactly how this
is done differs
from one operating system to another. Returns an unspecified value.

\end{entry}