formal proposal: A Modified Procedural Interface

[Robert Hieb <hieb@iuvax.cs.indiana.edu>]

% formal proposal: A Modified Procedural Interface
% [to provide for variable-arity procedures and multiple return values]

% See the accompanying note entitled
% ``informal proposal: A Modified Procedural Interface''
% for a more coherent discussion of the intent of this proposal.

% The following tex commands are derived from r4rs.tex.
% They allow this section to be latexed separately
% (although section numbers are lost or mutilated in the process).
% (You will still need commands.tex)

\documentstyle[twoside]{algol60}
\pagestyle{headings}
\showboxdepth=0
\input{commands}     
\def\theevenhead{Revised$^{3.5}$ Scheme}
\begin{document}
\hfil {\bf *** DRAFT --- \today{} ***}

% This is a patch to commands.tex to kill indexing for separate latexing:

\global\def\reallyindex#1#2#3{}

% The following should be added to commands.tex:

\newcommand{\lambdastarexp}{lambda* expression}
\newcommand{\Lambdastarexp}{Lambda* expression}
\newcommand{\ampersand}{{\bf \&}}

% The modifications begin at the start of chapter 3.  Unmodified sections have
% been omitted, so it must be correlated with the full report.

\chapter{Basic concepts}

\section{Variables and regions}

\label{specialformsection}

\label{variablesection}

Any identifier that is not a syntactic keyword \index{keyword} (see
section~\ref{keywordsection})  may be used as a variable. \index{syntactic
keyword}\index{identifier}\mainindex{variable} A variable may name a location
where zero or more values can be stored.  A variable that does so is said to be
{\em bound} to the location.  The set of all such bindings \mainindex{binding}
in effect at some point in a program is known as the {\em environment} in effect
at that point.  The values stored in the location to which a variable is bound
are called the variable's values. By abuse of terminology, the variable is
sometimes said to name the values or to be bound to the values.  This is not
quite accurate, but confusion rarely results from this practice.

\vest Certain expression types are used to create new locations and to bind
variables to those locations.  The most fundamental of these {\em binding
constructs} \mainindex{binding construct} is the \lambdastarexp{}
\index{\lambdastarexp{}}, because all other binding constructs can be explained
in terms of \lambdastarexp{}s. The other binding constructs are \ide{lambda},
\ide{let}, \ide{let*}, \ide{letrec}, and \ide{do} expressions (see
sections~\ref{lambdastar}, \ref{letrec}, and \ref{do}).

\vest Like Algol and Pascal, and unlike most other dialects of Lisp except for
Common Lisp, Scheme is a statically scoped language with block structure.  To
each place where a variable is bound in a program there corresponds a
\defining{region} of the program text within which the binding is effective. 
The region is determined by the particular binding construct that establishes
the binding.  Every reference to or assignment of a variable refers to the
binding of the variable that established the innermost of the regions containing
the use.  If there is no binding of the variable whose region contains the use,
then the use refers to the binding for the variable in the top level
environment, if any (section~\ref{initialenv}); if there is no binding for the
identifier, it is said to be \defining{unbound}. 
\mainindex{bound}\index{top level environment}


\chapter{Expressions}
\label{expressionchapter}

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

A Scheme expression is a construct that returns zero or more values, such as a
variable reference, literal, procedure call, or conditional.

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}.  They are
redundant in the strict sense of the word, but they capture common patterns of
usage, and are therefore provided as convenient abbreviations.

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

\subsection{Variable references}\unsection

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

An expression consisting of a variable \index{variable}
(section~\ref{variablesection}) is a variable reference.  The  values of the
variable reference are the values stored in the location to which the variable
is bound.  It is an error to reference an unbound \index{unbound} variable.

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

\subsection{Procedure calls}\unsection

\begin{entry}{%
\pproto{(\hyper{operator} \hyperi{operand} \dotsfoo)}{essential \exprtype}
\pproto{(\hyper{operator} \hyperi{operand} \dotsfoo \hyper{operand$_{n-1}$} \ampersand\ \hypern{operand})}{essential \exprtype}}

A procedure call is written by simply enclosing in parentheses expressions for
the procedure to be called and the arguments to be passed to it.  The operator
and operand expressions are evaluated (in an indeterminate order) and the
resulting procedure is passed the resulting arguments.
\mainindex{call}\mainindex{procedure call}

\begin{scheme}%
(+ 3 4)                          \ev  7
((if \schfalse + *) 3 4)         \ev  12%
\end{scheme}

