% reference manual for watML, typeset in latex

% to typeset: latex manual.tex
% to view: xdvi manual
% to print: lpr -Fd -Pic manual.dvi

\documentstyle[clbiba,11pt]{article}

\setlength{\textwidth}{18cm}
\setlength{\textheight}{23cm}
\setlength{\topmargin}{-1.5cm}
\setlength{\oddsidemargin}{-1.1cm}

\begin{document}
\title{watML}
\author{Luca Cardelli \\ Malcolm Newey \\ John Ophel}
\date{}

\maketitle

\begin{abstract}
watML is a dialect of standard ML. It includes a more general overloading
scheme for overloading than in ML. This manual describes watML and ML.

ML is a statically-scoped
{\bf functional}
programming language. Functions are first-class objects which can be passed
as parameters, returned as values and embedded in data structures. Higher-order
functions (i.e., functions receiving or producing other functions) are
used extensively.

ML is an {\bf interactive}
language. An ML session is a dialogue of questions and answers with the
ML system.  Interaction is achieved by an incremental compiler, which has
some of the advantages of interpreted languages (fast turnaround dialogues)
and of compiled languages (high execution speed).

ML is a {\bf strongly} {\bf typed}
language. Every ML expression has a type, which is determined statically.
The type of an expression is usually automatically inferred by the system,
without need of type definitions. The ML type system guarantees that any 
expression that can be typed will not generate type errors at run time.
Static typechecking traps at compile time a large proportion of bugs in
programs.

ML has a {\bf polymorphic} {\bf type} {\bf system}
which confers on the language much of the flexibility of type-free languages,
without paying the conceptual cost of run-time type errors or
the computational cost of run-time typechecking.

ML has a rich collection of data types. Moreover the user can define new
{\bf abstract} {\bf data} {\bf types},
which are indistinguishable from the system pre-defined types. Abstract
data types
are used extensively in large programs for modularity and abstraction.

ML has an {\bf exception-trap}
mechanism, which allows programs to handle uniformly system and user
generated exceptions. Exceptions can be selectively trapped, and exception
handlers can be specified.

watML programs can be grouped into {\bf modules} (different from
standard ML modules),
which can be separately compiled. Dependencies among modules can be easily
expressed, and the sharing of common submodules is automatically guaranteed.
The system keeps track of module versions to detect compiled modules which
are out of date.

This manual describes watML, an implementation of ML running on various
machines (including Vaxes, Suns and Pyramids) under
the Unix\footnote{Unix is a trade mark of American Telephone and
Telegraph Company
(AT\&T).} operating system.  This implementation is descended from ANU ML
which in turn was descended from the ML Pose3 compiler of Cardelli.
\end{abstract}

\newpage
\noindent{\bf Contents}
\begin{itemize}
\item[{1.}] {\bf Introduction}
\begin{itemize}
\item[{1.2}] \ \ Expressions
\item[{1.3}] \ \ Declarations
\item[{1.4}] \ \ Scope Blocks
\item[{1.5}] \ \ Lists
\item[{1.6}] \ \ Functions
\item[{1.7}] \ \ Polymorphism
\item[{1.8}] \ \ Higher-order functions
\item[{1.9}] \ \ Overloading and Implicit Parameters
\item[{1.10}] \ \ Exceptions
\item[{1.11}] \ \ Types
\item[{1.12}] \ \ Type Abbreviations
\item[{1.13}] \ \ Concrete Data Types
\item[{1.14}] \ \ Abstract Data Types
\item[{1.15}] \ \ Interacting with the ML system - the Read-Eval loop
\item[{1.16}] \ \ Errors
\item[{1.17}] \ \ Editing and debugging
\end{itemize}
\item[{2.}] {\bf Lexical matters}
\begin{itemize}
\item[{2.1}] \ \ Reserved Words
\item[{2.2}] \ \ Identifiers
\item[{2.3}] \ \ Integers and Reals
\item[{2.4}] \ \ Strings
\item[{2.5}] \ \ Comments
\end{itemize}
\item[{3.}] {\bf Expressions}
\begin{itemize}
\item[{3.1}] \ \ Unit
\item[{3.2}] \ \ Booleans
\item[{3.3}] \ \ Numbers
\item[{3.4}] \ \ Tuples
\item[{3.5}] \ \ Records
\item[{3.6}] \ \ Lists
\item[{3.7}] \ \ Strings
\item[{3.8}] \ \ Updatable references
\item[{3.9}] \ \ Arrays
\item[{3.10}] \ \ Patterns and matches
\item[{3.11}] \ \ Functions
\item[{3.12}] \ \ Application
\item[{3.13}] \ \ Conditional
\item[{3.14}] \ \ Sequencing
\item[{3.15}] \ \ While
\item[{3.16}] \ \ Case
\item[{3.17}] \ \ Let
\item[{3.18}] \ \ Exceptions and exception handling
\item[{3.19}] \ \ Equality
\end{itemize}
\item[{4.}] {\bf Type expressions}
\begin{itemize}
\item[{4.1}] \ \ Type variables
\item[{4.2}] \ \ Basic types and type constructors
\item[{4.3}] \ \ Record types
\end{itemize}
\item[{5.}] {\bf Declarations}
\begin{itemize}
\item[{5.1}] \ \ Value bindings
\item[{5.2}] \ \ Clausal function definitions
\item[{5.3}] \ \ Overloading and implicit parameters
\item[{5.4}] \ \ Type bindings
\item[{5.5}] \ \ Data type bindings
\item[{5.6}] \ \ Abstract type declarations
\item[{5.7}] \ \ Local declarations
\item[{5.8}] \ \ Sequential declarations
\item[{5.9}] \ \ Import declarations
\item[{5.10}] \ \ Lexical declarations
\end{itemize}
\item[{6.}] {\bf I/O streams}
\item[{7.}] {\bf Modules}
\begin{itemize}
\item[{7.1}] \ \ Module hierarchies
\item[{7.2}] \ \ Module sharing
\item[{7.3}] \ \ Module versions
\end{itemize}
\item[{8.}] {\bf The ML system}
\begin{itemize}
\item[{8.1}] \ \ Entering the system
\item[{8.2}] \ \ Exiting the system
\item[{8.3}] \ \ Calling the operating system from ML
\item[{8.4}] \ \ Error messages
\item[{8.5}] \ \ Monitoring the compiler
\item[{8.6}] \ \ Garbage collection and storage allocation
\end{itemize}
\item[{9.}] {\bf Editing and Debugging}
\begin{itemize}
\item[{9.1}] \ \ Basic concepts
\item[{9.2}] \ \ Editing commands
\item[{9.3}] \ \ Operations on source files
\item[{9.4}] \ \ Retests in AIMLESS
\item[{9.5}] \ \ Tracing functions
\end{itemize}
\end{itemize}

\noindent
References

\noindent
Appendix A: Lexical classes

\noindent
Appendix B: Syntax of ML

\noindent
Appendix C: Predefined identifiers

\noindent
Appendix D: Differences From Standard ML

\noindent
Appendix E: Transient Errors in watML

\noindent
Appendix F: System Limitations


\newpage
\section{Introduction}

ML is a {\it functional}
programming language. Functions are first-class objects which can be passed
as parameters, returned as values and embedded in data structures. Higher-order
functions (i.e., functions receiving or producing other functions) are
used extensively. Function application is the most important control construct,
and it is extremely uniform: all functions take exactly one argument and return
exactly one result. Arguments and results can however be arbitrary structures,
thereby achieving the effect of passing many arguments and producing many
results. Arguments to functions are evaluated before the function calls.

ML is an {\it interactive}
language. An ML session is a dialogue of questions and answers with the ML
system. Interaction is achieved by an incremental compiler, which has some of
the advantages of interpreted languages (fast turnaround dialogues) and of
compiled languages (high execution speed).

ML is {\it statically scoped}.
All identifiers are associated with values according to
where they occur in the program text, and not depending on run-time execution
paths. This avoids name conflicts in large programs, because names (of
variables and types)
can be hidden in local scopes, and prevents accidental damage to pre-existing
programs. Static scoping greatly improves the security and, incidentally,
the efficiency of an interactive language, and it is necessary for implementing
higher-order functions with their conventional mathematical meaning.

ML is a {\it strongly typed}
language. Every ML expression has a type, which is determined statically.
The type of an expression is usually automatically inferred by the system,
without need for type definitions. This {\it type inference}
property is very useful in interactive use, when it would be distracting
having to provide all the type information. However, it is always possible
to specify the type of any expression or function, e.g., as good documentation
practice in large programs. The ML type system guarantees that any expression
that can be typed will not generate type errors at run time (for some adequate
definition of what a type error is). Static typechecking traps at compile time
a large proportion of bugs in programs that make extensive use of the ML
data structuring capabilities (typechecking does not help in numerical
programs!). Usually, only truly ``logical'' bugs are left after compilation.

ML has a {\it polymorphic type system}.
Type expressions may contain type variables, indicating, for example, that
a function can work uniformly on a class of arguments of different
(but structurally related) types.  For example, the {\tt length}
function, which computes the length of a list of values of type,
has type {\bf $\alpha$ list $\rightarrow$ int}
(which is automatically inferred from the
obvious untyped recursive definition). Length can work on lists of any type
(lists of integers, lists of functions, lists of lists, etc.), essentially
because it disregards the elements of the list. The polymorphic
type system confers on ML much of the flexibility of type-free languages,
without paying the conceptual cost of run-time type errors or
the computational cost of run-time typechecking.

ML has a rich collection of data types. Moreover the user can
define new {\it abstract data types},
which are indistinguishable from the system predefined types. Abstract data
types are used extensively in large programs for modularity and abstraction.
They put a barrier between the implementor of a package and its users, so
that changes in the implementation of an abstract type will not influence
the users, as long as the external interface is preserved.
Abstract data types also provide a clean extension mechanism for the language.
If a new data type is needed which cannot be effectively implemented
with the existing ML primitives (e.g., bitmaps for graphics), this can
be still specified and prototyped in ML as a new abstract data type, and
then efficiently implemented and added to the basic system. This path has
already been followed for arrays, which are not part of the language
definition and can be considered as a predefined abstract data type which just
happens to be more efficient than its ML specification would lead one to
believe.

ML has an {\it exception-trap}
mechanism, which allows programs to uniformly handle system and user
generated exceptions. Exceptions can be selectively trapped, and
handlers can be specified.

watML programs can be grouped into {\it modules},
which can be separately compiled. Dependencies among modules can be easily
expressed, and the sharing of common submodules is automatically guaranteed.
The system keeps track of module versions to detect compiled modules which
are out of date.

While this document is principally concerned with describing the language
ML, it is tailored to a particular implementation known as watML. This
system is based on the ANU ML compiler, which is turn was
based on a compiler due to Luca Cardelli and described in the
document ``ML under Unix'' [Cardelli,1983].  The migration of that early
version of ML, and its retargeting, had been conducted at ANU from 1984-1990,
principally by Malcolm Newey and John Ophel.  Gordon
Keith also contributed with work on the Pyramid implementation.  watML
implements core standard ML (ML without modules) and includes
extensions for overloading and implicit parameters. Where watML and ML
are not equivalent is noted in the manual.

The present document is based on the ANU ML which (again) in turn
is based on the Cardelli manual.

\subsection{Expressions}

ML is an expression-based language; all the standard programming
constructs (conditionals, declarations, procedures, etc.) are packaged
into expressions yielding values. Strictly speaking there are no statements:
even side-effecting operations return values.

It is always meaningful to supply arbitrary expressions as arguments to
functions (when the type constraints are satisfied), or to combine
them to form larger expressions in the same way that simple constants can
be combined.

Arithmetic expressions have a fairly conventional appearance; the result of
evaluating an expression is presented as a value and its type separated by a
colon:

\begin{quote}
\begin{verbatim}
expression:             (3 + 5) * 2;

result:                 16 : int
\end{verbatim}
\end{quote}

Sequences of characters enclosed in quotes `{\tt "}' are called {\it strings} :
\begin{quote}
\begin{verbatim}
expression:             "this is it";

result:                 "this is it" : string
\end{verbatim}
\end{quote}

Tuples of values are enclosed in parentheses and their elements are
separated by commas;
the type of a tuple is given using the infix type operator {\tt *},
which denotes cartesian products.

\begin{quote}
\begin{verbatim}
expression:             (3,"abc");

result:                 (3,"abc") : int * string

expression:             (3,4,(true,"xyz"));

result:                 (3,4,(true,"xyz")) : int * int * (bool * string)
\end{verbatim}
\end{quote}

ML provides records as sets of labelled fields, where each field (identified
by its label) will have some particular type.  Records are enclosed in braces
and the fields, separated by commas, may appear in any order;  labels are
identifiers or integers.  The type of a record is determined by the set of
label/type pairs for the fields.

\begin{quote}
\begin{verbatim}
expression:             {name="john", age=22};

result:                 {age=22, name="john"} : {age:int, name:string}

expression:             {3=1, 2="a", 1=true};

result:                 (true,"a",1) : bool * string * int
\end{verbatim}
\end{quote}
\noindent
The (perhaps) surprising response of the ML system in the last example is
due to the (not too surprising) fact that n-tuples are syntactic sugar for
records with {\it n} fields labelled  1, 2, .. {\it n}.

Lists are enclosed in square brackets and their elements are separated
by commas. The {\tt list} type operator is a suffix: {\tt int list}
means list of integers.

\begin{quote}
\begin{verbatim}
expression:             [1, 2, 3, 4];

result:                 [1, 2, 3, 4] : int list

expression:             [(3,4), (5,6)];

result:                 [(3,4), (5,6)] : (int * int) list

\end{verbatim}
\end{quote}

Conditional expressions have the ordinary if-then-else syntax.  (The else
part is not optional.)

\begin{quote}
\begin{verbatim}
expression:             if true then 3 else 4;

result:                 3 : int

expression:             if (if 3 = 4 then false else true)
                        then false
                        else true;

result:                 false : bool
\end{verbatim}
\end{quote}

\noindent
The {\tt if} part must be a boolean expression; two predefined
constants {\tt true} and {\tt false} denote the basic boolean values;
standard boolean operators, including {\tt not}, {\tt \&} (and) and {\tt or},
are provided.

Selection between several choices is possible using a {\tt case}
expression.

\begin{quote}
\begin{verbatim}
expression:             case (5 - 4) of 0 => 2 |  1 => 3 |  _ => 99;

result:                 3 : int
\end{verbatim}
\end{quote}

\noindent
The result of computing {\tt (5-4)} matches the left hand side
of the second match rule, so the result of the case expression is the right
hand side of that same match rule. Any integer would match the underbar
symbol but matching is done from left to right.

\subsection{Declarations}

Variables can be bound to values by {\it declarations}.
Declarations can appear at the `top-level', in which case their scope is
{\it global}, or in scope blocks, in which case they are have a limited
{\it local} scope spanning a single expression.
Global declarations are introduced in this section, and local declarations
in the next one.

Declarations are not expressions: they establish bindings instead
of returning values. Value bindings are introduced by the keyword {\tt val},
additional value bindings are prefixed by {\tt and}:

\begin{quote}
\begin{verbatim}
declaration:            val a = 3  and  b = 5  and  c = 2;

bindings:               val a = 3 : int
                        val b = 5 : int
                        val c = 2 : int

expression:             (a + b) div c;

result:                 4 : int
\end{verbatim}
\end{quote}

\noindent
In this case we have defined the variables {\tt a}, {\tt b} and {\tt c}
at the top level;
they will always be accessible from now on, unless redefined. Value bindings
printed by the system are always prefixed by {\tt val}, to distinguish them
from {\tt type} bindings and {\tt module}
bindings which we shall encounter later.

You may notice that all the variables must be initialized when introduced.
Their initial values determine their types, which do not need to be given
explicitly. The type of an expression is generally inferred automatically
by the system and printed after the result.

Value declarations can also be used to define functions, but the following
syntax is more readable:

\begin{quote}
\begin{verbatim}
declaration:            fun f(x) = x + 1;

binding:                val f = fn: int -> int

declaration:            fun g(a,b) = (a + b) div 2;

binding:                val g = fn: (int * int) -> int

expression:             (f 3, g(8,4));

result:                 (4,6) : int * int

\end{verbatim}
\end{quote}

\noindent
The function {\tt f} obviously has one argument {\tt x}.  We may think
of the function {\tt g} above as having a pair of arguments, {\tt a} and
{\tt b}; in fact, it has one argument which is a pair of
integers.  The arrow symbol `{\tt -{\char '76}}' appears in the expression for
the type of a function to indicate a mapping; it is preceded by the
type of the function's argument and is followed by the type of the
function's result.

The result of
a function is just the value of its body, in this case {\tt x+1}.
Arguments to functions do not need to be parenthesized in general (both in
definitions and applications): the simple juxtaposition of two expressions is
interpreted as a function application. Function application is treated as
an invisible infix operator, and it is the strongest-binding infix
operator.  Consequently, expressions like {\tt f 3 + 4} are parsed
like {\tt (f 3) + 4} and not like {\tt f (3 + 4)}.

The identifiers {\tt f} and {\tt g} are plain variables which denote functions.
Function  variables do not need to be applied to arguments:

\begin{quote}
\begin{verbatim}
expression:             (f, f 3);

result:                 (fn,4) : (int -> int) * int

declaration:            val h = g;

binding:                val h = fn : (int * int) -> int
\end{verbatim}
\end{quote}

\noindent
In the first example above, {\tt f}
is returned as a function and is paired with
a number. Functional values are always printed {\tt fn}, without showing their
internal structure. In the second example, {\tt g} is bound to {\tt h}
as a whole function. Instead of {\tt val h = g}
we could also have written {\tt val h(a,b) = g(a,b)}.

Variables are statically scoped, and their types cannot change.
When new variables are defined, they may `hide' previously defined
variables having the same name, but they never `affect' them. For example:

\begin{quote}
\begin{verbatim}
declaration:            fun f x = a + x;

binding:                val f = fn : int -> int

declaration:            val a = [1,2,3];

binding:                val a = [1,2,3] : int list

expression:             f 1;

result:                 4 : int
\end{verbatim}
\end{quote}

\noindent
Here the function {\tt f} uses the top-level variable {\tt a},
which was bound to {\tt 3} in a previous example. Hence {\tt f} is a function
from integers to integers which returns its argument plus 3.
When {\tt a} is redefined at
the top level to be a list of three integers; any subsequent reference to
{\tt a} will yield that list (unless {\tt a} is redefined again). But {\tt f}
is not affected at all: the old value of {\tt a} was `frozen' in {\tt f}
at the moment of its definition, and {\tt f} keeps adding 3 to its arguments.

This kind of behavior is called {\it lexical} or {\it static}
scoping of variables. It is quite common in block-structured programming
languages,
but it is rarely used in languages which, like ML, are interactive. The use of
static scoping at the top-level may sometimes mislead.
For example, if a function {\tt f} calls a previously defined function {\tt g},
then a subsequent definition of {\tt g} which was intended to fix
a bug in that function will not change {\tt f}, which will
keep calling the old (erroneous) version of {\tt g}.  On the other hand, if
function {\tt F} uses some auxiliary function {\tt Fx} in its definition, then
its behaviour will not be changed by the inadvertent redefinition of {\tt Fx}.

\subsection{Scope Blocks}

Declarations can be made within an expression by embedding them between the
keywords {\tt let} and {\tt in} in a scope-block construct.
Following the keyword {\tt in} there is an expression, called the
{\it body} of the scope-block, terminated by the keyword {\tt end}.
The scope of the declaration is limited to this body.

\begin{quote}
\begin{verbatim}
expression:             let
                          val a = 3
                          and b = 5
                        in
                          (a + b) div 2
                        end;

result:                 4 : int
\end{verbatim}
\end{quote}

\noindent
Here the identifiers {\bf a} and {\bf b} are bound to the values {\bf 3 }
and {\bf 5 } respectively for the extent of the expression {\bf (a + b) div 2}.
No top-level binding is introduced; the whole {\bf let } construct is an
expression whose value is the value of its body.

Variables can be locally redefined, hiding the previous definitions for the
extent of the local scope. Outside the local scope, the old definitions
are not changed:

\begin{quote}
\begin{verbatim}
declaration:            val a = 3  and  b = 5;

bindings:               val a = 3 : int
                        val b = 5 : int

expression:             ((let val a = 8 in a + b end), a);

result:                 (13,3) : int * int
\end{verbatim}
\end{quote}

\noindent
The body of a scope-block can access all the variables declared
in the surrounding environment (like {\bf b}), unless they are redefined
(like {\bf a}).

The same technique can be used to introduce names with locality
that is just a declaration, as illustrated below.  The scope of the declaration
following the keyword {\bf local} is just the declaration that follows the
keyword {\bf in}.  This again is the body of the scope-block.

\begin{quote}
\begin{verbatim}
declaration:            local val a = 3 in val b = a+10;

bindings:               val b = 13 : int
\end{verbatim}
\end{quote}

\noindent
The binding of 3 to {\bf a} is local to the definition of {\bf b}.  A
previous value of {\bf a}, if one exists, is reinstated;  the phrase only
introduces a binding for {\bf b}.

The {\bf and} keyword is used to define sets of independent bindings: none
of them can use the variables defined by the other bindings. However,
a declaration often needs variables introduced by previous declarations.
At the top-level this is done by introducing those declarations
sequentially, as we have seen before.  When several declarations are typed
on the same line, the pattern of interaction is slightly different but
only because lines of ML code are never parsed by the system until complete.

\begin{quote}
\begin{verbatim}
declarations:           val a = 3; val b = 2 * a;

bindings:               val a = 3 : int
                        val b = 6 : int

\end{verbatim}
\end{quote}

The semi-colon is optional between declarations; in the syntax of ML all
declarations start with a keyword and can therefore be recognized.

\begin{quote}
\begin{verbatim}
declarations:           val a = 3 val b = 2 * a;

bindings:               val a = 3 : int
                        val b = 6 : int

\end{verbatim}

Declarations can also be composed sequentially in local scopes.

\begin{quote}
\begin{verbatim}
expression:             let
                          val a = 3
                          val b = 2 * a
                        in
                          (a,b)
                        end;

