% -*- Latex -*- $Id: scheme-reference-card.tex,v 1.7 1993/12/15 17:44:24 leavens Exp leavens $
\documentstyle[11pt]{article}

\setlength{\textwidth}{6.5in} 
\setlength{\oddsidemargin}{0in}		% i.e. 1 inch margins
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9in}
\setlength{\headheight}{.60in}
\setlength{\headsep}{.40in}
\setlength{\topmargin}{-1in}

\newenvironment{mytabbing}{
 \begin{tabular}{lll}
}{
 \end{tabular}
}

\newenvironment{SPECIALFORMS}{
 \subsection{Special Forms}
 \begin{tabular}{lll}
 Syntax & Example & Notes \\
 \hline
}{
 \end{tabular}
}

% use the following within SPECIALFORMS for syntax split over lines
% and for very long types ...
\newenvironment{MANYLINES}{%
\begin{minipage}[t]{3in}%
\begin{tabbing}%
m \= m \= m \= m \= \kill%
}{%
\end{tabbing}%
\end{minipage}%
}

\newenvironment{OPERATIONS}{
 \begin{tabular}{l@{~:~}ll}
 Name & Type & Example or Notes \\
 \hline
}{
 \end{tabular}
}

% Nonterminals are in italic; terminals are in a roman font.
% Keywords are bold-faced.