Only an expression following an \ampersand{} may evaluate to an indefinite
number of values; an error is signalled if exactly one value is not returned for
any other expressions in a procedure call. All of the values returned by an
expression following an \ampersand{} are passed to the called procedure.

\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.
\end{note}
\end{entry}

\subsection{Multiple return values}\unsection
\begin{entry}{%
\proto{values}{ \hyperi{operand} \dotsfoo}{essential procedure}}

The special procedure \ide{values} is used to return indefinite numbers of
values.  It follows the ordinary evaluation rules for procedures, and is a
first-class object like other procedures, but returns all of the values it
receives as arguments. It can be thought of as the multiple value identity
operator.

\begin{scheme}%
(list 1 2 \& (values))                 \ev (1 2)
(list 1 2 \& (values 3 4))             \ev (1 2 3 4)
(list 1 2 (values 3))                  \ev (1 2 3)
(list 1 2 (values 3 4))                \ev \scherror%
\end{scheme}

\begin{note}%
A description of \ide{values} is probably more properly placed in the section on
special control features.
\end{note}
\end{entry}

\subsection{\Lambdastarexp{}s}\unsection

\label{lambastar}

\begin{entry}{%
\proto{lambda*}{ \hyperi{clause} \hyper{clause$_2$} \dotsfoo}{essential \exprtype}}

\syntax
Each \hyper{clause} should be of the form
\begin{scheme}
(\hyper{formals} \hyper{body}).%
\end{scheme}
\hyper{Formals} should be a formal arguments list as described below, and
\hyper{body} should be a sequence of one or more expressions.

\semantics
\vest A \lambdastarexp{} evaluates to a procedure.  The environment in effect
when the \lambdastarexp{} was evaluated is remembered as part of the procedure. 
When the procedure is later called with some actual arguments, the appropriate
\hyper{clause} will be selected, and the environment in which the
\lambdastarexp{} was evaluated will be extended by binding the variables in its
formal argument list to fresh locations, the corresponding actual argument
values will be stored in those locations, and the expressions in the
\hyper{body} of the \hyper{clause} will be evaluated sequentially in the
extended environment.  The values returned by last expression in the
\hyper{body} will be returned as the result of the procedure call.  The first
\hyper{clause} whose \hyper{formals} accepts the actual arguments received by
the procedure is selected. An error is signaled if no \hyper{formals} accepts
the arguments received by a procedure.

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

\begin{itemize}
\item {\tt(\hyperi{variable} \dotsfoo\ \hypern{variable})}:
The \hyper{clause} accepts exactly $n$ arguments. The arguments will be stored
in the bindings of the corresponding variables, and the \hyper{body} of the
\hyper{clause} will be evaluated.

\item {\tt(\hyperi{variable} \dotsfoo\ \hypern{variable} \ampersand\ \hyper{variable$_{n+1}$})}:
The \hyper{clause} accepts $n$ or more arguments. The first $n$ arguments will
be stored in the bindings of the first $n$ corresponding variables; all
arguments left over will be stored in the binding of the variable following the
\ampersand{}. These values may be referenced by using the variable following an
\ampersand{} in a procedure call.
\end{itemize}

\begin{scheme}%
(lambda* ((x) x))         \ev  {\em{}a procedure}
((lambda* ((x) x)) 0)     \ev 0
((lambda* ((\& r) (list \& r)))
 1 2 3)                   \ev (1 2 3)
(define list
  (lambda*
    (() '())
    ((x \& r) (cons x (list \& r)))))%
\end{scheme}
\end{entry}

\subsection{Conditionals}\unsection

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

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

\semantics
An \ide{if} expression is evaluated as follows: first, \hyper{test} is
evaluated.  If it yields a true value\index{true} (see
section~\ref{booleansection}),then \hyper{consequent} is evaluated and its
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.  An error will be
signaled if \hyper{test} does not evaluate to exactly one value.

\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
(list \& (if \#t (values) 0))   \ev  ()
(if (values) 0 1)               \ev  \scherror%
\end{scheme}

\end{entry}


\subsection{Assignments}\unsection

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

\hyper{Expression} is evaluated, and the resulting values are stored in the
location to which \hyper{variable} is bound.  \hyper{Variable} must be bound
either in some region \index{region} enclosing the \ide{set!} expressionor at
top level.  The result of the \ide{set!} expression is unspecified.

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

\end{entry}

\end{document}

% Other modifications remain to be made, particularly in the syntax and
% semantics.