result:                 (3,6) : int * int
\end{verbatim}
\end{quote}

In simple cases, the effect of `{\bf ;}' can be achieved by nested scope blocks;
here is an equivalent formulation of the previous example:

\begin{quote}
\begin{verbatim}
expression:             let
                          val a = 3
                        in
                          let
                            val b = 2 * a
                          in
                            (a,b)
                          end
                        end;

result:                 (3,6) : int * int
\end{verbatim}
\end{quote}

\subsection{Lists}

List are {\it homogeneous},
i.e., all their elements must have the same type. It is possible to create
lists of any type, e.g., lists of strings, lists of lists of integers,
lists of functions (of some given type), etc. Many functions dealing with lists
can work on lists of any kind (e.g., computing the length),
and they do not have to be rewritten every time a new kind of list is needed.
Other list functions are more specialized, like taking the sum of all the
elements in a list. Even specialized functions can often be quickly defined from
general list utilities; for example, summation can be defined by distributing
the integer sum operation by a general {\bf fold} function which folds
lists under binary operations.

The fundamental list operations are {\bf nil}, the empty list, and
the infix {\bf ::} (cons), which appends an element (its left argument)
to the head of a list (its right argument).
The square-brackets notation for lists (e.g., {\bf [1,2,3]}), is an
abbreviation for a sequence of cons operations terminated by {\bf nil};
hence {\bf []} is another way of writing {\bf nil}. The system always
uses the square-brackets notation when printing lists.

\begin{quote}
\begin{verbatim}
        nil                             is              []
        1 :: [2, 3]                     is              [1, 2, 3]
        1 :: 2 :: 3 :: nil              is              [1, 2, 3]
\end{verbatim}
\end{quote}


Other predefined operations on lists include:
\begin{itemize}
\item {\bf null}, which returns true if its argument is {\bf nil}, and false on
any other list.
\item {\bf hd}, which returns the first element of a non-empty list.
\item {\bf tl}, which strips the first element from the head of a non-empty
list.
\item {\bf @ } (append), which concatenates lists.
\end{itemize}

\begin{quote}
\begin{verbatim}
        null []                         is              true
        null [1, 2, 3]                  is              false
        hd [1, 2, 3]                    is              1
        tl [1, 2, 3]                    is              [2, 3]
        [1, 2] @ []                     is              [1, 2]
        [] @ [3, 4]                     is              [3, 4]
        [1, 2] @ [3, 4]                 is              [1, 2, 3, 4]
\end{verbatim}
\end{quote}

\subsection{Functions}

All functions take exactly one argument and deliver exactly one result.
However arguments and results can be arbitrary structures, thereby achieving
the effect of passing multiple arguments and returning multiple results.
For example:

\begin{quote}
\begin{verbatim}
declaration:            fun divide(a,b) = a div b;

\end{verbatim}
\end{quote}

\noindent
the function {\bf divide} above takes a {\it single} argument {\bf (a,b)},
which is a pair of values. This could seem to be a pointless
distinction, but consider the two following ways of using {bf divide}:

\begin{quote}
\begin{verbatim}
expression:             divide(3,4);

expression:             let val x = (3,4)
                        in divide x end;
\end{verbatim}
\end{quote}

\noindent
The first use of {\bf divide} is the standard one: two arguments {\bf 3} and
{\bf 4} seem to be supplied to it. However we have seen that `{\bf ,}'
is a pair-building operator, and it constructs the pair {\bf (3,4)}
{\it before} applying {\bf divide} to it\footnote{This is true conceptually;
in practice a compiler can optimize away
the extra pair constructions in most situations.}.
This is clearer in the second use of {\bf divide}, where {\bf divide} receives
a single argument, which is actually a pair of values.