\newcommand{\meta}[1]{\mbox{{\em #1}}}       % grammar (meta) symbol
\newcommand{\code}[1]{\mbox{{\tt #1}}}       % meta symbol

\newcommand{\rArr}{\rightarrow}

\begin{document}

\title{Make Your Own
	Scheme `Reference Card'}
\author{Gary T. Leavens}
\maketitle

\section*{Introduction}

This `card' is based on the subset of Scheme used in
{\em Scheme and the Art of Programming\/}
by George Springer and Daniel P. Friedman
(1989, McGraw-Hill and MIT Press).

The material is organized by chapters, so that you can fill it in as
you go through the course.

This card is ``do it yourself'' in the sense that we do not provide all
the information for all of Scheme.
The idea is for you to learn by filling in the missing information
yourself, following the examples that we do supply.
Missing information is only indicated by blank space.
You should write in the blank spaces to help your learning.

You may also want to make notes for yourself on this card
with other information you find useful, such as describing
what things do in words.
Another useful thing to do with this card is to reorganize it.
For example, you might want to collect the information by types
(booleans, symbols, pairs, etc.).
You might also try to write down equations relating the operations
of the various types.

\subsection*{Syntax Conventions}

Scheme keywords and other parts of scheme code are written
in a {\code{typewriter}} font; for example, \code{define}.
Grammatical symbols, which are placeholders for what you write,
are written in an {\meta{italic}} font; for example, {\meta{expr}}.

In syntax, ``$\ldots$'' means that instances of the preceding
parentheses-balanced grammatical form
may occur zero or more times.
For example,
\begin{center}
\code{(\meta{operator} \meta{operand} $\ldots$)}
\end{center}
means that there may be zero or more {\meta{operand}}s in a procedure call.
For example, {\code{(no-arg-proc)}} and {\code{(p 1 2)}} are both
ways to instantiate this syntax.

\subsection*{Type Conventions}

A type can be thought of as a set of values with certain associated
procedures.  For example we use ``number'' as the name of the type of
all numbers (both exact and inexact, real and integer) in Scheme.
The procedures that work on numbers include {\code{+}} and {\code{*}}.

We write the types of procedures using a notation like
($\rArr$ ($S$ $T$ $U$) $V$),
which is the type of a procedure that takes 3 arguments
(the first of type $S$, the second of type $T$,
 and the third of type $U$)
and returns a result of type $V$.
For example, {\code{+}} is a procedure of type
($\rArr$ (number number) number).
We use a colon (:) for the phrase ``is of type'' (or ``has type'').
For example, we write
\begin{center}
\code{+} : ($\rArr$ (number number) number)
\end{center}

Since Scheme does not do type checking before a program is run,
the elements of a list do not all have to be of the same type.
Such a list is {\em heterogeneous\/};
a list, all of whose elements are of the same type is {\em homogeneous}.
We use types of the form ``(list $T$)'' for the type of homogeneous lists,
whose elements all have type $T$;
for example, we may write ``(list integer)'', ``(list number)'', or
``(list symbol)''.
We use the type ``(list datum)'' for the type of heterogeneous lists,
because we think of the type ``datum'' as the type of all the values in Scheme.
For example, lists, procedures, symbols, and numbers all have type datum.
As another example, we could write for \code{cons}:
\begin{center}
\code{cons} : ($\rArr$ (datum (list datum)) (list datum)).
\end{center}
We abbreviate ``(list datum)'' as ``list'' when space is at a premium.

The names of other types with components are written similarly;
for example, we write ``(tree number)'' or ``(pair symbol symbol)''.

Sometimes, especially in chapter 7 and beyond,
we wish to use the type information to show how data is transformed.
For this it is convenient to use type variables,
which are consistently replaced in a type when that type is used.
Type variables capital letters such as: T, S, U, V, and W.
For example, for Scheme's built in procedure {\code{map}} we write:
\begin{center}
\code{map} : ($\rArr$ (($\rArr$ (S) T) (list S)) (list T)).
\end{center}
This type has several instances, that is consistent replacements of
actual types for the type variables.
For example, some instances are:
\begin{center}
 ($\rArr$ (($\rArr$ (boolean) integer) (list boolean)) (list integer)) \\
 ($\rArr$ (($\rArr$ (number) number) (list number)) (list number)) \\
 ($\rArr$ (($\rArr$ ((list symbol)) (list datum)) (list (list symbol))) (list (list datum))).
\end{center}
The first of the above examples is what one would use when checking the types
of the application {\code{(map positive? '(3 -2 1))}};
the second of these examples would be used in checking the types of the
application {\code{(map add1 '(3 -2 1))}}.
Since ``datum'' is a type,
if we write such a type for {\code{cons}},
\begin{center}
\code{cons} : ($\rArr$ (T (list T)) (list T))
\end{center}
then it has the type given earlier as an instance.

We do not emphasize the formality of the type names and phrases,
but try to write something that is easy to understand.

\section{Chapter 1}

See pages 6--7 (in {\em Scheme and the Art of Programming\/})
for the syntax of \meta{symbol} and \meta{number}.
On page 7 the term {\em variable\/} is introduced.
In what senses is a variable like a symbol?
In what senses are they different?
The grammatical symbol for variable is \meta{var}.

Almost everything in Scheme is an {\em expression\/}.
What does an expression look like in general?  (See page 7.)
Write down examples to illustrate the various cases.
The grammatical symbol for an expression is \meta{expr}.

We adopt the convention that unexplained grammatical symbols are equivalent
to expressions.  For example {\meta{test}} used in the syntax of
{\code{cond}} and {\code{if}} is equivalent to {\meta{expr}}.
These different names are used to guide you.

\begin{SPECIALFORMS}
\code{(define \meta{var} \meta{expr})}
  & \code{(define ten (+ 5 5))} 
  & binds \code{ten} to 10. \\

\code{(quote \meta{expr})} 
 & \code{(quote ten)}
 & don't evaluate \code{ten} \\

\code{'\meta{expr}} 
 & \code{'(a b xyz)} &  \\

\code{(\meta{operator} \meta{operand} $\ldots$)} & &
\end{SPECIALFORMS}

The form \code{(define \meta{var} \meta{expr})} is {\em not\/} an expression.
All the other forms are expressions.

\subsection{Numbers}

\begin{OPERATIONS}
\code{+} & ($\rArr$ (number number) number) & addition \\
\code{-} & \\
\code{*} & \\
\code{/} & \\
\code{number?} & ($\rArr$ (datum) boolean) & 
\end{OPERATIONS}

\subsection{Interaction With Scheme and Files}

\begin{OPERATIONS}
\code{transcript-on} & ($\rArr$ (string) void) & \code{(transcript-on "foo.out")}\\
		& & records your session with Scheme \\
		& & in the file named ``foo.out'' \\
\code{transcript-off} & $\rArr$ void & \code{(transcript-off)}
\end{OPERATIONS}

The procedure \code{transcript-on} does not return a result,
and this is why its return type is listed as ``void''.

\subsection{Lists}

\begin{OPERATIONS}
\code{'()}  & (list T) & the empty list \\
\code{cons} & ($\rArr$ (T (list T)) (list T)) &  \\
\code{car} & ($\rArr$ ((list T)) T) & requires: the argument is not empty \\
\code{cdr} & \\
\code{c....r} &  & the \code{.} is \code{a} or \code{d},
              		up to 4 defined \\
\code{pair?} & ($\rArr$ (datum) boolean) &  \\
\code{null?} & ($\rArr$ (datum) boolean) & 
\end{OPERATIONS}

\subsection{Booleans}

\begin{OPERATIONS}
\verb|#t|      & boolean & logical truth \\
\verb|#f|      & boolean \\
\code{boolean?} & ($\rArr$ (datum) boolean)
\end{OPERATIONS}

\subsection{Other Predicates}

\begin{OPERATIONS}
\code{symbol?} & ($\rArr$ (datum) boolean) \\
\code{procedure?} & \\
\code{eq?} & ($\rArr$ ((or symbol pair) (or symbol pair)) boolean) \\
\code{eqv?} & \begin{MANYLINES}
		($\rArr$ ((or number symbol boolean) \\
		\> ~~(or number symbol boolean)) boolean)
	     \end{MANYLINES} \\
\code{equal?} & ($\rArr$ (datum, datum) boolean)
\end{OPERATIONS}

Something has type ``(or symbol pair)'' if it is either a symbol or a pair.

\section{Chapter 2}

\begin{SPECIALFORMS}
\begin{MANYLINES}
\code{(lambda (\meta{parameter} $\ldots$)} \\
\>\code{\meta{body})}
\end{MANYLINES}
 & \code{(lambda (x) (cons x '()))}
 & makes a procedure \\
\begin{MANYLINES}
\code{(cond}\\
\>\code{(\meta{condition$_1$} \meta{body$_1$})}\\
\qquad\qquad \vdots\\
\>\code{(\meta{condition$_n$} \meta{body$_n$})}\\
\>\code{(else \meta{body$_{n+1}$}))}
\end{MANYLINES}
\\
\begin{MANYLINES}
\code{(if} \= \meta{condition}\\
\> \meta{consequent}\\
\> \code{\meta{alternative})}
\end{MANYLINES}
&
& Normal usage.
\\
\begin{MANYLINES}
\code{(if} \= \meta{condition}\\
\> \meta{consequent}\code{)}
\end{MANYLINES}
 &
 \begin{MANYLINES}
 \code{(if (null? ls)} \\
 \> \code{(writeln "n too large"))}
 \end{MANYLINES}
 & Only for side effects.
\\
\code{(and \meta{expr$_1$} \meta{expr$_2$} $\ldots$ \meta{expr$_n$})}\\
\code{(or \meta{expr$_1$} \meta{expr$_2$} $\ldots$ \meta{expr$_n$})}\\
\code{(begin \meta{expr$_1$} $\ldots$ \meta{expr$_n$})}
\end{SPECIALFORMS}

The {\meta{parameter}}s in a {\code{lambda}} are {\em not\/} expressions,
but names of formal parameters.
All the other forms are expressions.

\subsection{Lists}

\begin{OPERATIONS}
\code{list} & ($\rArr$ (T $\ldots$) (list T))
\end{OPERATIONS}

The procedure \code{list} takes zero or more arguments;
so we write $\ldots$ in the type.

\subsection{Booleans}

\begin{OPERATIONS}
\code{not} &  ~~~~~~~~~~~~~~~~~~ &
\end{OPERATIONS}

Note that \code{and} and \code{or} are special forms.

\subsection{Debugging}

\begin{OPERATIONS}
\code{writeln} & ($\rArr$ (datum $\ldots$) void)
\end{OPERATIONS}

The \code{writeln} operation does not return a useful result.
So we write ``void'' for the return type to signify this.
Note that void is not the type of a value.

\subsection{Strings}

\begin{OPERATIONS}
\code{"a string"} & string & 
\end{OPERATIONS}

\subsection{Interaction With Scheme and Files}

\begin{OPERATIONS}
\code{load} & ($\rArr$ (string) datum)
	 & \code{(load "foo.ss")} runs code in ``foo.ss''
\end{OPERATIONS}

\section{Chapter 3}

\subsection{Numbers}

\begin{OPERATIONS}
\code{integer?} & ($\rArr$ (number) boolean) & \\
\code{real?} & & \\
\code{positive?} & & \\
\code{negative?} & & \\
\code{zero?} & & \\
\code{add1} & ($\rArr$ (number number) number) & \\
\code{sub1} &  & \\
\end{OPERATIONS}

The procedures {\code{add1}} and {\code{sub1}} are in Chez Scheme and 
PC Scheme, but may not be in other dialects of Scheme.

There are many other numeric procedures summarized on page 76.

\subsection{Lists}

\begin{OPERATIONS}
\code{length} & ($\rArr$ (list) number) & \\
\code{list-ref} & & 
\end{OPERATIONS}

\subsection{Error Reporting}

\begin{OPERATIONS}
\code{error} & ($\rArr$ (datum $\ldots$) poof)
 & \code{(error "should be" 5)} prints ``Error:~should be 5''
\end{OPERATIONS}

The procedure {\tt error} not only has no return value, it does not return
at all! Instead it rather returns to the user prompt.

\subsection{Basic Procedures for Ratls}

\begin{OPERATIONS}
\code{make-ratl} & ($\rArr$ (integer integer) ratl)
 & requires: the second argument is non-zero \\
\code{numr} & ($\rArr$ (ratl) integer)
 & \\
\code{denr} & ($\rArr$ (ratl) integer)
 & 
\end{OPERATIONS}

\section{Chapter 4}

\subsection{Lists}

\begin{OPERATIONS}
\code{append} & ($\rArr$ ((list T) (list T)) (list T)) & \\
\code{reverse} & & \\
\end{OPERATIONS}

\subsection{Trees}

\begin{OPERATIONS}
\code{atomic-item?} & ($\rArr$ (datum) boolean) &
\end{OPERATIONS}

The procedure {\code{atomic-item?}} is my own invention, and will be discussed
in class.

\section{Chapter 5}

\begin{SPECIALFORMS}
\begin{MANYLINES}
\code{(let}\= ~\code{(}\=\code{(\meta{var$_1$} \meta{val$_1$})} \\
\>\>$\ldots$ \\
\>\>\code{(\meta{var$_n$} \meta{val$_n$}))} \\
\>\code{\meta{body})}
\end{MANYLINES}
 & \code{(let ((x 2)) (+ x x))}
 & binds \code{x} to 2 and returns 4 \\
\begin{MANYLINES}
\code{(letrec}\= ~\code{(}\=\code{(\meta{var$_1$} \meta{val$_1$})} \\
\>\>$\ldots$ \\
\>\>\code{(\meta{var$_n$} \meta{val$_n$}))} \\
\>\code{\meta{body})}
\end{MANYLINES}
 &  & 
\end{SPECIALFORMS} \\
The {\meta{var}}s in a {\code{let}} and {\code{letrec}}
are {\em not\/} expressions, but are names of local variables.
All the other forms are expressions.
The {\meta{val}}s in a {\code{letrec}} are usually {\code{lambda}} expressions.

\subsection{Basic Procedures for Polynomials}

\begin{OPERATIONS}
\code{the-zero-poly} & poly & represents $0x^0$, which is $0$ \\
\code{degree} & ($\rArr$ (poly) natural) & \\
\code{leading-coef} & & \\
\code{rest-of-poly} & & \\
\code{poly-cons} & ($\rArr$ (natural real poly) poly) & requires: 3rd argument's degree is \\
& & ~~ less than the 1st argument, or 0
\end{OPERATIONS}

\section{Chapter 6}

\subsection{Strings}

\begin{OPERATIONS}
\code{string-append} & ($\rArr$ (string string) string) & \\
\code{string-length} & & \\
\code{substring} & & \\
\code{symbol->string} & & \\
\code{string=?} & & \\
\code{string-ci=?} & &
\end{OPERATIONS}

\subsection{Implicit Begin}

What special forms allow an implicit begin in their \meta{body}?
Which do not?
What do you think the grammatical symbol {\meta{body}} really stands for?

\subsection{Input and Output}

\begin{OPERATIONS}
\code{display} & ($\rArr$ (datum) void) & prints things in human-readable format \\
\code{write} & & \\
\code{read} & $\rArr$ datum & {\tt (read)} gets a value entered from the keyboard \\
\code{newline} & &
\end{OPERATIONS}

Note that {\tt display} and {\tt writeln} do not return anything useful.
The procedure {\tt read} takes no arguments.

\section{Chapter 7}

\begin{SPECIALFORMS}
\begin{MANYLINES}
\code{(lambda \meta{var}} \\
\>\code{\meta{body})}
\end{MANYLINES}
 & \code{(lambda ls ls)} 
 & makes a procedure that returns its argument list
\end{SPECIALFORMS}
\\
Note that this version of lambda is for defining procedures that take many
arguments, like {\tt list}, {\tt writeln}, and {\tt error}.
The normal version was described in Chapter 2.
The {\meta{var}} in an unrestricted {\code{lambda}}
is {\em not\/} an expression, but a the name of the parameter list.

\subsection{Procedures that take Procedures as Arguments}

\begin{OPERATIONS}
\code{map}
 & ($\rArr$ (($\rArr$ (S) T) (list S)) (list T))
 &  \\
\code{for-each}
 & ($\rArr$ (($\rArr$ (S) void) (list S)) void)
 &  \\
\code{apply}
 & ($\rArr$ (($\rArr$ (datum $\ldots$) T) (list datum)) T)
 &
\end{OPERATIONS}

You may wish to make a similar table for the examples in this
chapter of procedures that return procedures as arguments.
None of these are built in to Scheme, but a few examples follow
below to help you get started.

\begin{OPERATIONS}
\code{compose} 
 &  ($\rArr$ (($\rArr$ (T) U) ($\rArr$ (S) T)) ($\rArr$ (S) U))
 & \\
\code{member-c?} 
 &  ($\rArr$ (T) ($\rArr$ ((list T)) boolean))
 & \\
\code{apply-to-all}
 &  ($\rArr$ (($\rArr$ (S) T)) ($\rArr$ ((list S)) (list T)))
 &
\end{OPERATIONS}

\subsection{Procedural Abstractions of Flat and Deep Recursion}

\begin{OPERATIONS}
\code{flat-recur} 
 & ($\rArr$ (T ($\rArr$ (S T) T)) ($\rArr$ ((list S)) T))
 & \\
\code{deep-recur} 
 & \begin{MANYLINES}
   ($\rArr$ (T ($\rArr$ (S T) T) ($\rArr$ (T T) T)) \\
   \> ~~($\rArr$ ((tree S)) T))
   \end{MANYLINES}
 & \\
\code{deep-recur-abs}
 & \begin{MANYLINES}
  ($\rArr$ (T ($\rArr$ (S T) T) ($\rArr$ (T T) T) ($\rArr$ (datum) boolean)) \\
 \> ~~($\rArr$ ((tree S)) T))
   \end{MANYLINES}
 &
\end{OPERATIONS}

The procedure {\code{deep-recur-abs}} is my own invention,
and will be discussed in class.

\section{Chapter 8}

\subsection{Basic Procedures for Sets}

\begin{OPERATIONS}
\code{the-empty-set} 
 & (set T)
 & \\
\code{empty-set?} 
 & ($\rArr$ ((set T)) boolean)
 & \\
\code{set?} 
 & 
 & \\
\code{pick} 
 & & \\
\code{residue} 
 & & \\
\code{adjoin} 
 & &
\end{OPERATIONS}

\subsection{Basic Procedures for Ordered Pairs}

\begin{OPERATIONS}
\code{make-op} 
 & ($\rArr$ (S T) (ordered-pair S T))
 & \\
\code{op?} 
 & 
 & \\
\code{op-1st} 
 & ($\rArr$ ((ordered-pair S T)) S)
 & \\
\code{op-2nd} 
 & & 
\end{OPERATIONS}

\section{Chapter 9}

\subsection{Vectors}

\begin{OPERATIONS}
\code{make-vector} 
 & (and ($\rArr$ (integer) (vector datum))
        ($\rArr$ (integer T) (vector T)))
 & \code{(make-vector 2 'x)} \\
\code{list->vector} 
 & ($\rArr$ ((list T)) (vector T))
 & \\
\code{vector} 
 & ($\rArr$ (T $\ldots$) (vector T))
 & \\
\code{vector?} 
 & & \\
\code{vector-generator}
 & \begin{MANYLINES}
    ($\rArr$ (($\rArr$ (natural) T)) \\
   \> ~~($\rArr$ (natural) (vector T)))
   \end{MANYLINES}
 & \\
\code{vector-length}
 & & \\
\code{vector-ref} 
 & & \\
\code{vector-set!} 
 & ($\rArr$ ((vector T) integer T) void) & 
\end{OPERATIONS}

The procedure {\code{vector-generator}} is not built-in to Scheme,
but is one of the basic procedures for vectors.

\subsection{Basic Procedures for Matrices}

\begin{OPERATIONS}
\code{matrix-generator}
 & \begin{MANYLINES}
    ($\rArr$ (($\rArr$ (natural natural) T)) \\
   \> ~~($\rArr$ (natural natural) (matrix T)))
   \end{MANYLINES}
 & \\
\code{matrix-ref}
 & \begin{MANYLINES}
    ($\rArr$ ((matrix T)) \\
   \> ~~($\rArr$ (natural natural) (matrix T)))
   \end{MANYLINES}
 & \\
\code{matrix-rows} 
 & & \\
\code{matrix-cols} 
 & & \\
\code{matrix-set!}
 & \begin{MANYLINES}
    ($\rArr$ ((matrix T)) \\
   \> ~~($\rArr$ (natural natural T) void))
   \end{MANYLINES}
 & 
\end{OPERATIONS}

\section{Chapter 10}

\subsection{Timing}

\begin{OPERATIONS}
\code{timer} 
 & ($\rArr$ (($\rArr$ (datum) datum) datum) void)
 &
\end{OPERATIONS}

\subsection{Relational Calculus}

\begin{OPERATIONS}
\code{unlist} 
 & ($\rArr$ (($\rArr$ (datum $\ldots$) T)) ($\rArr$ (list datum) T))
 &
\end{OPERATIONS}

\section{Chapter 11}

\begin{SPECIALFORMS}
\code{(set!~\meta{var} \meta{val})}
 & \code{(set!~x (+ x 7))} 
 &
\end{SPECIALFORMS}

\subsection{List Mutation}

\begin{OPERATIONS}
\code{set-car!} 
 & ($\rArr$ ((pair S T) S) void)
 &  \\
\code{set-cdr!} 
 & 
 &
\end{OPERATIONS}

\section{Chapter 12}

\begin{SPECIALFORMS}
\begin{MANYLINES}
\code{(case \meta{target}} \\
\> \code{((\meta{key$_{1,1}$} \meta{key$_{1,2}$} $\ldots$) \meta{body$_1$})} \\
\> $\ldots$ \\
\> \code{((\meta{key$_{n,1}$} \meta{key$_{n,2}$} $\ldots$) \meta{body$_n$})} \\
\> \code{(else \meta{body$_{n+1}$}))} \\
\end{MANYLINES}
 & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 &
\end{SPECIALFORMS}

A {\meta{key}} is syntactically an expression, but is interpreted as if
it were quoted.

\subsection{Operations for Boxes}

\begin{OPERATIONS}
\code{box-maker}
 & ($\rArr$ (T) (box T))
 &  \\
\code{send type}
 & ($\rArr$ ((box T)) symbol)
 &  \\
\code{send show}
 & ($\rArr$ ((box T)) T)
 &  does not print anything \\
\code{send update!}
 & ($\rArr$ ((box T) T) void)
 & \code{(send update! my-box 3)} \\
\code{send swap!}
 & ($\rArr$ ((box T) T) T)
 & \\
\code{send reset!}
 & ($\rArr$ ((box T)) void)
 &
\end{OPERATIONS}

We write {\code{send}} before the names of instance operations,
to show that they are not truly procedures with the types indicated,
but the names of messages.

\subsection{Operations for Counters}

\begin{OPERATIONS}
\code{counter-maker}
 &  ($\rArr$ (T ($\rArr$ (T) T)) (counter T))
 &  \\
\code{send type}
 & 
 & \\
\code{send show}
 & 
 & \\
\code{send update!}
 & ($\rArr$ ((counter T)) void)
 & \code{(send update! my-counter)} \\
\code{send reset!}
 &
 &
\end{OPERATIONS}

There are too many other types in chapter 12 to describe them all here.
But you may want to describe them all for yourself using these examples
to get you started.

\section*{Where to Look for More Details}

R. Kent Dybvig's book {\em The Scheme Programming Language\/}
(1987, Prentice-Hall) describes the whole language.
The current defining document for Scheme is
the ``Revised$^4$ Report on the Algorithmic Language Scheme,''
edited by W. Clinger and J. Rees (Nov. 2, 1991).
The ``Revised$^3$ Report'' was published in {\em ACM SIGPLAN Notices},
volume 21, number 12 (December 1986), pages 37--79.

The type system used in this document is similar to that 
originated by R. Milner and used in the programming language Standard ML
(See ``A Theory of Type Polymorphism in Programming,''
{\em Journal of Computer and System Sciences\/}, volume 17, number 3
(December 1978), pages 348--375.)
A more tutorial presentation of this kind of type system is found in
the survey article 
``On Understanding Types, Data Abstraction and Polymorphism,''
by L. Cardelli and P. Wegner, which appears in {\em ACM Computing Surveys\/},
volume 17, number 4 (December 1985), pages 471--522.
The idea of the type ``datum'' arises from the idea of subtyping,
although the name itself comes from the book
{\em Essentials of Programming Languages\/}, by
D. P. Friedman, M. Wand, and C. T. Haynes (McGraw-Hill, 1992).

\section*{Acknowledgements}

Thanks to the student management team of Spring 1993 for notational
suggestions, and the Chris Haynes for a discussion on notation.
Thanks to P. Wadler for a discussion about the type of call/cc
which solidified my idea of the type ``poof'' as a subtype of every type.

\end{document}

