expr.tex

\chapter{Expressions}
\label{expressionchapter}

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

Expression types are categorized as {\em primitive} or {\em derived}.
Primitive expression types include variables and procedure calls.
Derived expression types are not semantically primitive, but can
instead be explained in terms of the primitive constructs as in
section~\ref{derivedsection}.

\section{Primitive expression types}
\label{primitivexps}

\subsection{Variable references}\unsection

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

An expression consisting of a variable\mainindex{variable}
(section~\ref{variablesection}) is a variable reference.  The value of
the variable reference is the value stored in the
variable.  It is an error to reference an
unbound\mainindex{unbound} variable.

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

\subsection{Literal expressions}\unsection
\label{literalsection}

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

{\cf (quote \hyper{datum})} evaluates to \hyper{datum}.\mainschindex{'}
\hyper{Datum}
can be any external representation of a Scheme object (see
section~\ref{externalreps}).  This notation is used to include literal
constants in Scheme code.
\begin{scheme}%
(quote a)                     \ev  a
(quote (a b c))     \ev  (a b c)
(quote (+ 1 2))               \ev  (+ 1 2)%
\end{scheme}

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

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

Numerical constants and boolean constants evaluate to
themselves; they need not be quoted.

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

\end{entry}

\subsection{Procedure calls}\unsection

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

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

A number of procedures are available as the values of variables in the initial environment.  For example, the addition and multiplication
procedures in the above examples are the values of the variables {\cf +}
and {\cf *}.  New procedures are created by evaluating \lambdaexp{}s
(see section~\ref{lambda}).

Procedure calls in Pico Scheme return one value.


\begin{note} In contrast to other dialects of Lisp, the order of
evaluation is unspecified, and the operator expression and the operand
expressions are always evaluated with the same evaluation rules.
Because Pico Scheme procedures do not have side effects, the order of
evaluation does not affect results.
\end{note}

\begin{note}
Although the order of evaluation is otherwise unspecified, the effect of
any concurrent evaluation of the operator and operand expressions is
constrained to be consistent with some sequential order of evaluation.
The order of evaluation may be chosen differently for each procedure call.
\end{note}

\begin{note} In many dialects of Lisp, the empty list, {\tt
()}, is a legitimate expression evaluating to itself.  In Scheme, the expression {\tt ()} is an error, however {\tt (quote ())} can be used.
\end{note}

\end{entry}


\subsection{Procedures}\unsection
\label{lamba}

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

\syntax
\hyper{Formals} is a formal arguments list as described below,
and \hyper{body} is a sequence of zero or more definitions
followed by one expression.

\semantics
\vest A \lambdaexp{} evaluates to a procedure.  The environment in
effect when the \lambdaexp{} was evaluated is remembered as part of the
procedure.  When the procedure is later called with some actual
arguments, the environment in which the \lambdaexp{} was evaluated will
be extended by binding the variables in the formal argument list to
the corresponding actual argument values.
Next, the definitions and expression in the
body of the lambda expression
will be evaluated sequentially in the extended environment.
The results of the expression in the body will be returned as
the results of the procedure call.

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

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

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

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

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

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

\end{itemize}

It is an error for a \hyper{variable} to appear more than once in
\hyper{formals}.

\begin{scheme}
((lambda x x) 3 4 5 6)          \ev  (3 4 5 6)
\end{scheme}

\end{entry}

\subsection{Conditionals}\unsection

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

\syntax
\hyper{Test}, \hyper{consequent}, and \hyper{alternate} are
expressions.

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

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

\end{entry}

\section{Derived expression types}
\label{derivedexps}

The constructs in this section can be created via rewrite rules with the primitive constructs described in the previous section.

\subsection{Conditionals}\unsection

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

\syntax
\hyper{Clauses} take one form
\begin{scheme}
(\hyper{test} \hyper{expression})%
\end{scheme}
where \hyper{test} is any expression.
The last \hyper{clause} can be
an ``else clause,'' which has the form
\begin{scheme}
(else \hyper{expression})\rm.%
\end{scheme}
\mainschindex{else}

\semantics
A {\cf cond} expression is evaluated by evaluating the \hyper{test}
expressions of successive \hyper{clause}s in order until one of them
evaluates to a true value\mainindex{true} (see
section~\ref{booleansection}).  When a \hyper{test} evaluates to a true
value, the remaining \hyper{expression} in its \hyper{clause} is
evaluated, and the result of the \hyper{expression} in the
\hyper{clause} are returned as the results of the entire {\cf cond}
expression.

If all \hyper{test}s evaluate
to \schfalse{}, and there is no else clause, then the result of
the conditional expression is unspecified; if there is an else
clause, then its \hyper{expression} is evaluated, and the value of it is
returned.

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

(cond ((> 3 3) 'greater)
      ((< 3 3) 'less)
      (else 'equal))            \ev  equal%

\end{scheme}


\end{entry}

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

\semantics
The \hyper{test} expressions are evaluated from left to right, and if
any expression evaluates to \schfalse{} (see
section~\ref{booleansection}), then \schfalse{} is returned.  Any remaining
expressions are not evaluated.  If all the expressions evaluate to
true values, the value of the last expression is returned.  If there
are no expressions, then \schtrue{} is returned.

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

\end{entry}


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

\semantics
The \hyper{test} expressions are evaluated from left to right, and the value of the
first expression that evaluates to a true value (see
section~\ref{booleansection}) is returned.  Any remaining expressions
are not evaluated.  If all expressions evaluate to \schfalse{}
or if there are no expressions, then \schfalse{} is returned.

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

\end{entry}

\subsection{Binding constructs}
\label{bindingsection}

The binding construct {\cf let}
gives Scheme a block structure, like Algol 60.  In a {\cf let} expression, the initial
values are computed before any of the variables become bound.

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

\syntax
\hyper{Bindings} has the form
\begin{scheme}
((\hyperi{variable} \hyperi{init}) \dotsfoo)\rm,%
\end{scheme}
where each \hyper{init} is an expression, and \hyper{body} is a
sequence of zero or more definitions followed by
one expression as described in section~\ref{lambda}.  It is
an error for a \hyper{variable} to appear more than once in the list of variables
being bound.

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

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

(let ((x 2) (y 3))
  (let ((x 7)
        (z (+ x y)))
    (* z x)))                   \ev  35%
\end{scheme}

\end{entry}