As every function actually has a single argument, we can put every function
definition in the `normal' form {\bf fun f x = ..}.  For example, We can
put the definition of {\bf divide} in this form as follows:

\begin{quote}
\begin{verbatim}
declaration:            fun divide x = let val (a,b) = x in a div b end;
\end{verbatim}
\end{quote}

\noindent
What we did in the previous definitions of {\bf divide} was to use a
{\it pattern} {\bf (a,b)} for {\bf x}, which implicitly associated {\bf a}
and {\bf b} respectively with the first and second components of {\bf x}.
These patterns come in many forms.
For example a pattern {\bf [a,b,c]} matches a list of
exactly three elements, which are bound to {\bf a}, {\bf b} and {\bf c};
a pattern {\bf first::rest} matches a non-empty list whose first element is
associated with {\bf first}, and the rest of the list to {\bf rest};
similarly {\bf first::second::rest} matches a list of at least two elements;
etc. The most common patterns are of course tuples, like {\bf (a,b,c)},
but more complicated patterns can be
constructed by nesting, like {\bf (([a,b],c,(d,e))::\_)}.
The special pattern {\bf \_} matches any value without establishing any binding.
Patterns can conveniently replace the
use of selector functions for unpacking data.

Patterns do not only appear in function
parameters: they can also be used in simple variable declarations:

\begin{quote}
\begin{verbatim}
declaration:            fun f[a,b] = (a,b);

binding:                val f = fn : 'a list -> 'a * 'a

declaration:            val ((a,b),(c,d)) = (f[1,2], f["a","b"]);

bindings:               val a = 1 : int
                        val b = 2 : int
                        val c = "a" : string
                        val d = "b" : string
\end{verbatim}
\end{quote}

\noindent
In the above example we have a function {\bf f}
returning a pair of values, and the pattern {\bf (a,b)}
is used to unpack the result of {\bf f[1,2]} into
its components.  By the way the ML system generates a warning message when
{\bf f} is defined; it complains that the pattern {\bf [a,b]} is not
exhaustive.  The intent is to point out that the function has not been
defined on all lists (e.g., lists of with one element or more than two
elements).

Functions can also be introduced as lambda calculus terms as follows:

\begin{quote}
\begin{verbatim}
declaration:            val g = fn x => x+1;

binding:                val g = fn : int -> int

expression:             g 5;

result:                 6 : int
\end{verbatim}
\end{quote}


In the syntax for lambda terms, {\bf fn} is used for the abstraction operator
($\lambda$)
and is followed by the parameter of the function;  this parameter is
separated from the body of the function by {\bf ={\tt {\char '76}}}.
The parameter may be an identifier but may also be a pattern, as in
{\bf (fn (x,y)={\tt {\char '76}} x+y)}.

Functions defined using the function declaration syntax are naturally
recursive.  For example, the function {\bf factorial}, below is recursive:

\begin{quote}
\begin{verbatim}
declaration:            fun factorial n =
                              if n = 0
                                then 1
                                else n * factorial(n-1);

binding:                val factorial = fn : int -> int
\end{verbatim}
\end{quote}

Mutually recursive functions can be
defined simultaneously by using the {\bf and} connective.

\begin{quote}
\begin{verbatim}
declaration:            fun even n = if (n=0) then true
                                         else odd (n-1)
                        and odd n = if (n=0) then false
                                          else even (n-1);

binding:                val even = fn : int -> bool
                        val odd = fn : int -> bool
\end{verbatim}
\end{quote}

An equivalent way of defining factorial is using a {\bf val} definition
with the keyword {\bf rec} just before the function identifier:

\begin{quote}
\begin{verbatim}
declaration:            val rec factorial =
                                fn n => if n = 0  then 1
                                        else n * factorial(n-1);

binding:                val factorial = fn : int -> int
\end{verbatim}
\end{quote}

\noindent
The keyword {\bf rec} is needed to identify the recursive occurrence of the
identifier {\bf factorial} with its defining occurrence. If {\bf rec} is
omitted, the identifier {\bf factorial}
is searched for in the environment outside the
definition; if there were no previous definition of {\bf factorial},
an error would be reported.

The effect of {\bf rec} propagates to whole groups of definitions; this is
another way that mutually recursive functions may be defined:

\begin{quote}
\begin{verbatim}
declaration:            val rec even = fn n => .. odd ..
                                and odd = fn n => .. even .. ;
\end{verbatim}
\end{quote}

Functions can also be defined by {\it case analysis},
as a sequence of pattern-action pairs separated by vertical bars.  This
is clausal form of function definition.

\begin{quote}
\begin{verbatim}
declaration:            fun summation nil = 0 |
                            summation (head :: tail) = head + summation tail;
\end{verbatim}
\end{quote}

\noindent
The patterns are evaluated sequentially from left to right. When a pattern
matches the argument, the variables in the pattern are bound to the respective
parts of the argument, and the corresponding action is executed. It there are
several patterns matching some argument, only the first one is activated.
If all patterns fail to match some argument, a run-time exception occurs.

\subsection{Polymorphism}

A function is said to be {\it polymorphic}
when it can work uniformly over a class of arguments of different data types.
For example consider the following function, computing the length of a list:

\begin{quote}
\begin{verbatim}
declaration:            fun length nil = 0 |
                            length (_ :: tail) = 1 + length tail;

binding:                val length = fn : 'a list -> int

expression:             (length [1, 2, 3], length ["a", "b", "c", "d"]);

result:                 (3,4) : int * int
\end{verbatim}
\end{quote}

\noindent
The type of {\bf length} contains a {\it type variable} ({\bf 'a}),
indicating that any kind of list can be used; e.g., an integer list or
a string list. Any identifier or number prefixed by a prime `{\bf '}'
is a type variable.

A type is called {\it polymorphic}, or a {\it polytype},
if it contains type variables, otherwise it is called {\it monomorphic},
or a {\it monotype}.
A type variable can be replaced by any ML type to form an {\it instance}
of that type, for example, {\bf int list}
is a monomorphic instance of {\bf 'a list}.
The instance types can contain more type variables, for example
{\bf ('b * 'c) list} is a polymorphic instance of {\bf 'a list}.

Several type variables can be used in a type, and each
variable can appear several times, expressing contextual relationships between
components of a type; for example, {\bf 'a * 'a}
is the type of all pairs having
components of the same type. Contextual constraints can also be expressed
between arguments and results of functions, like in the identity function,
which has type {\bf 'a $\rightarrow$ 'a},
or the following function which swaps pairs:

\begin{quote}
\begin{verbatim}
declaration:            fun swap(x,y) = (y,x);

binding:                val swap = fn : ('a * 'b) -> ('b * 'a)

expression:             swap([],"abc");

result:                 ("abc",[]) : string * ('a list)
\end{verbatim}
\end{quote}


Incidentally, you may notice that the empty list {\bf []} is a polymorphic
object of type {\bf 'a list}, in the sense that it can be considered an empty
integer list, or an empty string list, etc..

In printing out polymorphic types, the ML system uses the type
variables {\bf 'a}, {\bf 'b}, etc. in succession
(they are pronounced `alpha', `beta', etc.), starting again
from {\bf 'a} at every new top-level declaration. After {\bf 'z} there
are {\bf 'ba} , .. {\bf 'bz}, {\bf 'ca} , .. {\bf 'cz}, etc.,
but these are rarely necessary.
Type variables are really anonymous objects, and it is not important how they
are expressed as long as the contextual relations are clear.

Several primitive functions are polymorphic. For example, we have already
encountered the list operations, whose types are:

\begin{quote}
\begin{verbatim}
        nil             : 'a list
        ::              : ('a * 'a list) -> 'a list
        null            : 'a list -> bool
        hd              : 'a list -> 'a
        tl              : 'a list -> 'a list
        @               : ('a list * 'a list) -> 'a list
\end{verbatim}
\end{quote}

\noindent
Note that if these operators were not polymorphic, we would need
different primitive operators for all possible types of list elements!
The {\bf 'a} shared by the two arguments of {\bf ::} (cons)
prevents any attempt to build lists containing objects of different
types, ensuring lists are homogeneous.

One can always determine the type of any ML function or object just by typing
its name at the top level; the object is evaluated and, as usual, its type is
printed after its value.

\begin{quote}
\begin{verbatim}
expression:             [];

result:                 [] : 'a list

expression:             hd;

result:                 fn : ('a list) -> 'a
\end{verbatim}
\end{quote}

\subsection{Higher-order functions}

ML supports higher-order functions, i.e., functions which take other functions
as arguments or deliver functions as results. A good example of use of
higher-order functions is in {\it partial application}:

\begin{quote}
\begin{verbatim}
declaration:            fun times (a:int) b = a * b;

binding:                val times = fn : int -> (int -> int)

expression:             times 3 4;

result:                 12 : int

declaration:            val twice = times 2;

binding:                val twice = fn : int -> int

expression:             twice 4;

result:                 8 : int
\end{verbatim}
\end{quote}

\noindent
Note the type of {\bf times}, and how it is applied to arguments:
{\bf times 3 4 } is read as {\bf (times 3) 4}.
Times first takes an argument {\bf 3} and
returns a function from integers to integers; this function is then
applied to {\bf 4} to give the result {\bf 12}. We may choose to give a single
argument to times (this is what is meant by partial application) to define
the function {\bf twice}, and supply the second argument later.

The function composition function, defined below, is a good example of
partial application (it also has an interesting polymorphic type). Note
how patterns are used in its definition.

\begin{quote}
\begin{verbatim}
declaration:      fun comp (f,g) x = f (g x);

binding:          val comp = fn : (('a -> 'b)  *  ('c -> 'a)) -> ('c -> 'b)

declaration:      fun fourtimes = comp(twice,twice);

binding:          val fourtimes = fn : int -> int

expression:       fourtimes 5;

result:           20 : int
\end{verbatim}
\end{quote}

\noindent
Function {\bf comp} takes two functions {\bf f} and {\bf g} as arguments,
and returns a function which when applied to an argument {\bf x} yields
{\bf f (g x)}. Composing {\bf twice} with itself, by partially applying
{\bf comp} to the pair {\bf twice,twice},
produces a function which multiplies numbers by four.
Function composition is also a predefined operator in ML; it is
called {\bf o} (infix), so that the composition of {\bf f} and {\bf g}
can be written {\bf f o g}.

Suppose now that we need to partially apply a function {\bf f} which,
like {\bf plus}, takes a pair of arguments. We could redefine {\bf f}
as {\tt val f = fn a ={\char '76} (fn b ={\char '76} f(a,b))}:
the new {\bf f} can
be partially applied, and uses the old {\bf f} with the expected
kind of arguments.

To make this operation more systematic, it is possible to write a function
which transforms any function of type, {\bf ('a * 'b) $\rightarrow$ 'c}
(which requires a pair of arguments) into a function  of type
{\bf 'a $\rightarrow$ ('b $\rightarrow$ 'c)}
(which can be partially applied); this process is usually called {\it currying}
a function:

\begin{quote}
\begin{verbatim}
declaration:       fun curry f a b = f(a,b);

binding:           val curry = fn : (('a * 'b)  -> 'c) -> ('a -> ('b -> 'c))

declaration:       fun curryplus = curry plus;

binding:           val curryplus = fn : int -> (int -> int)

declaration:       fun successor = curryplus 1;

binding:           val successor = fn : int -> int
\end{verbatim}
\end{quote}

\noindent
The higher-order function {\bf curry} takes any function {\bf f}
defined on pairs, and two arguments {\bf a} and {\bf b}, and applies {\bf f}
to the pair {\bf (a,b)}. If we now partially apply {\bf curry} to {\bf plus},
we obtain a function {\bf curryplus} which works exactly like {\bf plus},
but which can be partially applied.

\subsection{Overloading and Implicit Parameters}

Identifiers can be {\it overloaded} in watML. An overloaded identifier
can have more than one implementation; the implementation (or {\it instance})
that best fits in the current context (in a manner defined in section 5.4)
is chosen.

\begin{quote}
\begin{verbatim}
expression:           1 + 2;

result:               3 : int
\end{verbatim}
\end{quote}

\noindent
In the above example, {\bf +} is an overloaded identifier; the initial
environment has definitions for integer, real and complex instances of
{\bf +}. From context, the integer instance of {\bf +} is selected and
used to add the two integers together, to return an integer result.

New instances of an overloaded identifier can be defined.

\begin{quote}
\begin{verbatim}
declaration:          overload + = fn (x,y) => x^y;
                                    (* ^ is built-in string concatenation *)

binding:              val + = fn : string * string -> string

expression:           "ab" + "cd";

result                "abcd" : string;
\end{verbatim}
\end{quote}

An {\bf overload} declaration defines a new instance of an overloaded
identifier. This instance can then be selected and used.

If an instance cannot be chosen in the current context, an
{\it implicit parameter} is introduced. The implicit parameter signifies that
an overloaded instance could not be chosen in the original context and
must be later chosen.

\begin{quote}
\begin{verbatim}
declaration:          fun double x = x + x;

binding:              val double = [?+: 'a * 'a -> 'a] 'a -> 'a

expression:           (double 4, double 4.4);

result:               (8,8.8) : int * real
\end{verbatim}
\end{quote}

ML does not have implicit parameters. In ML only a small set
of pre-defined identifiers are overloaded, and they must be resolved
in the context in which they appear. For example, the definition of
{\bf double} in the above example would be invalid.

\subsection{Exceptions}

Certain primitive functions can only give a failure
on some argument(s). For example, on attempting division by zero, the normal
flow of execution will be interrupted and (in the absence of a suitable
{\it exception handler)} control will pass the top level with an error message
informing us that division failed:

\begin{quote}
\begin{verbatim}
expression:             1 div 0;

failure:                Unhandled exception Div
\end{verbatim}
\end{quote}

Another common exception is raised when trying to extract the head
of an empty list:

\begin{quote}
\begin{verbatim}
expression:             hd [];

failure:                Unhandled exception Hd
\end{verbatim}
\end{quote}

These are two of many (different) exceptions that are pre-declared and the
ML programmer is able to invent others, when required.  In either
case, every exception has a {\it name,}
which typically indicates the reason for failure and this name is
printed if the exception is not caught.  In the above examples {\bf Hd}
and {\bf Div} are the names of the built-in exceptions
that indicate inadmissible arguments to the built-in functions
{\bf hd} and {\bf div}, respectively.

Exceptions can be {\it trapped}
before they propagate all the way to the top level, so that alternative values
(of the same type) can be returned from the expression causing the exception.

\begin{quote}
\begin{verbatim}
expression:             hd [] handle Hd => 3;

result:                 3 : int
\end{verbatim}
\end{quote}

The construct {\bf handle Hd ={\tt {\char '76}} 3}
is termed an {\it exception handler}
and serves to trap exceptions with name {\bf Hd} which happen during the
execution of the integer expression on its left, and returns the value 3
in its place.  This handler will not trap exceptions other then the
one bound to identifier {\bf Hd} so these will continue to propagate
outwards until they become exceptions of an expression which does have
the appropriate handler.  If the (integer) expression preceding the handler
does not raise exceptions, then its value is the value of the construct
and the handler is ignored.  (In particular, the expression in the handler
will not be evaluated.)

Exceptions can be trapped indiscriminately by using the underbar symbol
in place of an exception identifier.  This works, as we shall see below,
because the syntax of handlers is defined in terms of the pattern matching
constructs that support clausal form function definition.

\begin{quote}
\begin{verbatim}
expression:             hd [] handle _ => 3;

result:                 3 : int

expression:             [hd(L) div 0] handle _ => []:int list;

result:                 [] : int list
\end{verbatim}
\end{quote}

\noindent
In the most recent example the handler is executed no matter whether
{\bf hd(L)} evaluates successfully (to an integer) or not.  If the list
is empty then the resulting {\bf Hd} exception will be handled
by the universal handler; if not,
then the division by 0 will cause an exception.

The user can generate exceptions by the {\bf raise} keyword followed by
an identifier which is the name of an exception.  Standard exceptions can
be so raised but normally the user will use those for their intended
purposes and choose to raise an exception which
is unique to some routine.  In the latter case the user must declare the
exception (and so bind it to an identifier).

\begin{quote}
\begin{verbatim}
expression:             raise Hd;

failure:                Unhandled exception Hd

declaration:            exception Emptylist;

expression:             hd [] handle _ => raise Emptylist;

failure:                Unhandled exception Emptylist
\end{verbatim}
\end{quote}

There is no real distinction between system and user generated exceptions:
both can be trapped and are reported at the top level in the same way.

The identifier bound to an exception is used to distinguish it from all
other exceptions but since the normal ML static scoping rules apply to
exception identifiers one must be careful to have the raising and handling
of one class of exception done in the scope of the identifier used.

Information may be carried with an exception as it is
propagated out through expressions and function calls to the handler
which traps it.  The item of information may be of any type
but the type ({\bf t}, say) must be declared
at the same time as the exception identifier which is then deemed
to have the type {\bf (t $\rightarrow$ exn)}. A value of this type must then be
given in the raise statement and the handler must expect to capture
a value of this type.

\begin{quote}
\begin{verbatim}
declaration:             exception badL of int list;

declaration:             fun bad(x) = raise badL [2];

expression:              bad(2) handle badL [1] => 5 | badL[2] => 7;

result:                  7 : int
\end{verbatim}
\end{quote}

\noindent
This example illustrates both the passing of information in an
{\it exception packet}
and the use of this information as a basis for pattern matching in the
handler. One should also note that exceptions are data objects and
so one may bind old exceptions to new identifiers thus:

\begin{quote}
\begin{verbatim}
declaration:            val HH = Hd;

binding:                val HH = exception H : exn
\end{verbatim}
\end{quote}
 
\subsection{Types}

Types describe the {\it structure}
of objects, i.e., whether they are numbers, tuples, lists, strings etc. In the
case of functions, they describe the structure of the function arguments
and results, e.g., {\bf int} to {\bf int} functions, {\bf string list}
to {\bf bool} functions, etc.

A type only gives information about attributes which can be computed at
compile time, and does not help distinguishing among different classes of
objects having the same structure. Hence the set of positive integers is not
a type, nor is the set of lists of length 3.

On the other hand, ML types can express structural relations inside
objects, for example that the right part of a pair must have the same
type (whatever that type is) as the left part of the pair, or that a
function must return an object of the same type as its argument (whatever
that type may be).

Types like {\bf bool}, {\bf int}, {\bf real}, {\bf complex} and {\bf string},
which do not show any internal structure, are called {\it basic}.
Compound types are built by {\it type operators} like {\bf *}
(cartesian product), {\bf list} (list) and {\bf $\rightarrow$} (function space).
Type operators are usually infix or suffix: {\bf int * int},
{\bf int list} and {\bf int $\rightarrow$ int}
are the types of integer pairs, lists and functions.
Strictly speaking, basic types are type operators which take no arguments.
Type operators can be arbitrarily nested:
e.g., {\bf ((int $\rightarrow$ int) list) list}
is the type of lists of lists of integer functions.

Type variables can be used to express polymorphic types. Polytypes are mostly
useful as types of functions, although some non-functional objects,
like {\bf [] : $\alpha$ list}, are also polymorphic. A typical example of
polymorphic function is {\bf hd : ($\alpha$ list $\rightarrow$ $\alpha$)},
which extracts the first element (of type $\alpha$) of a list
(of type $\alpha$ {\bf list)}.  The type of {\bf hd} tells us that {\bf hd}
can work on any list, and that
the type of the result is the same as the type of the elements of the list.

Every type denotes a {\it domain},
which is a set of objects, all of the given type; for example {\bf (int * int)}
is (i.e., denotes) the domain of integer pairs, and
{\bf (int $\rightarrow$ int)} is the
domain of all integer functions. An object can have several types, i.e., it can
belong to several domains. For example the identity function
{\tt (fn x={\char '76} x)}
can be said to have the type {\bf (int $\rightarrow$ int)}
as it maps any object (of type integer) to itself (of type integer),
but it is also has the type {\bf (bool $\rightarrow$ bool)}
for the same reason. The most
general type for the identity function is ($\alpha$ $\rightarrow$ $\alpha$)
because all the types of the identity are instances of it.
($\alpha$ $\rightarrow$ $\alpha$)
gives more information than ({\bf int $\rightarrow$ int}),
for instance, because the former encompasses all
the types that the identity function can have and thus expresses all
the ways that the identity function can be used. Hence
($\alpha$ $\rightarrow$ $\alpha$)
is a `better' type for {\tt (fn x={\char '76} x)}, although
{\bf (int $\rightarrow$ int)}
is not wrong.
The ML typechecker always determines the `best' type for an expression,
given the information contained in that expression.

Of course, it is unusual for Greek letters to be easily representable on
input devices, so ML adopts a convention that type variables have
identifiers that start with a quote character.  Thus we write the type
of {\tt (fn x={\char '76} x)} as {\bf 'a $\rightarrow$ 'a}.

A type constraint can be appended to an expression, in order to {\it specify}
the type of the expression:

\begin{quote}
\begin{verbatim}
expression:             3 : int;

result:                 3 : int

expression:             [(3,4), (5,6) : int * int];

result:                 [(3,4); (5,6)] : (int * int) list
\end{verbatim}
\end{quote}

\noindent
In the above examples, the type specifications following `{\bf :}'
do not really
have any effect. The types are independently inferred by the system and
checked against the specified types. Any attempt to specify a type incorrectly
will result in a type error:

\begin{quote}
\begin{verbatim}
expression:             3 : bool;

type error:             Type Clash in:  3 : bool
                        Looking  for :  bool
                        I have found :  int
\end{verbatim}
\end{quote}

However, a type specification can restrict the types inferred by the system
by constraining polymorphic objects or functions:

\begin{quote}
\begin{verbatim}
expression:             [] : int list;

result:                 [] : int list

expression:             (fn x=> x) : int -> int;

result:                 fn : int -> int
\end{verbatim}
\end{quote}

\noindent
Note that the type normally inferred for {\bf []} is {\bf 'a list}
and for {\tt (fn x={\char '76} x)} is {\bf 'a $\rightarrow$ 'a}.

Type specifications can be used in bindings:

\begin{quote}
\begin{verbatim}
declaration:            val (a : int) = 3;

declaration:            fun f (a : int, b : int) : int = a + b;

declaration:            fun f ((a,b) : int * int) = (a + b) : int;
\end{verbatim}
\end{quote}

\noindent
The last two examples are equivalent. A `{\bf : type}' just before the {\bf =}
of a function definition refers to the result type of the function.

ML uses type specifications to mean
that the object must have the same type as the
specification. The expression {\bf (3 : 'a)} is therefore invalid in ML.

New types may be defined in three ways: type abbreviations, concrete data
type declarations and abstract data type declarations.

\subsection{Type Abbreviations}

In a type abbreviation a type identifier is
introduced as shorthand for a (usually more complex) type expression.

\begin{quote}
\begin{verbatim}
declaration:            type int3 = int*int*int;

binding:                type int3 = int * int * int

expression:             (1,2,3):int3 = (1,2,3):int*int*int;

result:                 true: bool
\end{verbatim}
\end{quote}

\subsection{Concrete types}

A {\it concrete type} is a type for which {\it constructors}
are available, together with other operations. A constructor is an operation
which creates elements of some concrete type, by assembling
simpler objects of other types.

Constructors are invertible functions: whatever a constructor does,
can be undone by disassembling the parts which had been put together
by the constructor. This allows constructors (or actually, their inverses)
to be used in patterns to destructure data. We have already seen examples of
this dual usage concerning the tuple constructor `(.. , ..)' and the
{\bf list} constructors {\bf nil} and {\bf ::} (cons).

A concrete type and its constructors should be considered as a single
conceptual unit. Whenever a new concrete type is defined, its constructors
are defined at the same time. Wherever a concrete type is known, its
constructors are also known.

New concrete types and their constructors can be defined by
{\it datatype declarations} .
A data type declaration defines at the same time a new type name, the names of
the constructors for that type and the structure of the new type.
In general a new type can consist of several alternatives, separated
by `{\bf $|$}'; for each of them we have a separate constructor, followed by
the keyword {\bf of} and the type of the argument of that constructor.
The keyword {\bf of} and the succeeding type can be omitted: in this case the
constructor is also called a {\it constant} of the new type.

For example, money can be a coin of some value (in cents), a bill of
some value (in dollars), a check of some bank (a string) for some
amount (in cents), or the absence of money.

\begin{quote}
\begin{verbatim}
declaration:       datatype money = Nomoney | Coin of int | Bill of int |
                                         Check of string * int;

bindings:          datatype money = Nomoney | Coin of int | Bill of int |
                                         Check of string * int
                   con Nomoney : money
                   con Coin : int -> money
                   con Bill : int -> money
                   con Check : (string * int) -> money
\end{verbatim}
\end{quote}

\noindent
Here {\bf Nomoney}, {\bf Coin}, {\bf Bill} and {\bf Check} are {\bf money}
constructors ({\bf Nomoney} is a {\bf money} constant). Constructors can
be used like ordinary functions in expressions:

\begin{quote}
\begin{verbatim}
declaration:            val nickel = Coin 5
                        and dime = Coin 10
                        and quarter = Coin 25;
\end{verbatim}
\end{quote}
                                
They can also be used in patterns, as in the following definition; the
function {\bf amount}
returns the value (in cents) of any object of type {\bf money}.

\begin{quote}
\begin{verbatim}
declaration:            fun amount Nomoney  = 0 |
                            amount (Coin cents) = cents |
                            amount (Bill dollars) = 100 * dollars |
                            amount (Check(bank,cents)) = cents;

binding:                val amount = fn : money -> int
\end{verbatim}
\end{quote}

\noindent
Note that {\bf quarter} is not a constructor, and we cannot have a
clause {\tt amount {\bf quarter = 25}} in the above definition ({\bf quarter}
would be interpreted as a normal variable, like {\bf x}).

A type can be entirely made of constants, in which case we have something
similar to Pascal enumeration types.

\begin{quote}
\begin{verbatim}
declaration:            datatype color = Red | Blue | Yellow;
\end{verbatim}
\end{quote}

If the definition of a type involves type variables, the type is called
{\it parametric}
and all the type variables used on the right hand side of the {\bf =}
must be listed on the left hand side as type parameters: here are type
operators with one and two type parameters:

\begin{quote}
\begin{verbatim}
declaration:

     datatype 'a predicate = Predicate of 'a -> bool
     and ('b,'c) leftprojection = Leftprojection of ('b * 'c) -> 'b;

bindings:

     datatype 'a predicate = Predicate of 'a -> bool
     con Predicate : ('a -> bool) -> ('a predicate)
     datatype ('b,'c) leftprojection = Leftprojection of ('b * 'c) -> 'b
     con Leftprojection : (('b * 'c) -> 'b) -> ('b,'c) leftprojection
\end{verbatim}
\end{quote}

Types introduced using this syntax are mutually recursive. Here is how the
pre-defined {\bf list} type is defined:

\begin{quote}
\begin{verbatim}
declaration:            datatype 'a list = Nil | op :: of 'a * 'a list;

bindings:               datatype 'a list = nil | :: of 'a * ('a list)
                        con Nil : 'a list
                        con :: : ('a * ('a list)) -> ('a list)
\end{verbatim}
\end{quote}

\noindent The {\bf op} keyword is necessary as {\bf ::} is an infix
constructor.

\subsection{Abstract types}

An abstract data type is a type with a set of operations defined on it.
The structure of an abstract type is hidden from the user of the type, together
with the all the constructors of the underlying structure.
The associated operations are the only way of creating and manipulating
objects of that type. However, the hidden structure and constructors are
available while defining the operations.

An abstract data type provides an interface between the use and the
implementation of a set of operations. The structure of the type, and the
implementation of the operations, can be changed while preserving the
external meaning of the operations.

For example we can define an abstract type (additive-) {\bf color}
which is a combination of three primary colors which can each have an
intensity in the range 0..15:

\begin{quote}
\begin{verbatim}
declaration:

        abstype color = Blend of int * int * int
        with
          val white  = Blend(0,0,0)
          and red = Blend(15,0,0)
          and blue = Blend(0,15,0)
          and yellow = Blend(0,0,15)
          exception Mix
          fun mix (parts: int, Blend(red,blue,yellow): color,
                   parts': int, 
                   Blend(red',blue',yellow'): color) : color =
            if parts < 0 or parts' < 0 then raise Mix
              else let val totalparts = parts + parts'
                   in Blend(
                        (parts*red + parts'*red') div totalparts,
                        (parts*blue + parts'*blue') div totalparts,
                        (parts*yellow + parts'*yellow') div totalparts)
                   end
        end;

bindings:

        abstype color
        val white = - : color
        val red = - : color
        val blue = - : color
        val yellow = - : color
        val Mix = exception Mix: exn
        val mix = fn : (int * color * int * color) -> color
\end{verbatim}
\end{quote}

Composite colors can be obtained by mixing the primary colors in different
proportions:

\begin{quote}
\begin{verbatim}
declaration:            val green = mix(2,yellow,1,blue)
                        and black = mix(1,red,2,mix(1,blue,1,yellow))
                        and pink  = mix(1,red,2,white);
\end{verbatim}
\end{quote}

\noindent
The bindings determined by the abstract type declaration are: an abstract
type {\bf color} whose internal structure is hidden; four colors
({\bf white}, {\bf red}, {\bf blue} and {\bf yellow}, printed as {\bf -})
which are abstract objects whose structure is
hidden; and a function to mix colors. No other operation can be applied to
colors (unless defined in terms of the primitives), not even equality:
if needed, an equality on colors can be defined
as part of the abstract type definition.

An operation like {\bf mix}, which takes abstract objects and produces abstract
objects, typically uses patterns to get the representations of its arguments,
manipulates the representations, and then uses constructors to produce the
result.

As we said, the structure of abstract types and objects is hidden;
for example, any attempt to match {\bf (redpart, \_, \_)} with {\bf pink}
does not give the intensity of red in that color, but produces a type error:

\begin{quote}
\begin{verbatim}
expression:             val (redpart,_,_) = pink;

type error:             Type Clash in:  ((redpart,_,_) = pink)
                        Looking  for :  'a * 'b * 'c
                        I have found :  color
\end{verbatim}
\end{quote}

\noindent
The correct thing to do is {\tt val Blend(redpart,\_,\_) = pink},
but only where {\bf blend} is available (i.e., inside the abstract data type
declaration).

This protection mechanism allows one to change the representation of an abstract
type without affecting the programs which are already using that type. For
example we could have three pigments {\bf red}, {\bf blue} and {\bf yellow},
and let a color be a list of pigments, where each pigment can appear at most
15 times; {\bf white} would be blend {\bf []}, etc.
If we define all the operations
appropriately, nobody will be able, from the outside, to distinguish between
the two implementations of colors.

\subsection{Interacting with the ML system - the Read-Eval loop}

ML is an interactive language. It is entered by typing {\bf ml} as a Unix
command, and it is exited by typing {\bf Control-D}.

Once the system is loaded, the user types phrases (i.e., expressions, top level
declarations or commands), and some result or acknowledgement is printed.
This cycle is repeated over and over, until the system is exited.
A phrase can be
distributed over several lines by breaking it at any position where a blank
character is accepted. Several phrases can also be written on the same line;
and will be acted on when the line is complete.

When working interactively at the top level, the first two characters of every
line are reserved for system prompts.

\begin{quote}
\begin{verbatim}
                - val a = 3; fun f x = x + 1;
                > val a = 3 : int
                > val f = fn : int -> int

                - a + 1;
                  4 : int
\end{verbatim}
\end{quote}


`- ' is the normal system prompt, indicating that a top-level phrase is
expected, and `  ' is the continuation prompt indicating that the phrase on
the previous line has not been completed.
Again, all the top level expressions and declarations must be terminated by a
semicolon.

In the example above, the system responded to the first definition by
confirming the binding of the variables {\bf a} and {\bf f};
`{\tt {\char '76}\ }' marks
the confirmation of the a new binding, followed `{\tt $|$\ }' on the subsequent
lines when many variables are defined simultaneously. In general, the
prompts `{\tt {\char '76}\ }' and `{\tt $|$\ }' are followed by a variable name,
an {\bf =} sign, the new value of the variable, a `{\bf :}',
and finally the type of the variable. If the value is a
functional object, then the value is represented by {\bf fn}.

When an expression is evaluated, the system responds with a blank
prompt `{\bf \ \ }', followed by the value of the expression (just {\bf fn}
for functions and `-' for objects defined in an abstract data type),
a `{\bf :}' and the type of the expression.

The variable {\bf it} is always bound to the value of last top level expression
evaluated; {\bf it} is undefined just after loading the system,
and is not affected by declarations or by computations which for
some reason fail to terminate.

\begin{quote}
\begin{verbatim}
                - 1 + 1;
                   2 : int

                - it;
                   2 : int

                - it + 1;
                   3 : int

                - val a = 5;
                > val a = 5 : int

                - it;
                   3 : int

                - it + z;
                Unbound Identifier: z

                - it;
                   3 : int

                - 1 div 0;
                Unhandled exception Div

                - (it,it);
                   (3,3) : int * int
\end{verbatim}
\end{quote}


The {\bf it} variable is very useful in interaction, when used to access
values which have `fallen on the floor' because they have been computed as
expressions but have not been bound to any variable. {\bf it} is not a
keyword or a command, but just a plain variable (you can even temporarily
redefine it). Every time that an expression {\bf exp;}
is entered at the top level, this is considered an abbreviation
for {\tt val it = exp;}. Hence {\bf it} is statically scoped, so that old
{\bf it}s and new {\bf it}s are totally independent
and the newer simply hides the older.

\subsection{Errors}

Syntax errors report the fragment of code which could not be parsed, and
often suggest the reason for the error. The erroneous program fragment is at
most one line long; ellipses appear at its left when the source code was
longer than a line. It is important to remember that the error was found at the
{\it extreme right} of the error message.

\begin{quote}
\begin{verbatim}
        - if true then 3;
        Syntax Error: if true then 3;
        I was expecting an "else"
\end{verbatim}
\end{quote}

Identifiers, type identifiers and type variables can be undefined; here
are the messages given in those situations (type variables must be present
on the left of a type definition whenever they are used on the right):

\begin{quote}
\begin{verbatim}
        - noway;
        Unbound Identifier: noway

        - 3 : noway;
        Unbound Type Identifier: noway

        - type t = 'noway
        Unbound Type Variable: 'noway
\end{verbatim}
\end{quote}

Type errors show the context of occurrence of the error and the two types
which could not be matched. The context might not correspond exactly
to the source code because it is reconstructed from internal data structures.

\begin{quote}
\begin{verbatim}
        - 3 + true;
        Type Clash in:  (3 + true)
        Looking  for :  int
        I have found :  bool
\end{verbatim}
\end{quote}

The example above is a common matching type error. A different kind of
matching error can be generated by self-application, and in general
by constructs leading to circularities in the type structures:

\begin{quote}
\begin{verbatim}
        - fn x=> x x;
        Type Clash  in: (x x)
        Attempt to build a self-referential type
        by equating var: 'a
        to type expr: 'a -> 'b

        - fun f _ = f;
        Type Clash  in: f _ =  f
        Attempt to build a self-referential type
        by equating var: 'a
        to type expr: 'b -> 'a
\end{verbatim}
\end{quote}

Less common error messages are described in section ``Error messages''.

\subsection{Editing and debugging}

ANU ML provides a programming environment which make writing a ML module
much easier by providing support for editing and debugging.  This
subsystem is call AIMLESS (An Interactive ML Editing Support System).  As
discussed in section 1.2 ML has lexical scoping of variables at the
top-level. If a function {\bf f} calls a previously defined function {\bf g},
then a subsequent definition of {\bf g} will not change {\bf f}. AIMLESS
provides a mechanism for changing the original definition of {\bf g} by
undoing previously entered phrases, changing {\bf g} and re-entering the
undone phrases.

In the usual eval-loop implementation of an interactive language, valid
phrases are accepted (expressions are evaluated and declarations are
elaborated), while invalid phrases are rejected.  In ANU ML, the latter
are not discarded but are kept in a FIFO list for subsequent correction;
this list is called the {\it buffer}.  The ordered list of valid phrases that
have been accepted by the system is called the {\it script}. The
{\it phraselist} is just the concatenation of the script and the buffer.

\begin{quote}
\begin{verbatim}
        - val a = 10;
        > val a = 10 : int

        - val b = 1 + true;
        Type Clash  in:  (1 + true)
        Looking  for :   int
        I have found :   bool

        - val c = a;
        > val c = 10 : int

        - val d ===;
        Syntax Error:   val d ===;
        I was expecting an "="

        - show all;
        --------------------------------------- 
        val a = 10;
        val c = a;
        ************************** 
        val d ===;
        val b = 1 + true;
        --------------------------------------- 
\end{verbatim}
\end{quote}

\noindent
The AIMLESS directive, {\bf show all}, has caused the phraselist to be
shown.  Clearly the row of asterisks separates the script from the
buffer.  Note that the phrases are not now in order of entry since
valid phrases are evaluated and added to the end of the {\it script}
but invalid phrases are added to the front of the {\it buffer}.
Of course, either script or buffer can be shown without the other.
\begin{quote}
\begin{verbatim}
        - show script;
        val a = 10;
        val c = a;

        - show buffer;
        val d ===;
        val b = 1 + true;
\end{verbatim}
\end{quote}

The phraselist is manipulated by commands {\bf reset}, {\bf pop}, {\bf push},
{\bf del} and {\bf edit}.
{\bf Reset} restores the ML system to its initial configuration.  {\bf Pop}
moves the last phrase on the script onto the buffer, undoing all bindings
associated with the phrase. {\bf Push}
attempts to move the first phrase on the buffer onto the script;  if the
phrase is invalid, it is left on the buffer.  {\bf Del} simply discards
the first phrase on the buffer.  The {\bf edit} command puts the user
into a text editor, editing the first phrase on the buffer. On leaving the
editor, the phrase is pushed. Thus if a phrase is invalid due to
a typo error, command {\bf edit} is a convenient way of correcting the
error without having to enter the phrase again.

To change a phrase on the script, sufficient pop operations should be
performed that the phrase in question will be at the head of the buffer;
it may then be edited.  When popped phrases are then
pushed back onto the script they will use the new definition of the
changed phrase. Command {\bf alter}
performs the appropriate sequence
of operations;  it takes an identifier as an argument
and pops phrases until the most recent phrase defining the identifier
in a declaration is on the buffer. The phrase is then edited
and all popped phrases pushed. Command {\bf altertype} is equivalent
to {\bf alter} but changes the most recent phrase defining the identifier
in a type definition.

AIMLESS interacts with the file store through the commands {\bf use},
{\bf save} and {\bf cleanup}. An ML source file looks exactly
like a set of top-level phrases. A file
{\bf prog.ml} containing ML source code can be loaded as follows:

\begin{quote}
\begin{verbatim}
        use  "prog.ml";
\end{verbatim}
\end{quote}

\noindent
where the string indicates a file name according to the conventions
of the operating system on which ML is running.  The files loaded by
a {\bf use} command may themselves contain {\bf use}
commands (up to some stacking
depth).  The file extension {\bf .ml} is normally used for ML source
files, but this is not compulsory.

The {\bf save script} command also takes a string representing a file and
writes the {\it script} to that specified
file.  This command will be used when a module has been composed and
tested.

\begin{quote}
\begin{verbatim}
        save script "prog.ml";
\end{verbatim}
\end{quote}
        
The command {\bf save all}, on the other hand, writes the whole
phraselist out to its specified file.  This action is appropriate to
save a version of a module under development, even before the syntax
and/or typing errors have been corrected.

AIMLESS also includes debugging mechanisms. For details on these, and
further editing commands, see section 9.

\newpage
\section{Lexical matters}

The following lexical entities are recognized: reserved words, identifiers,
integers, strings and comments.

\subsection{Reserved words}

The following are reserved words in Standard ML.  They may not (except
for {\bf =}) be used as identifiers.

\begin{quote}
\begin{verbatim}
  abstype   and   andalso   as   case   do   datatype   else   eqtype
  end   exception   fn   fun   functor   handle   if   in   include
  infix   infixr   let   local   nonfix   of   op   open   orelse 
  raise   rec   sharing   sig   signature   struct   structure   then
  type   val   with   withtype   while
  (   )    [   ]    {   }    ,   :   ;   ...   _   |   =    =>    ->    #
\end{verbatim}
\end{quote}

Some of these reserved words are not used by watML (all the ML module
specific keywords) but, for consistency, they are reserved in watML.

\subsection{Identifiers}

An identifier is either (i) a sequence of letters, numbers, primes `{\bf '}'
and underscores `{\bf \_}'
starting with a letter or a prime, or (ii) a sequence
of the following characters.  The exceptions are the reserved words enumerated
above.  Identifiers that start with a prime are classed as type variable
identifiers while the others may be used for value variables, constructors
etc.

\begin{quote}
\begin{verbatim}
  !   %   &   $  #   +   -   :   <   =   >   ?   @   \    ~   '   ^   |   *
\end{verbatim}
\end{quote}

\subsection{Integers and Reals}

A sequence of digits, possibly preceded by a tilde `{\bf \~{}}', denotes
an integer.

A real constant is an integer constant, possibly followed by a period (.)
and at least one digit, possibly then followed by E (the exponent symbol)
and an integer constant; at least one of these two optional parts must
occur (or else we just have an integer constant).

\subsection{Strings}

Strings are sequences of characters delimited by string quotes `{\tt "}'.
String quotes
and non-printable characters can be introduced in strings by using the
escape character `{\bf $\backslash$}'.
These are the meaningful escape sequences:

\begin{quote}
\begin{verbatim}
        \n              The end of line character
        \t              The horizontal tab character
        \^c             For any ASCII character c, the corresponding
                        control character (eg.  \^C, \^G, \^H)
        \ddd            ASCII character with 3-digit decimal code ddd
        \"              "
        \\              \ 
\end{verbatim}
\end{quote}

The escape character can also be used to exclude formatting characters
from a string.  A sequence of the form $\backslash$ f . . . f $\backslash$ 
(where each f is a space, tab,
newline etc.) appearing in a string, contributes no characters to the
string.  For example, {\bf {\tt "}abc{\tt "}}
is the same string as {\bf {\tt "}a$\backslash$\ $\backslash$\ bc{\tt "}}.

\subsection{Comments}

Comments are enclosed in comment brackets `{\bf (*}' and `{\bf *)}',
and can be properly nested.

\newpage
\section{Expressions}

Expressions denote values, and have a type which is statically determined.
Expressions can be constants, identifiers, data constructors,
tuples, lists, sequences, records, conditionals, function objects
(fn-expressions), function applications, infix operator applications,
let expressions, while expressions, case expressions,
exception raising and exception handling expressions, and explicitly
typed expressions.
All these different kinds of expression are described in this section.

\subsection{Unit}

The expression {\bf ()} (called {\it unity}) denotes the only object
of type {\bf unit}.

\begin{quote}
\begin{verbatim}
        ()                      : unit                  (constant)
\end{verbatim}
\end{quote}

The unit type is useful when defining
functions with no argument or no values: they take a {\bf unit} argument or
produce a {\bf unit} result. There are no primitive operations on unity.

The {\bf unit} type is not strictly primitive; it could be introduced by
the declaration:

\begin{quote}
\begin{verbatim}
declaration:            datatype unit = ();

bindings:               datatype unit = ()
                        con () : unit
\end{verbatim}
\end{quote}

\noindent
The above is not actually legal ML syntax: user defined constants
must be identifiers, and {\bf ()} is treated specially.

\subsection{Booleans}

The pre-defined constants

\begin{quote}
\begin{verbatim}
        true, false             : bool                          (constants)
\end{verbatim}
\end{quote}

\noindent
denote the respective boolean values. Boolean operators are:

\begin{quote}
\begin{verbatim}
        not                     : bool -> bool
        &, or                   : (bool * bool) -> bool         (infixes)
\end{verbatim}
\end{quote}

\noindent
Both arguments of {\bf \&} and {\bf or} are always evaluated.  The
connectives {\bf andalso} and {\bf orelse} are similar to {\bf \&} and
{\bf or}; the difference is that they evaluate only the first argument
when this is sufficient to determine the
result; the same effect can be achieved in ML by using nested conditional
expressions.
The expression {\bf E} will be evaluated in ({\bf true andalso E}) and in
({\bf false orelse E});  it will not be evaluated in ({\bf false andalso E})
and in ({\bf true orelse E}).

Both {\bf \&} and {\bf or} are not part of standard ML, but can be easily
defined in ML.

\subsection{Numbers}

The integer operators are:
\begin{quote}
\begin{verbatim}
    ~                               : int -> int
    +, -, *, /, div, mod            : (int * int) -> int    (infixes)
    >, >=, <=, <                    : (int * int) -> bool   (infixes)
\end{verbatim}
\end{quote}

\noindent
All of the above operations (except for {\bf div} and {\bf mod}) are
overloaded.

Of course, the special polymorphic relation for equality ({\bf =}), and its
inverse ({\bf $<>$}) apply to pairs of integers.

Negative integers are written {\bf \~{}3}, where `{\bf \~{}}'
is the complement function (while `{\bf -}' is difference).
Integers, in the current version, do
not have unbounded precision and so a variety of exceptions are possible due
to overflow.  Programmers are warned that in the near future this
limitation will be relaxed; at that time
arithmetic exceptions will only be generated by integer
division ({\bf Div}) and remainder-on-division ({\bf Mod})
when their second argument is zero.

The integer type could in principle be defined in ML as:

\begin{quote}
\begin{verbatim}
declaration:            datatype nat = one | succ of nat;

declaration:            datatype int =  neg of nat | zero | pos of nat;
\end{verbatim}
\end{quote}

The usual arithmetic operations on reals are available:-
\begin{quote}
\begin{verbatim}
    ~                       : real -> real
    +, -, *, /              : (real * real) -> real         (infixes)
    >, >=, <=, <            : (real * real) -> bool         (infixes)
\end{verbatim}
\end{quote}

\noindent
All of the above operations are overloaded.

The standard mathematical functions {\bf sqrt}, {\bf sin}, {\bf cos},
{\bf arctan}, {\bf exp} and {\bf ln}
all have type {\bf real $\rightarrow$ real}. The function {\bf sqrt}, {\bf exp}
and {\bf ln} can
be handed unsuitable arguments; the exceptions {\bf Sqrt}, {\bf Exp} and
{\bf Ln} are used to indicate the failure.  Conversions between integer and
real types are handled by the functions {\bf floor} and {\bf real}.
({\bf floor(r)} is the largest integer not greater than {\bf r};
it returns exception Floor if {\bf r} is out of range.)

Although the usual tests for equality ({\bf =} and {\bf $<>$}) are
available, they should be used with discretion because of round-off
errors arising from the floating point hardware.

The usual arithmetic operations on complex numbers are available:-
\begin{quote}
\begin{verbatim}
    ~                       : complex -> complex 
    +, -, *, /              : (complex * complex) -> complex        (infixes)
    rpart, ipart            : complex -> real
    +^                      : (real*real) -> complex                (infix)
\end{verbatim}
\end{quote}

\noindent
Again, the basic operators are overloaded.

Real and imaginary parts of a complex number are selected by use of the
functions {\bf rpart} and {\bf ipart}.  Complex numbers are constructed
using the {\tt +\^{}} infix operator.

\begin{quote}
\begin{verbatim}

declaration:            val C = 1.1 +^ 2.2;

binding:                val C = 1.1+^2.2 : complex

expression:             (ipart C) +^ (rpart C);

result:                 2.2+^1.1 : complex
\end{verbatim}
\end{quote}

\subsection{Tuples}

A {\it tuple} is a fixed-length heterogeneous sequence of values.
The unity value (i.e. {\bf ()}) might be considered as a zero-length tuple.
There are no tuples of length one; they are identified with their unique
component. Tuples of length two or more are written as sequences of values
separated by commas:

\begin{quote}
\begin{verbatim}

syntax:         "("exp1 "," .. "," expn")"              n >= 2
\end{verbatim}
\end{quote}

The type of an n-ary tuple is an n-ary cartesian product, denoted in the
usual way using {\bf n-1} asterisks to separate the {\bf n} types.
Parentheses are used to express non-flat cartesian product types.

The various elements of a tuple can be extracted using selectors
of the form {\bf \#n}, where {\bf n} is a positive integer constant.

\begin{quote}
\begin{verbatim}
expression:             #2 (2,4,6)

result:                 4 : int
\end{verbatim}
\end{quote}

Beyond the basic use of commas to build tuples and the selectors
to extract items, there are no primitive functions.
Destructuring will normally be done by pattern matching:

\begin{quote}
\begin{verbatim}
declaration:            val (a,b,c) = (1,2,3);

result:                 val a = 1 : int
                        val b = 2 : int
                        val c = 3 : int
\end{verbatim}
\end{quote}

The type of a tuple is the cartesian product of the types of its components:

\begin{quote}
\begin{verbatim}
typing rule:            if e1 : t1 and .. and en : tn
                        then (e1 , .. , en ) : t1 * .. * tn
\end{verbatim}
\end{quote}

\subsection{Records}

ML provides the following mechanism to specify the values for each field
of a record with {\bf n} fields.

\begin{quote}
\begin{verbatim}

syntax:   "{" lab1 "=" exp1 ","  ..  "," labn "=" expn "}"        n >= 1
\end{verbatim}
\end{quote}

What might be considered the null record `$\{\}$', is treated just as
another name for the unit object `()'.

Even more than with tuples, information is extracted from records via
the pattern matching process.  To help in regard, record patterns may
include a wildcard `{\bf ...}' which stands for `the rest of the fields'.

\begin{quote}
\begin{verbatim}
declaration:            val Canberra = {long=149, lat=35};

result:                 val Canberra = {lat=35, long=149} : {lat:int, long:int}

declaration:            val {long=e,lat=s} = Canberra;

result:                 val s = 35 : int
                        val e = 149 : int

declaration:            val {lat=b, ...} = Boulder;

result:                 val b = ~40 : int
\end{verbatim}
\end{quote}

The type of a record is given by the types of its components, each labelled
by the names of the respective fields:

\begin{quote}
\begin{verbatim}
typing rule:            if e1 : t1 and .. and en : tn
                        then {f1=e1 , .. , fn=en ) : f1:t1 * .. * en:tn
\end{verbatim}
\end{quote}

Records are one of the few really fundamental types in ML; they
cannot be explained in terms of other constructs in the language.

\subsection{Lists}

A list of elements {\bf exp$i$} is written:

\begin{quote}
\begin{verbatim}
syntax:         "[" exp1 ","  ..  "," expn "]"          n >= 0
\end{verbatim}
\end{quote}

\noindent with {\bf []}
as the empty list. All the elements of a list must have the same type,
otherwise a compile-time type error will occur.

The basic constructors for lists are:

\begin{quote}
\begin{verbatim}
    nil          : 'a list                             (constant)
    ::           : ('a * 'a list) -> 'a list           (infix constructor)
\end{verbatim}
\end{quote}

\noindent {\bf nil} is the empty list (the same as {\bf []}),
{\bf ::} (cons) adds an element to a list (e.g. 1::[2,3,4] is the same as
[1,2,3,4]).

Some other frequent operations on lists are predefined in the system:

\begin{quote}
\begin{verbatim}
    null                 : 'a list -> bool
    hd                   : 'a list -> 'a
    tl                   : 'a list -> 'a list
    length               : ('a list) -> int
    @                    : ('a list * 'a list) -> 'a list        (infix)
    rev                  : ('a list) -> ('a list)
    map                  : ('a -> 'b) -> (('a list) -> ('b list))
    fold, revfold        : (('a * 'b) -> 'b) -> (('a list) -> ('b -> 'b))
\end{verbatim}
\end{quote}

\begin{itemize}
\item
  {\bf null} tests whether a list is empty.
\item
  {\bf hd} (head) extracts the first element of a list; it escapes
with exception {\bf Hd} on empty lists.
\item
  {\bf tl} (tail) returns a list where the first element has been removed;
it escapes with exception {\bf Tl} on empty lists.
\item
  {\bf length} returns the length of a list.
\item
  {\bf @} (append) appends two lists (e.g. {\bf [1,2]@[3,4]} is the same as
{\bf [1,2,3,4]}).
\item
  {\bf rev} returns the reverse of a list.
\item
  {\bf map} takes a function and then a list, and applies the
function to all the elements of the list, returning the list of the results
(i.e. {\bf map f [e1, .. , en]} is {\bf [f (e1), .. , f (en)]}).
\item
  {\bf fold} maps a binary function to an n-ary function over a list
(e.g. it can map {\bf +}
to the function computing the sum of the elements of a list), it takes first
a binary function, then the list to accumulate, then the value to return on
empty lists (i.e. {\bf fold f [e1, .. , en] e} is {\bf f (e1, .. f (en,e)..)}).
\item
  {\bf revfold} is just like {\bf fold} but
accumulates in the opposite direction (that is,\break
{\bf revfold f [e1, .. , en] e} is {\bf f\ (en, .. f\ (e1,e)..)}).
\end{itemize}

The type of lists can be defined in ML as:

\begin{quote}
\begin{verbatim}
declaration:            infix :: ;

declaration:            datatype 'a list = nil | op :: of int * (int list);

bindings:               datatype 'a list = nil | :: of int * (int list);
                        con nil : 'a list
                        con :: : ('a * ('a list)) -> ('a list)
\end{verbatim}
\end{quote}

All the list operations can then be defined by case analysis.
The bracket notation (e.g. {\bf [1,2]}) is just an abbreviation for
the compositions of list constructors (e.g. {\bf 1::2::nil}).

\begin{quote}
\begin{verbatim}
typing rule:            if e1 : t and .. and en : t   
                        then [e1, .. , en] : t list
\end{verbatim}
\end{quote}

\subsection{Strings}

The operation on strings are:
\begin{quote}
\begin{verbatim}
    size                         : string -> int
    extract                      : (string * int * int) -> string
    explode                      : string -> string list
    implode                      : string list -> string
    explodeascii                 : string -> int list
    implodeascii                 : int list -> string
    intofstring                  : string -> int
    realofstring                 : string -> real 
    makestring                   : 'a -> string
\end{verbatim}
\end{quote}

\begin{itemize}
\item {\bf size} returns the length of a string.
\item {\bf extract} extracts a substring from a string: the first argument is
the source string, the second argument
is the starting position of the substring in the string (the first character
in a string is at position 1), and the third argument is the length of the
substring; it generates exception {\bf Extract}
if the numeric arguments are out of range.
\item {\bf explode} maps a string into the list of its characters, each one
being a 1-character string.
\item {\bf implode} maps a list of strings into a string which is their
concatenation.
\item {\bf explodeascii} is like {\bf explode}, but produces a list of the
ASCII representations of the characters contained in the string.
\item {\bf implodeascii} maps a list of numbers interpreted as the ASCII
representation of characters into a string containing those characters; it
escapes with exception {\bf Implodeascii}
if the integers are not valid ASCII codes.
\item {\bf intofstring} converts a numeric string to the corresponding integer
number, negative numbers start with `{\bf \~{}}';
it will generate exception {\bf Intofstring} if the string is not numeric.
\item {\bf realofstring} converts a numeric string to the corresponding real 
number, negative numbers start with `{\bf \~{}}';
it will generate exception {\bf Realofstring} if the string is not numeric.
\item {\bf makestring} returns a string containing the print representation
of an arbitrary expression.
\end{itemize}

For ASCII characters we intend here full 8-bit codes in the range 0..255.

\subsection{Updatable references}

Assignment operations act on {\it reference} objects.
A reference object is an updatable pointer to another object.
References are, together with arrays, the
only data objects which can be side effected; they can be inserted anywhere
an update operation is needed in variables or data structures.

References are created by the operator {\bf ref}, updated by {\bf :=}
and dereferenced by {\bf !}. The assignment operator {\bf :=}
always returns unity. Reference objects have type {\bf t ref}, where {\bf t}
is the type of the object contained in the reference.

\begin{quote}
\begin{verbatim}
    ref             : [?ref: 'a -> ('a ref)]'a -> ('a ref)  (constructor)
    !               : 'a ref -> 'a
    :=              : 'a ref * 'a -> unit                   (infix)
\end{verbatim}
\end{quote}

The implicit parameter introduced by {\bf ref} prevents type errors occurring
with polymorphic references. This is discussed below.
Here is a simple example of the use of references. A reference to the
number {\bf 3} is created and updated to contain {\bf 5},
and its contents are then examined.

\begin{quote}
\begin{verbatim}
declaration:            val a = ref 3;

binding:                val a = ref 3 : int ref

expression:             a := 5;

result:                 () : unit

expression:             !a;

result:                 5 : int
\end{verbatim}
\end{quote}

References can be embedded in data structures. Side effects on embedded
references are reflected in all the structures which share them:

\begin{quote}
\begin{verbatim}
declaration:            datatype 'a refpair = Refpair of 'a ref * 'a ref;

binding:                datatype 'a refpair = Refpair of ('a ref) * ('a ref)
                        con Refpair : (('a ref) * ('a ref)) -> ('a refpair)

declaration:            val r = ref 3;  val p = Refpair(r,r);

bindings:               val r = ref 3 : int ref
                        val p = Refpair(ref 3,ref 3) : int refpair

expression:             r := 5;

result:                 () : unit

expression:             p;

result:                 Refpair(ref 5,ref 5) : int refpair
\end{verbatim}
\end{quote}

The implicit parameter introduced by {\bf ref} prevents type insecurities that
can be introduced by assignment in a polymorphic type system.

\begin{quote}
\begin{verbatim}
declaration:         val a = ref [];

binding:             val a = [?ref: ('a list) -> (('a list) ref)]('a list) ref
\end{verbatim}
\end{quote}

\noindent If the type of {\bf a} was simply {\bf 'a list ref} then it would be
possible to assign both a list of {\bf int}s and a list of {\bf boolean}s
to {\bf a} which could lead to type errors. Instead the implicit parameter in
the type is not resolved until {\bf a} becomes a monomorphic type.

\begin{quote}
\begin{verbatim}
expression:             a := [1,2,3];

result:                 ()

expression:             a;

result:                 ref [1,2,3] : (int list) ref

expression:             a := [true,false];

result:                 Type Clash  in:  (a := (true :: (false :: nil)))
                        Looking  for :   int
                        I have found :   bool
\end{verbatim}
\end{quote}

\noindent After the assignment of an integer list to {\bf a} is now
a monomorphic object ({\bf (int list) ref}) and therefore attempting to
assign a boolean list is an error.

ML uses a different system with {\it weak types};
New Jersey ML uses an extended system of weak types;
types have `levels' of weakness, a normal type variable has a level of
infinity, the original declaration of {\bf a} in the above examples would
have level 0. Each use within a lambda abstraction raises the level by
one: {\bf ref} therefore has the type {\bf '1a $\rightarrow$ '1a} where
each variable has level 1. It is illegal to have a weak type of level 0
at the top level. The original declaration of {\bf a} above would be
in error.

\subsection{Arrays}

Arrays are ordered collections of values with a constant access time retrieval
operation. They have a lower bound and a size, which are integers, and can
be indexed by integer numbers in the range lowerbound $=<$ i $=<$
lowerbound+size.
Arrays can have any positive or null size, but once they are built they retain
their initial size.

Arrays over values of type {\bf t} have type {\bf t array}.
Arrays can be built over elements of any type; arrays of arrays account
for multi-dimensional arrays.

The array primitives are:

\begin{quote}
\begin{verbatim}
     array                : [?ref: 'a -> ('a ref)](int * int * 'a) -> 'a array
     arrayoflist          : [?ref: 'a -> ('a ref)](int * 'a list) -> 'a array
     lowerbound           : 'a array -> int
     arraysize            : 'a array -> int
     sub                  : ('a array * int) -> 'a              (infix)
     update               : ('a array * (int * 'a)) -> unit     (infix)
     arraytolist          : 'a array -> 'a list
\end{verbatim}
\end{quote}

\begin{itemize}
\item
{\bf array} makes a constant array (all items equal to the third argument)
of size n$>=$0 (second argument) from a lowerbound (first argument).
The exception {\bf Array} is generated if the size is negative.
\item
  {\bf arrayoflist} makes an array out of a list, given a lower bound for
indexing.
\item
  {\bf lowerbound} returns the lower bound of an array.
\item
  {\bf arraysize} returns the size of an array.
\item
  {\bf sub} extracts the i-th item of an array. It escapes with
exception {\bf Sub} if the index is not in range.
\item
  {\bf update} updates the i-th element of an array with a new value.
It escapes with exception {\bf Update} if the index is not in range.
\item
  {\bf arraytolist} converts an array into the list of its elements.
\end{itemize}

Arrays are not a primitive concept in ML: they can be defined as an abstract
data type over lists of assignable references. This specification of arrays,
which is given below, determines the semantics of arrays, but does not have
a fast indexing operation. Arrays are actually implemented at a lower
level as contiguous blocks of memory with constant time indexing.
Here is an ML specification of arrays, semantically equivalent to their
actual implementation (see sections ``Lists'', ``Updatable references''
and ``Lexical declarations'' to properly understand this program).
\begin{quote}
\begin{verbatim}
    abstype 'a array =
      Arr of (*lowerbound:*) int * (*size:*) int * (*table:*) 'a ref list
    with
      local
        fun el (n: int, (head :: tail): 'a list) : 'a = 
                if n=0 then head else el(n-1,tail)
      in
        exception Array
        fun array (lb: int, length: int, item: 'a) : 'a array =
                  if length<0 then raise Array
                  else Arr(lb,length,list length)
                          where rec val list n =
                                  if n=0 then [] else (ref item) :: list(n-1)
                          end

        fun arrayoflist (lb: int, list: 'a list) : 'a array =
                Arr(lb,length list,map ref list)

        fun lowerbound (Arr(lb,_,_): 'a array) : int = lb

        fun arraysize (Arr(_,size,_): 'a array) : int = size

        infix sub
        exception Sub
        fun (Arr(lb,size,table): 'a array) sub (n: int) : 'a =
                let val n' = n-lb
                in      if n'<0 or n'>=size then raise Sub
                        else !(el(n',table))
                end

        infix update
        exception Update
        fun (Arr(lb,size,table): 'a array)
            update (n: int, value: 'a) : unit =
                let val n' = n-lb
                in      if n'<0 or n'>=size then raise Update
                        else el(n',table):=value
                end

        fun arraytolist (Arr(_,_,table): 'a array) : 'a list =
                map (op !) table
      end
    end;
\end{verbatim}
\end{quote}

\noindent Arrays are currently undergoing review in standard ML. It is
likely that some features of watML will become non-standard.

\subsection{Patterns and matches}

The left hand side of an {\bf =} in a value definition can be a simple variable,
or a more complex {\it pattern}
involving several distinct variables. Patterns are also used in formal
parameters of functions and in case expressions. In all these situations a
value has to be
decomposed according to its structure; the matching process produces a set of
{\it bindings}
by associating the variables in the pattern with the corresponding parts of
the value.

A pattern can be a {\bf \_} sign (matching any value), an identifier (preceded
by {\bf op} if infix), a constant, a construction, an infixed construction,
a list pattern, a tuple pattern, a record pattern, a typed pattern,
a layered pattern or a parenthesized pattern.

\begin{quote}
\begin{verbatim}
syntax:     simp_pat ::=    "_"
                            constant
                            ["op"] var
                            "{" patrow "}"
                            "()"
                            "(" pat  "," .. ","  pat ")"
                            "[" pat  "," .. ","  pat "]"
                            "(" pat ")"

                 pat ::=    simp_pat
                            ["op"] con pat
                            ["op"] excon pat
                            pat con pat
                            pat excon pat
                            pat ":" type
                            ["op"] var [":" type] "as" pat

              patrow ::=    "..."
                            lab "=" `pat [ "," patrow ]
                            id [ ":" type ] [ "as" pat ] [ "," patrow  ]
\end{verbatim}
\end{quote}

The pattern matching rules are given recursively on the structure of the
pattern. The letter {\bf k} denotes constructors, {\bf c} denotes constants,
{\bf a} and {\bf b} denote variables, {\bf u} and {\bf v} denote values,
and {\bf p} and {\bf q} denote patterns.

\begin{tabbing}

\ \ \ \ \ \ \ \= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \= \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \= \ \ \kill
\> Pattern \> Value \> Match(Pattern,Value)  \\
\> \_ \> v \> $\emptyset$  \\
\> a \> v \> $\{$a = v$\}$  \\
\> () \> () \> $\emptyset$  \\
\> c \> c \> $\emptyset$  \\
\> k \> k \> $\emptyset$  \\
\> k p \> k v \> Match(p,v)  \\
\> [p1,..,pn] \> [v1,..,vn] \> Match(p1,v1) $\cup$ .. $\cup$ Match(pn,vn) \ \ \ \ \ n$>=$0  \\
\> (p1,..,pn) \> (v1,..,vn) \> Match(p1,v1) $\cup$ .. $\cup$ Match(pn,vn) \ \ \ \ \ n$>=$2  \\
\> $\{$s1=p1,..,sn=pn$\}$ \> $\{$s1=v1,..,sn=vn$\}$ \> Match(p1,v1) $\cup$ .. $\cup$ Match(pn,vn) \ \ \ \ \ n$>=$0  \\
\> a as p \> v \> {a = v} $\cup$ Match(p,v)  \\

\end{tabbing}

Example:

\begin{quote}
\begin{verbatim}
declaration:            val (a,b) :: [c,_] = [(1,2), (3,4), (5,6)];

bindings:               val a = 1 : int
                        val b = 2 : int
                        val c = (3,4) : int * int

declaration:            val x as (a,b) = (1,2);

bindings:               val x = (1,2) : int * int
                        val a = 1 : int
                        val b = 2 : int
\end{verbatim}
\end{quote}

The variables in a single pattern must all be distinct. Patterns are not
expressions; they can only appear as part of value declarations, function
declarations, fn-expressions and case expressions.

It often is clumsy to have to show all the field names of a record in
a pattern when a partial match is all that is needed.  For such
circumstances the record wildcard (...) is provided; this construct
matches any unspecified fields of a record.  The feature can only be used,
however, in a context where the type of the record can be inferred.

\begin{quote}
\begin{verbatim}
declaration:            val {f=(x,y), g=z, ...} = {e=1, f=(2,3), g=4, h=5}

bindings:               val x = 2 : int
                        val y = 3 : int
                        val z = 4 : int
\end{verbatim}
\end{quote}

A {\it match} is a sequence of pattern-action pairs separated by vertical bars.

\begin{quote}
\begin{verbatim}
syntax:         match  ::=  pat "=>" exp  "|"  ..  "|"  pat "=>" exp
\end{verbatim}
\end{quote}

Matches are used to destructure values and to execute fragments of
code depending on the form of values: they replace test and 
selection operations.  The patterns in a match are
matched in turn, from left to right, against some value {\bf v}.
The first successful match is used to destructure {\bf v},
and the variables in the pattern are bound to the respective parts of {\bf v}.
Then the corresponding expression is executed, and its result is
returned as the result of the matching. If none of the patterns matches
{\bf v}, then in an expression exception {\bf Match} is raised, in a
declaration exception {\bf Bind} is raised.

Matches are not expressions; they can only appear in fn-expressions, in
case expressions and in exception handlers.

\subsection{Functions}

Functions can be introduced in a value declaration where an expression with
the appropriate function value can be readily written down.

\begin{quote}
\begin{verbatim}
declaration:            val quad = twice o twice

binding:                val quad = fn : int -> int
\end{verbatim}
\end{quote}

The normal method, however, is by clausal function declarations:-

\begin{quote}
{\tt
syntax:

\ \ \ \ \ \ fun ["op"] var  simp\_pat$_{1,1}$  ..  simp\_pat$_{1,n}$  [ ":" type]  "="  exp$_1$  |

\ \ \ \ \ \ . . . .

 \ \ \ \ \ \ \ \ \ \ ["op"] var  simp\_pat$_{j,1}$   ..  simp\_pat$_{j,n}$   [ ":" type]  "="  exp$_j$;
}
\end{quote}

The {\bf op} keyword is appropriately used when {\bf f} is an infix;
alternatively ({\bf pat f pat'}) can be used instead of {\bf op f (pat,pat')}.
(The parentheses may be dropped if the next lexical item is `{\bf :}' or
`{\bf =}' .) The {\bf simp\_pat} patterns are {\bf \_}, variables, constants,
lists, tuples, records and parenthesized patterns, in particular
they must be parenthesized when they have the form {\bf (pat' : type)}.
The {\bf optional type} expressions refer to the type of the result of the
function.

Unnamed functions can be introduced as expressions by the use of the
{\it fn-notation}, which is just a match preceded by the keyword {\bf fn}:

\begin{quote}
\begin{verbatim}
syntax:         "fn" match
\end{verbatim}
\end{quote}

A {\bf fn}
expression denotes a function, which can be associated with an identifier
by a normal value definition, for example:

\begin{quote}
\begin{verbatim}
declaration:            val plus = fn x => fn y => x + y

declaration:            val null = fn nil => true  |  a :: b => false;
\end{verbatim}
\end{quote}

The following curried function definition is a sugaring
of the first declaration above, and the clausal function
definition (next) is a sugaring of the second declaration:

\begin{quote}
\begin{verbatim}
declaration:            fun plus x y = x + y

declaration:            fun null nil = true  |  null (a :: b) = false;
\end{verbatim}
\end{quote}

The type of every expression and pattern can be specified by suffixing a colon
and a type expression to it (note that parentheses are needed around type
specifications
in patterns, when they are not part of larger patterns). To completely specify
the type of a fn-expression we may use either of the two forms:

\begin{quote}
\begin{verbatim}
expression:

  fn (a: bool)=> fn (b: int, c: int)=> (if a then b else c) : int;

expression:

  (fn a=> fn (b,c)=> if a then b else c): bool -> ((int * int) -> int);

result:

   fn : bool ->  ((int * int) -> int)
\end{verbatim}
\end{quote}

In declarations, we have the following options (and more):

\begin{quote}
\begin{verbatim}
declaration:

  fun f (a: bool) (b: int, c: int) : int = if a then b else c;

declaration:

  fun f (a: bool) ((b,c) : int * int) = (if a then b else c): int;

binding:

  val f = fn : bool ->  ((int * int) -> int)
\end{verbatim}
\end{quote}

The first form should be preferred; note how the result type of the
function precedes the {\bf =} sign of the definition.

This explicit type information is often redundant.
However, the system checks
the explicit types against the types it infers from the expressions. Introducing
explicit type information is a good form of program documentation, and helps
the system in discovering type errors exactly where they arise. Sometimes,
when explicit type information is omitted, the system is able to infer a type
(not the intended one) from an incorrect program; this `misunderstanding'
is only discovered in some later use of the program and can be difficult to
trace back.

The type of a function expression is determined by the type of its binder
(or binders) and the type of its body (or bodies):

\begin{quote}
\begin{verbatim}
typing rule:    if  p1 : t and .. and pn : t and e1 : t' and .. and en : t'
                then (fn p1=> e1 | .. | pn=> en) : t -> t'
\end{verbatim}
\end{quote}

The type automatically inferred by the system is the `most polymorphic' of
the typings which obey the typing rules. For example, from the previous typing
rule we can infer that {\bf (fn x ={\tt {\char '76}} x)
: int -{\tt {\char '76}} int}, and also
that {\bf (fn x={\tt {\char '76}} x) : 'a -{\tt {\char '76}} 'a};
the latter type is more polymorphic (in the sense that the
{\bf int $\rightarrow$ int}
can be obtained by instantiating the type variables of
{\bf 'a -{\tt {\char '76}} 'a});
in fact it is the most general typing, and is taken as the default type
for {\bf (fn x={\tt {\char '76}} x)}.

\subsection{Application}

There are two lexical categories of identifiers, which determine how functions
are syntactically applied to arguments: {\it nonfix} and {\it infix}.
Any identifier can be declared to fall in one of these categories: see
section ``Lexical declarations'' about how to do this.

Nonfix identifiers are the ordinary ones; they are applied by juxtaposing
them with their argument (in this section we use {\bf f} and {\bf g} for
functions and {\bf a}, {\bf b}, {\bf c} for arguments):

\begin{quote}
\begin{verbatim}
syntax:         f a
\end{verbatim}
\end{quote}

The expression {\bf a} can also be parenthesized (as any expression can),
obtaining the standard application syntax {\bf f (a)}. It is common {\it not}
to use parentheses when the argument is a simple variable,
a string\break
({\bf f {\tt "}abc{\tt "}}) or a list ({\bf f [1,2,3]}). It is necessary to
use parentheses when the argument is an infix expression like an
arithmetic operation because the precedence
of application is normally greater than the precedence of the infix
operators;  {\bf f a+b} is interpreted as {\bf (f a)+b}.
Function application binds stronger than any operator, as is clear
from the table below.  In case of
partial application, the form {\bf f g a}, is interpreted as {\bf (f g) a},
and not as {\bf f (g a)}.

Infix identifiers can be applied in two ways:

\begin{quote}
\begin{verbatim}
syntax:         a f b

syntax:         op f (a,b)
\end{verbatim}
\end{quote}

The first form is the expected one; an infix identifier has
always a type matching {\bf ('a * 'b) -> 'c}.
The second possibility derives from the fact that there must be a way of
passing an infix operator {\bf f} as an argument to a function {\bf g};
{\bf g(f)} will produce a syntax error, but {\bf g(op f)} is accepted.
In general the {\bf op} keyword coerces any infix identifier to a nonfix one.

Infix operators in order of decreasing precedence 
(see section ``Lexical declarations'').

\begin{quote}
\begin{verbatim}
        >9      {application}                           left associative
        9       sub                                     right associative
        7       /  *  div  mod                          left associative
        6       +  -  ^                                 left associative
        5       ::  @                                   right associative
        4       =  <>  >  <  >=  <=                     right associative
        3       update  :=  o                           right associative
        2       &                                       right associative
        1       or                                      right associative
        <0      ( .. , .. , .. )                        n-ary infix
\end{verbatim}
\end{quote}

The typing rule for function application states that the type of the argument
must match the type of the domain of the function:

\begin{quote}
\begin{verbatim}
typing rule:            if f : t -> t'  and  a : t   
                        then (f a) : t'
\end{verbatim}
\end{quote}

\noindent
For example, {\bf (fn x ={\tt {\char '76}} x)}
has the type {\bf 'a $\rightarrow$ 'a}
and all the instances of it, e.g. {\bf int $\rightarrow$ int}.
Hence {\bf (fn x ={\tt {\char '76}} x) 3} has type {\bf int}.

\subsection{Conditional}

The syntactic form for conditional expressions is:

\begin{quote}
\begin{verbatim}
syntax:         "if" e1 "then" e2 "else" e3
\end{verbatim}
\end{quote}

The expression {\bf e1} is evaluated to obtain a boolean value. If the
result is {\bf true} then {\bf e2} is evaluated; if the result if
{\bf false} then {\bf e3} is evaluated. Example:

\begin{quote}
\begin{verbatim}
expression:             fun sign n =
                                if n < 0 then ~1
                                else if n = 0 then 0
                                else 1;
\end{verbatim}
\end{quote}

The {\bf else} branch must always be present.

The typing rule for the conditional states that the condition must be
a boolean, and that the {\bf then} and {\bf else} branches must have compatible
types:

\begin{quote}
\begin{verbatim}
typing rule:            if  e1 : bool  and  e2 : t  and  e3 : t
                        then    (if e1 then e2 else e3) : t
\end{verbatim}
\end{quote}

Note that the types of two branches only have to match, not to be identical.
If one branch is more polymorphic than the other, than it also has the
type of the other (by instantiation of the type variables), and the above
rule can be applied.

\subsection{Sequencing}

When several side-effecting operations have to be executed in sequence,
it is useful to use {\it sequencing}:

\begin{quote}
\begin{verbatim}
syntax:         "("e1";" .. ";" en")"                   n >= 2
\end{verbatim}
\end{quote}

\noindent
(the parentheses are needed), which
evaluates {\bf e1} .. {\bf en} in turn and returns the value of {\bf en}.
The type of a sequencing expression is the type of {\bf en}. Example:

\begin{quote}
\begin{verbatim}
expression:             (a := 4;  a := !a div 2;  !a)

result:                 2 : int
\end{verbatim}
\end{quote}

Note that {\bf (e)} is equivalent to {\bf e}, and that {\bf ()} is unity.

\begin{quote}
\begin{verbatim}
typing rule:            if  e : t    
                        then  (e1; .. ; en; e) : t            n >= 1
\end{verbatim}
\end{quote}

\subsection{While}

The while construct can be used for iterative computations. It is included
in ML more as a matter or style and convenience than necessity, as
all {\it tail recursive}
functions (e.g. functions which end with a recursive call to themselves
or to other functions)
are automatically optimized to iterations by the compiler.

The while construct has two parts: a test, preceded by the keyword {\bf while}
and a body, preceded by the keyword {\bf do}. If the test evaluates
to {\bf true} then the body is executed, otherwise {\bf ()} is returned.
This process  is repeated until the test yields {\bf false} (if ever) or an
exception occurs.

\begin{quote}
\begin{verbatim}
syntax:         "while" e1 "do" e2
\end{verbatim}
\end{quote}

The result of a terminating while construct is always {\bf ()}, hence
{\bf while}s
are only useful for their side effects. The body of the while is also expected
to yield {\bf ()} at every iteration.

\begin{quote}
\begin{verbatim}
typing rule:            if  e1 : bool  and  e2 : unit
                        then  (while e1 do e2) : unit
\end{verbatim}
\end{quote}

As an illustration, here is an iterative definition
of factorial which uses two local assignable variables
{\bf count} and {\bf result}:

\begin{quote}
\begin{verbatim}
declaration:        fun fact n =
                          let val count = ref n
                              and result = ref 1
                          in      (while !count <> 0 do
                                          (result := !count * !result;
                                           count := !count-1);
                                   !result)
                          end;
\end{verbatim}
\end{quote}

\subsection{Case}

A case expression is just a different syntax for pattern matching: see section
``Patterns and matches'' for a description of {\it matches}.

\begin{quote}
\begin{verbatim}
syntax:         "case" exp "of" match
\end{verbatim}
\end{quote}

The expression {\bf exp} is matched against the {\bf match}, which is a
set of pattern-action pairs; the first pattern to match is activated, and
the corresponding action is evaluated and returned as the result of the
case expression.

\begin{quote}
\begin{verbatim}
declaration:            datatype color = Red | Purple | Yellow
                        and  fruit = Apple | Plum | Banana;

bindings:               datatype color = Red | Purple | Yellow
                        datatype fruit = Apple | Plum | Banana

declaration:            fun fruitcolor (fruit: fruit): color =
                                case fruit of
                                        Apple => Red |
                                        Banana => Yellow |
                                        Plum => Purple;

binding:                val fruitcolor : fruit -> color
\end{verbatim}
\end{quote}

The {\bf case} construct is a convenient form of saying ({\it if fruit=Apple
then Red else if fruit=Banana then Yellow else if fruit=Plum then Purple
else raise {\bf Match}});  the {\bf raise} is never executed in this
case because the list of cases is exhaustive.

The typing rule for {\bf case} is:

\begin{quote}
\begin{verbatim}
typing rule:            if  x : t' and p1 : t' and .. and pn : t'
                                and  e1 : t  and .. and en : t
                        then  (case x of p1=> e1  | .. |  pn=> en) : t
\end{verbatim}
\end{quote}

\noindent
This says that all the patterns must have the same type as value being
inspected, and that the values returned for each case must have the same type.

\subsection{Let}

A let expression introduces new variables and delimits their scope.
This has the same function of begin-end constructs in Algol-like
languages, but they have a fairly different flavor due to the fact of being
expressions returning values, instead of groups of statements.

\begin{quote}
\begin{verbatim}
syntax:         "let" declaration "in" exp1";"  . . . expn "end"
\end{verbatim}
\end{quote}

\noindent
This construct introduces new variable bindings in the {\bf declaration}
part which can be used in the {\bf exp} part (and there only). Newly
introduced variables hide externally declared variables having the same
name for the scope of {\bf exp}; the externally declared variables remain
accessible outside {\bf exp}.

The value returned by a let expression is the value of its expression part.
Similarly the type of a let expression is the type of its expression part.

\begin{quote}
\begin{verbatim}
typing rule:            if  e : t    
                        then  (let d in e end) : t
\end{verbatim}
\end{quote}

\subsection{Exceptions and exception handling}

An {\it exception} (sometimes loosely called a {\it failure})
can be raised by a system primitive or by a user program. When
an exception is raised, the execution of the current expression is abandoned,
and an {\it exception packet}
is propagated outward, tracing back along the history of function calls and
expression evaluations which led to the exception. If the exception is
allowed to propagate up to the top level, a {\it failure message} is printed.

\begin{quote}
{\tt
failure:                Unhandled exception {\it reason}
}
\end{quote}

\noindent
where {\it reason} is the identifier bound to the exception.  This
identifier is often similar to the
name of the system primitive or user function which raised the exception.

User exceptions are raised using the {\bf raise} construct:

\begin{quote}
\begin{verbatim}
syntax:         "raise" exp
\end{verbatim}
\end{quote}

The expression {\bf exp} above must evaluate to an exception.

The propagation of exceptions can only be stopped by a {\it handler}
construct whose syntax follows:

\begin{quote}
\begin{verbatim}
syntax:         "handle" Match
\end{verbatim}
\end{quote}

The pattern clauses in the match are tested from left to right for one
with the correct exception name and argument (if any) of the right form.
If such a one is found then the handler will have trapped the exception
and the expression with successful handler will return the value computed
from the successful match rule. If no match is found the exception continues.

Some system exceptions may be raised at any time, independently of the
expression which is being evaluated. They are {\bf Interrupt},
which is generated by a {\bf \^{}C} during execution, and {\bf Collect},
which is generated when there is no space left.
Even these exceptions can be trapped.

The typing rule for {\bf raise} says that an exception is compatible with every
type, i.e. that it can be generated without regard to the expected
value of the expression which contains it. The rules for the
trap operators state that the exception handler must yield a value of the same
type as the possibly failing expression, so that the resulting
type is the same whether the exception is raised or not.

\begin{quote}
\begin{verbatim}
 typing rule:           (raise e) : 'a
\end{verbatim}
\end{quote}

\subsection{Equality}

The standard equality predicate is {\it structural equality}:
two objects are equal when they are the same atomic object, or they have
the same structure and their corresponding components are equal.

The mathematical definition of equality over domains is in general undecidable,
hence some restrictions are imposed on the objects which can be compared, in
order to obtain a decidable predicate.
Equality is considered to be a pre-defined overloaded operator, i.e. an
infinite collection of decidable equality operators. In ML, a type variable
that {\it admits} equality is represented as a type variable with double
primes; therefore {\bf =} has the type {\bf (''a * ''a) $\rightarrow$ bool}.
It is a compile-time error to restrict an equality type variable to
a type that does not admit equality.

Equality is disallowed on functions, on streams
and on elements of abstract data types. When needed, these objects can
be marked by data having a decidable equality, but then the user must
write a special purpose equality routine.

Equality on reference object is not structural equality, but `sameness',
or pointer equality (e.g. {\bf ref 3 = ref 3} is false).

Equality over abstract types might be implemented as
equality over the corresponding concrete representations.
However in this case abstract types would not be transparent to
a change of representation (e.g. from an int list to an
int$\rightarrow$int), as equality
would behave differently on the different representations.
Also, if we implement abstract sets by concrete multisets, equality
could distinguish between sets which should be equal, giving dangerous
insights on the chosen representation, as well as not corresponding to
set equality.

Here are examples of `right' and `wrong' comparisons (at the top level).
The `wrong' comparisons produce compile-time type errors:

\begin{quote}
\begin{verbatim}
        Right                                   Wrong

        () = ();
        true = false;
        3 = 3;
        "a" = "";
        (2,"a") = (2,"a");
        [] = ([]: int list);
        [1,2] = [3];
        (fn (a,b)=> a=b) 
                                                (fn a=> a) = (fn a=> a);
                                                set[3] = set[3];
\end{verbatim}
\end{quote}

\noindent
where {\bf set} is an abstract type.

watML implements the same behaviour using its implicit parameter mechanism.
An expression that uses equality generates an implicit parameter in the
type of the expression for the use of equality. This implicit is resolved
when the type is known of the equality operation is known. For example,

\begin{quote}
\begin{verbatim}
        - fun member x [] = false
            | member x (a::b) = (x=a) orelse (member x b);
        > val member = [?=: ('a * 'a) -> bool]'a -> (('a list) -> bool)
       
        - member 3 [2,3,4];
          true : bool

        - member (fn x=>x) [(fn x => x)];
        Equality error
        type: 'a -> 'a
        cannot be used as equality type

\end{verbatim}
\end{quote}

\newpage
\section{Type expressions}

A type expression is either a {\it type variable}, a {\it basic type},
a {\it record type} or the application of a {\it type constructor}
to a sequence of type expressions. Type operators are suffix, except
for cartesian product {\bf *} and the infix operator {\bf $\rightarrow$}.

\subsection{Type variables}

A type variable is an identifier starting with `{\bf '}'.
Type variables are used to represent polymorphic types.

\subsection{Basic Types and Type Constructors}

A basic type is a type constructor with no parameters, like {\bf int}. A
parametric type operator, like {\bf $\rightarrow$} or {\bf list},
takes one or more arguments which are
arbitrary type expressions, as in {\bf 'a $\rightarrow$ (('a  list) list)}.
If an operator
takes many parameters, these are separated by commas and enclosed in
parentheses, as in {\bf ('a, 'b) tree}.

\begin{quote}
\begin{verbatim}
          unit            Unit Type                       Nonfix
          bool            Boolean Type                    Nonfix
          int             Integer Type                    Nonfix
          real            Real Type                       Nonfix
          complex         Complex Type                    Nonfix
          string          String Type                     Nonfix
          *               Cartesian Product               N-ary infix
          ->              Function Space                  Infix
          list            List Type                       Suffix
          ref             Reference Type                  Suffix
          array           Array Type                      Suffix
\end{verbatim}
\end{quote}

\subsection{Record Types}

The type of a record value is simply the selector-name / type pairs for each
item in the record.

\begin{quote}
\begin{verbatim}
syntax:                 record_type ::= "{"  tyrow  "}"

                        tyrow ::=  lab ":" type  [ "," tyrow ]
\end{verbatim}
\end{quote}

\newpage
\section{Declarations}

Declarations are used to establish bindings of identifiers to values.
Every declaration is said to {\it import} some variables, and to {\it export}
other variables. The imported variables are the ones which are used in
the declaration, and are usually defined outside the declaration (except in
recursive declarations). The exported variables are the ones defined in
the declaration, and that are accessible in the scope of the declaration.

A declaration can be a value binding, an overload declaration,
a type binding, a sequential composition,
a local declaration, a module import or a lexical declaration.

\begin{quote}
\begin{verbatim}
syntax:         declaration ::= "val" value_binding
                                "fun" fun_binding
                                "overload" overload_binding
                                "type" type_binding
                                "datatype" datatype_binding
                                abstype_declaration
                                "exception" exception_binding
                                local_declaration
                                sequential_declaration
                                import_declaration
                                lexical_declaration
\end{verbatim}
\end{quote}

\subsection{Value bindings}

Value bindings introduce identifiers and give them values (including
functional values), and are prefixed by the
keyword {\bf val}.

\begin{quote}
\begin{verbatim}
syntax:         value_binding ::= pat "=" exp  [ "and" value_binding ]
                                  "rec" value_binding
\end{verbatim}
\end{quote}

\subsubsection{Simple bindings}

The simplest form of value binding, called a {\it value definition},
introduces a single pattern or function.  It has the form pat = exp.
Each such declaration imports the variables used in the expression
{\bf exp} and exports the variables defined on the left of {\bf =}.
Here are some examples:

\begin{quote}
\begin{verbatim}
declaration:                    val x = 2 * 3;

binding:                        val x = 6 : int

declaration:                    val (x,y) = (x+1,[]);

bindings:                       val x = 7 : int
                                val y = [] : 'a list

declaration:                    val K = (fn x=> (fn y=> y))x;

binding:                        val K : 'a -> ('b -> 'a)
\end{verbatim}
\end{quote}

Note that the expression on the right is evaluated in the environment
that applies at the point the declaration is encountered.

\subsubsection{Parallel bindings}

To bind the patterns {\bf p1} .. {\bf pn } simultaneously to the values
of {\bf e1} .. {\bf en} one can write either of the following declarations:

\begin{quote}
\begin{verbatim}
        val (p1, .. ,pn) = (e1, .. ,en);

        val p1 = e1 and .. and pn = en;
\end{verbatim}
\end{quote}

\noindent
The first case involves a composite pattern; in the second case
we use the parallel binding {\bf and} construct.
The bindings of each declaration are
established `in parallel', in the sense that the bindings exported from
any of the component declarations are not imported by any other component.
The whole construct exports the union of the bindings made in
{\bf p1} .. {\bf pn}. It is 
illegal to bind to the same variable more than one component declaration.

For example, note how it is possible to swap two values without using
a temporary variable:

\begin{quote}
\begin{verbatim}
declaration:            val a = 10 and b = 5;

bindings:               val a = 10 : int
                        val b = 5 : int

declaration:            val a = b and b = a;

bindings:               val a = 5 : int
                        val b = 10 : int
\end{verbatim}
\end{quote}

\subsubsection{Recursive bindings}

The operator {\bf rec} builds recursive bindings, and it is used to define
recursive and mutually recursive functions. The binding {\bf rec d}
exports the variables exported by the binding {\bf d},
and imports the variables imported by {\bf d} and the variables exported by
{\bf d}.

\begin{quote}
\begin{verbatim}
syntax:         recursive_value_binding ::= "rec" value_binding

declaration:

  val rec fib = (fn n => if n < 2 then 1 else fib(n-1) + fib(n-2));
\end{verbatim}
\end{quote}

\noindent
Note that if {\bf rec} were omitted, the identifier {\bf fib} on the
right of {\bf =} would not refer to its defining
occurrence on the left of {\bf =}, but to some previously defined {\bf fib}
value (if any) in the surrounding scope.

A recursive value declaration can only define functions; all the bindings
contained in a {\bf rec} must be {\it syntactically} functions, i.e., simple
variable bindings having fn-expressions on the right of the {\bf =}.
A definition like {\bf val rec g = f;} is not accepted, even if {\bf f}
is a function.

\subsection{Clausal function definitions}

\noindent
A clausal function definition is a convenient method of defining functions,
it is equivalent to a {\bf val} binding to a lambda expression with
patterns.

\begin{quote}
\begin{verbatim}
syntax:         clausal_fun_defn ::= clause_defn [ "and" clausal_fun_defn ]


syntax:         clause_defn ::= ide arglist [: type] "=" expression
                                  [ "|" clause_defn ]

syntax:         arglist ::= simp_pat [arglist]
\end{verbatim}
\end{quote}

See appendix B for the full syntax of clausal function definitions
that contains a number of variants for infix function definitions.

A clausal function definition is mutually recursive; all functions defined
can refer to each other and themselves. Each function must have a consistent
name and number of arguments, and no function name can be defined more than
once in a definition.

\begin{quote}
\begin{verbatim}
declaration:      fun fact 0 = 1
                    | fact n = n * fact (n-1);

binding:          val fact = fn : int -> int
\end{verbatim}
\end{quote}

\noindent
The above definition of {\bf fact} defines the factorial function. The
first clause matches the base case of the factorial of 0 which is 1. The
second clause matches other values and evaluates {\bf n * (n-1)!}.

The clausal function definition is derived form:

\begin{quote}
{\tt
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ fun ide a$_{11}$ .. a$_{1n}$ : ty$_1$= E$_1$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | ..

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | ide a$_{m1}$ .. a$_{mn}$ : ty$_m$= E$_m$
}
\end{quote}

\noindent is equivalent to

\begin{quote}
{\tt
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ val rec ide = fn var$_1$ => .. fn var$_n$ =>

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ case (var$_1$,..,var$_n$) of

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (a$_{11}$, .., a$_{1n}$) = E$_1$ : ty$_1$

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | ..

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | (a$_{m1}$, .., a$_{mn}$) = E$_m$ : ty$_m$
}
\end{quote}

\subsection{Overloading and Implicit Parameters}

The main area that watML extends standard ML is in its more general
overloading scheme based on implicit parameters. An overload binding
either defines an overload {\it template} or an overload {\it instance},
and is prefixed by the keyword {\bf overload}.

\begin{quote}
\begin{verbatim}
syntax:         overload_binding ::= ide [: [ implicits ] type ] [ = exp ]
\end{verbatim}
\end{quote}

\subsubsection{Overload Templates}

An overload template defines an identifier as being overloaded and gives
it a base type.

\begin{quote}
\begin{verbatim}
declaration:    overload + : 'a * 'a -> 'a;
\end{verbatim}
\end{quote}

\noindent In the above example, {\bf +} is defined as an overloaded
identifier, and any occurrence of overloaded {\bf +} will be given
an initial type when type checking of {\bf 'a * 'a $\rightarrow$ 'a}. If
no type is given, the identifier has an initial type of {\bf 'a}.

\subsubsection{Overload Instances}

An overload instance defines one instance of an overloaded identifier.

\begin{quote}
\begin{verbatim}
declaration:    overload +  = fn (x,y) => x^y;

binding:        val overload = fn : string * string -> string
\end{verbatim}
\end{quote}

\noindent The above instance defines {\bf +} for strings.

\subsubsection{Overloading}

When the analyser looks up an identifier in the current environment,
if its most recent entry is overloaded, then the identifier is overloaded
and has an initial type of its most recent template. After type checking,
the compiler tries to find an overloaded instance that `matches' its
use, and if it finds an instance, substitutes it in for the overloaded
identifier.

The matching process can be defined as follows. First, define the
{\it argument type} of a type, $T$, to be, if $T$ is not a function then
$T$, else it is the longest type $P$ such that for some type $R$,
$P$ $\rightarrow$ $R$ = T. In other words, if $T$ is a function, the argument
type is all the curried arguments (with the result type stripped off).
Now, an overloaded identifier matches an instance, if the
argument type of the instance can be specialized to be the same as
the argument type of the identifier, and both full types unify.

Intuitively, the arguments to an overloaded function are used in the match,
but not its result type, and
an instance can be specialized to be made equal to an identifier,
but an identifier cannot be specialized. So an instance of {\bf eq} of type
$ ({}'a *{}'b) * ({}'a *{}'b) \rightarrow bool $
can be specialized and will match an
identifier {\bf eq} of type $ (int * bool) * (int * bool) \rightarrow{}'a $
but an identifier {\bf +} of type $ ({}'a *{}'a) \rightarrow{}'a $
will not be specialized to match instance $ int * int \rightarrow int $.

If an overloaded identifier is not resolved (a matching instance is not
found) an {\it implicit parameter} is introduced. An implicit parameter
acts like an ordinary function parameter except that it is inferred
automatically by the compiler. An implicit parameter is denoted in a type
expression by a prefix of {\it [ ? ide : type ]}.

\begin{quote}
\begin{verbatim}
declaration:      fun sq x = x * x;

binding:          val sq = [?*: 'a * 'a -> 'b] 'a -> 'b
\end{verbatim}
\end{quote}

\noindent In this example, the overloaded identifier {\bf *} (with initial
type {\bf 'a}) could not be resolved, and introduces an implicit parameter.
The internal representation of {\bf sq} would be

\begin{quote}
{\tt
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ fun sq *$'$ x = x *$'$ x;
}
\end{quote}

\noindent
The use of {\bf sq} will add the overloaded identifier {\bf *} which
must be resolved as before; the only difference is that if {\bf *} is
resolved, instead of the matching instance substituting the overloaded
identifier, it is supplied as an argument to {\bf sq}.

\begin{quote}
{\tt
expression:               (sq 3, sq 4.5);

translation:              (sq *$_{int}$ 3, sq *$_{real}$ 4.5);

result:                   (9,20.25) : int * real
}
\end{quote}

An overload instance can have implicit parameters. For example,

\begin{quote}
\begin{verbatim}
declaration:    overload eq = fn ((a,b),(c,d)) => eq(a,c) andalso eq(b,d);

binding:        val eq = [?eq: 'a * 'b -> bool] [?eq: 'c * 'd -> bool]
                            ('a * 'c) * ('b * 'd) -> bool
\end{verbatim}
\end{quote}

\noindent This overloaded instance of {\bf eq} for pairs requires an
overloaded instance of {\bf eq} for each component of the pair.

In some cases, an instance requires an overloaded identifier that it doesn't
actually use in its definition. For example, if the reference constructor
{\bf ref} is being defined as an overloaded identifier using an unsafe
primitive {\bf address} that returns a reference to any object, the
instance for lists could be defined as 
 
\begin{quote}
\begin{verbatim}
declaration:    overload ref : [? ref: 'a -> 'a ref] 'a list -> 'a list ref
                            = fn l => address l;
\end{verbatim}
\end{quote}

\noindent
The implicit parameter {\bf ref} is required for the element of the list
but is not needed in the expression defining the instance.

Implicit parameters cannot occur inside a type, e.g., the type
{\tt (int * [?+:('a * 'a) -> 'a]'a -> 'a)} is illegal.
This restricts the use of overloaded identifiers.

\begin{quote}
\begin{verbatim}
declaration:      val x = (3,double);

binding:          val x = [?+: ('a * 'a) -> 'b] (int * ('a -> 'b))

declaration:      val (a,b) = x;

result:           Error: val declaration has invalid form for implicits
\end{verbatim}
\end{quote}

\noindent As the type of {\bf x} has the implicit {\bf +} outside of
{\tt int * 'a -> 'b}, then {\bf x} cannot be destructed by pattern matching
until the implicit parameter is resolved.

\subsection{Type bindings}

Type bindings define type abbreviations, and are prefixed by the
keyword {\bf type}. Type bindings are {\it non-generative}; they do not
define new types in the system, only abbreviations.

\begin{quote}
\begin{verbatim}
syntax:       type_binding ::= typvarseq ide "=" type ["and" type_binding]
\end{verbatim}
\end{quote}

Some examples demonstrate the definition of type bindings:

\begin{quote}
\begin{verbatim}
declaration:      type person = {name: string, age: int}

declaration:      type 'a idfun = 'a -> 'a;

declaration:      type ('a,'b) pair = ('a * 'b);
\end{verbatim}
\end{quote}

During type checking, a type abbreviation can be regarded as being fully
expanded. When reporting bindings and results at the top-level, however,
the system uses any type abbreviation information it knows about an expression.

\begin{quote}
\begin{verbatim}
declaration:      type x = int;

expression:       3 : x;

result:           3 : x

expression:       2 + (3 : x);

result:           5 : int
\end{verbatim}
\end{quote}

\subsection{Data Type Declarations}

Data type bindings define new types and their constructors, and are prefixed
by the keyword {\bf datatype}. Data type bindings are mutually recursive.
Unlike type bindings, data type bindings define new types and are therefore
{\it generative}.

\begin{quote}
\begin{verbatim}
syntax:         datatype_binding ::= typvarseq ide = type_cases
                                       [and datatype_binding]

syntax:         type_cases ::= ["op"] con ["of" type] ["|" type_cases]
\end{verbatim}
\end{quote}

By convention, constructors start with a capital letter.

Here are examples of data types with zero, one and two type parameters and
a recursive data type:

\begin{quote}
\begin{verbatim}
declaration:    datatype intpair = Intpair of int * int;

bindings:       datatype intpair = Intpair of int * int
                con Intpair : (int * int) -> intpair

declaration:    datatype 'a pair = Pair of 'a * 'a;

bindings:       datatype 'a pair = Pair of 'a * 'a
                con Pair : ('a * 'a) -> ('a pair)

declaration:

    datatype ('a,'b) pairpair = Pairpair of ('a * 'b) * ('a * 'b);

bindings:

    datatype ('a,'b) pairpair = Pairpair of ('a * 'b) * ('a * 'b)
    con Pairpair : (('a * 'b) * ('a * 'b)) -> (('a, 'b) pairpair)

declaration:

    datatype 'a tree = leaf of 'a | node of ('a tree) * ('a tree);

bindings:

    datatype 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree)
    con Leaf : 'a -> ('a tree)
    con Node : (('a tree) * ('a tree)) -> ('a tree)
\end{verbatim}
\end{quote}

All the type variables appearing on the right of the defining {\bf =} sign
must appear of the left as parameters of the type being defined. The list
of parameters on the left of the {\bf =} sign must be a sequence of distinct
type variables. All constructors within a single data type must be
distinct, and all data type identifiers must be distinct.


\subsection{Abstract Data Type Declarations}

Abstract data types can be defined by the {\bf abstype} declaration.

\begin{quote}
\begin{verbatim}
syntax:           abstract_declaration ::=
                    "abstype" datatype_binding "with" declaration "end"
 
\end{verbatim}
\end{quote}

An abstract data type defined by the {\bf abstype} keyword is like a concrete
data type defined by the {\bf datatype} keyword, but its constructors are
only available in the declaration following the {\bf with} keyword. Outside
the body of the abstract data type, the constructors are hidden and cannot
be referred to. The abstract data type therefore provides a mechanism for
information hiding; the implementation used for the abstract data type
cannot be accessed outside the abstract data type.

\begin{quote}
\begin{verbatim}
declaration:      abstype position = Position of int * int
                  with
                    val origin = Position(0,0);
                    fun stepx (Position(x,y)) = Position(x+1,y);
                    fun stepy (Position(x,y)) = Position(x,y+1)
                  end;

binding:          abstype position
                  val origin = - : position
                  val stepx = fn : position -> position
                  val stepy = fn : position -> position
\end{verbatim}
\end{quote}

\noindent
In this example, a position can only be achieved by single steps from the
origin. The representation of the origin is printed as ``-'' at the top-level
as its implementation is hidden.

Here is a definition of a parametric recursive data type of binary trees
with leaves of type {\bf 'a}:

\begin{quote}
\begin{verbatim}
declaration:      abstype 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
                  with
                    fun mkleaf a = Leaf a;
                    fun mknode (s,t) = Node(s,t);
                    fun isleaf(Leaf _) = true |
                        isleaf _ = false;
                    fun left (Node(s,_)) = s;
                    fun right (Node(_,t)) = t;
                    fun tip (Leaf a) = a
                  end;

binding:          abstype 'a tree
                  val mkleaf = fn : 'a -> ('a tree)
                  val mknode = fn : (('b tree) * ('b tree)) -> ('b tree)
                  val isleaf = fn : ('c tree) -> bool
                  val left = fn : ('d tree) -> ('d tree)
                  val right = fn : ('e tree) -> ('e tree)
                  val tip = fn : ('f tree) -> 'f

\end{verbatim}
\end{quote}

\noindent
The constructors {\bf Leaf} and {\bf Node} are only known during the definition
of the basic operations on trees, and are not exported outside the
abstract data type definition. All users of the {\bf tree} abstract data type
will be unable to take advantage of the concrete representation of trees
given by `{\bf leaf of 'a $|$ node of 'a tree * 'a tree}', thus making
this type `abstract'.

In keeping with their abstractness,
abstract data types do not admit equality (see section 3.19).

\subsection{Exception Declarations}

An exception declaration defines one or more exception
constructors. A simple exception constructor (one without an argument)
can be regarded as as an exception itself, a complex exception constructor
takes an argument and produces an exception. All exceptions have type
{\bf exn}.

\begin{quote}
\begin{verbatim}
syntax:         exception_declaration ::= "exception" exbind

syntax:         exbind ::= ["op"] ide ["of" type] ["and" exbind]
\end{verbatim}
\end{quote}

Following the convention of datatype constructors, exceptions usually
have their first letter capitalized.

Exception declarations are {\it generative} and produce a fresh exception
each time they are evaluated. For example,

\begin{quote}
\begin{verbatim}
declaration:       fun f x =
                     let
                       exception F
                     in
                       if x=0 then raise F
                         else (f (x-1)) handle F => 0
                     end;

expression:        f 4;

result:            Unhandled exception F
\end{verbatim}
\end{quote}

\noindent
As the declaration {\bf exception F} generates a new exception each time
{\bf f} is called, the exception {\bf F} raised when {\bf x} is 0, is
different from the exception {\bf F} being trapped by the {handle} expression,
and so is not caught.

\subsection{Local Declarations}

A local declaration sets up temporary
bindings for a declaration; that is, variables exported from the first
declaration are imported by the second one but not from the whole
construct.  Instead, the whole construct exports just those bindings
made in the second declaration.

\begin{quote}
\begin{verbatim}
syntax:         "local" declaration "in" declaration "end"
\end{verbatim}
\end{quote}

The first declaration remains in force just while the second is being
elaborated.

\begin{quote}
\begin{verbatim}
declaration:            local
                          fun rev' ([],l) = l
                            | rev' (a::b,l) = rev' (b,a::l)
                        in
                          fun reverse l = rev' (l,[])
                        end;

binding:                val reverse = fn : ('a list) -> ('a list)
\end{verbatim}
\end{quote}

\subsection{Sequential declarations}

Cascaded, or `sequential' declarations are provided by the environment
operator `{\bf ;}', which makes earlier declarations available inside later
declarations.

\begin{quote}
\begin{verbatim}
syntax:         sequential_declaration ::= declaration ";" declaration
\end{verbatim}
\end{quote}

In {\bf d1} ; {\bf d2}, the variables exported by {\bf d1} are imported
into {\bf d2}, but not vice versa. The variables exported by
the whole declaration are the ones exported by {\bf d2},
plus the ones exported by {\bf d1} which are not redefined
in {\bf d2}.

\begin{quote}
\begin{verbatim}
expression:             let val a = 10;   val b = a + 5  in b end;

result:                 15 : int
\end{verbatim}
\end{quote}

\subsection{Import declarations}

The {\bf import} environment operator acts on precompiled modules, and it is
explained in detail in section ``Modules''.
A declaration import {\bf M} imports
no variables from the surrounding environment, and exports the variables
exported by the module {\bf M}.

\begin{quote}
\begin{verbatim}
syntax:         import_declaration ::= "import" module_name .. module_name

declaration:                    import minmax;

bindings:                       val min : (int * int) -> int
                                val max : (int * int) -> int
\end{verbatim}
\end{quote}

where the module {\bf minmax} contains definitions for the {\bf min} and
{\bf max } functions.

\subsection{Lexical declarations}

Special kinds of declaration, introduced by the keywords {\bf nonfix},
{\bf infix} and {\bf infixr} are used to
specify lexical attributes of identifiers.
These declarations have only a lexical meaning; they do not introduce bindings,
nor causes evaluations.

All identifiers have a property called {\it fixity}, which can be {\it infix}
or {\it nonfix}
(i.e., normal). The fixity of an identifier determines the way arguments
are syntactically supplied to it (see section ``Application'' for the
patterns of usage).  The result of parsing also depends on whether
infix operators are left or right associative.
Fixity can be specified in a {\it lexical} declaration, before the identifier
is used in declarations or expressions; at this time it can be given
a precedence and it associativity will be specified.

\begin{quote}
\begin{verbatim}
syntax:         lexical_declaration ::=
                                "infix"  [digit]  ide .. ide
                                "infixr" [digit]  ide .. ide
                                "nonfix"  ide .. ide

declarations:             infix  5  <-->;
                          infixr !!
                          nonfix +;
\end{verbatim}
\end{quote}

This example declares a left associative infix operator {\bf $<$--$>$}
with precedence 5 and a right associative operator {\bf !!} with default
precedence 0 as well as putting the operator {\bf +} back to a status of
non-infix identifier. These operators can now
be uses in expressions and declarations according to their new lexical status.

A lexical declaration can be used in scopes blocks. In this case
the newly defined fixity status is only active in the local scope.

\newpage
\section{I/O streams}

Input-output is done on input streams (type {\bf instream}) and output
streams (type {\bf outstream}) as appropriate.  They are both abstract data
types but may be thought of as being a (possibly infinite) sequence of
characters.  These are the predefined objects that relate to streams:-

\begin{quote}
\begin{verbatim}

        std_in                 :instream
        std_out                :outstream

        open_in                :string -> instream
        input                  :(instream * int) -> string
        lookahead              :instream -> string
        close_in               :instream -> ()
        end_of_stream          :instream -> bool

        open_out               :string -> outstream
        output                 :(outstream * string) -> ()
        close_out              :outstream -> ()
\end{verbatim}
\end{quote}

The streams {\bf std\_in} and {\bf std\_out} are the normal means of
accessing the terminal, while {\bf open\_in} and {\bf open\_out} are the
means of accessing the file whose name (a string) is supplied.


The call {\bf input(IS,n)} returns a string containing the n leading
characters in stream {\bf IS}. The stream is side-effected,
the n characters being removed from {\bf IS}.
If the file associated with {\bf IS} ends after
only k characters (less than the required n characters), then
the string returned has length k.

The point of the lookahead function is to determine what the next
character in an input stream is, without removing it.  If the file is
closed the empty string is returned.

It is possible for an input stream (which may be a communication channel)
to not be able to satisfy a lookahead or input request for some time;  in
this case the input operation suspends until characters are available.

The call {\bf output(OS,s)} simply writes the characters of s onto
the stream OS.

\newpage
\section{Modules}

A {\it module}
is a (normally related) set of bindings (values, functions and types)
which can be compiled and stored away, and later {\it imported}
as a declaration wherever those bindings are needed. Modules are identified
by {\it module names}.
Module names can syntactically be represented as simple identifiers,
or as strings containing Unix file paths, say, to access modules in
directories other than the current one.  Here is a module
called {\bf Pair} which defines a type and two functions.

\begin{quote}
\begin{verbatim}
module:         module Pair
                body
                  abstype 'a pair = pair of 'a * 'a
                  with
                    val newpair (a,b) = pair(a,b)
                    and left (pair(a,_))  =  a
                    and right (pair(_,b))  =  b
                  end
                end;
\end{verbatim}
\end{quote}

Module definitions can only appear at the top level, and they cannot
rely on bindings defined in the surrounding scope (e.g., previous
top level definitions). All the bindings used by a module must either
be defined in the module itself, or imported from other modules.

The processing of a module definition is called a module {\it compilation},
whose only effect is to produce a separately compiled version of the module.
Module definitions do not evaluate to values, and they do not
introduce new bindings.

Modules can be defined interactively, but usually they are contained in
external source files. In the latter case, a command `{\tt use "Mod.ml";}'
(see section "Loading source files") can be used to compile a module definition
contained in the file {\bf Mod.ml}.
Once a module is compiled, it can be imported:

\begin{quote}
\begin{verbatim}
declaration:            import Pair;

bindings:               module /usr/lib/ml/lib
                        abstype 'a pair
                        val newpair : ('b * 'b) -> ('b pair)
                        val left : 'c pair -> 'c
                        val right : 'd pair -> 'd
\end{verbatim}
\end{quote}

A declaration {\bf import M} can also appear in local scopes and inside
functions, wherever a declaration is accepted (the binding module
{\bf /usr/lib/ml/lib} mentioned above is explained later).

Importing can result in {\it loading}
a module, when that module is imported for the first time in an
interactive session, or in {\it sharing}
an already loaded module, all the subsequent times.
The loading/sharing mechanism is explained below in ``Module sharing''.

No evaluation takes place when a module is compiled. Instead, the module body
is evaluated every time the module is {\it loaded}.
If the module body contains side effecting operations (such as input/output),
they have effect at loading time, i.e., they do not have effect if the module
is being shared.

More precisely, we can say that a module is an {\it environment}
{\it generator}; loading a module corresponds to generating a new environment,
and sharing a module corresponds to using an already generated environment.

\subsection{Module hierarchies}

A module {\bf A} can import other modules {\bf B}, {\bf C}, etc.
The import relations
between modules determine a module hierarchy. The hierarchy is
dynamic, because of the possibility of conditional imports and of
hidden imports caused by functions imported from other modules.

A module can import other modules for several reasons.

\begin{quote}
\begin{verbatim}
module:         module A1
                body
                  fun f a =
                    let import B1
                    in .. end
                end;

module:         module A2
                body
                  local
                    import B2
                  in 
                    fun f a = ..
                    and g b = ..
                  end
                end;

module:         module A3
                body
                  import B3;
                  fun f a = ..
                  and g b = ..
                end;
\end{verbatim}
\end{quote}

The first example above shows a module {\bf B1} locally imported for the
private use of a function in {\bf A1}. The second example shows a module
{\bf B2} imported for private use in a module {\bf A2}; the {\bf local}
construct guarantees that {\bf B2} is not exported from {\bf A2}.
The third example shows a module {\bf B3} which is imported by {\bf A3},
and also reexported.

Sometimes an imported module {\bf B} {\it must}
be reexported from an importing module {\bf A}.
This happens when a type identifier {\bf t} defined in {\bf B}
is contained in the (types of the) bindings exported by {\bf A}.
Exporting those binders without exporting {\bf B}
may potentially generate objects
of an unknown (in the current scope) type {\bf t}, on which no operations are
available.  Hence the following restriction applies:
whenever a type identifier is involved in the exports of a module,
its type definition must also be exported.

There is an alternative notation for modules which are imported and
{\bf reexported}.

\begin{quote}
\begin{verbatim}
module:         module A
                includes B C
                body
                        ..
                end;

module:         module A
                body
                  import B C;
                  ..
                end;
\end{verbatim}
\end{quote}

\noindent
The two forms above are equivalent; the first one is just an abbreviation for
the second one. The {\bf includes} keyword should be understood as the
set-theoretical inclusion of the bindings of {\bf B} and {\bf C};
not as the inclusion of the source lines constituting the definition of {\bf B}
and {\bf C}.

Every module automatically imports a standard library module, often
called {\bf /usr/lib/ml/lib}, which contains all the predefined ML types,
functions and values (remember that a module cannot access any outside
binding, except the ones explicitly imported; this also applies to the
predefined ML identifiers).
The library module is shown as a module {\bf /usr/lib/ml/lib}
binding, on import:

\begin{quote}
\begin{verbatim}
module:                 module A
                        body
                          val a = 3
                        end;
        
declaration:            import A;

bindings:               module /usr/lib/ml/lib
                        val a = 3 : int
\end{verbatim}
\end{quote}

The module {\bf /usr/lib/ml/lib} binding is only an abbreviation for all the
bindings defined in\break
{\bf /usr/lib/ml/lib.ml}:
they are really imported and (re-)defined at this point.

Similarly, when importing a module {\bf B} which exports a module {\bf A},
the bindings of {\bf A} are not explicitly listed. Instead a module {\bf A}
binding is presented as an abbreviation.

\begin{quote}
\begin{verbatim}
module:                 module A
                        body
                          val a = 3
                        end;

module:                 module B        
                        includes A
                        body
                          val b = 5
                        end;

declaration:            import B;

bindings:               module /usr/lib/ml/lib
                        module A
                        val b = 5 : int
\end{verbatim}
\end{quote}

In what follows, when we want to make those hidden bindings explicit,
we write them indented under the respective {\bf module} bindings:

\begin{quote}
\begin{verbatim}
declaration:            import B;

bindings:               module /usr/lib/ml/lib
                        module A
                                val a = 3 : int
                        val b = 5 : int
\end{verbatim}
\end{quote}

\subsection{Module sharing}

In an interactive session, a compiled module can be imported several times,
but it is only loaded {\it once},
the first time it is imported. All the following imports of that module
simply fetch the already loaded module. For example, two consecutive top
level {\bf import A;} declarations are semantically equivalent to only one
of them, and no extra work is actually done in the second import.

At any moment there is at most one copy of a module in the system,
and that copy is shared among all the modules which import it.
Sharing means that types are shared, and that values are shared; for example:

\begin{quote}
\begin{verbatim}
module:                 module A
                        body
                          abstype T = T of int
                          with    val absT n = T n
                                  and repT (T n) = n
                          end;
                          val a = ref 3
                        end;


module:                 module B
                        includes A
                        body
                          val BabsT,BrepT = absT,repT
                          and b = a
                        end;

module:                 module C
                        includes A
                        body
                          val CabsT,CrepT = absT,repT
                          and c = a
                        end;

module:                 module D
                        includes B C
                        body
                        end;

declaration:            import D;

bindings:               module /usr/lib/ml/lib
                        module B
                                module /usr/lib/ml/lib
                                module A
                                        module /usr/lib/ml/lib
                                        type T
                                        val absT : T -> int
                                        val repT : int -> T
                                        val a = (ref 3) : int ref
                                type T
                                val BabsT : T -> int
                                val BrepT : int -> T
                                val b = (ref 3) : int ref
                        module C
                                module /usr/lib/ml/lib
                                module A
                                        module /usr/lib/ml/lib
                                        type T
                                        val absT : T -> int
                                        val repT : int -> T
                                        val a = (ref 3) : int ref

                                type T
                                val CabsT : T -> int
                                val CrepT : int -> T
                                val c = (ref 3) : int ref
\end{verbatim}
\end{quote}

\noindent
Note that {\bf A} is imported by {\bf D} through two different import paths.

Sharing of types means that the module {\bf A} is not typechecked twice:
if it were, than we would have two {\it different} abstract types called
{\bf T} and {\bf CrepT(BabsT 3)}, for example, would produce
a type error.

Sharing of values means that the module {\bf A} is not evaluated twice:
hence {\bf b} and {\bf c} are the {\it same}
reference variable, so that any side effect on {\bf b}
will be reflected on {\bf c}, and vice versa.

Sharing of values also has the desirable effect that multiply imported
functions (e.g., the library functions) are not replicated.

\subsection{Module versions}

The system automatically keeps track of module versions, to make sure,
for example, that when a module is significantly modified,
all the modules which depend on it are recompiled. The system however
does not automatically recompile obsolete modules; it simply produces
an error message and an exception. For example, when an obsolete module
{\bf A } is trying to import a new version of module {\bf B}, we have:

\begin{quote}
\begin{verbatim}
declaration:            import A;

failure:                Module A must be compiled
                        Unhandled exception Link
\end{verbatim}
\end{quote}

\noindent
This error message is generated in a variety of circumstances, but the
effect is always the same: module {\bf A} must be recompiled.

A new version of a module is generated whenever that module is recompiled and
its external interface (i.e., the types of the exported bindings) changes.

\newpage
\section{The ML system}

\subsection{Entering the system}

The user enters the ML system by typing ml as a shell command.  The
program invoked is actually a shell script which calls the real ML
executable with vanilla parameters.  The user may choose to adapt
this shell script.

The ML compiler takes three arguments; the library, the boot file and the editor
used by the AIMLESS
edit command. The library and boot are compulsory and must be
full path names. The editor is optional and defaults to {\bf vi}. A library
of standard functions is then loaded. This library is installation dependent
and is meant to contain the functions which are most used locally. The boot
file may reflect a user's individual requirements for predefined functions.

After the system prompt ('- '),
you can start typing expressions or definitions, or using AIMLESS commands.

\subsection{Exiting the system}

Type {\bf Control-D} to exit the system.
No program or data created during an ML session is preserved, except for
saved phrases (e.g. by using {\bf save all}) and compiled modules.

\subsection{Calling the operating system from ML}

Two functions are provided for communicating with the operating system.

\underline{system {\tt "}$<$command$>${\tt "};\ \ }
takes a string and executes the string as a command in the job control
language of the operating system. For example,

\begin{quote}
{\tt
\ \ \ - fun myedit str = system "vi "\^{}str;

\ \ \ {\char '76} val myedit = fn: string -{\char '76} ()
}
\end{quote}

defines a function {\bf myedit} that takes a string name of a file
and then calls the Unix command to edit that file.

\underline{systemquery {\tt "}$<$jcl variable$>${\tt "};\ \ }
takes job control language variable (as a
string) and returns the string bound to that variable in the
operating system environment in which ML was called. If the variable
is not bound exception Systemquery is raised. For example,

\begin{quote}
\begin{verbatim}
   - systemquery "HOME";
     "/users/jlo" : string
\end{verbatim}
\end{quote}

the variable {\bf HOME} is bound to /users/jlo in the current (Unix)
shell environment.

\subsection{Error messages}

The most common syntax and type errors are described in section ``Errors''. 
Here are some unfrequent messages which are generated in particular situations.

A type error occurs when two isomorphism types having the same
name are defined, and are allowed to interact:

\begin{quote}
\begin{verbatim}
        - let  abstype A = A of int
                with val absA n = A n end;
                abstype A = A of int
                with val repA (A n) = n end
           in repA(absA 3) end;
        Type Clash in:  (repA (absA 3))
        Looking  for :  A
        I have found :  A
        Clash between two different types having the same name: A
\end{verbatim}
\end{quote}

Equality has its own type errors:
\begin{quote}
\begin{verbatim}
        - let
            fun f a = a
          in 
            f = f
          end;
        Type Clash  in:  (f = f)
        Equality error
        type: 'a -> 'a
        cannot be used as equality type

        - let
            abstype a = A of int
            with 
              fun absA n = A n
              and repA (A n) = n
            end
          in
           absA 3 = absA 3
          end;
        Type Clash  in:  ((absA 3) = (absA 3))
        Equality error
        type: x
        cannot be used as equality type
\end{verbatim}
\end{quote}

A record pattern with a wildcard must be resolved or else an error occurs:
\begin{quote}
\begin{verbatim}
        - fun f {age=x,...} = x;
        Record: {age=x,...}
        Syntax Error: Record could not be resolved
\end{verbatim}
\end{quote}

In modules, all variables must be either locally declared or imported from other
modules: global variables cannot be used:
\begin{quote}
\begin{verbatim}
        - val a = 3;
        > val a = 3 : int

        - module A
           body val b = a end;
        Modules cannot have global variables.
        Unbound Identifier:  a
\end{verbatim}
\end{quote}

Modules which have never been compiled, or which are obsolete, produce a link
exception:

\begin{quote}
\begin{verbatim}
        - import A;

        Module A must be compiled
        Unhandled exception Link
\end{verbatim}
\end{quote}
 
\subsection{Monitoring the compiler}

\subsection{Garbage collection and storage allocation}

\newpage
\section{Editing and Debugging}

AIMLESS, An Interactive ML Editing Support System, is a programming
environment for ANU ML.  It provides a user interface for interactively
entering, testing and debugging ML programs.

\subsection{Basic Concepts}

The {\it phraselist}, represented as
$<$ $p_1$, .., $p_i$ $|$  $p_{i+1}$, ..,$p_n$ $>$ 
with $<$ $p_1$, .. , $p_n$$>$ being the {\it script}
and $<$ $p_{i+1}$, .. , $p_n$ $>$ the {\it buffer} ,
is the current collection of top-level phrases that the user has
some interest in.
Valid phrases entered into the system are added to the end of the script,
invalid phrases are added to the head of the buffer. At any time, the
phrases on the script define the current program. That is, only the phrases
on the script add to the top-level environment, phrases on the buffer are
``in limbo'' and do not add to the system.

The top-level environment and the store consist of the bindings and the
side-effects (respectively) of the phrases on the script.
The script may be viewed as that part of the program, or module, under
development that has proved acceptable to the ML system.
Phrases in the buffer are not part of the top-level environment and will
not have affected the store.

For example, with the initially empty phraselist $<$ $|$ $>$, if the user enters
the phrase {\tt val x = 10;} it is compiled and executed and the
phraselist becomes $<$ val x = 10; $|$ $>$.  If the syntactically invalid
phrase {\tt val a == x;} is then entered, it will be added to the
buffer. The phraselist would be $<$ val x = 10; $|$ val a == x; $>$.
The top-level environment would only have a binding for {\bf x}.

Definitions that raise a top-level exception are considered to be invalid
and are therefore placed on the buffer. An expression raising
a top-level exception is however considered valid and added to the script.

Continuing the previous example with phraselist of
$<$ val x = 10; $|$ val a == x; $>$, if the phrase {\tt val x = 10 div 0;}
is entered it raises a top-level Div exception. The phrase is added to
the buffer. The phraselist would be
$<$ val x = 10; $|$ val x = 10 div 0; , val a == x; $>$. Executing phrase
{\tt 10 div 0;} also raises a top-level Div exception but
as the phrase is an expression it is placed on the script. 
The phraselist would then be
$<$ val x = 10;, 10 div 0; $|$ val x = 10 div 0;, val a == x; $>$.

When an invalid phrase is added to the buffer, the phrase and the rest
of input is put as one phrase on the buffer. For example, if the
phrase {\tt val x = y; val z = x;} is entered with {\bf y } undefined
in the top-level environment, the ML phrase {\tt val x = y;}
will be invalid. The whole phrase {\tt val x = y; val z = x;}
is placed on the buffer.

\subsection{Editing Commands}

The AIMLESS editing commands manipulate the phraselist. Commands shown to
take integer argument n, default to 1 if no argument is given.

AIMLESS commands can only be executed at the top-level.

\underline{reset;\ \ }
restores AIMLESS to its initial state. The phraselist is empty.

\underline{pop n;\ \ }
moves phrases from the script onto the buffer. All bindings
added to the top-level environment and store side-effects caused
by popped phrases are undone.
No error message is reported if n is greater than
the number of phrases on the script.
{\bf pop all;} moves the whole script onto the buffer.

\underline{push n;\ \ }
attempts to move n phrases from the buffer onto the script.
If a phrase is invalid, the phrase remains on the buffer and the command
stops. No error message is reported if n is greater than
the number of phrases on the buffer.
{\bf push all;} attempts to push the whole buffer onto the script.

\underline{del n;\ \ }
deletes the first n phrases on the buffer.
No error message is reported if n is greater than
the number of phrases on the buffer. {\bf del all;} deletes the whole buffer.

\underline{edit n;\ \ }
textually appends the first n phrases
on the buffer, and places the resulting text in a text editor.
The text editor is specified in the initial call to ML.
The default editor is {\bf vi}. After editing the phrase is pushed.
No error message is reported if n is greater than
the number of phrases on the buffer.
{\bf edit all;} textually edits the whole buffer.

\underline{move k;\ \ }
takes an integer argument k and puts the k-th phrase in the
buffer as the first phrase on the buffer.
If k is zero or greater than the number of phrases on the buffer an
error is reported.

\underline{alter $<$ide$>$;\ \ }
takes an identifier argument ide, and finds the most recent phrase that
defines $<$ide$>$  in a {\bf val} or {\bf fun} definition.
If no phrase is found an error is reported. If a phrase is found, it
is moved onto the buffer by successive pops, edited (in the
same manner as command {\bf edit}) and then all phrases popped by this
command are pushed. If a pushed phrase is invalid, the pushing stops.

\underline{altertype $<$ide$>$;\ \ }
takes an identifier argument ide, and finds the most recent phrase that
defines $<$ide$>$  in a {\bf type}, {\bf datatype} or {\bf abstype}
definition. If no phrase is found an error is reported.
If a phrase is found, it
is moved onto the buffer by successive pops, edited (in the
same manner as command {\bf edit}) and then all phrases popped by this
command are pushed. If a pushed phrase is invalid, the pushing stops.

\underline{defer $<$ide-list$>$;\ \ }
adds a temporary
function definition for each identifier in its argument list. The deferred
function can then by mentioned by later phrases, but the application
of a deferred function at run-time is an error. Command {\bf defer} permits
programs to be built top-down; missing functions are deferred until they
are defined.

The AIMLESS display command shows parts of the phraselist.

\underline{show $\{$ script $|$ buffer $|$ all $|$ program $\}$;\ \ }
lists either the script, buffer, script and buffer, or the program, as
specified. The program is declarations, less any expressions.

\underline{whatdefn $<$ide$>$;\ \ }
takes an identifier
$<$ide$>$ and displays the most recent phrase on the script defining $<$ide$>$
in a {\bf val} or {\bf fun} definition.

\underline{whattype $<$ide$>$;\ \ }
displays the most recent phrase on the script defining $<$ide$>$
in a {\bf type}, {\bf datatype} or {\bf abstype} definition.

The AIMLESS aggregate composition and decomposition commands either construct
or destruct aggregates such as {\bf let}, {\bf local}, {\bf abstype} and
{\bf module}.

\underline{make $\{$ let $|$ local $|$ abstype $\}$;\ \ } prompts the
user as to which phrases to add to the aggregate specified. Any phrases
not included are added to the buffer.

\underline{make module;\ \ }
prompts for module name and then packages up specified phrases into a
module. The module is compiled and then imported.

\underline{unmake;\ \ } destructs the most recent phrase on the script into
sub-phrases, these are then pushed onto the script.

AIMLESS creates files in some temporary area.  In the case of an
extraordinary exit, these should be removed manually.  Under Unix the
area is /usr/tmp and the file can be eliminated by the command
{\bf rm /usr/tmp/ml*.}

\subsection{Operations on source files}

The AIMLESS file operations load or save parts of the phraselist from or to
file store.

\underline{use {\tt "}$<$filename$>${\tt "};\ \ }
redirects input from the specified file until end of file or an invalid phrase.
If an invalid phrase is read, the invalid phrase
and the rest of the file are placed as one
phrase on the buffer.  The filename can be any file name.
The file extension {\bf .ml} is normally used for ML source files, but this is
not compulsory.

Source files may again contain {\bf use} commands to load other source files
in a cascade.
There is a system-dependent limit on the depth of recursive loading: the
message {\bf Cannot open file: filename} is printed when such limit is
exceeded. The file {\bf filename} will not be loaded, but the loading of the 
previously opened files will continue.

Typing {\bf DEL} while loading a file will interrupt loading and bring you back
to the top level. This might not happen immediately, because some parts
of the compilation process are not interruptible, but it will have effect as
soon as the current phrase has finished compiling.

\underline{save $\{$ script $|$ buffer $|$ all $|$ program $\}$ {\tt "}$<$filename$>${\tt "};\ \ }
writes out the specified object (as shown by an equivalent {\bf show} command)
to the specified file.

The intended use of these file operations, is for the user to {\bf use}
a file containing the current program under development on starting
a login/logout session.
The program is then developed using the AIMLESS phraselist
operations. The script (or the script and the buffer) are saved if the
session is finished. When the program is finished, if desired,
it can be saved as a module by the {\bf make module} command.

\underline{cleanup $\{$ script $|$ buffer $|$ all $|$ program $\}$
$\{$prompt$\}$;\ \ }
As an alternative, the cleanup mechanism keeps track of phrases and the files
that they were read from. The cleanup command writes phrases back to their
files. The user is prompted for a file association for any phrases entered
interactively. The optional {\bf prompt} has the cleanup command prompt for
all phrases (so that phrase can be moved from one file association to another).

\subsection{Retests in AIMLESS}

The AIMLESS retest mechanisms provide feedback on changed test (top-level
expression) evaluation. Any expression popped onto the buffer and later
pushed back prints a warning message if its previous value is not equal
to its current value.

For example,
\begin{quote}
\begin{verbatim}
  - fun f x = x;
  > val f = fn: 'a -> 'a

  - f 10;
  10 : int

  - alter f;

(* edit f to be fun f x = x + 1; *)

  > val f = fn: int -> int
  ***********************
  test value changed
  Test Phrase: (f 10)
  Old: 10: int
  New: 11: int
  ***********************
\end{verbatim}
\end{quote}


Assertions can be used as ML declarations. An assertion has the form
\begin{quote}
\begin{verbatim}
       assert <expression> = <expression>;
\end{verbatim}
\end{quote}

\noindent If an assertion is appended or
pushed and is not true, it is in error and placed on the buffer.

\subsection{Tracing functions}

The AIMLESS trace commands allow function calls to be traced. The function
and its evaluated arguments are displayed on entry. On exit, the final
result of the application is displayed.

\underline{trace $<$ide-list$>$;}: Command {\bf trace} sets the trace flag on
the definition of each identifier in $<$ide-list$>$.
The definition must be a top-level binding and must be either a {\bf fun}
definition or a structured {\bf val} definition of the form
{\tt val $<$ide$>$ = fn PAT ={\char '76} EXP;}. It can be defined in an
{\bf abstype} or {\bf local} declaration but not a
module. Note that editing a function definition by
{\bf edit} or {\bf alter} does not remove the trace flag.
The trace command will fail if identifiers {\bf std\_out}, {\bf output},
{\bf  \^{}} or {\bf makestring} are re-defined. Note that identifier {\bf \^{}}
is an ANU ML primitive.

\underline{untrace $<$ide-list$>$;\ \ }
resets the trace flag on the definition of each identifier in $<$ide-list$>$.

\underline{importtrace $<$module$>$;\ \ }
is equivalent to an {\bf import} command except that any functional
form imported can now be traced. Note that popping the importtrace phrase
resets any trace flags set.

\newpage
\noindent{\bf Appendix A. Lexical classification of ASCII characters}

Ascii characters are classified into the following categories:
\begin{itemize}
\item Illegal \verb+          + Unacceptable in a source program. These
characters are ignored, and a warning message is printed.
\item Eof \verb+              + End-of-file character. It terminates an
interactive session, or stops
the process of reading a source ml file. A top level control-D is interpreted
as Eof, thereby exiting the system.
\item Blank \verb+            + Characters which are interpreted as a space
character ` '.
\item Digits \verb+           + Digits.
\item Letter \verb+           + Letters and other characters which can be used to form
identifiers.
\item Symbol \verb+           + 
A class of character which can be used to form symbolic identifiers.
\item Escape \verb+           + 
Escape character in strings. It behaves as a Symbol outside strings.
\item Quote \verb+            + String quotation character.
\item Delim \verb+            + One-character punctuation marks and
parentheses.
\end{itemize}

Moreover, any sequence of legal character enclosed between {\bf (*}
and {\bf *)} or end of file is a {\it comment}
(except when {\bf (*} and {\bf *)} appear in a string).
Comments can be nested. Each comment is considered equivalent
to a single space character.

\begin{quote}
\begin{verbatim}

000    nul     Eof;         001    soh     Illegal;     002    stx     Illegal;
003    etx     Illegal;     004    eot     Illegal;     005    enq     Illegal;
006    ack     Illegal;     007    bel     Illegal;     010    bs      Illegal;
011    ht      Blank;       012    lf      Blank;       013    vt      Blank;
014    ff      Blank;       015    cr      Blank;       016    so      Illegal;
017    si      Illegal;     020    dle     Illegal;     021    dc1     Illegal;
022    dc2     Illegal;     023    dc3     Illegal;     024    dc4     Illegal;
025    nak     Illegal;     026    syn     Illegal;     027    etb     Illegal;
030    can     Illegal;     031    em      Illegal;     032    sub     Illegal;
033    esc     Illegal;     034    fs      Illegal;     035    gs      Illegal;
036    rs      Illegal;     037    us      Illegal;     040    ' '     Blank;
041    '!'     Symbol;      042    '"'     Quote;       043    '#'     Symbol;
044    '$'     Symbol;      045    '%'     Symbol;      046    '&'     Symbol;
047    '''     Letter;      050    '('     Delim;       051    ')'     Delim;
052    '*'     Symbol;      053    '+'     Symbol;      054    ','     Delim;
055    '-'     Symbol;      056    '.'     Delim;       057    '/'     Symbol;
060    '0'     Digit;       061    '1'     Digit;       062    '2'     Digit;
063    '3'     Digit;       064    '4'     Digit;       065    '5'     Digit;
066    '6'     Digit;       067    '7'     Digit;       070    '8'     Digit;
071    '9'     Digit;       072    ':'     Symbol;      073    ';'     Delim;
074    '<'     Symbol;      075    '='     Symbol;      076    '>'     Symbol;
077    '?'     Symbol;      100    '@'     Symbol;      101    'A'     Letter;
102    'B'     Letter;      103    'C'     Letter;      104    'D'     Letter;
105    'E'     Letter;      106    'F'     Letter;      107    'G'     Letter;
110    'H'     Letter;      111    'I'     Letter;      112    'J'     Letter;
113    'K'     Letter;      114    'L'     Letter;      115    'M'     Letter;
116    'N'     Letter;      117    'O'     Letter;      120    'P'     Letter;
121    'Q'     Letter;      122    'R'     Letter;      123    'S'     Letter;
124    'T'     Letter;      125    'U'     Letter;      126    'V'     Letter;
127    'W'     Letter;      130    'X'     Letter;      131    'Y'     Letter;
132    'Z'     Letter;      133    '['     Delim;       134    '\'     Escape;
135    ']'     Delim;       136    '^'     Symbol;      137    '_'     Letter;
140    '`'     Symbol;      141    'a'     Letter;      142    'b'     Letter;
143    'c'     Letter;      144    'd'     Letter;      145    'e'     Letter;
146    'f'     Letter;      147    'g'     Letter;      150    'h'     Letter;
151    'i'     Letter;      152    'j'     Letter;      153    'k'     Letter;
154    'l'     Letter;      155    'm'     Letter;      156    'n'     Letter;
157    'o'     Letter;      160    'p'     Letter;      161    'q'     Letter;
162    'r'     Letter;      163    's'     Letter;      164    't'     Letter;
165    'u'     Letter;      166    'v'     Letter;      167    'w'     Letter;
170    'x'     Letter;      171    'y'     Letter;      172    'z'     Letter;
173    '{'     Delim;       174    '|'     Symbol;      175    '}'     Delim;
176    '~'     Symbol;      177    DEL     Illegal;

\end{verbatim}
\end{quote}

\newpage
\noindent{\bf Appendix B. The Context-Free Syntax of ML}

In the following productions, strings between quotes `{\tt {\char '42}}'
are terminals, while identifiers are non-terminals.

Juxtaposition is syntactic concatenation and `$|$' is syntactic alternative.

`\{ .. \}n' indicates a phrase ` .. ' repeated n or more times (default n=0) and
`[ .. ]' indicates an optional construct (i.e. repeat of 0 or 1) ` .. '.
 `\{ .. / - \}n' means n (default 0) or more times `..' separated by `-'.

Parentheses `( .. )' are used for precedence.

\noindent {\bf Syntax of lexical entities}

\begin{quote}
\begin{verbatim}

Letter ::=   "a"  |  ..  |  "z"  |  "A"  |  ..  |  "Z"  |   "_".

Digit ::=   "0"  |  ..  |  "9".

Symbol ::= "!"  |  "#"  |  "%"  |  "&"  |  "*"  |  "+"  |  "-"  |  "/"  |
           ":"  |  "<"  |  "="  |  ">"  |  "?"  |  "@"  |  "\"  |  "^"  |
           "`"  |  "|"  |  "~".

Character ::= ..
     (see appendix "Lexical classes" for a list of legal characters)

Ide ::=   Letter {Letter  |  Digit  |  "'"}   |   {Symbol}1.

Integer ::=   {Digit}1.

Real ::=    Integer "." {Digit}   |  Integer "E" Integer   |
            Integer "." {Digit} "E" Integer.

String ::=   """" {Character} """".

Var ::=   Ide.

Constant ::=   Integer  |  Real  |  String.

Con ::=   Ide.

ExCon ::=   Ide.

TypeIde ::=   Ide.

TypeVar ::=   "'" ["'"] ["_"] Ide.

Lab ::=   Ide  |  Integer.

ModuleName ::= Ide   |   String.

\end{verbatim}
\end{quote}

\newpage
\noindent{\bf Syntax of Composite Phrases}

Syntactic alternatives are in order of decreasing precedence.

\begin{quote}
\begin{verbatim}

Phrase ::=   [Exp  |  Decl  |  Module  |  "use" String  |  "monitor"] ";".

Module ::=  "module" ModuleName ["includes" {ModuleName}1] "body" Decl "end".

SimpleExp ::= Constant
              ["op"] Var  |
              ["op"] Con  |  ["op"] ExCon  |
              "{" {Lab "=" Exp / ","} "}"  |
              "#" Lab  |
              "()"   |
              "(" {Exp / ","}2 ")"  |
              "[" {Exp / ","} "]"  |
              "(" {Exp / ";"}1 ")"  |
              "let" Decl "in" Exp "end"
              "(" Exp ")".

ApplExp ::=   SimpleExp   |   ApplExp  SimpleExp.

InfixExp ::=   ApplExp   |   InfixExp Ide InfixExp.

Exp ::= InfixExp  |
        Exp ":" Type  |
        Exp andalso Exp  |
        Exp orelse Exp  |
        Exp "handle" Match  |
        "raise" Exp  |
        "if" Exp "then" Exp "else" Exp  |
        "while" Exp "do" Exp  |
        "case" Exp "of" Match  |
        "fn" Match.

Decl ::= "val" ValBind  |
         "fun" FValBind  |
         "overload" OverBind |
         "type" TypeBind  |
         "datatype" DataTypeBind ["withType" TypeBind]  |
         "abstype" DataTypeBind ["withType" TypeBind] "with" Decl "end"  |
         "exception" ExBind  |
         "local" Decl "in" Decl  |
         [ Decl ]  |
         "import" {ModuleName}1  |
         Decl [;] Decl  |
         "infix" [Digit] {Ide}1  |  "infixr" [Digit] {Ide}1  |  "nonfix" {Ide}1.
\end{verbatim}
\end{quote}

\newpage

\begin{quote}
\begin{verbatim}

ValBind ::=   Pat "=" Exp ["and" ValBind]   |   "rec" ValBind.

FValBind ::=   { ["op"] Var {SimpleExp}1 [":" Type] "=" Exp / "|" }1
                           ["and" FValBind].

  If Var has infix status, either "op" must be present, or Var must be infixed,
as in (SimpleExp Var SimpleExp)...; the parentheses may also be dropped if
":" Type or "=" follows immediately.

OverBind ::=   ide [: [ Implicits ] Type] [ = Exp ].

TypeBind ::=   [TypeParams] TypeIde "=" Type ["and" TypeBind].

DataTypeBind ::=   [TypeParams] TypeIde "=" {["op"] Con ["of" Type] / "|"}1
                           ["and" TypeBind].

ExBind ::=   ExCon ["of" Type] ["and" ExBind].

TypeParams ::=   TypeVar   |   "(" {TypeVar / ","}1 ")".

SimplePat ::= "_"  | Constant |
              ["op"] Var  |
              ["op"] Con  |  ["op"] ExCon  |
              "{" PatRow "}"  |
              "()" |
              "(" {Pat / ","}2 ")"  |
              "[" {Pat / ","} "]"  |
              "(" Pat ")".

PatRow ::= "..."  |
           Lab "=" Pat ["," PatRow]  |
           Ide [":" Type] ["as" Pat]  ["," PatRow].

Pat ::= SimplePat  |
        ["op"] Con SimplePat  |  ["op"] ExCon SimplePat  |
        Pat Con Pat  |  Pat ExCon Pat  |
        Pat ":" Type  |
        ["op"] Var [":" Type] "as" Pat.

Match ::=   {Pat "=>" Exp / "|"}1

Type ::= TypeVar  |
         "{" {Lab ":" Type / ","}1 "}"  |
         [Type | "(" {Type / ","}1 ")"] TypeIde  |
         {Type / "*"}2  |
         Type "->" Type  |
         "(" Type ")".
\end{verbatim}
\end{quote}
\newpage
\noindent{\bf Appendix C. Predefined identifiers.}

Predefined identifiers in watML are given below with their fixity status
and other information. Nonstandard identifiers are noted. Identifiers
defined in the system library are indicated as such.

\begin{quote}
\begin{verbatim}

true                logical true             nonfix constant
false               logical false            nonfix constant
not                 logical not              nonfix
&                   logical and              infix nonstandard
or                  logical or               infix nonstandard

~                   negation                 nonfix
+                   plus                     infix overloaded
-                   difference               infix overloaded
*                   times                    infix overloaded
/                   divide                   infix overloaded
div                 integer division         infix
mod                 integer modulo           infix
=                   equal                    infix
<>                  not equal                infix library
>                   greater than             infix overloaded
<                   less than                infix overloaded
>=                  greater-equal            infix overloaded
<=                  less-equal               infix overloaded
abs                 absolute value           nonfix overloaded
floor               truncate real to int     nonfix
real                convert int to real      nonfix
sqrt                square root              nonfix
sin                 sin (degrees)            nonfix
cos                 cos (degrees)            nonfix
arctan              arctan (degrees)         nonfix
exp                 natural exponent         nonfix
ln                  natural log              nonfix
+^                  complex constructor      infix nonstandard
rpart               real selector            nonfix nonstandard
ipart               imaginary selector       nonfix nonstandard

size                string length            nonfix
chr                 string to int conv.      nonfix
ord                 int to string conv.      nonfix
extract             substring extraction     nonfix nonstandard
explode             string explosion         nonfix
implode             string implosion         nonfix
explodeascii        string to ascii conv.    nonfix nonstandard
implodeascii        ascii to string conv.    nonfix nonstandard
^                   string concatenation     infix
intofstring         string to int conv.      nonfix nonstandard
realofstring        string to real conv.     nonfix nonstandard
makestring          anything to string conv. nonfix nonstandard

nil                 empty list               nonfix constant
::                  list cons                infix constructor
hd                  list head                nonfix library
tl                  list tail                nonfix library
null                list null                nonfix library
length              list length              nonfix nonstandard library
@                   list append              infix library
map                 list map                 nonfix library
rev                 list reverse             nonfix library
fold                list folding             nonfix nonstandard library
revfold             list reverse folding     nonfix nonstandard library

ref                 new reference            nonfix constructor
!                   deference                nonfix
:=                  assignment               infix

array               new array                nonfix nonstandard
arrayoflist         list to array            nonfix nonstandard
lowerbound          array lower bound        nonfix nonstandard
arraysize           array size               nonfix nonstandard
sub                 array index              infix nonstandard
update              array assignment         infix nonstandard
arraytolist         array to list            nonfix nonstandard

o                   function composition     infix library

std_in              standard input           constant
std_out             standard output          constant
open_in             open input stream        nonfix
input               read from stream         nonfix
lookahead           peek from stream         nonfix
close_in            close input stream       nonfix
end_of_stream       check input stream       nonfix
open_out            open output stream       nonfix
output              write to stream          nonfix
close_out           close output stream      nonfix

system              call Unix function       nonfix nonstandard
systemquery         access Unix variable     nonfix nonstandard

\end{verbatim}
\end{quote}


\newpage
\noindent{\bf Appendix D. Differences From Standard ML.}

watML does not support standard ML modules.

The {\bf withtype} construct is not implemented.

ML now allows

\begin{quote}
\begin{verbatim}
   let datatype x = a in a end;
\end{verbatim}
\end{quote}

\noindent
(originally this was allowed, then it wasn't, now it is). ANU ML doesn't allow
it.

Function {\bf mod} has different semantics from the standard (which has
peculiar semantics which are not used by New Jersey ML either).

Version 4 of the report (appendix D) is not clear on the
behaviour in some cases. ANU ML

\begin{itemize}
\item allows a stream to be closed multiple times

\item allows input from a closed stream (an empty string is returned)

\item raises (Io ``Invalid Argument'') exception for invalid argument to
input (e.g., input (is,~1);)

\item input(std\_in,0) returns ``'' -- should argument be $>$ 0?

\item raises (Io ``Cannot open s'') for open\_out if file cannot be created

\item raises (Io ``Output steam is closed'') for output if write doesn't work
e.g., stream is closed

\item raises (Io ``System Error'') for various internal errors (file space full,
etc)
\end{itemize}

\newpage
\noindent{\bf Appendix E. Transient Errors in watML.}

Functions {\bf chr} and {\bf ord} are not yet implemented.

This should not be allowed (it is illegal ML)

\begin{quote}
\begin{verbatim}
  exception e of 'a;
  fun f (0,x) = raise (e x);
  f (0,true) handle e x => x;
\end{verbatim}
\end{quote}


The exception {\bf Corruption} is produced when something goes wrong
in the system.

The copying garbage collection algorithm is recursive. Because of this,
the system can crash during garbage collection when (1) very deep (thousands
of levels) lists or other structures are present in memory and (2) not
enough virtual memory can be obtained for the system stack, e.g., because
of Unix limits on the size of page tables, or for lack of swap space on disk.

The exception {\bf Alloc} may be generated when compiling big programs or
big modules. The absolute size of the program is not directly relevant;
the important factors are th size of every individual {\bf fun}-expression
and the number of definitions in a module. The preferred programming style
should consist of writing a large number of small modules (1-5 pages)
containing small (10-100 line) functions. The size of type definitions
has no relevance to these problems.

The overloading mechanism has a few problems to be ironed out: it is
possible to make the resolution get into an infinite loop and no error is
reported.

Some small bugs still exist in watML. 

\begin{itemize}
\item {\tt $\{$0=true$\}$ $\{$\~{}1=true$\}$ $\{$01=true$\}$} should all be
errors. watML doesn't parse single digits.

\item {\tt infix 09 x;} shouldn't parse but does. See above.

\item {\tt 0.0 = \~{}0.0;} is false, as both are represented differently!

\item {\tt fun f (true as x) = x;} compiles, should be an error.

\item {\tt infix f; fun (op f) (x,y) = x div y;} works,
but brackets are not legal around the {\bf op}.

\item Unit is not supposed to allow a spaces between the brackets; watML
parses {\tt ( (* a comment *) );} as unit.

\end{itemize}

\noindent The editing system has the error that any text after a push or edit
done from a file (because either a {\bf use} or another push or edit is being
executed) is lost.

\newpage
\noindent{\bf Appendix F. System Limitations.}

There is a limit on the size of any single ML object, due to storage
allocation problems. This limit is currently 4K words.
Thus {\tt array(0,2040,0)} cannot
be allocated (as each entry takes two words and the array object has fields).
It is possible to define a 2039 by 2039 matrix, as each entry in the first
array is a pointer to another array.
This limit can be extended by recompiling the system, but
will then be less efficient with memory usage.
All the limitations mentioned in
this section are further constrained by this restriction.

The semantic limit on the length of strings is 64K chars.

The syntactic limit on the length of string quotations in a source program
is also 64K chars.

Several memory areas inside the system have fixed size. When one of these
is exceeded, compilation fails and a message is printed. The only solution
to this problem is to increase the memory allocated and recompile the
system.

At the moment, only 8 streams (as well as std\_in and std\_out)
can be opened and closing a stream does not allow another one to be opened.

Integers range between -268435456 .. 268435455.

On some machines (notably Sun 3's running Sun OS 3) which do not have
memory protection, if the stack overflows, the system will crash. On machines
with memory protection this produces a memory overflow exception.

\end{document}
