% manual.tex v. 2.00.4 Copyright (C) Peter Sestoft 1994, 2000-07-20
%
% You may edit for lay-out, or leave out irrelevant sections (if
% such omissions are marked somehow), but you may not redistribute the
% sources.  The authors' names and the Moscow ML URL must be left in place.

\documentclass[fleqn,a4paper]{article}

\usepackage{isolatin1,mosml,pslatex}
\usepackage{geometry}
\usepackage[T1]{fontenc}

% True if running pdflatex
\newif\ifpdf
\ifx\pdfoutput\undefined
    \pdffalse
\else
    \pdftrue
\fi

% hyperref should be the *last* package loaded
\ifpdf
   \pdfcompresslevel=9
   % For interactive color output devices (i.e. computer displays):
   \usepackage[pdfpagemode=None,colorlinks,urlcolor=blue]{hyperref}
\else
   % For passive black and white output devices (i.e. printers):
   \usepackage{hyperref}
\fi

\begin{document}

\begin{center}

  {\huge\bf Moscow ML Owner's Manual}\\[0.5cm]

Version 2.00 of June 2000\\[0.5cm]

Sergei Romanenko, Russian Academy of Sciences, Moscow, Russia\\
Claudio Russo, Cambridge University, Cambridge, United Kingdom\\
Peter Sestoft, Royal Veterinary and Agricultural University, 
Copenhagen, Denmark

%{\large Sergei Romanenko\footnote{
%Keldysh Institute of Applied Mathematics, 
%Russian Academy of Sciences, Miusskaya Pl. 4, 125047 Moscow, Russia.  
%Email: roman@keldysh.ru}
%and Peter Sestoft\footnote{Department of Mathematics and
%  Physics, Royal Veterinary and Agricultural University,
%  Thorvaldsensvej 40, DK-1871 Frederiksberg C, Denmark.  E-mail:
%  sestoft@dina.kvl.dk}}\\[1ex]
\end{center}

\vspace{0.5cm}

\noindent 
Moscow ML implements Standard ML (SML), as defined in the 1997 {\em
  Definition of Standard ML\/}, including the SML Modules language
and some extensions.  Moreover, Moscow ML supports most required parts
of the SML Basis Library.  It supports separate compilation and the
generation of stand-alone executables.

This document explains how to use the Moscow ML system.  A companion
document, the {\em Moscow ML Language Overview\/}, summarizes Moscow
ML syntax and the most common built-in functions
\cite{MoscowML:2000:MoscowMLLanguage}.  Another companion document,
the \emph{Moscow ML Library Documentation}, describes in detail all
Moscow ML library modules \cite{MoscowML:2000:MoscowMLLibrary}. 

\vspace{0.5cm}

\tableofcontents

\vfill

\begin{center}
\begin{tabular}{|c|}\hline
\rule[-0.4cm]{0cm}{1cm}The Moscow ML home page is\ \
    \url{http://www.dina.kvl.dk/~sestoft/mosml.html}\\\hline
\end{tabular}
\end{center}

\vfill


\newpage

\section{Getting started}
\label{sec-getting-started}

\subsection{Installation}

Get a copy of the Moscow ML system executables (see
Section~\ref{sec-how-to-get} for instructions) and unpack them in your
home directory (under Unix) or in directory \verb#C:\# (under MS
Windows and DOS)\@.  This creates a directory {\tt mosml}.  Read the
file {\tt mosml/install.txt}.  This manual, as well as the {\em Moscow
  ML Language Overview\/} and the \emph{Moscow ML Library
  Documentation}, are in directory {\tt mosml/doc}.


\subsection{The interactive system}

The interactive system is invoked by typing {\tt mosml} at the shell
prompt.  It allows you to enter declarations and evaluate expressions:

\begin{program}
\$ mosml
Moscow ML version 2.00 (June 2000)
Enter `quit();' to quit.
-  fun fac n = if n = 0 then 1 else n * fac (n-1);
> val fac = fn : int -> int
-  fac 10;
> val it = 3628800 : int
\end{program}

\noindent You can quit the interactive session by typing `{\tt
  quit();}' or control-D (under Unix) or control-Z followed by newline
(under MS Windows and DOS)\@.  Type {\tt help "lib";} for an overview
of built-in function libraries, and e.g.\ {\tt help "Array"} for help
on {\tt Array} operations.  See Section~\ref{sec-interactive-system}
for further information on {\tt mosml}.


\subsection{The batch compiler and linker}

The batch compiler and linker is invoked by typing {\tt mosmlc} at the
shell prompt.  It can compile ML source files separately ({\tt mosmlc
  -c}) and link them to obtain executables ({\tt mosmlc -o}), in a
manner similar to C compilers.  See Section~\ref{sec-batch-compiler}
for further information on {\tt mosmlc}.


\subsection{The Moscow ML Modules language}

The Moscow ML Modules language is a conservative extension of the
Standard ML Modules language, so that any Standard ML program can be
compiled with Moscow ML 2.00, using toplevel-mode compilation; see
Section~\ref{sec-toplevel-mode}.

Moreover, the Moscow ML Modules language is backwards compatible with
Moscow ML versions 1.44 and before, so that any existing Moscow ML
program can be compiled with Moscow ML 2.00, using structure-mode
compilation; see Section~\ref{sec-structure-mode}.


\subsection{What is new in release 2.00}

\begin{itemize}
\item The Moscow ML Modules language (designed and implemented by
  Claudio Russo) includes the full Standard ML Modules language
  (structures, signatures, and functors):
\item The Moscow ML Modules language extends the Standard ML Modules
  language in three ways:
  \begin{itemize}
  \item higher-order functors: a functor may be defined within
    a structure, passed as an argument to another functor, or 
    returned as the result
    of a functor; 
    see Sections~\ref{sec-ho-modules}, \ref{sec-applicative-functors} and \ref{sec-functor-signatures}
  \item first-class modules: structures and functors may be packed and
    then handled as Core language values, which may then be unpacked
    as structures or functors again; see
    Section~\ref{sec-firstclass-modules}
  \item recursive modules:  structures and  signatures may be
    recursively defined; see Section~\ref{sec-rec-modules}
  \end{itemize}

\item Value polymorphism has become friendlier: non-generalizable free
  type variables are left free, and become instantiated (once only)
  when the bound variable is used; see Section~\ref{sec-valuepoly}.
\item Added facilities for creating and communicating with
  subprocesses (structure \texttt{Unix} and \texttt{Signal} from SML
  Basis Library).
\item Added facilities for efficient functional generation of HTML
  code (structure \texttt{Msp}); also supports the writing of ML
  Server Page scripts.
\item Added facilities setting and accessing `cookies' in CGI scripts
  \texttt{Mosmlcookie}, thanks to Hans Molin.
\item The \texttt{Gdimage} structure now produces PNG images (using
  Thomas Boutell's gd library).
\item Internal changes: restrictions on datatype constructor ordering
  have been removed; the runtime system and bytecode format now
  accommodate much larger programs; the representation of exceptions
  has been simplified; literals are now shared inside topdecs; etc.
% cvr: removed
%\item A project manager \texttt{mosmlpm} for recompilation management.
\end{itemize}

% \subsection{What is new in release 1.44}

% \begin{itemize}
% \item Added interface to the PostgreSQL and MySQL database servers
%   (structure {\tt Postgres} and {\tt Mysql}); see Sections
%   \ref{sec-using-mpq} and~\ref{sec-using-mmysql}.  Requires
%   {\tt Dynlib}.
  
% \item Added interface to POSIX 1003.2 regular expressions (structure
%   {\tt Regex}); see Section \ref{sec-using-mregex}.  Requires {\tt
%     Dynlib}.
  
% \item Added interface to Thomas Boutell's gd library for creating GIF
%   images (structure {\tt Gdimage}); see Section \ref{sec-using-mgd}.
%   Requires {\tt Dynlib}.
  
% \item Added interface to Internet and file sockets (structure {\tt
%     Socket}); see Section \ref{sec-using-msocket}. Requires {\tt
%     Dynlib}.
  
% \item Added registration of ML values, including functions, for access
%   from C code (structure \texttt{Callback}).
  
% \item Faster bytecode execution, especially on RISC CPUs.
  
% \item A list of the loaded structures is accessible as {\tt
%     Meta.loaded()}.

% \item For other minor changes and fixes, see file
%   mosml/doc/releases.txt.
% \end{itemize}


% \subsection{What is new in release 1.43}

% \begin{itemize}

% \item Weak pointers and arrays of weak pointers (structure Weak); see
%   Section~\ref{sec-weak-pointers}.

% \item The load paths can be set from the interactive system, and the
%   system's prompts and responses can be turned off (option {\tt
%     -quietdec}, variable {\tt Meta.quietdec}).  This facilitates
%   writing scripts with mosml.

% \item Prettyprinters can be installed also on base types and abstract
%   types.

% \item  The Help facility can be adapted to other uses.

% \item  Mosmllex now supports abbreviations for regular expressions
%   (thanks to Ken Larsen).

% \item Added dynamic linking of external functions (structure {\tt
%     Dynlib}) under Linux, Solaris and OSF/1 (thanks to Ken Larsen).
%   See Section~\ref{sec-dynamic-linking}.

% \item Access to GNU gdbm persistent hashtables (structures {\tt Gdbm},
%   {\tt Polygdbm}); see Section~\ref{sec-using-mgdbm}.  Requires {\tt
%     Dynlib}.

% \item For other minor changes and fixes, see file
%   mosml/doc/releases.txt.
% \end{itemize}

%\subsection{What was new in release 1.42}
%
%\begin{itemize}
%\item The linker ({\tt mosml -o A.uo B.uo \ldots}) now automatically
%  includes all (and only) those bytecode files referred to by the
%  specified files {\tt A.uo}, {\tt B.uo}, etc.  Option {\tt -i} makes
%  the linker report which files were linked.  Option {\tt -noautolink}
%  disables the autolinker and gives you full control of the order of
%  linking.
%
%\item A new structure Mosmlcgi provides support for writing CGI
%  scripts in Moscow ML (thanks to Jonas Barklund).
%
%\item Structures Array2, CommandLine, and Option have been added to
%  the Basis Library.  Structure Old was renamed to SML90.  
%
%\item Faster compilation, thanks to changes in compiler internals.
%
%\item Faster bytecode execution, thanks to Doug Currie.
%
%\item Explicit type variable parameters (introduced in SML'96) in val
%  and fun declarations have been implemented.
%
%\item For other minor changes and fixes, see file
%  mosml/doc/releases.txt.
%\end{itemize}
%
%
%\subsection{What was new in release 1.41}
%
%\begin{itemize}
%\item The input-output functions are no longer at top-level; they are
%  now in units {\tt TextIO} and {\tt BinIO}.  The math functions are
%  no longer at top-level; they are in {\tt Math}.
%
%\item The type checker now uses value polymorphism by default,
%  avoiding the mysterious imperative type variables \verb#'_a#; see
%  Section~\ref{sec-valuepoly}.
%
%\item If your existing program fails to compile because of these
%  changes, try invoking {\tt mosml} with options {\tt -imptypes -P nj93}.
%
%\item Overloaded operators are resolved to type {\tt int} by default.
%  Hence {\tt fn (x, y) => x + y} now elaborates, with type {\tt int *
%    int -> int}.
%
%\item Hexadecimal integer constants {\tt 0x1F} and word constants {\tt
%    0w31} and {\tt 0wx1f} have been introduced.  Word constants are
%  overloaded on type {\tt Word.word} and {\tt Word8.word} and resolved
%  to {\tt Word.word} by default.
%
%\item The standard syntax for signatures and non-nested structures may
%  be used in unit signatures and bodies; this improves portability
%  between Moscow ML and SML/NJ\@.  See
%  Section~\ref{sec-old-compilation-units}.
%\end{itemize}


%\subsection{What was new in release 1.31}
%
%\begin{itemize}
%\item Installable prettyprinters are provided.
%\end{itemize}
%
%
%\subsection{What was new in release 1.30}
%
%\begin{itemize}
%\item The system has been rewritten in Standard ML and can compile
%  itself.  This makes installation under Unix much easier than
%  it used to be.
%
%\item The garbage collector of the Caml Light runtime system has been
%  improved (by Damien Doligez at INRIA).
%
%\item The new initial basis for Standard ML has been adopted.  
%  A new primitive type
%  {\tt char} has been introduced, the types of {\tt chr}, {\tt
%    explode}, {\tt implode} and {\tt ord} have changed, and several
%  new utility libraries have been added.
%
%\item Quotations and antiquotations are supported.
%\end{itemize}


\section{Additional documentation}

Moscow ML implements Standard ML (SML) as revised in 1997, also known
as SML'97 \cite{Milner:1990:TheDefinition, Milner:1997:TheDefinition},
and some extensions to the SML Modules language.  Moscow ML implements
much of the Standard ML Basis Library \cite{SMLBasis:1996:StandardML},
the most important omission being the functional stream input-output
operations.  The Standard ML Basis Library is a joint effort of the
Standard ML of New Jersey, MLWorks, and Moscow ML
developers\footnote{The Basis Library authors are Andrew Appel
  (Princeton, USA); Emden Gansner (AT\&T Research, USA); John Reppy,
  Lal George, Lorenz Huelsbergen, Dave MacQueen (Lucent Bell
  Laboratories, USA); Matthew Arcus, Dave Berry, Richard Brooksby,
  Nick Barnes, Brian Monahan, Jon Thackray (Harlequin Ltd., Cambridge,
  England); Carsten M{\"u}ller (Berlin, Germany); and Peter Sestoft
  (Royal Veterinary and Agricultural University, Denmark).} to enhance
the portability of Standard ML programs.

The {\em Moscow ML Language Overview\/}
\cite{MoscowML:2000:MoscowMLLanguage} describes the Moscow ML source
syntax, which is SML'97 with some extensions, and the most common
built-in functions.

The \emph{Moscow ML Library Documentation}
\cite{MoscowML:2000:MoscowMLLibrary} describes in detail all Moscow ML
library modules and has a comprehensive index to exceptions,
functions, structures, types, and values.  The same information is
available also from {\tt mosml}'s built-in help function
(Section~\ref{sec-mosml-help}) and as hypertext from Moscow ML's
homepage and in the file\\ \texttt{mosml/doc/mosmllib/index.html}.

The \emph{Moscow ML for the Apple Macintosh}
\cite{Currie:1999:MoscowMLMac} is a detailed user guide to the Apple
Macintosh version of Moscow ML\@.

\newpage

\section{The interactive system: mosml}
\label{sec-interactive-system}

The interactive system {\tt mosml} is invoked simply by typing {\tt
  mosml} at the command line:

\begin{program}
\$ mosml
Moscow ML version 2.00 (June 2000)
Enter `quit();' to quit.
- 
\end{program}

\noindent The interactive system can be terminated by typing {\tt
  quit();} and newline, or control-D (under Unix) or control-Z and
newline (under MS Windows and DOS).  Type `{\tt help "";}' for help on
built-in functions.

Invoking the interactive system with command line arguments

\begin{program}
mosml file\sub{1} \ldots\ file\sub{n}
\end{program}

\noindent is equivalent to invoking {\tt mosml} and, when Moscow ML
has started, entering

\begin{program}
(use "file\sub{1}"; \ldots; use "file\sub{n}");  
\end{program}


\subsection{On-line help}
\label{sec-mosml-help}

In a {\tt mosml} session, you may type {\tt help "lib";} for an
overview of built-in function libraries.  To get help on a particular
identifier, such as {\tt fromString}, type

\begin{program}
help "fromstring";
\end{program}

\noindent This will produce a menu of all library structures which
contain the identifier {\tt fromstring} (disregarding the
lowercase/uppercase distinction):

{\small\begin{verbatim}
    --------------------------------
    |   1 | val  Bool.fromString   |
    |   2 | val  Char.fromString   |
    |   3 | val  Date.fromString   |
    |   4 | val  Int.fromString    |
    |   5 | val  Path.fromString   |
    |   6 | val  Real.fromString   |
    |   7 | val  String.fromString |
    |   8 | val  Time.fromString   |
    |   9 | val  Word.fromString   |
    |  10 | val  Word8.fromString  |
    --------------------------------
\end{verbatim}}

\noindent Choosing a number from this menu will invoke the help
browser on the desired structure, e.g.\ {\tt Int}.  The help browser
is primitive but easy to use.  It works best with a window size of 24
lines.


\subsection{Editing and running ML programs}
\label{sec-editing}
\begin{description}
\item[Unix and Emacs] You may run {\tt mosml} as a subshell under
  Emacs.  You should use the {\tt mosml}-version of the SML mode for
  Emacs; see file {\tt mosml/utility/emacs} for instructions.  In case
  of errors, Emacs can interpret {\tt mosml}'s error messages and jump
  to the offending piece of source code.  This is very convenient.

\item[Window systems] In a window-oriented system, such as MacOS, MS
  Windows, or the X window system, you may run {\tt mosml} in one
  window and edit source code in another.  After (re-)editing the
  source file, you must issue a {\tt use} command in the {\tt mosml}
  window.
  
\item[MS DOS and MS Windows] You may use the simple {\tt edit} script
  to invoke an editor from inside a {\tt mosml} session; see file
  \verb#mosml\utility\dosedit# for instructions.  You will not need to
  quit the {\tt mosml} session to edit a source file, and the script
  will automatically reload the newly edited file.
\end{description}


\subsection{Command-line options of mosml}
\label{sec-mosml-options}

\begin{description}
\item[{\tt -conservative}]\mbox{ }
  
  Sets conservative mode for compilation of subsequent units: accept
  all extensions to the SML Modules language, but issue a warning for
  each use; see Section~\ref{sec-modules-extensions}.  This is the
  default.

\item[{\tt -I {\rm directory}}]\mbox{ }

  Specifies directories to be searched for interface files, bytecode
  files, and source files.  A call to {\tt use}, {\tt load} or {\tt
    loadOne} will first search the current directory, then all
  directories specified by option `{\tt -I}' in order of appearance
  from left to right, and finally the standard library directory.
  (This option affects the variable {\tt Meta.loadPath}; see
  Section~\ref{sec-nonstandard-interactive}).

\item[{\tt -imptypes}]\mbox{ }

  Specifies that the type checker should distinguish between
  imperative and applicative type variables, generalize all
  applicative type variables, and generalize imperative type variables
  only in non-expansive expressions.  See Section~\ref{sec-valuepoly}.

\item[{\tt -liberal}]\mbox{ }
  
  Sets liberal mode for compilation of subsequent units: accept
  without warnings all extensions to the SML Modules language; see
  Section~\ref{sec-modules-extensions}.

\item[{\tt -orthodox}]\mbox{ }
  
  Sets orthodox mode for the compilation of subsequent units: reject
  all uses of the extensions to the SML Modules language.  That is,
  accept only SML Modules syntax; see
  Section~\ref{sec-modules-extensions}.

\item[{\tt -P {\rm unit-set}}]\mbox{ }

  Determines which library units will be included and open at
  compile-time.  Any library unit in the load path can be used by the
  {\tt compile} function for type checking purposes.  Thus regardless
  of the {\tt -P} option, the {\tt compile} function knows the type of
  library functions such as {\tt Array.foldl}.

  \begin{description}
  \item[{\tt -P default}] The initial environment for the SML Basis
    Library: modules {\tt Array}, {\tt Char}, {\tt List}, {\tt
      String}, and {\tt Vector} will be loaded, and {\tt Char}, {\tt
      List}, and {\tt String} will be partially opened.

  \item[{\tt -P sml90}] This provides an initial environment which is
    upwards compatible with that of the 1990 {\em Definition of
      Standard ML\/} and with pre-1.30 releases of Moscow ML\@.  In
    particular, the functions {\tt chr}, {\tt explode}, {\tt implode},
    and {\tt ord} work on strings, not characters.  The new versions
    of these functions are still available as {\tt Char.chr}, {\tt
      Char.ord}, {\tt String.explode}, and {\tt String.implode}.  The
    math functions and input-output facilities required by the 1990
    Definition \cite[Appendix C and D]{Milner:1990:TheDefinition} are
    available at top-level.  In addition the same libraries are
    loaded as with {\tt -P default}.

  \item[{\tt -P nj93}] This provides a top-level environment which is
    mostly compatible with that of SML/NJ 0.93.  The functions {\tt
      app}, {\tt ceiling}, {\tt chr}, {\tt dec}, {\tt explode}, {\tt
      fold}, {\tt hd}, {\tt implode}, {\tt inc}, {\tt max}, {\tt min},
    {\tt nth}, {\tt nthtail}, {\tt ord}, {\tt ordof}, {\tt revapp},
    {\tt revfold}, {\tt substring}, {\tt tl}, and {\tt truncate} have
    the same type and meaning as in SML/NJ 0.93.  Note that this is
    incompatible with SML/NJ version 110\@.  The math functions and
    input-output facilities required by the 1990 Definition
    \cite[Appendix C and D]{Milner:1990:TheDefinition} are available
    at top-level.  In addition the same (new) libraries are loaded as
    with {\tt -P default}.  This option does {\em not\/} imply {\tt
      -imptypes}.

  \item[{\tt -P full}] This loads all the libraries marked {\tt F} in
    the library list (see \cite{MoscowML:2000:MoscowMLLanguage}), and
  partially opens the {\tt Char}, {\tt List}, and {\tt String} units.

  \item[{\tt -P none}] No library units are loaded or opened initially.
  \end{description}
  
  Additional library units can loaded into the interactive system by
  using the {\tt load} function; see
  Section~\ref{sec-nonstandard-interactive} below.

\item[{\tt -quietdec}]\mbox{ }
  
  Turns off the interactive system's prompt and responses, except for
  warnings and error messages.  Useful for writing scripts in SML\@.
  Sets {\tt Meta.quietdec} to {\tt true}; see
  Section~\ref{sec-nonstandard-interactive}.
  
\item[{\tt -stdlib {\rm stdlib-directory}}]\mbox{ }

  Specify the standard library directory to be stdlib-directory.  The
  default standard library is usually {\tt mosml/lib} under Unix and
  \verb#c:\mosml\lib# under MS Windows and DOS.

\item[{\tt -valuepoly}]\mbox{ }

  Specifies that the type checker should use `value polymorphism'; see
  Section~\ref{sec-valuepoly}.  Default.
\end{description}


\subsection{Non-standard primitives in the interactive system}
\label{sec-nonstandard-interactive}

The following non-standard primitives are defined in unit {\tt Meta},
loaded (and open by default) only in the interactive system.  Hence
these primitives cannot be used from source files which are compiled
separately.  The functions {\tt compile}, \texttt{compileStructure},
\texttt{compileToplevel} and {\tt load} deal with Moscow ML
compilation units; see Section~\ref{sec-compilation-units}.

\begin{description}

\item[{\tt compile :\ string -> unit}]\mbox{ }
  
  Evaluating {\tt compile "{\rm U.sig}"} will compile and elaborate
  the specifications in file U.sig in structure mode, producing a
  compiled signature U in file U.ui.  This function is backwards
  compatible with Moscow ML 1.44 and earlier.  Equivalent to
  \texttt{compileStructure [] "{\rm U.sig}"}.
  
  Evaluating {\tt compile "{\rm U.sml}"} will elaborate and compile
  the declarations in file U.sml in structure mode, producing a
  compiled structure U in bytecode file U.uo.  If there is an explicit
  signature U.sig, then file U.ui must exist, and the structure must
  match the signature.  If there is no U.sig, then an inferred
  signature will be produced in file U.ui.  No evaluation takes place.
  This function is backwards compatible with Moscow ML 1.44 and
  earlier.  Equivalent to \texttt{compileStructure [] "{\rm U.sml}"}.

  The declared identifiers will be reported if {\tt verbose} is {\tt
    true} (see below); otherwise compilation will be silent.  In any
    case, compilation warnings are reported, and compilation errors
    abort the compilation and raise the exception {\tt Fail} with a
    string argument.

\item[{\tt compileStructure :\ string list -> string -> unit}]\mbox{ }
  
  Evaluating \texttt{compileStructure $opnunits$ "{\rm U.sig}"
    } will elaborate and compile the specifications in file U.sig in
  structure mode, producing a compiled signature U in file U.ui.  The
  units listed in $opnunits$ are added to the compilation
  context in which the specifications in U.sig are compiled.  
  
  Evaluating \texttt{compileStructure $opnunits$ "{\rm U.sml}"
    } will elaborate and compile the declarations in file U.sig in
  structure mode, producing a compiled structure U in bytecode file
  U.uo.  The contents of the units listed in $opnunits$ are
  added to the compilation context in which the declarations in U.sml
  are compiled.  If there is an explicit signature U.sig, then file
  U.ui must exist, and the structure must match the signature.  If
  there is no U.sig, then an inferred signature will be produced in
  file U.ui.  No evaluation takes place.


\item[{\tt compileToplevel :\ string list -> string -> unit}]\mbox{ }
  
  Evaluating \texttt{compileToplevel $opnunits$ "{\rm U.sig}" }
  will elaborate and compile the specifications in file U.sig in
  toplevel mode, producing a compiled interface file U.ui.  The units
  listed in $opnunits$ are added to the compilation context in
  which the specifications in U.sig are compiled.
  
  Evaluating \texttt{compileStructure $opnunits$ "{\rm U.sml}"
    } will elaborate and compile the declarations in file U.sig in
  toplevel mode, producing a bytecode file U.uo.  The contents of the
  units listed in $opnunits$ are added to the compilation
  context in which the declarations in U.sml are compiled.  If there
  is an explicit signature U.sig, then file U.ui must exist, and
  declarations must match the interface.  If there is no U.sig, then
  an inferred signature will be produced in file U.ui.  No evaluation
  takes place.

\item[{\tt conservative :\ unit -> unit}]\mbox{ }
  
  Evaluating \texttt{conservative ()} sets conservative mode for the
  compilation functions: accept all extensions to the SML Modules
  language, but issue a warning for each use; see
  Section~\ref{sec-modules-extensions}.  The conservative mode may be
  set also by the \texttt{mosml} option \texttt{-conservative}.
  Conservative mode is the default.

\item[{\tt installPP :\ (ppstream -> 'a -> unit) -> unit}]\mbox{ }

  Evaluating {\tt installPP $pp$} installs the prettyprinter $pp$ at
  type {\tt ty}, provided $pp$ has type {\tt ppstream -> ty -> unit}.
  The type {\tt ty} must be a nullary (parameter-less) type
  constructor, either built-in (such as {\tt int} or {\tt bool}) or
  user-defined.  Whenever a value of type {\tt ty} is about to be
  printed by the interactive system, and whenever function {\tt
    printVal} is invoked on an argument of type {\tt ty}, the
  prettyprinter $pp$ will be invoked to print it.  See the example in
  {\tt mosml/examples/pretty}.

\item[{\tt liberal :\ unit -> unit}]\mbox{ }
  
  Evaluating \texttt{liberal ()} sets liberal mode for the compilation
  functions: accept (without warnings) all extensions to the SML
  Modules language; see Section~\ref{sec-modules-extensions}.  The
  liberal mode may be set also by the \texttt{mosml} option
  \texttt{-liberal}.

\item[{\tt load :\ string -> unit}]\mbox{ }
  
  Evaluating {\tt load "{\rm U}"} will load and evaluate the compiled
  unit implementation from file U.uo.  The resulting values are not
  reported, but exceptions are reported, and cause evaluation and
  loading to stop.  If U is already loaded, then {\tt load "{\rm U}"}
  has no effect.  If any other unit is mentioned by U but not yet
  loaded, then it will be loaded automatically before U.  The loaded
  unit(s) must be in the current directory or in a directory on the
  {\tt loadPath} list (see below).

  After loading a unit, it can be opened with {\tt open U}.  Opening
  it at top-level will list the identifiers declared in the unit.
  
  When loading U, it is checked that the interfaces of units mentioned
  by U agree with the interfaces used when compiling U, and it is
  checked that the interface of U has not been modified since U was
  compiled; these checks are necessary for type safety.  The exception
  {\tt Fail} is raised if the interface checks fail, or if the file
  containing U or a unit mentioned by U is not found.

\item[{\tt loaded :\ unit -> string list}]\mbox{ }
  
  Evaluating {\tt loaded ()} will return a list of the names of loaded
  units in some order (not including the preloaded units {\tt Meta}
  and {\tt General}).

\item[{\tt loadOne :\ string -> unit}]\mbox{ }

  Evaluating {\tt loadOne "{\rm U}"} is similar to {\tt load "{\rm
      U}"}, but raises exception {\tt Fail} if U is already loaded or
  if some unit mentioned by U is not yet loaded.  That is, it does not
  automatically load any units mentioned by U.  It performs the same
  interface checks as {\tt load}.

\item[{\tt loadPath :\ string list ref}]\mbox{ }

  This variable determines the load path: which directories will be
  searched for interface files (.ui files), bytecode files (.uo
  files), and source files (.sml files).  This variable affects the
  {\tt load}, {\tt loadOne}, and {\tt use} functions.  The current
  directory is always searched first, followed by the directories in
  {\tt loadPath}, in order.  By default, only the standard library
  directory is in the list, but if additional directories are
  specified using option {\tt -I}, then these directories are
  prepended to {\tt Meta.loadPath}.

\item[{\tt orthodox :\ unit -> unit}]\mbox{ }
  
  Evaluating \texttt{orthodox ()} sets orthodox mode for the
  compilation functions: reject all uses of the extensions to the SML
  Modules language; see Section~\ref{sec-modules-extensions}.  That
  is, accept only SML Modules syntax.  The orthodox mode may be set
  also by the \texttt{mosml} option \texttt{-orthodox}.

\item[{\tt printVal :\ 'a -> 'a}]\mbox{ }
  
  This is a polymorphic function provided as a quick debugging aid.
  It is an identity function, which as a side-effect prints its
  argument to standard output exactly as it would be printed at
  top-level.  Output is flushed immediately.  For printing strings,
  the function {\tt print} is more useful than {\tt printVal}.

\item[{\tt printDepth :\ int ref}]\mbox{ }

  This variable determines the depth (in terms of nested constructors,
  records, tuples, lists, and vectors) to which values are printed by
  the top-level value printer and the function {\tt printVal}. The
  components of the value whose depth is greater than {\tt printDepth}
  are printed as `{\tt \#}'.  The initial value of {\tt printDepth} is
  20. 

\item[{\tt printLength :\ int ref}]\mbox{ }
  
  This variable determines the depth to which list values are printed
  by the top-level value printer and the function {\tt printVal}.
  Only the first {\tt printLength} elements of a list are printed, and
  the remaining elements are printed as `\ldots'.  The initial value
  of {\tt printLength} is 200.

\item[{\tt quietdec :\ bool ref}]\mbox{ }

  This variable, when {\tt true}, turns off the interactive system's
  prompt and responses, except warnings and error messages.  Useful
  for writing scripts in SML\@.  The default value is {\tt false}; it
  can be set to {\tt true} with the {\tt -quietdec} command line
  option; see Section~\ref{sec-mosml-options}.

\item[{\tt quit :\ unit -> unit}]\mbox{ }

  Evaluating {\tt quit()} quits Moscow ML immediately.

\item[{\tt quotation :\ bool ref}]\mbox{ }

  Determines whether quotations and antiquotations are permitted in
  declarations entered at top-level and in files compiled with {\tt
    compile}; see Section~\ref{sec-quotations}.  When {\tt quotation}
  is {\tt false} (the default), the backquote character is an ordinary
  symbol which can be used in ML symbolic identifiers.  When {\tt
    quotation} is {\tt true}, the backquote character is illegal in
  symbolic identifiers, and a quotation {\tt `a b c`} will be
  evaluated to an object of type {\tt 'a frag list}.

\item[{\tt system :\ string -> int}]\mbox{ }

  Evaluating {\tt system "$com$"} causes the command $com$ to be
  executed by the operating system.  If a non-zero integer is
  returned, this must indicate that the operating system has failed to
  execute the command.  Under MS DOS, the integer returned always
  equals 0.

\item[{\tt use :\ string -> unit}]\mbox{ }

  Evaluating {\tt use "$f$"} causes ML declarations to be read from
  file $f$ as if they were entered from the console.  The file must be
  in the current directory or in a directory on the {\tt loadPath}
  list.  A file loaded by {\tt use} may, in turn, evaluate calls to
  {\tt use}.  For best results, use {\tt use} only at top level, or at
  top level within a {\tt use}'d file.

\item[{\tt valuepoly :\ bool ref}]\mbox{ }

  Determines whether the type checker should use `value polymorphism';
  see Section~\ref{sec-valuepoly}.  Command-line option {\tt
    -valuepoly} sets {\tt valuepoly} to {\tt true} (the default),
  whereas option {\tt -imptypes} sets {\tt valuepoly} to {\tt false};
  see Sections~\ref{sec-mosml-options} and~\ref{sec-mosmlc-options}.

\item[{\tt verbose :\ bool ref}]\mbox{ }

  Determines whether the signature inferred by a call to {\tt compile}
  will be printed.  The printed signature follows the syntax of Moscow
  ML signatures, so the output of {\tt compile "{\rm U.sml}"} can be
  edited to subsequently create file U.sig.  The default value is {\tt
    false}.
\end{description}


\newpage

\section{Understanding inferred types and signatures}

When you enter a declaration in the interactive toplevel,
\texttt{mosml} responds with a type or signature.  The response
provides much information about the declaration.  It is worth learning
how to interpret this information.

In the type reported for a value binding, the generalized type
variables are listed between the \texttt{val} keyword and the
identifier bound by the declaration:

\begin{program}
- val f = length;
> val 'a f = fn : 'a list -> int        \rm{--- polymorphic function; \texttt{'a} has been generalized}
\end{program}

\noindent When value polymorphism (see
Section~\ref{sec-valuepoly}) prevents the generalization of a type
variable, it remains free and ungeneralized.  Hence \texttt{'a} will
appear in the type \texttt{'a list -> int}, but will not be listed
between \texttt{val} and \texttt{f}.

For a \texttt{datatype} declaration, which is generative, the response
describes the new internal type names (here \texttt{u}), the
datatype's type structure (consisting of the internal type name and
the constructors), and the constructors:

\begin{program}
- datatype u = A;
> New type names: =u
  datatype u = (u,\verb+{+con A : u\verb+}+)
  con A = A : u
\end{program}

\noindent
The notation \texttt{=u} means that the internal type name \texttt{u}
admits equality.  Since the \texttt{datatype} declaration is
generative, repeated declaration of datatype \texttt{u} will produce
distinct new internal type names \texttt{u/1}, \texttt{u/2}, etc.  If
the datatype is polymorphic, the internal type name will be a type
function, taking as parameter a type variable \texttt{'a}:

\begin{program}
- datatype 'a u = A of 'a;
> New type names: =u
  datatype 'a u = ('a u,\verb+{+con 'a A : 'a -> 'a u\verb+}+)
  con 'a A = fn : 'a -> 'a u
\end{program}

\noindent 
For a signature specifying an unknown type, the response is a type
function \verb+/\t.{...}+ mapping any internal type name \texttt{t} to
a record \verb+{...}+, which is the internal representation of the
signature:

\begin{program}
- signature SIG = sig type t val x : t end;
> signature SIG = /\verb+\+t.\verb+{+type t = t, val x : t\verb+}+
\end{program}

\noindent 
For a structure declaration, the response describes any new internal
type names, and then the internal signature of the structure.  Here it
has three components (datatype \texttt{t}, constructor \texttt{A}, and
value identifier \texttt{x}):

\begin{program}
- structure S = struct datatype t = A; val x = A end;
> New type names: =t
  structure S : \verb+{+datatype t = (t,\verb+{+con A : t\verb+}+), con A : t, val x : t\verb+}+
\end{program}

\noindent 
For a functor, the response describes a signature function
\verb+{...}->{...}+, mapping the signature of the functor argument to
the signature of the functor body:

\begin{program}
- functor F(X : sig val x : int end) = struct val y = X.x end;
> functor F : \verb+{+val x : int\verb+}+->\verb+{+val y : int\verb+}+
\end{program}

\noindent When the functor argument signature specifies an unknown
type, the signature function will have the form\\ \verb+!t.{...}->{...}+
in which the internal type name \texttt{t} has been generalized:

\begin{program}
- functor F(X : sig type t; val x : t end) = struct val y = X.x end;
> functor F : !t.\verb+{+type t = t, val x : t\verb+}+->\verb+{+val y : t\verb+}+
\end{program}

\noindent When the body of a (standard) generative functor \texttt{G}
contains a \texttt{datatype} declaration, the response describes what
new internal type names will be generated at every application of the
functor.  The notation \verb+{}->...+ means that the functor argument
signature is empty, and the notation \verb+?=t.{...}+ says that there
is some internal type name \verb+t+, admitting equality, such that
the functor body has the signature \verb+{...}+:

\begin{program}
- functor F() = struct datatype t = A end;
> functor F : \verb+{+\verb+}+->?=t.\verb+{+datatype t = (t,\verb+{+con A : t\verb+}+), con A : t\verb+}+
\end{program}

\noindent When the functor is applicative (see
Section~\ref{sec-applicative-functors}) then no new internal type
names are generated at functor application.

\newpage
\section{Compilation units}
\label{sec-compilation-units}

Moscow ML programs can be split into several source files, so-called
compilation units, or units for short.  A compilation unit consists of
an implementation file \texttt{unitid.sml} and an optional interface
file \texttt{unitid.sig}.  A unit must be compiled in one of two modes:

\begin{itemize}
\item \textbf{Structure mode:} File \texttt{A.sml} declares a single
  SML structure \texttt{A}, and file \texttt{A.sig}, if present,
  declares an explicit SML signature \texttt{A} that is used as an
  opaque constraint for structure \texttt{A}.

% cvr: removed  
%   A structure-mode unit has a restricted syntax: it can declare only a
%   single SML structure, and therefore admits simple recompilation
%   management using \texttt{mosmldep} and makefiles; see
%   Section~\ref{sec-structure-mode-recompilation}.
  
  Structure-mode units are backwards compatible with the simple
  structures used in Moscow ML version 1.20 through 1.44.  Hence old
  Moscow ML programs can be compiled (in structure mode) with no
  changes.
  
  To compile a unit in structure mode, use the function
  \texttt{compileStructure} (see
  Section~\ref{sec-nonstandard-interactive}), or invoke the batch
  compiler \texttt{mosmlc}, preceding the unit file name with option
  \texttt{-structure} (see Section~\ref{sec-mosmlc-options}).
  
\item \textbf{Toplevel mode:} File \texttt{A.sml} contains a Moscow ML
  declaration (which may itself be a sequence of declarations), and
  file \texttt{A.sig}, if present, must be a Moscow ML specification
  (which may itself be a sequence of specifications).

  Toplevel-mode units can contain arbitrary Moscow ML code, and hence
  arbitrary Standard ML code.
  
  To compile a unit in toplevel mode, use the function
  \texttt{compileToplevel} (see
  Section~\ref{sec-nonstandard-interactive}), or invoke the batch
  compiler \texttt{mosmlc}, preceding the unit file name with option
  \texttt{-toplevel} (see Section~\ref{sec-mosmlc-options}).

\end{itemize}

\noindent 
The implementation file and the interface file (if any) of a unit must
be compiled in the same mode.  The precise syntax of structure-mode
units and toplevel-mode units is given in the \emph{Moscow ML Language
  Overview} \cite{MoscowML:2000:MoscowMLLanguage}.

A programming project may consist of a mixture of structure-mode and
toplevel-mode compilation units. See the example in Section  \ref{sec-example-mixed-units}.
% See Section
% However, the old recompilation
% management with makefiles and \texttt{mosmldep} (see
% Section~\ref{sec-structure-mode-recompilation}) will work only with
% structure-mode units.  
% The new project manager \texttt{mosmlpm} (see
% Section~\ref{sec-project-manager}) can manage recompilation of
% both kinds of units.
 

\subsection{Compiling, linking and loading units}

Compiling a unit interface \texttt{A.sig} produces a compiled unit
interface in file \texttt{A.ui}\@.  Compiling a unit implementation
\texttt{A.sml} produces a compiled unit implementation in file
\texttt{A.uo}, containing bytecode.  In addition, if there is no
correspond interface \texttt{A.sig}, then a file \texttt{A.ui},
containing an inferred unit interface, is produced.

Only the compiled unit interface \texttt{A.ui} is needed when
compiling other units that depend on \texttt{A.sml}.

Thus the following file name extensions have a special meaning: 

\begin{center}
\begin{tabular}{|l|l|}\hline
Extension & Contents\\\hline
\texttt{.sig} & unit interface\\
\texttt{.sml} & unit implementation\\
\texttt{.ui}  & compiled (or inferred) unit interface\\
\texttt{.uo}  & compiled unit implementation (bytecode)\\\hline
\end{tabular}
\end{center}

\noindent 
Compiled unit implementations can be linked together using {\tt mosmlc
  -o mosmlout A.uo \ldots} to produce a linked executable bytecode
file {\tt mosmlout}.  The linker will automatically link in any
required bytecode files into {\tt mosmlout}.  See
Section~\ref{sec-mosmlc-options} for more options.

Compiled units can be loaded into the interactive system {\tt mosml}
using the primitives {\tt load} and \texttt{loadOne}; see
Section~\ref{sec-nonstandard-interactive}.  Loading a unit makes the
entities declared by the unit accessible to subsequent declarations in
the interactive system.


\subsection{Compiling existing SML programs that involve .sig files}

The special meaning of .sig files may cause conflicts when compiling
existing SML programs (written for other compilers),
in which .sig files are often used rather
informally to contain signature declarations.  For instance, file
\texttt{A.sig} may declare the signatures of structures declared in
file \texttt{A.sml} (but might contain other arbitrary SML
declarations besides).

By contrast, in Moscow ML, .sig files play a formal role.  More
precisely, Moscow ML expects file \texttt{A.sig} to contain a unit
interface.  Thus it may be necessary to rename \texttt{A.sig} to
\texttt{A-sig.sml}, compile it before \texttt{A.sml}, and make its
contents available to \texttt{A.sml} (see also
Section~\ref{sec-toplevel-mode}):

\begin{program}
mosmlc -c -toplevel A-sig.sml
mosmlc -c -toplevel A-sig.ui A.sml
\end{program}


% In Moscow ML structure-mode units, and in Moscow ML 1.44 and before,
% the unit interface \texttt{A.sig} plays two roles: (1) it declares a
% signature \texttt{A} for constraining the structure \texttt{A}
% declared by file \texttt{A.sml}, and (2) it supports separate
% compilation (by permitting changes to \texttt{A.sml} without requiring
% recompilation of files that depend on \texttt{A}).

% In Moscow ML toplevel-mode units, file \texttt{A.sig} plays only role
% (2) above: it supports separate compilation by specifying the entities
% declared in file \texttt{A.sml}, but it does not itself declare
% anything (role 1).

% Schematically, the roles of .sig files is this:

% \begin{center}
% \begin{tabular}{|l|ccc|}\hline
% & Informal use & Mosml structure-mode units & Mosml
% toplevel-mode units\\

% &  & Mosml 1.44 units & \\\hline
% Declares signature            & yes & yes & no \\
% Supports separate compilation & no  & yes & yes\\\hline
% \end{tabular}
% \end{center}


\subsection{Unit names and MS DOS/Windows/OS2 file names}

In MS DOS, Windows, and OS/2, the file system may change the case of
unit file names, and even truncate them (in MS DOS)\@.  Under MS
Windows, file names are not truly case sensitive.  Since file names
are used as unit names, this may cause problems.  We attempt to
circumvent these problems as follows:

\begin{itemize}
\item Unit names used inside ML programs under MS DOS and MS Windows
  are `normalized': the first character is made upper case (if it is a
  letter), all other characters are made lower case, and (under MS DOS
  only) the unit name is truncated to eight characters.  Hence a unit
  which resides in file {\tt commands.sml} can be referred to as unit
  {\tt Commands} inside an ML program.
  
\item The following names are exceptions to this rule: {\tt BasicIO},
  {\tt BinIO}, {\tt CharArray}, {\tt CharVector},\\ {\tt CommandLine},
  {\tt FileSys}, {\tt ListPair}, {\tt OS}, {\tt StringCvt}, {\tt
    Substring}, {\tt TextIO}, {\tt Word8Array}, {\tt Word8Vector};
  they are normalized precisely as shown above for compatibility with
  the SML Basis Library.

% \item In DOS makefiles, the file names appearing after {\tt all:}\
%   must be all lower case and at most 8 characters long (otherwise
%   `make' will not work properly).  For instance, the unit {\tt
%     CharArray} must be called {\tt chararra} in a DOS makefile.
  
\item Under MS DOS (only), a unit name given as argument to e.g.\ {\tt
    load} or {\tt compile}, or to the batch compiler, is truncated and
  made lower case, so evaluating {\tt load "VeryLongName"} will load
  bytecode file {\tt verylong.uo}.
\end{itemize}


\newpage

\section{Structure-mode compilation units}
\label{sec-structure-mode}

This section describes the use of structure-mode compilation units,
which are backwards compatible with Moscow ML versions 1.20 through
1.44.


\subsection{Basic concepts}

A structure-mode compilation unit consists of a {\em unit
  implementation}, in file \texttt{unitid.sml}, and an optional {\em
  unit interface}, in file \texttt{unitid.sig}\@.  

The file \texttt{unitid.sml} must contain a declaration of a single
Moscow ML structure \texttt{unitid}, and file \texttt{unitid.sig}, if
present, must contain a declaration of a single Moscow ML signature
\texttt{unitid}.  When the unit interface is present, it is called the
{\em explicit signature\/} to distinguish it from the signature
inferred when elaborating the unit implementation.  When present, the
explicit signature must be matched by the implementation, and only
those identifiers specified in the signature are visible outside the
unit.

For a structure-mode unit it is immaterial whether a compilation
unit's interface and implementation are compiled and directly executed
in the interactive toplevel system:

\begin{program}
mosml
> use "unitid.sig";
> use "unitid.sml";
\end{program}

\noindent 
or whether they are first compiled in structure-mode, and then loaded
into the interactive toplevel system:

\begin{program}
mosmlc -c -structure unitid.sig unitid.sml 
mosml
> load "unitid";
\end{program}

\noindent where \texttt{unitid.sig}, if present, must be compiled
before \texttt{unitid.sml}.

More generally, when a compilation unit depends on a number of other
compilation units \texttt{"unitid\et"},\ldots,\texttt{"unitid\n"},
then compilation inside the interactive system:

\begin{program}
mosml
> app load ["unitid\et",\ldots,"unitid\n"];
> use "unitid.sig";
> use "unitid.sml";
\end{program}

\noindent is equivalent to structure-mode compilation followed by
loading into the interactive system:

\begin{program}
mosmlc -c -structure unitid\et.ui \ldots unitid\n.ui unitid.sig unitid.sml 
mosml
> app load ["unitid\et",\ldots,"unitid\n"];
> load "unitid";
\end{program}



\subsection{Structure-mode units without explicit signature}
\label{sec-units-without}

A unit U without an explicit signature consists of a file U.sml
containing 

% \begin{program}
% structure U = struct {\rm \ldots\ declarations\ \ldots} end
% \end{program}
\begin{program}
  structure U = {\rm modexp}
\end{program}


\noindent This is the same as a simple SML structure declaration.
There must be no corresponding explicit signature file U.sig.


\subsection{Structure-mode units with explicit signature}
\label{sec-units-with}

A unit U with an explicit signature consists of a signature file
U.sig containing

%\begin{program}
%signature U = sig {\rm \ldots\ specifications\ \ldots} end
%\end{program}

\begin{program}
signature U = {\rm sigexp}
\end{program}

\noindent and a file U.sml, containing

% \begin{program}
% structure U :> U = struct {\rm \ldots\ declarations\ \ldots} end
% \end{program}

\begin{program}
structure U :> U = {\rm modexp} 
\end{program}


\noindent This is similar to an SML structure declaration with an
opaque signature constraint.  Note that the file name, signature name,
and structure name must be the same.  The notation `{\tt U :> U}' is
an opaque signature constraint, meaning that other units have no
access to the internals of U.sml, only to the signature U.sig.


% \subsection{An example program consisting of three structure-mode units}
% \label{sec-example-units}

% To illustrate structure-mode units, we present a tiny program working
% with arithmetic expressions.  It consists of three units {\tt Expr},
% {\tt Reduce}, and {\tt Evaluate}.  This example is in {\tt
%   mosml/examples/manual}.

% File {\tt Expr.sml} below contains structure {\tt Expr}, which defines
% a datatype {\tt expr} for representing expressions and a function {\tt
%   show} to display them.  It has no signature constraint and therefore
% exports both the datatype and the function:

% \begin{program}
% structure Expr = struct
%    datatype expr = Cst of int | Neg of expr | Plus of expr * expr

%    fun show (Cst n)         = makestring n
%      | show (Neg e)         = "(-" ^ show e ^ ")"
%      | show (Plus (e1, e2)) = "(" ^ show e1 ^ "+" ^ show e2 ^ ")"
% end
% \end{program}

% \noindent File {\tt Reduce.sig} below contains the signature  {\tt
%   Reduce}:

% \begin{program}
% signature Reduce = sig
%    val reduce : Expr.expr -> Expr.expr
% end
% \end{program}

% \noindent File {\tt Reduce.sml} below contains the structure {\tt
%   Reduce}, which has the explicit signature shown above, and therefore
% exports only the function {\tt reduce} specified in the signature:

% \begin{program}
% structure Reduce :> Reduce = struct 
%    local open Expr
%    in
%        fun negate (Neg e) = e
%          | negate e       = Neg e
%        fun reduce (Neg (Neg e))      = e
%          | reduce (Neg e)            = negate (reduce e)
%          | reduce (Plus (Cst 0, e2)) = reduce e2
%          | reduce (Plus (e1, Cst 0)) = reduce e1
%          | reduce (Plus (e1, e2))    = Plus (reduce e1, reduce e2)
%          | reduce e                  = e
%    end
% end
% \end{program}

% \noindent File {\tt Evaluate.sig} below contains the signature {\tt
%   Evaluate}, which specifies a function {\tt eval} for evaluating
% expressions, and a function {\tt test}:

% \begin{program}
% signature Evaluate = sig
%    val eval : Expr.expr -> int
%    val test : Expr.expr -> bool
% end
% \end{program}

% \noindent File {\tt Evaluate.sml} below contains structure {\tt
%   Evaluate}, which has a signature constraint, and mentions unit {\tt
%   Expr} as well as {\tt Reduce}:

% \begin{program}
% structure Evaluate :> Evaluate = struct
%    local open Expr 
%    in 
%        fun eval (Cst n)         = n
%          | eval (Neg e)         = ~ (eval e)
%          | eval (Plus (e1, e2)) = eval e1 + eval e2;
%        fun test e = (eval e = eval (Reduce.reduce e))
%    end
% end
% \end{program}


% \subsection{Recompilation management for structure-mode programs}
% \label{sec-structure-mode-recompilation}

% Recompilation management helps the programmer recompile only what is
% necessary after a change to a unit interface or unit implementation.  


% Recompilation management for structure-mode units (that declare only
% flat structures)\footnote{For managing the recompilation of full
%   Standard ML programs, see Sections~\ref{sec-mixed-recompilation}
%   and~\ref{sec-project-manager}.} may be performed using the standard
% `make' tool in conjunction with the Moscow ML program
% \texttt{mosmldep}.

% Consider the example program in Section~\ref{sec-example-units}
% consisting of the three units Evaluate, Expr, and Reduce.  Assume
% their source files *.sig and *.sml reside in a particular directory.
% Copy the Makefile stub from \texttt{mosml/tools/Makefile.stub} to that
% directory, and change to that directory.

% \begin{enumerate}
% \item Edit the Makefile so that the names of the bytecode files
%   Evaluate.uo, Expr.uo, and Reduce.uo appear on the line beginning
%   with `{\tt all:}' (see the example makefile in
%   \texttt{mosml/examples/manual/Makefile}).

% \item Compute the dependencies among the files by executing:
% \begin{program}
% make depend
% \end{program}

% \item Recompile all those files which have not yet been compiled, or
%   which have been modified but not yet recompiled, or which depend on
%   modified files, by executing:
        
% \begin{program}
% make    
% \end{program}
% \end{enumerate}

% \noindent Step (3) must be repeated whenever you have modified a
% component of the program system.  Step (2) need only be repeated if
% the inter-dependencies of some components change, or if you add or
% remove an explicit signature file.  Step (1) need only be repeated
% when you add or delete an entire unit of the program system.

% The compiled *.ui and *.uo files can be removed by executing:

% \begin{program}
% make clean  
% \end{program}

% \noindent The unit dependencies are computed by the ML program
% {\tt mosmldep}, which can handle only structure-mode units, and only
% flat structures, neither functors nor nested structures.


\newpage

\section{Toplevel-mode compilation units}
\label{sec-toplevel-mode}

A toplevel-mode compilation unit may contain arbitrary Moscow ML
toplevel declarations, and consequently, arbitrary Standard ML
toplevel declarations (including functor, signature and fixity
declarations).


\subsection{Basic concepts}

A toplevel-mode compilation unit consists of a {\em unit
  implementation}, in file \texttt{unitid.sml}, and an optional {\em
  unit interface}, in a file called \texttt{unitid.sig}\@.  

The file \texttt{unitid.sml} may contain arbitrary Moscow ML
declarations, and file \texttt{unitid.sig}, if present, may contain
arbitrary Moscow ML specifications.  When the unit interface is
present, the unit implementation must implement everything specified
in the unit interface, and only those identifiers specified in the
interface are visible outside the unit.  It is considered a
mistake for the implementation to declare more identifiers
than specified in the interface or
for the implementation to
declare an identifier as a constructor or exception, but the interface
to specify that identifier as an ordinary value:
a warning is issued in these cases. 
 
Provided the interface and implementation agree on which identifiers
are declared, then it is immaterial whether a compilation unit is
compiled and directly executed in the interactive toplevel system:

\begin{program}
mosml
> use "unitid.sml";
\end{program}

\noindent 
or whether it is first compiled in toplevel-mode, and then loaded into
the interactive system:

\begin{program}
mosmlc -c -toplevel unitid.sig unitid.sml 
mosml
> load "unitid";
\end{program}

\noindent In contrast to a structure-mode unit, the
unit interface \texttt{unitid.sig} should not be loaded in the
interactive system, as it declares nothing.  If there is no
\texttt{unitid.sig}, then leave it out in the \texttt{mosmlc} command
above.

More generally, when a toplevel compilation unit depends on a number
of other compilation units \texttt{"unitid\et"}, \ldots,
\texttt{"unitid\n"} (compiled in structure mode or toplevel mode),
then compilation inside the interactive system:

\begin{program}
mosml
> app load ["unitid\et",\ldots,"unitid\n"];
> use "unitid.sml";
\end{program}

\noindent is equivalent to toplevel-mode compilation followed by
loading into the interactive system:

\begin{program}
mosmlc -c -toplevel unitid\et.ui \ldots unitid\n.ui unitid.sig unitid.sml 
mosml
> app load ["unitid\et",\ldots,"unitid\n"];
> load "unitid";
\end{program}

\noindent 
Again, if there is no \texttt{unitid.sig}, then leave it out in the
\texttt{mosmlc} command above.


\newpage
\section{An example program consisting of four mixed-mode units}
\label{sec-example-mixed-units}

To illustrate units, we present a tiny program working
with arithmetic expressions.  It consists of two structure-mode units, {\tt Expr}
and {\tt Reduce} and two toplevel-mode units, {\tt Evaluate} and {\tt Test}.  This example is in {\tt
  mosml/examples/units}.

File {\tt Expr.sml} below is a structure-mode unit implementation that
contains structure {\tt Expr} which defines a datatype {\tt expr} for
representing expressions and a function {\tt show} to display them.
It has no signature constraint and therefore exports both the datatype
and the function:

\begin{program}
structure Expr = struct
   datatype expr = Cst of int | Neg of expr | Plus of expr * expr

   fun show (Cst n)         = makestring n
     | show (Neg e)         = "(-" ^ show e ^ ")"
     | show (Plus (e1, e2)) = "(" ^ show e1 ^ "+" ^ show e2 ^ ")"
end
\end{program}

\noindent File {\tt Reduce.sig} below is a structure-mode unit interface 
that contains the signature {\tt Reduce}:

\begin{program}
signature Reduce = sig
   val reduce : Expr.expr -> Expr.expr
end
\end{program}

\noindent 
File {\tt Reduce.sml} below is a structure-mode unit implementation
that declares the structure {\tt Reduce}, with the explicit signature
shown above, and therefore exports only the function {\tt reduce}
specified in that signature:

\begin{program}
structure Reduce :> Reduce = struct 
   local open Expr
   in
       fun negate (Neg e) = e
         | negate e       = Neg e
       fun reduce (Neg (Neg e))      = e
         | reduce (Neg e)            = negate (reduce e)
         | reduce (Plus (Cst 0, e2)) = reduce e2
         | reduce (Plus (e1, Cst 0)) = reduce e1
         | reduce (Plus (e1, e2))    = Plus (reduce e1, reduce e2)
         | reduce e                  = e
   end
end
\end{program}

\noindent 
File {\tt Evaluate.sig} below is a toplevel-mode unit interface that
contains the specification of a functor {\tt Eval}, which maps any
structure {\tt R} matching the signature {\tt Reduce} to a structure
with a function {\tt eval} for evaluating expressions, and a function
{\tt test} for testing {\tt R}:

\begin{program}
functor Eval : functor(R:Reduce) ->
                 sig val eval: Expr.expr -> int 
                     val test: Expr.expr -> bool
                 end
\end{program}

\noindent
File {\tt Evaluate.sml} below is a toplevel-mode unit implementation
that contains the actual functor {\tt Eval}, which mentions the unit
{\tt Expr} as well as well as the unit interface {\tt Reduce}:

\begin{program}
functor Eval(R:Reduce) =
struct
  local open Expr in
  fun eval (Cst n)         = n
    | eval (Neg e)         = ~ (eval e)
    | eval (Plus (e1, e2)) = eval e1 + eval e2;
  fun test e = (eval e = eval (R.reduce e)) 
  end
end
\end{program}

\noindent 
File {\tt Test.sml} is a toplevel-mode unit implementation which
mentions the unit {\tt Expr}, the unit {\tt Reduce}, and the functor
{\tt Eval} defined in the unit {\tt Evaluate}, applies the functor to
{\tt Reduce} and carries out two tests:

\begin{program}
structure T = Eval(Reduce)
open Expr 
val t1 = T.test (Plus (Cst 244, Cst 0))
val t2 = T.test (Neg (Plus (Neg (Cst 140), Cst 0)))
\end{program}

\noindent The simplest way to compile this example is to enter:

\begin{program}
mosmlc -c -structure Expr.sml Reduce.sig Reduce.sml -toplevel Evaluate.sig Evaluate.sml Test.sml
\end{program}

\noindent
which is equivalent to issuing the following individual commands:
\begin{program}
mosmlc -c -structure Expr.sml 
mosmlc -c -structure Expr.ui Reduce.sig 
mosmlc -c -structure Expr.ui Reduce.sml 
mosmlc -c -toplevel Expr.ui Reduce.ui Evaluate.sig 
mosmlc -c -toplevel Expr.ui Reduce.ui Evaluate.sml 
mosmlc -c -toplevel Expr.ui Reduce.ui Evaluate.ui Test.sml 
\end{program}

\noindent 
The above command (re)compiles all files unconditionally.  However,
when modifying a program consisting of several units, it suffices to
recompile just those units that have changed, and those units that
depend on units that have changed.  Moreover, compilation uses only
the \emph{interfaces} of other units, so it suffices to recompile just
those units that depend on unit interfaces that have changed.

Thus if \texttt{Expr.sml} but not \texttt{Expr.sig} changes, it
suffices to recompile just \texttt{Expr.sml}, not the units
\texttt{Reduce}, \texttt{Evaluate}, or \texttt{Test}\@.  Similarly, if
\texttt{Reduce.sml} but not \texttt{Reduce.sig} changes, it suffices
to recompile just \texttt{Reduce.sml}, not the units \texttt{Evaluate}
or \texttt{Test}\@.

The next section explains recompilation management using
\texttt{mosmldep} and \texttt{make}.


\newpage
\section{Recompilation management using mosmldep and make}
\label{sec-mixed-mode-recompilation}

Recompilation management helps the programmer recompile only what is
necessary after a change to a unit interface or unit implementation.  

Consider the example program in Section~\ref{sec-example-mixed-units}
consisting of the four units {\tt Expr}, {\tt Reduce}, {\tt Evaluate}
and {\tt Test}.  Assume their source files {\tt *.sig} and {\tt *.sml}
reside in a particular directory (you may copy them from
\texttt{mosml/examples/units}).  Copy the Makefile stub from
\texttt{mosml/tools/Makefile.stub} to that directory, and change to
that directory.

\begin{enumerate}
\item\label{zero} Edit the Makefile so that the names of the units
  {\tt Expr}, {\tt Reduce}, {\tt Evaluate},  and {\tt Test} appear on the line beginning
  with `{\tt UNITS=}', with each unit preceded by the option {\tt -structure} (the default) or
  {\tt -toplevel}
  to indicate its mode
  (see the example makefile in \texttt{mosml/examples/units/Makefile}):

\begin{program}
UNITS= -structure Expr Reduce -toplevel Evaluate Test
\end{program}

\item\label{one} Edit the Makefile so that the names of the compiled
  unit implementation files {\tt Expr.uo}, {\tt Evaluate.uo}, {\tt
    Reduce.uo} and {\tt Test.uo} appear on the line beginning with
  `{\tt all:}':

\begin{program}
all: Expr.uo Reduce.uo Evaluate.uo Test.uo
\end{program}

\item\label{two} Compute the dependencies among the files by executing:

\begin{program}
make depend
\end{program}

\item\label{three} Recompile all those files which have not yet been compiled, or
  which have been modified but not yet recompiled, or which depend on
  modified files, by executing:
        
\begin{program}
make    
\end{program}
\end{enumerate}

\noindent Step (\ref{three}) must be repeated whenever you have modified a
component of the program system.  Step (\ref{two}) need only be repeated if
the inter-dependencies of some components change, or if you add or
remove an explicit signature file.  Steps (\ref{one} and \ref{zero}) need only be repeated
when you add, delete or change the mode of an entire unit in the program system.

The compiled {\tt *.ui} and {\tt *.uo} files can be removed by executing:

\begin{program}
make clean  
\end{program}

\noindent The unit dependencies are computed by the ML program
{\tt mosmldep}, called with

\begin{program}
mosmldep \$(UNITS)
\end{program}

\noindent When you explicitly list the units (together with the indication of
their compilation mode):

\begin{program}
UNITS= -structure Expr Reduce -toplevel Evaluate Test
\end{program}

\noindent 
then {\tt mosmldep} merely constructs a dependency file on the
assumption that a unit may depend on all preceding units (to the
left), taking into account the presence of explicit interfaces ({\tt
  .sig} files).  Unfortunately, this means that {\tt mosmldep} will
generally create an inefficient Makefile, containing more dependencies
than are actually in your source files.  However, it still saves some
recompilation (which is cheap in Moscow ML anyway) and is more
convenient than hand-crafting the Makefile.  We hope to improve on
this situation in the future, but computing dependencies for full
Standard ML programs is known to be difficult.

If you omit step (\ref{zero}) and leave {\tt \$(UNITS)} undefined:

\begin{program}
UNITS=
\end{program}

\noindent 
then {\tt mosmldep} will accurately \emph{infer} the dependencies
between all the {\tt .sig} and {\tt .sml} source files in the
directory by inspecting their contents and looking for occurrences
of unit names.  Unfortunately, this process
only works for programs containing just structure-mode units, that
themselves contain only flat structures, but no functors or sub-structures. 
This is the behaviour of {\tt mosmldep} in releases of
Moscow ML prior to 2.00, and is provided for backwards compatibility.

% cvr: removed section on mosmlpm for now
% \subsection{Mixed-mode recompilation management using mosmlpm}
% \label{sec-project-manager}

% The purpose of the project manager \texttt{mosmlpm}\footnote{The
%   project manager was developed by Ken Larsen and Martin Elsman.}  is
% to manage the compilation of projects consisting of more than one
% compilation unit (file).  The project manager invokes the batch
% compiler \texttt{mosmlc} to actually compile the source files.

% The current \texttt{mosmlpm} implementation has the following
% limitations: (1) source files must be have extension .sml --- it
% cannot handle files with extension .sig; (2) it does not resolve
% filename conflicts in different (sub)projects; (3) error checking and
% error messages should be improved.


% \subsubsection{Project files}
% \label{sec:gramm-proj-files}

% Each project is described by a \emph{project file}.  Projects can be
% organized hierarchically.  A project file has file extension
% \texttt{.pm} and must follow this grammar:

% \begin{tabular}{lcll}

% \textit{imports} &$::=$& \textit{path}\texttt{.pm} \textit{imports} & project\\
%                  & $|$ &                                            & empty\\
% \textit{body}    &$::=$& \textit{path}\texttt{.sml} \textit{body} & source\\
%                  & $|$ & \texttt{local} \textit{body} \texttt{in}
%                          \textit{body} \texttt{end} \textit{body} & local\\
%                  & $|$ &                                          & empty\\
% \textit{project} &$::=$& \texttt{import} \textit{imports} \texttt{in}
%                          \textit{body} \texttt{end} & with import\\
%                  & $|$ & \textit{body}              & basic
% \end{tabular}

% \noindent A project file can import source files and other project
% files using absolute or relative paths (relative to the location of
% the project file).  Project files may contain Standard ML style
% comments.  The declared identifiers of a project is the union of the
% identifiers declared by the source files in the project, except for
% source files included inside \texttt{local}.

% A source file must contain Standard ML top-level declarations.  The
% scope of a declaration is the subsequent source files mentioned in the
% project file, and other projects that import this project file.  Thus,
% a source file may depend on source files mentioned earlier in the
% project file and on other imported projects.  

% The meaning of a project is the meaning of the top-level declaration
% that would result from first expanding all imported projects and then
% concatenating all the source files listed in the project file (with
% appropriate renaming of declared identifiers of source files that are
% included using \texttt{local}), in the order they are listed, except
% that each project is executed only the first time it is imported.
 

% \subsubsection{A simple project manager example}
% \label{sec:simple-example}

% Consider again the files \texttt{Expr.sml}, \texttt{Reduce.sig},
% \texttt{Reduce.sml}, \texttt{Evaluate.sig}, and \texttt{Evaluate.sml},
% from Section~\ref{sec-example-units}.  To compile these files with
% \texttt{mosmlpm} we first have to rename all
% \textit{name}\texttt{.sig} files to \textit{name}\texttt{-sig.sml}
% becase \texttt{mosmlpm} cannot handle \texttt{.sig} files (yet).

% Now we can make a project file (\texttt{evaluator.pm}) with the
% following contents:

% \begin{program}
% Expr.sml
% Reduce-sig.sml
% Reduce.sml 
% Evaluate-sig.sml
% Evaluate.sml
% \end{program}

% \noindent 
% This file can then be compiled and linked with the command:

% \begin{program}
% mosmlpm evaluator.pm
% \end{program}

% \noindent For a more advanced example, see file
% \texttt{mosml/examples/mosmlpm}. 


% \subsubsection{Command-line options of mosmlpm}
% \label{sec:command-line-options-mosmlpm}

% \newenvironment{commandlineoptions}{%
%   \begin{list}{}%
%     {\renewcommand{\makelabel}[1]{\parbox[b]{\labelwidth}{%
%           \makebox[0pt][l]{\texttt{##1}}\\}}}
%   }
%   {\end{list}}

% The following command--line options are recognized by
% \texttt{mosmlpm}.

% \begin{commandlineoptions} 
% \item[-c] Compile only; do not link the compiled files.  Source code
%   files are turned into compiled files (.ui and .uo), but no
%   executable file is produced.
  
% \item[-quiet] Do not report the progress of compilation, linking, etc.
  
% \item[-o \textrm{exec-file}] Specifies the name of the output file
%   produced by the linker.  In the absence of this option the name of
%   the main project file (without the \texttt{.pm} extension) is used.

  
% \item[-standalone] Passes the option \texttt{standalone} on to
%   \texttt{mosmlc}
% \end{commandlineoptions}

\newpage

\section{The batch compiler and linker: mosmlc}
\label{sec-batch-compiler}

Moscow ML includes a batch compiler and linker {\tt mosmlc} in
addition to the interactive system {\tt mosml}.  It compiles units and
links programs, and can turn them into standalone executable bytecode
files.  The batch compiler can be invoked from a Makefile (see
Section~\ref{sec-mixed-mode-recompilation}),
%or from the project manager (see Section~\ref{sec-project-manager})
which simplifies the
(re)compilation of large programs considerably.


\subsection{Overview}

The {\tt mosmlc} command has a command-line interface similar to that
of most C compilers.  It accepts several types of arguments: source
files for unit interfaces, source files for unit implementations,
compiled unit interfaces (which are added to the compilation context),
and compiled unit implementations (which are added to the linked
executable).

\begin{itemize}
\item An argument ending in .sig is taken to be the name of a source
  file containing a unit interface.  Given a file U.sig, the compiler
  produces a compiled interface in the file U.ui.
  
\item An argument ending in .sml is taken to be the name of a source
  file containing a unit implementation.  Given a file U.sml, the
  compiler produces compiled object code in the file U.uo.  It also
  produces an inferred interface file U.ui if there is no explicit
  interface U.sig.
  
\item An argument ending in .ui is taken to be the name of a
  compilation unit interface.  The contents of that compilation unit
  are added to the compilation context of the remaining source files.
  
\item An argument ending in .uo is taken to be the name of a compiled
  unit implementation.  Such files are linked together, along with the
  compiled unit implementations obtained by compiling .sml arguments
  (if any), and the necessary Moscow ML library files, to produce a
  standalone executable program.
  
  The linker automatically includes any additional bytecode files
  required by the files specified on the command line; option {\tt -i}
  makes it report all the files that were linked.  The linker issues a
  warning if a file {\tt B} is required by a file {\tt A} that
  precedes {\tt B} in the command line.  At run-time, the top-level
  declarations of the files are evaluated in the order in which the
  files were linked; in the absence of any warning, this is the order
  of the .uo and .sml files on the command line.
  
  The linker (and the {\tt load} function in the interactive toplevel)
  ensure probabilistically type-safe linking, so it is virtually
  impossible to cause the system to create a type-unsafe program.
\end{itemize}

\noindent 
The output of the linking phase is a file containing compiled code
that can be executed by the runtime system {\tt camlrunm}.  If {\tt
  mosmlout} is the name of the file produced by the linking phase
(with option \texttt{-o mosmlout}), the command

\begin{program}
mosmlout arg\sub{1} arg\sub{2} \ldots\ arg\sub{n}
\end{program}

\noindent executes the compiled code contained in {\tt mosmlout}.
Executing the code means executing the toplevel declarations of all
the bytecode files involved, in the order in which they were linked.
The list of command-line arguments \texttt{arg\sub{1} \ldots\ 
  arg\sub{n}} can be obtained in a program by {\tt
  CommandLine.arguments ()}.

There is no distinguished function which is automatically invoked when
the program is executed, but it is common to define a \texttt{main}
function and invoke it using the toplevel declaration \texttt{val \_ =
  main()}, like this:

\begin{program}
fun main () = 
    case CommandLine.arguments () of 
        [arg] => print ("The argument is " ^ arg ^ "\verb+\+n")
      | _     => print "Usage: mosmlout arg\verb+\+n\verb+\+n"

val _ = main ();
\end{program}




\begin{description}
\item[MS Windows and DOS:] If the output file produced by the linking
  phase has extension {\tt .exe}, and option {\tt -noheader} is not
  used, then the file is directly executable.  Hence, an output file
  named {\tt mosmlout.exe} can be executed with the command

\begin{program}
mosmlout arg1 arg2 ... argn    
\end{program}

The output file {\tt mosmlout.exe} consists of a tiny executable file
prepended to a linked bytecode file.  The executable invokes the {\tt
  camlrunm} runtime system to interpret the bytecode.  As a
consequence, this is not a standalone executable: it still requires
{\tt camlrt.dll} to be present in directory \verb+C:\mosml\bin+.

\item[Unix:] The output file produced by the linking phase is directly
  executable (unless the {\tt -noheader} option is used).  It
  automatically invokes the {\tt camlrunm} runtime system, either
  using a tiny executable prepended to the linked bytecode file, or
  using the Unix incantation \verb|#!/usr/local/bin/camlrunm| or
  similar.  In the former case, {\tt camlrunm} must be in one of the
  directories in the path; in the latter case it must be in {\tt
    /usr/local/bin}.  To create a true stand-alone executable, use
  \texttt{mosmlc} option \texttt{-standalone}.
\end{description}


\subsection{Command-line options of mosmlc}
\label{sec-mosmlc-options}

The following command-line options are recognized by {\tt mosmlc}.

\begin{description}
\item[{\tt -c}]\mbox{ }

  Compile only. Suppresses the linking phase of the compilation.
  Source code files are turned into compiled files (.ui and .uo), but
  no executable file is produced.  This option is useful for compiling
  separate units.

\item[{\tt -conservative}]\mbox{ }
  
  Sets conservative mode for compilation of subsequent units: accept
  all extensions to the SML Modules language, but issue a warning for
  each use; see Section~\ref{sec-modules-extensions}.  This is the
  default.

\item[{\tt -files {\rm response-file}}]\mbox{ }

  Pass the names of files listed in file response-file to the linking
  phase just as if these names appeared on the command line.  File
  names in response-file are separated by blanks (spaces, tabs,
  newlines) and must end either in .sml or .uo.  A name U.sml
  appearing in the response file is equivalent to U.uo.  Use this
  option to overcome silly limitations on the length of the
  command line (as in MS DOS).

\item[{\tt -g}]\mbox{ }

  This option causes some information about exception names to be
  written at the end of the executable bytecode file.  

\item[{\tt -i}]\mbox{ }
  
  Causes the compiler to print the inferred interface(s) of the unit
  implementation(s) being compiled.  Also causes the linker to list
  all object files linked.  A U.sig file corresponding to a given
  U.sml file can be produced semi-automatically by piping the output
  of the compiler to a file U.out, and subsequently editing this file
  to obtain a file U.sig.

\item[{\tt -I {\rm directory}}]\mbox{ }
  
  Add the given directory to the list of directories searched for
  compiled interface files (.ui) and compiled implementation files
  (.uo).  By default, the current directory is searched first, then
  the standard library directory.  Directories added with {\tt -I} are
  searched after the current directory, but before the standard
  library directory.  When several directories are added with several
  {\tt -I} options on the command line, these directories are searched
  from left to right.

\item[{\tt -imptypes}]\mbox{ }

  Specify that the type checker should distinguish imperative and
  applicative type variables, generalize all applicative type
  variables, and generalize imperative type variables only in
  non-expansive expressions.  See Section~\ref{sec-valuepoly}.

\item[{\tt -liberal}]\mbox{ }
  
  Sets liberal mode for compilation of subsequent units: accept
  without warnings all extensions to the SML Modules language; see
  Section~\ref{sec-modules-extensions}.

\item[{\tt -msgstyle \textrm{style}}]\mbox{ }
  
  By specifying \texttt{-msgstyle msdev}, one can make the compiler
  generate error messages understandable by Microsoft Developer
  Studio.  The default behaviour is to generate error messages
  understandable the Emacs editor in SML mode.

\item[{\tt -noautolink}]\mbox{ }
  
  The linker automatically links in any additional object files
  required by the files explicitly specified on the command line.
  With option {\tt -noautolink} all required object files must be
  explicitly specified in the appropriate order.

\item[{\tt -noheader}]\mbox{ }

  Causes the output file produced by the linker to contain only the
  bytecode, not preceded by any executable code.  A file {\tt
    mosmlout} thus obtained can be executed only by explicitly
  invoking the runtime system as follows: {\tt camlrunm mosmlout}.

\item[{\tt -o {\rm exec-file}}]\mbox{ }

  Specify the name of the output file produced by the linker.  In the
  absence of this option, a default name is used.  In MS Windows and
  DOS, the default name is {\tt mosmlout.exe}; in Unix it is {\tt
    a.out}.

\item[{\tt -orthodox}]\mbox{ }
  
  Sets orthodox mode for the compilation of subsequent units: reject
  all uses of the extensions to the SML Modules language.  That is,
  accept only SML Modules syntax; see
  Section~\ref{sec-modules-extensions}.

\item[{\tt -P {\rm unit-set}}]\mbox{ }

  Determines which library units will be {\em open\/} at compile-time.
  Any library unit in the load path can be used by the compiler for
  type checking purposes.  Thus regardless of the {\tt -P} option, the
  compiler knows the type of library functions such as {\tt
    Array.foldl}.

  \begin{description}
  \item[{\tt -P default}] The units {\tt Char}, {\tt List}, and {\tt
      String} will be partially opened.  This is the default,
    permitting e.g.\ {\tt String.concat} to be referred to just as
    {\tt concat}.

  \item[{\tt -P sml90}] Provides an initial environment which is
    upwards compatible with that of the 1990 {\em Definition of
      Standard ML\/} and with pre-1.30 releases of Moscow ML\@.  In
    particular, the functions {\tt chr}, {\tt explode}, {\tt implode},
    and {\tt ord} work on strings, not characters.  The math functions
    and input-output facilities required by the 1990 Definition
    \cite[Appendix C and D]{Milner:1990:TheDefinition} are available
    at top-level.  In addition the same (new) libraries are opened as
    with {\tt -P default}.

  \item[{\tt -P nj93}] Provides a top-level environment which is
    mostly compatible with that of SML/NJ 0.93.  The functions {\tt
      app}, {\tt ceiling}, {\tt chr}, {\tt dec}, {\tt explode}, {\tt
      fold}, {\tt hd}, {\tt implode}, {\tt inc}, {\tt max}, {\tt min},
    {\tt nth}, {\tt nthtail}, {\tt ord}, {\tt ordof}, {\tt revapp},
    {\tt revfold}, {\tt substring}, {\tt tl}, and {\tt truncate} have
    the same type and meaning as in SML/NJ 0.93.  The math functions
    and input-output facilities required by the 1990 Definition
    \cite[Appendix C and D]{Milner:1990:TheDefinition} are available
    at top-level.  In addition the same (new) libraries are opened as
    with {\tt -P default}.  This option does {\em not\/} imply {\tt
      -imptypes}.

  \item[{\tt -P full}] Same as {\tt -P default}.

  \item[{\tt -P none}] No library units are initially opened.
  \end{description}
  
  Additional directories to be searched for library units can be
  specified with the {\tt -I {\rm directory}} option.

\item[{\tt -q}]\mbox{ }

  Enables the quotation/antiquotation mechanism; see
  Section~\ref{sec-quotations}.

\item[{\tt -standalone}]\mbox{ }
  
  Unix: Specifies that the runtime system should be prepended to the
  linked bytecode, thus creating a stand-alone executable.  This adds
  75--100 KB to the size of the linked file.  MS Windows: This option
  cannot be used.  Under MS Windows, all mosmlc-generated executables
  require the dynamically linked library \texttt{camlrt.dll} to be
  present in the directory \verb+C:\mosml\bin+.

\item[{\tt -stdlib {\rm stdlib-directory}}]\mbox{ }

  Specifies the standard library directory, which will be searched by
  the compiler and linker for the .ui and .uo files corresponding to
  units mentioned in the files being linked.  The default standard
  library is set when the system is created, and is usually {\tt
    \$\{HOME\}/mosml/lib} under Unix and \verb#c:\mosml\lib# under MS
  Windows and DOS.

\item[{\tt -structure}]\mbox{ }
  
  Specifies that subsequent .sml and .sig source files must be
  compiled in structure mode; see Section~\ref{sec-structure-mode}.
  Default.

\item[{\tt -toplevel}]\mbox{ }
  
  Specifies that subsequent .sml and .sig source files must be
  compiled in toplevel mode; see Section~\ref{sec-toplevel-mode}.

\item[{\tt -v}]\mbox{ }
  
  Prints the version number of the various passes of the compiler.

\item[{\tt -valuepoly}]\mbox{ }

  Specify that the type checker should use `value polymorphism'; see
  Section~\ref{sec-valuepoly}.  Default.
\end{description}





\newpage
\section{Extensions to the Standard ML Modules language}
\label{sec-modules-extensions}

The Moscow ML Modules language extends the Standard ML Modules
language in several ways:

\begin{itemize}
\item higher-order functors: a functor may be defined within
  a structure, passed as an argument to another functor, 
  or returned as the result
  of a functor; see Section~\ref{sec-ho-modules}
\item applicative as well as (the usual) generative functors; see
   Section~\ref{sec-applicative-functors}
\item transparent as well as opaque functor signatures; see
    Section~\ref{sec-functor-signatures}
\item first-class modules: structures and functors may be packed and
  then handled as Core language values, which may then be unpacked as
  structures or functors again; see
  Section~\ref{sec-firstclass-modules}
\item recursive modules:  structures and signatures may be recursively
  defined; see Section~\ref{sec-rec-modules}
\item relaxation of miscellaneous Standard ML restrictions;
 see Section~\ref{sec-misc-relaxations}.
\end{itemize}

\noindent 
The \emph{Moscow ML Language Overview} defines the precise syntax of
the extensions.
For some additional examples of their use, see the directory {\tt
mosml/examples/modules} and its {\tt README} file.

By default, Moscow ML accepts all non-Standard ML extensions, but
issues a warning at every use.  This is the behaviour of Moscow ML's 
\emph{conservative} compilation mode.  Two other compilation modes are available:
\emph{liberal}, in which all extensions are silently accepted, and
\emph{orthodox}, in which all extensions are rejected as errors.

The compilation mode can be set by the command-line options
\texttt{-conservative}, \texttt{-liberal}, and \texttt{-orthodox}; see
Sections~\ref{sec-mosml-options} and~\ref{sec-mosmlc-options}.
In the interactive system \texttt{mosml}, the compilation mode affects
ML code entered interactively, as well as the functions
\texttt{compile}, \texttt{compileStructure}, \texttt{compileToplevel},
and \texttt{use}.  The compilation mode can be set by the functions
\texttt{conservative}, \texttt{liberal}, and \texttt{orthodox}.

The extensions described here are based in part on
\cite{Russo:TypesForModules,Russo:FirstClassStructures}; a formal
definition of the extensions, derived from
\cite{Milner:1990:TheDefinition, Milner:1997:TheDefinition}, is
available on request.



\subsection{Higher-order modules}

\label{sec-ho-modules}

In Standard ML Modules, structures and functor bodies cannot declare
functors.  In Moscow ML Modules, they can:

\begin{program}
functor F1(S : sig type t; val x : t end) = struct
    functor G(T : sig type u; val y : u end) = struct val pair = (S.x, T.y) end
end
structure R11 = F1(struct type t=int val x=177 end)
structure R12 = R11.G(struct type u=string val y="abc" end)
val (a, b) = R12.pair
\end{program}

\noindent 
A functor that returns a functor can be curried, avoiding the intermediate
structure:

\begin{program}
functor F2(S : sig type t; val x : t end) (T : sig type u; val y : u end) = 
   struct val pair = (S.x, T.y) end
structure R2 = 
   F2(struct type t=int val x=177 end)(struct type u=string val y="abc" end)
val (a, b) = R2.pair
\end{program}

\noindent 

% The definition of {\tt F2} above is short-hand for declaring {\tt F2} to return
% an anonymous functor:
% \begin{program}
% functor F2 (S : sig type t; val x : t end) = 
%    functor(T : sig type u; val y : u end) => struct val pair = (S.x, T.y) end  (* anonymous functor *)
% \end{program}

\noindent 
A functor may be declared to take another functor as an argument, whose
type is specified using a functor signature:

\begin{program}
(* G is a functor signature *)
signature G = functor(X:sig type t=int val x: t end)->sig type u val y : u end

(* F3 takes the functor F as an argument, and applies it *)
functor F3(F:G) = F(struct type t=int val x=177 end) 

(* R3 is the result of F3 applied to an anonymous functor *)        
structure R3 = F3(functor(X:sig type t=int val x:t end)=> 
                  struct type u = X.t * X.t val y= (X.x,X.x) end)
\end{program}

\noindent 
In the definition of {\tt R3}, the argument to {\tt F3} happens to be an anonymous functor.

\noindent 
Wherever a functor of a certain type is expected, one may supply
instead a functor that has more a general type, that is, one which is
more polymorphic, expects a less general argument, or produces a more
general result:

\begin{program}
(* F3  is applied to a more general functor than it specifically requires *)
structure R4 = F3(functor(X:sig type t end)=> 
                  struct type u = X.t val y = 1 val z = [] end)
\end{program}

\noindent 
As in Standard ML, functors and structures reside in separate name spaces,
so it is perfectly legal to re-use the same name for both a structure and a functor, without
one hiding the other:

\begin{program}
structure M = struct end
functor M() = struct end
structure N1 = M             (* structure N1 bound to structure M *)
functor   N2 = M             (* functor N1 bound to functor M *)
structure N3 = M(M)          (* functor M applied to structure M *)
\end{program}

\noindent
However, when another functor, say {\tt P}, simply returns the identifier {\tt M}, as in:
\begin{program}
functor P () = M
\end{program}

\noindent
it is not clear whether {\tt M} refers to the structure {\tt M} or the functor {\tt M}\@. 
In this ambiguous case, Moscow ML always interprets 
{\tt M}, on its own, as a structure, but you can write {\tt op M}
to refer to the functor {\tt M} instead:
\begin{program}
functor P () = M      (* P returns the structure M *)
functor Q () = op M   (* Q returns the functor M *) 
\end{program}

\noindent 
The files {\tt mosml/examples/modules/\{poly.sml,bootstrap.sml\}} contain
examples that use higher-order functors.

\subsection{Applicative functors}
\label{sec-applicative-functors}

In the Standard ML Modules language, all functors are generative.  If
the body of generative functor \texttt{FG} declares a datatype 
or opaque type
\texttt{t}, then two applications of \texttt{FG} will create two
structures \texttt{SG1} and \texttt{SG2} with distinct types
\texttt{SG1.t} and \texttt{SG2.t}:

\begin{program}
functor FG (S : sig end) = struct datatype t = C end    (* generative  *)
structure SG1 = FG() and SG2 = FG()
val res = if true then SG1.C else SG2.C;                (* ill-typed   *)
\end{program}

\noindent
Recall that a conditional expression requires both branches to have
equivalent types, so the last declaration above is well-typed only if the
type \texttt{SG1.t} is equivalent to \texttt{SG2.t}.

If functors had an \emph{applicative}, not generative,
semantics, the two types would be equivalent. 
Moscow ML Modules allows the declaration of applicative
functors\footnote{Similar to Objective Caml.} as well as generative
functors.  An applicative version \texttt{FA} of the above functor is
declared the same way, except that the formal functor argument
\texttt{S :\ sig end} is not enclosed in parentheses:

\begin{program}
functor FA S : sig end = struct datatype t = C end      (* applicative *)
structure SA1 = FA() and SA2 = FA() 
val res = if true then SA1.C else SA2.C;                (* well-typed  *)
\end{program}

\noindent
More generally, if a type in an applicative functor's body depends on
a datatype or opaque type of the functor's formal argument, then the
types returned by separate applications of the applicative functor
will be equivalent, provided the functor is applied to equivalent type
arguments:
\begin{program}
functor GA S : sig type t end = struct datatype u = C of S.t end  (* applicative, *) 
                                                                  (* but u depends on S.t *)
structure TA1 = GA(type t = int) and TA2 = GA(type t = bool) and TA3 = GA(type t = int)
val res = if true then TA1.C 1 else TA3.C 1;            (* well-typed *)
val res = if true then TA1.C 1 else TA2.C true;         (* ill-typed  *)
\end{program}

\noindent 
Moscow ML supports type projections \texttt{X.u} (the dot notation for
types) with local structure bindings.  This makes it possible to refer
directly to a type returned by an applicative functor within another
type expression, which is useful for expressing sharing constraints:

\begin{program}
signature S = sig functor F: functor X:sig type t end -> sig type u end
                  type v = X.u where X = F(type t = int)          (* X is local to X.u *)
              end
\end{program}

\noindent
The local binding has no run-time effect and is only elaborated at
compile-time for its type information.  For more examples of
applicative functors, see the files {\tt
  mosml/examples/modules/\{collect.sml,bootstrap.sml\}}.


\subsection{Opaque and transparent functor signatures}
\label{sec-functor-signatures}

The types of functors are specified using functor signatures. Similar
to the distinction between generative and applicative functor
expressions, functor signatures may be \emph{opaque} or
\emph{transparent}.  Whether a functor signature is opaque or
transparent affects the interpretation of any datatype or opaque type
specifications in its body signature:

The \emph{opaque} functor signature 
\begin{program}
signature GO = functor(X:sig type t val x:t end)->sig type u val y:u end   (* opaque      *)
\end{program}

\noindent
specifies the type of those functors that, when applied to an actual
argument matching the argument signature \texttt{sig type t val x:t end}, 
return a result matching the body signature \texttt{sig type u val y:u end}, 
for some unknown implementation of the type \texttt{u}
(possibly depending on \texttt{X.t}).


A \emph{transparent} version \texttt{GT} of the above functor
signature is written the same way, except that the formal functor
argument \texttt{X:sig type t val x:t end} is \emph{not} enclosed in
parentheses:
\begin{program}
signature GT = functor X:sig type t val x:t end -> sig type u val y:u end  (* transparent *)
\end{program}

\noindent
This functor signature
specifies the \emph{family} of functor types that, for a given 
implementation of the result type \texttt{u} (possibly 
depending on \texttt{X.t}),
map structures matching the argument signature
\texttt{sig type t val x:t  end} to structures
matching the body signature \texttt{sig type u val y:u end}.

In practice, when writing a functor \texttt{H} that 
takes a functor \texttt{F} as an argument,
the choice between specifying that argument using an opaque
or transparent signature will affect the amount of 
type information that is propagated whenever \texttt{H}
is applied to an actual functor.
For instance, consider the four functors:

\begin{program}
functor F1 (X:sig type t val x:t end) = struct type u = X.t val y = X.x end
functor F2 (X:sig type t val x:t end) = struct type u = int val y = 1 end

functor HO(F:GO) = F(struct type t = string val x = "abc" end)
functor HT(F:GT) = F(struct type t = string val x = "abc" end)
\end{program}

\noindent
Functor \texttt{F1} returns a renamed version of its argument, and
functor \texttt{F2} just ignores its argument and returns the same
structure regardless.  The two higher-order functors \texttt{HO} and
\texttt{HT} apply the supplied \texttt{F} to the same argument (in
which \texttt{x} is a string), but assume, respectively, an opaque and
a transparent signature for \texttt{F}.

Since functor \texttt{HO} uses the opaque signature \texttt{GO}, its
formal argument \texttt{F}\ is assumed to return some new unknown type
\texttt{u} whenever it is applied, so that the two applications of
\texttt{HO} return new abstract types \texttt{RO1.u} and
\texttt{RO2.u}:

\begin{program}
structure RO1 = HO(F1) and RO2 = HO(F2)
val resO1 = if true then RO1.y else "def";            (* ill-typed *) 
val resO2 = if true then RO2.y else 1;                (* ill-typed *) 
\end{program}

\noindent 
Functor \texttt{HT}, on the other hand, uses the transparent signature
\texttt{GT}\@.  This ensures that, no matter what the actual
dependency of result type \texttt{u} on argument type \texttt{t},
\texttt{HT} may be applied to any functor \texttt{F} whose argument
signature and result signature match \texttt{GT}, with the actual
definition of \texttt{u} reflected in the result.  In particular, the
two applications of \texttt{HT} return the same definitions for type
\texttt{u} as would the substitution of \texttt{F1} and \texttt{F2}
directly into the body of \texttt{HT}\@.  That is, the types
\texttt{RT1.u} and \texttt{RT2.u} are equivalent to \texttt{string}
and \texttt{int}:

\begin{program}
structure RT1 = HT(F1) and RT2 = HT(F2)
val resT1 = if true then RT1.y else "def";            (* well-typed *)
val resT2 = if true then RT2.y else 1;                (* well-typed *)
\end{program}

\noindent 
Another way to look at this is that \texttt{HO}'s formal argument has
a generative specification, so that its application in {\tt HO}'s  body returns
a new type,  while
\texttt{HT}'s formal argument has an
applicative specification, so that its application in {\tt HT}'s body
returns the same type as \texttt{HT}'s actual argument.

\subsection{First-class modules}

\label{sec-firstclass-modules}

In the Moscow ML Modules language, a structure or functor can be
wrapped up as a \emph{package}, which is a first-class Core language
value just like any other value, and then subsequently unpacked to
re-create the structure or functor:

\begin{program}
signature NAT = sig type nat  val Z:nat  val S:nat -> nat  val plus: nat -> nat -> nat end
structure SafeNat =  (* unlimited range but slow *)
  struct datatype nat = Z | S of nat  fun plus Z m = m | plus (S n) m = S (plus n m) end
structure FastNat =  (* limited range but fast *)
  struct type nat = int  val Z = 0  fun S n = n + 1  fun plus n m = n + m end

type natpack = [ NAT ]                                (* package type *)
val safeNat = [ structure SafeNat as NAT ];           (* packing      *)
val fastNat = [ structure FastNat as NAT ];    
structure Nat as NAT =                                (* unpacking    *)
      if (913 mod 7 = 5) then safeNat else fastNat
val natlist = [safeNat,fastNat] : [ NAT ] list;
\end{program}

\noindent 
A functor may be packed using the similar Core expression
\texttt{ [ functor {\it modexp} as {\it sigexp} ]} and unpacked using
the functor binding \texttt{ functor {\it funid} as {\it sigexp} =
  {\it exp}}.

Package type equivalence is determined by structure, not name, so the
following package types are equivalent:

\begin{program}
[sig type t val x: t type u = t val y: u end]
[sig type u val x: u type t = u val y: t end]
\end{program}

\noindent 
because the signatures are equivalent (every structure that matches
one also matches the other).

For type soundness reasons, a package may not be unpacked in the body
of a functor (although it may be unpacked within a Core expression
occurring in that body):

\begin{program}
functor Fail (val nat : [ NAT ]) = 
  struct structure Nat as NAT = nat end                        (* illegal *)
functor Ok (val nat : [ NAT ]) = 
  struct val x = let structure Nat as NAT = nat in nat end end (* legal *)
\end{program}

\noindent 
The files {\tt
  mosml/examples/modules/\{sieve.sml,array.sml,choice.sml,matrix.sml\}}
contain more examples.


\subsection{Recursive structures and signatures}
\label{sec-rec-modules}

The Standard ML Modules language does not permit recursively defined
modules.  For instance, two structures \texttt{Even} and \texttt{Odd}
may not depend on each other.  In the Moscow ML Modules language, a
structure may be defined recursively:

\begin{program}
structure S = rec (X:sig structure Odd : sig val test : int -> bool end end)  
              struct structure Even = struct fun test 0 = true 
                                               | test n = X.Odd.test (n-1)
                                      end        
                     structure Odd  = struct fun test 0 = false
                                               | test n = Even.test (n-1)
                                      end               
              end;
\end{program}

\noindent
Here, \texttt{X} is a forward declaration of the structure's body
that allows \texttt{Even.test} to refer to
\texttt{X.Odd.test} before it has been defined.
The body of a recursive structure must match the signature of
the forward declaration; any opaque type or datatype 
specified in the signature must be implemented in the body
by \emph{copying} it using a forward reference:

\begin{program}
structure Ok   = (* well-typed *)
                 rec (X:sig datatype t = C type u type v = int end)
                 struct datatype t = datatype X.t type u = X.u type v = int end 
structure Fail = (* ill-typed *)
                 rec (X:sig datatype t = C type u type v = int end)
                 struct datatype t = C type u = int type v = int end 
\end{program}

\noindent
At run-time, attempting to evaluate the forward reference of a recursive structure
before its body has been been fully evaluated raises the exception
\texttt{Bind}:

\begin{program}
structure Fail = rec (X:sig end) X;                            (* raises Bind   *)
structure Fail = rec (X:sig val x: int end) 
                 struct val x = X.x end;                       (* raises Bind   *)
structure Ok = rec (X:sig val f: int -> int end) 
               struct fun f n = X.f n  end;                    (* ok            *)
val res = Ok.f n                                               (* infinite loop *)
\end{program}

\noindent
On their own, recursive structures cannot be used to declare mutually
recursive datatypes that span module boundaries.  For this purpose,
Moscow ML also supports \emph{recursive signatures}:

\begin{program}
signature REC = rec(X: sig structure Odd: sig type t end end)
                sig structure Even: sig datatype t = Zero | Succ of X.Odd.t end
                    structure  Odd: sig datatype t = One  | Succ of Even.t end
                end;
\end{program}

\noindent
Here, \texttt{X}\ is a forward declaration of a structure implementing
the body of the signature that allows the specification of
\texttt{Even.t} to refer to the type \texttt{X.Odd.t} before it has
been fully specified.  In a recursive signature, the body of the
signature must match the forward declaration and specify an
implementation for any opaque types or datatypes declared within the
forward specification.

Once a recursive signature has been defined, it can be used to
implement the recursive structure \texttt{T} with datatypes that span
module boundaries:

\begin{program}
structure T = rec(X:REC)
              struct structure Even = struct datatype t = datatype X.Even.t 
                                             fun succ Zero = X.Odd.One 
                                               | succ E = X.Odd.Succ E
                                       end
                     structure Odd  = struct datatype t = datatype X.Odd.t
                                             fun succ O = Even.Succ O
                                      end
              end
\end{program}

\noindent The files {\tt mosml/examples/modules/\{recursion.sml,bootstrap.sml\}}
contain examples of using recursive structures and signatures.

\subsection{Miscellaneous relaxations of Standard ML restrictions}
\label{sec-misc-relaxations}

In Standard ML, functors and signatures may only be declared at
top-level, and structures may only be declared at top-level and within
structures.  None of these may be declared within Core let
expressions.  Moscow ML removes these restrictions so that functors,
signatures and structures may be declared anywhere, which is
particularly useful when programming with first-class modules.

In Standard ML, every parameterised type definition, and every type
scheme occurring within a signature, must be closed and must not
mention any type variables that are not explicitly listed as
parameters.  Moscow ML does not impose this restriction, and allows
free type variables, provided they are bound in an enclosing scope.
Again, this is useful when programming with first-class modules.

\begin{program}
type t = 'a -> 'a                                (* illegal, since 'a not in scope      *)

fun f (x:'a) = let type t = 'a * 'a              (* legal Mosml, illegal SML            *)
               in (x,x):t 
               end;

type 'a stackpack =                              (* legal Mosml                         *)
    [ sig                             
          type stack = 'a list;                  (* 'a occurs free in this type binding *)
          val push : 'a -> stack -> stack        (* 'a occurs free in this type scheme  *)
      end ]
\end{program}

\newpage

\section{Value polymorphism}
\label{sec-valuepoly}

The 1997 revision of Standard ML \cite{Milner:1997:TheDefinition}
adopts value polymorphism, discarding the distinction between
imperative (\verb#'_a#) and applicative (\verb#'a#) type variables,
and generalizing type variables only in non-expansive expressions.  In
Moscow ML 2.00, non-generalized type variables are left free, to be
instantiated later.  Consider a {\tt val}-binding

\begin{program}
val x = e;
\end{program}

\noindent With {\em value polymorphism\/}, the free type variables in
the type of {\tt x} are generalized only if the right-hand side {\tt
  e} is non-expansive.  This is a purely syntactic criterion: an
expression is {\em non-expansive\/} if it has the form {\it nexp\/},
defined by the grammar below:

\begin{quot} 
\begin{tabular}{@{}lcll}
{\it nexp} & ::= & {\it scon\/}  & special constant\\
&& {\it longvid\/} & (possibly qualified) value identifier\\           
&& \verb#{# $\langle${\it nexprow\/}$\rangle$ \verb#}# & record of
non-expansive expressions\\
&& \verb#(# {\it nexp\/} \verb#)# & parenthesized non-expansive expression\\
&& {\it con\/}\ {\it nexp\/} & constructor application, where {\it con\/}
is not {\tt ref}\\
&& {\it excon\/}\ {\it nexp\/} & exception constructor application\\
&& {\it nexp} \verb#:# {\it ty\/} & typed non-expansive expression\\
&& \verb#fn# {\it match} & function abstraction\\
& & {\tt [ structure {\it nmodexp\/} as {\it sigexp\/} ]} & structure package \\
& & {\tt [ functor {\it nmodexp\/} as {\it sigexp\/} ]} & functor package \\[2ex]
{\it nmodexp\/} & ::=  & $\langle${\tt op} $\rangle$ {\tt {\it longmodid\/}}& module identifier\\
& & {\tt ( {\it nmodexp\/} )} & \\
& & {\tt {\it nmodexp\/} :}({\tt :>}) {\tt {\it sigexp\/}} & transparent (opaque) constraint \\
& & {\tt functor {\it  arg} => {\it modexp}}  & functor  \\
& & {\tt rec ( {\it strid\/} :\ {\it sigexp} ) {\it nmodexp}}  & recursive structure \\[2ex]
{\it nexprow} & ::= & {\it lab\/} \verb#=# {\it nexp\/}
$\langle$\verb#,# {\it nexprow\/}$\rangle$  \\
\end{tabular}
\end{quot}

\noindent Roughly, a non-expansive expression is just a value, that
is, an expression in normal form.  For example, the right-hand side
{\tt length} below is an identifier, and so is non-expansive.  Hence
the free type variable {\tt 'a} in the type {\tt 'a list -> int} of
{\tt x} becomes generalized, as shown by the occurrence of \texttt{'a}
between \texttt{val} and \texttt{x}:

\begin{program}
- val x = length;
> val 'a x = fn : 'a list -> int
\end{program}

\noindent On the other hand, the right-hand side {\tt (fn f => f)
  length} below, although it evaluates to the same value as the
previous one, is expansive: it is not derivable from the above
grammar.  Hence the type variable {\tt 'a} will not be generalized,
and a warning will be issued:

\begin{program}
- val x = (fn f => f) length;
! Warning: Value polymorphism: 
! Free type variable(s) at top level in value identifier x
> val x = fn : 'a list -> int
\end{program}

\noindent Note that the type variable \texttt{'a} has not been
generalized.  Thus type variable \texttt{'a} is free and may become
instantiated when \texttt{x} is used.  If so, the type of \texttt{x}
becomes more specific:

\begin{program}
- x ["abc", "def"];
! Warning: the free type variable 'a has been instantiated to string
> val it = 2 : int
- x;
> val it = fn : string list -> int
\end{program}

\noindent To make sure that a type variable gets generalized, one may {\em
  eta-expand\/} the right-hand side expression.  Eta-expansion
replaces an expression $e$ with \texttt{fn y => (e y)} thus making it
non-expansive:

\begin{program}
- val x1 = fn y => (fn f => f) length y;
> val 'b x1 = fn : 'b list -> int
\end{program}

\noindent Compatibility: All programs compiled with Moscow ML 1.44
will compile also with Moscow ML 2.00\@.  To compile old programs that
use imperative type variables as in the 1990 Definition, you may
invoke {\tt mosml} or {\tt mosmlc} with the option {\tt -imptypes}.

% In Moscow ML versions prior to 1.40, the type checker would
% distinguish imperative and applicative type variables, generalize all
% applicative type variables, and generalize imperative type variables
% only in non-expansive expressions, as required by the 1990 {\em
%   Definition\/} \cite{Milner:1990:TheDefinition}.  To reinstate this
% behaviour, invoke {\tt mosml} or {\tt mosmlc} with the option {\tt
%   -imptypes}.  This is useful for compiling old programs.

\newpage


\section{Weak pointers}
\label{sec-weak-pointers}

Moscow ML supports weak pointers and arrays of weak pointers, using
library structure {\tt Weak}.  A {\em weak pointer\/} is a pointer
that cannot itself keep an object alive.  Hence the object pointed to
by a weak pointer may be deallocated by the garbage collector if the
object is reachable only by weak pointers.

The interface to arrays of weak pointers is the same as that of
standard arrays (structure {\tt Array}), but the subscript function
{\tt sub} may raise exception {\tt Fail} if the accessed object is
dead.  On the other hand, if {\tt sub} returns a value, it is
guaranteed not to die unexpectedly: it will be kept alive by the
returned pointer.  Also, the weak array iteration functions iterate
only over the live elements of the arrays.

One application of weak pointers is to implement hash consing without
space leaks.  The idea in hash consing is to re-use pairs: whenever a
new pair ($a$, $b$) is to be built, an auxiliary table is checked to
see whether such a pair exists already.  If so, the old pair is
reused.  In some applications, this may conserve much space and time.
However, there is a danger of running out of memory because of a space
leak: the pair ($a$, $b$) cannot be deallocated by the garbage
collector because it remains forever reachable from the auxiliary
table.  To circumvent this problem, one creates a weak pointer from
the auxiliary table to the pair, so that the auxiliary table in itself
cannot keep the pair alive.

For an example, see {\tt mosml/examples/weak}.  See also the
description of {\tt Weak} in the \emph{Moscow ML Library
  Documentation}, or try `{\tt help "Weak";}'.


\section{Dynamic linking of foreign functions}
\label{sec-dynamic-linking}

Moscow ML supports dynamic linking of foreign (C) functions, using
library structure {\tt Dynlib}\footnote{Thanks to Ken Larsen.}.  A
library of functions may be written in C and compiled into a
dynamically loadable library, using appropriate compiler options.
With the {\tt Dynlib} structure one can load this library and call the
C functions from Moscow ML, without recompiling the runtime system.

It is the responsibility of the C functions to access and construct
SML values properly, using the macroes defined in {\tt
  mosml/include/mlvalues.h}.  For this reason, the foreign
function interface is included only with the source distribution.  As
usual, type or storage mistakes in C programs may crash your programs.

The ML garbage collector may run at any time an ML memory allocation
is made.  This may cause ML values to be moved (from the young
generation to the old one).  To make sure that ML heap pointers needed
by your C function are adjusted correctly by the garbage collector,
register them using the \verb+Push_roots+ and \verb+Pop_roots+ macroes
from {\tt mosml/include/memory.h}.

To modify a value in the ML heap, you must use the {\tt Modify} macro
from {\tt mosml/include/memory.h}; otherwise you may confuse the incremental
garbage collector and crash your program.

When loading the compiled library one must specify the absolute path
unless it has been installed as a system library.  This may require
putting it in a particular directory, such as {\tt /lib} or {\tt
  /usr/lib}, or editing {\tt /etc/ld.so.conf} and running {\tt
  ldconfig}.

To compile Moscow ML\footnote{Supported under Linux, FreeBSD, NetBSD,
  Solaris, Digital Unix, HP-UX, MacOS, and MS Windows'95/98/NT.} with
support for dynamic linking, edit file {\tt mosml/src/Makefile.inc} as
indicated there.

For more information, see the examples in directory {\tt
  mosml/src/dynlibs}, in particular\\ {\tt
  mosml/src/dynlibs/interface}\@.  See also the {\tt Dynlib} section
in the \emph{Moscow ML Library Documentation}
\cite{MoscowML:2000:MoscowMLLibrary}; or try `{\tt help "Dynlib";}'.


\newpage \section{Guide to selected dynamically loaded libraries}

\subsection{Using GNU gdbm persistent hash tables }
\label{sec-using-mgdbm}

Moscow ML provides an interface to GNU gdbm persistent hashtables, via
structures {\tt Gdbm} and {\tt Polygdbm}; see the appropriate sections
in \cite{MoscowML:2000:MoscowMLLibrary}.  GNU gdbm provides fast
access even to very large hashtables stored on disk, ensuring mutual
exclusion, and are handy for creating simple databases for use by CGI
scripts etc.

Using \texttt{Gdbm} or \texttt{Polygdbm} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): GNU gdbm (not included with Moscow
ML) must be installed, and the interface to GNU gdbm defined in {\tt
  mosml/src/dynlibs/mgdbm} must be compiled and installed.  For
instructions, see the {\tt README} file there.


\subsection{Using POSIX regular expressions}
\label{sec-using-mregex}

Moscow ML provides an interface to the GNU regex implementation of
POSIX 1003.2 regular expressions, with additional support for
replacing matching substrings etc., via structure {\tt Regex}; see the
appropriate section in \cite{MoscowML:2000:MoscowMLLibrary}.

Using \texttt{Regex} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): The GNU regex library (which is
included with Moscow ML) and the interface defined in {\tt
  mosml/src/dynlibs/mregex} must be compiled and installed.  For
instructions, see the {\tt README} file there.


\subsection{Using the PostgreSQL relational database server}
\label{sec-using-mpq}

Moscow ML provides an interface to the PostgreSQL relational database
server, via structure {\tt Postgres}; see the appropriate section in
\cite{MoscowML:2000:MoscowMLLibrary}.

Using \texttt{Postgres} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): the PostgreSQL database server
(not included) must be installed, and the interface to PostgreSQL
defined in {\tt mosml/src/dynlibs/mpq} must be compiled and installed.
For instructions, see the {\tt README} file there.


\subsection{Using the MySQL relational database server}
\label{sec-using-mmysql}

Moscow ML provides an interface\footnote{Thanks to Thomas S.
  Iversen.} to the MySQL relational database server, via structure
{\tt Mysql}; see the appropriate section in
\cite{MoscowML:2000:MoscowMLLibrary}.

Using \texttt{Mysql} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): the MySQL database server (not
included) must be installed, and the interface to Mysql defined in
{\tt mosml/src/dynlibs/mmysql} must be compiled and installed.  For
instructions, see the {\tt README} file there.


\subsection{Using the PNG image library}
\label{sec-using-mgd}

Moscow ML provides an interface to Thomas Boutell's gd graphics
package for creating PNG images, via structure {\tt Gdimage}; see the
appropriate section in \cite{MoscowML:2000:MoscowMLLibrary}.

Using \texttt{Gdimage} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): the gd image package (not
included) must be installed, and the interface defined in {\tt
  mosml/src/dynlibs/mgd} must be compiled and installed.  For
instructions, see the {\tt README} file there.


\subsection{Using the Socket interface}
\label{sec-using-msocket}

Moscow ML provides an interface\footnote{Thanks to Ken Larsen; initial
  development financed by the PROSPER project.} to Internet and file
sockets, via structure {\tt Socket}, which adheres fairly closely to
the SML Basis Library structure of the same name; see the
appropriate section in \cite{MoscowML:2000:MoscowMLLibrary}.

Using structure {\tt Socket} requires {\tt Dynlib} (see
Section~\ref{sec-dynamic-linking} above): the sockets interface defined in\\
{\tt mosml/src/dynlibs/msocket} must be compiled and installed.  For
instructions, see the {\tt README} file there.

\newpage
\section{Quotations and antiquotations}
\label{sec-quotations}

Moscow ML implements {\em quotations\/}, a non-standard language
feature useful for embedding object language phrases in ML programs.
Quotations are disabled by default.  This feature originates in the
Standard ML of New Jersey implementation.  To enable quotations in the
interactive system ({\tt mosml}), execute {\tt quotation := true}.
This allows quotations to appear in declarations entered at top-level
and in files compiled by the primitive {\tt compile}.  To enable
quotations in files compiled with the batch compiler {\tt mosmlc},
invoke it with option {\tt -q} as in {\tt mosmlc -q}.

A quotation is a particular kind of expression and consists of a
non-empty sequence of (possibly empty) {\em fragments\/} surrounded by
backquotes:

\begin{quot} 
\begin{tabular}{@{}lcll}
{\it exp} & ::= & \makebox[5cm][l]{{\tt `}{\it frags\/}{\tt `}}  & quotation\\[2ex]

{\it frags} & ::= & {\it charseq\/} & character sequence \\
& & {\it charseq\/} {\tt \verb#^#}{\it id} {\it frags\/}
                                        & antiquotation variable\\
& & {\it charseq\/} {\tt \verb#^#(}{\it exp}{\tt )} {\it frags\/} 
                                        & antiquotation expression\\
\end{tabular}
\end{quot}

\noindent The {\it charseq\/} is a possibly empty sequence of
printable characters or spaces or tabs or newlines.  A quotation
evaluates to a value of type {\tt ty frag list} where {\tt ty} is the
type of the antiquotation variables and antiquotation expressions, and 
the type {\tt 'a frag} is defined as follows:

\begin{program}
datatype 'a frag = QUOTE of string | ANTIQUOTE of 'a
\end{program}

\noindent A {\it charseq\/} fragment evaluates to {\tt QUOTE "{\it
    charseq\/}"}.  An antiquotation fragment {\tt \verb#^#{\it id\/}}
or {\tt \verb#^#(}{\it exp\/}{\tt )} evaluates to {\tt ANTIQUOTE {\it
    value\/}} where {\it value\/} is the value of the variable {\it
  id\/} resp.\ the expression {\it exp\/}.  All antiquotations in a
quotation must have the same type {\tt ty}.

An antiquotation fragment is always surrounded by (possibly empty)
quotation fragments; and no two quotation fragments can be adjacent.
The entire quotation is parsed before any antiquotation inside it is
evaluated.  Hence changing the value of {\tt Meta.quotation} in an
antiquotation inside a quotation has no effect on the parsing of the
containing quotation.

For an example, say we have written an ML program to analyse C program
phrases, and that we want to enter the C declaration {\tt char s[6] =
  "abcde"}.  We could simply define it as a string:

\begin{program}
val phrase = "char s[6] = \verb#\"#abcde\verb#\#"";
\end{program}

\noindent but then we need to escape the quotes ({\tt "}) in the C
declaration, which is tiresome.  If instead we use a quotation, these
escapes are not needed:

\begin{program}
val phrase = `char s[6] = "abcde"`;
\end{program}

\noindent It evaluates to {\tt [QUOTE "char s[6] =
  \verb#\"#abcde\verb#\#""] :\ 'a frag list}.  Moreover, suppose we
want to generate such declarations for other strings than just {\tt
  "abcde"}, and that we have an abstract syntax for C phrases:

\begin{program}
datatype cprog =
    IntCst of int
  | StrCst of string
  | ...  
\end{program}

\noindent Then we may replace the string {\tt "abcde"} by an
antiquotation {\tt \verb#^#(StrCst str)}, and the array dimension 6 by
an antiquotation {\tt \verb#^#(IntCst (size str + 1))}, and make the
string {\tt str} a function parameter:

\begin{program}
fun mkphrase str = `char s[^(IntCst (size str + 1))] = ^(StrCst str)`;
\end{program}

\noindent Evaluating {\tt mkphrase "longer"} produces the following
representation of a C phrase:

\begin{program}
[QUOTE "char s[", ANTIQUOTE (IntCst 7), QUOTE "] = ", 
 ANTIQUOTE (StrCst "longer"), QUOTE ""] : cprog frag list
\end{program}


\newpage

\section{A lexer generator: mosmllex}
\label{sec-mosmllex}

This section describes {\tt mosmllex}, a lexer generator which is
closely based on {\tt camllex} from the Caml Light implementation by
Xavier Leroy.  This documentation is based on that of {\tt camllex}
also.  


\subsection{Overview}

Given a set of regular expressions with attached semantic actions,
{\tt mosmllex} produces a lexical analyser in the style of {\tt lex}.
If file {\tt lexer.lex} contains a specification of a lexical
analyser, then executing

\begin{program}
mosmllex lexer.lex  
\end{program}

\noindent produces a file {\tt lexer.sml} containing Moscow ML code
for the lexical analyser.  This file defines one lexing function per
entry point in the lexer definition.  These functions have the same
names as the entry points.  Lexing functions take as argument a lexer
buffer, and return the semantic attribute of the corresponding entry
point.

Lexer buffers are an abstract data type implemented in the library
unit {\tt Lexing}.  The functions\\ {\tt createLexerString} and {\tt
  createLexer} from unit {\tt Lexing} create lexer buffers that read
from a character string, or any reading function, respectively.

When used in conjunction with a parser generated by {\tt mosmlyac}
(see Section~\ref{sec-mosmlyac}), the semantic actions compute a value
belonging to the datatype {\tt token} defined by the generated parsing
unit.

Example uses of {\tt mosmllex} can be found in directories {\tt calc}
and {\tt lexyacc} under {\tt mosml/examples}.


\subsection{Hints on using mosmllex}

A lexer definition must have a rule to recognize the special symbol
{\tt eof}, meaning end-of-file.  In general, a lexer must be able to
handle all characters that can appear in the input.  This is usually
achieved by putting the wildcard case \verb#_# at the very end of the
lexer definition.  If the lexer is to be used with e.g.\ MS Windows,
MS DOS or MacOS files, remember to provide a rule for the
carriage-return symbol \verb#\r#.  Most often \verb#\r# will be
treated the same as \verb#\n#, e.g.\ as whitespace.

Do not use string constants to define many keywords; this may produce
large lexer programs.  It is better to let the lexer scan keywords the
same way as identifiers and then use an auxiliary function to
distinguish between them.  For an example, see the {\tt keyword}
function in {\tt mosml/examples/lexyacc/Lexer.lex}.


\subsection{Syntax of lexer definitions}

The format of a lexer definition is as follows:

\begin{program}
\verb#{# {\rm header} \verb#}#
let {\rm abbrev} = {\rm regexp}
\ldots
let {\rm abbrev} = {\rm regexp}
rule {\rm entrypoint} =
  parse {\rm regexp} \verb#{# {\rm action} \verb#}#
      | \ldots
      | {\rm regexp} \verb#{# {\rm action} \verb#}#
and {\rm entrypoint} =
  parse \ldots
and \ldots
;
\end{program}

\noindent Comments are delimited by {\tt (*} and {\tt *)}, as in
SML\@.  An abbreviation (abbrev) for a regular expression may refer
only to abbreviations that strictly precede it in the list of
abbreviations; in particular, abbreviations cannot be recursive.


\subsubsection{Header section and entry points}

The \emph{header section} is arbitrary Moscow ML text enclosed in curly
braces \verb#{# and \verb#}#.  It can be omitted.  If it is present,
the enclosed text is copied as is at the beginning of the output file
{\tt lexer.sml}.  Typically, the header section contains the {\tt
  open} directives required by the actions, and possibly some
auxiliary functions used in the actions.

The names of the \emph{entry points} must be valid ML identifiers.


\subsubsection{Regular expressions}

The \emph{regular expressions} regexp are in the style of {\tt lex},
but with a more ML-like syntax.

\begin{description}
\item[{\tt `{\rm char}`}]\mbox{ }

  A character constant, with a syntax similar to that of Moscow ML
  character constants; see Section~\ref{sec-character-string-constants}.
  Match the denoted character.

\item[{\tt \_}]\mbox{ }

   Match any character.

\item[{\tt eof}]\mbox{ }

  Match the end of the lexer input.

\item[{\tt "{\rm string}"}]\mbox{ }
  
  A string constant, with a syntax similar to that of Moscow ML string
  constants; see Section~\ref{sec-character-string-constants}.  Match
  the denoted string.

\item[{\tt [ {\rm character-set} ]}]\mbox{ }

  Match any single character belonging to the given character set.
  Valid character sets are: single character constants {\tt `c`};
  ranges of characters {\tt `$c_1$` - `$c_2$`} (all characters between
  $c_1$ and $c_2$, inclusive); and the union of two or more character
  sets, denoted by concatenation.

\item{{\tt [ \verb#^# {\rm character-set} ]}}\mbox{ }

  Match any single character not belonging to the given character set.

\item[{\tt {\rm regexp} *}]\mbox{ }

  Match the concatenation of zero or more strings that match regexp.
  (Repetition).

\item[{\tt {\rm regexp} +}]\mbox{ }

  Match the concatenation of one or more strings that match regexp.
  (Positive repetition).

\item[{\tt {\rm regexp} ?}]\mbox{ }

  Match either the empty string, or a string matching regexp.
  (Option).

\item[{\tt {\rm regexp}$_1$ | {\rm regexp}$_2$}]\mbox{ }

  Match any string that matches either regexp$_1$ or regexp$_2$.
  (Alternative).

\item[{\tt {\rm regexp}$_1$ {\rm regexp}$_2$}]\mbox{ }

  Match the concatenation of two strings, the first matching
  regexp$_1$, the second matching regexp$_2$.  (Concatenation).

\item[{\tt {\rm abbrev} }]\mbox{ }

  Match the same strings as the regexp in the most recent {\tt
    let}-binding of abbrev.

\item[{\tt ( {\rm regexp} )}]\mbox{ }

  Match the same strings as regexp.

\end{description}

\noindent The operators {\tt *} and {\tt +} have highest precedence,
followed by {\tt ?}, then concatenation, then {\tt |} (alternative).

\newpage
\subsubsection{Actions}

An \emph{action} is an arbitrary Moscow ML expression.  An action is
evaluated in a context where the identifier {\tt lexbuf} is bound to
the current lexer buffer.  Some typical uses of {\tt lexbuf} in
conjunction with the operations on lexer buffers (provided by the {\tt
  Lexing} library unit) are listed below.

\begin{description}
\item[{\tt Lexing.getLexeme lexbuf}]\mbox{ }

  Return the matched string.

\item[{\tt Lexing.getLexemeChar lexbuf n}]\mbox{ }
 
  Return the {\tt n}'th character in the matched string.  The first
  character has number 0.

\item[{\tt Lexing.getLexemeStart lexbuf}]\mbox{ }

  Return the absolute position in the input text of the beginning of
  the matched string.  The first character read from the input text
  has position 0.

\item[{\tt Lexing.getLexemeEnd lexbuf}]\mbox{ }

  Return the absolute position in the input text of the end of the
  matched string.  The first character read from the input text has
  position 0.

\item[{\tt entrypoint lexbuf}]\mbox{ }

  Here {\tt entrypoint} is the name of another entry point in the same
  lexer definition.  Recursively call the lexer on the given entry
  point.  Useful for lexing nested comments, for example.
\end{description}


\subsubsection{Character constants and string constants}
\label{sec-character-string-constants}

A \emph{character constant} in the lexer definition is delimited by
\verb#`# (backquote) characters.  The two backquotes enclose either a
space or a printable character {\it c\/}, different from \verb#`# and
\verb#\#, or an escape sequence:

\begin{quot}
\begin{tabular}{@{}|l|l|}\hline
Sequence & Character denoted \\\hline
\verb#`#{\it c\/}\verb#`# & the character {\it c\/}\\
\verb#`\\`#        &  backslash (\verb#\#)\\
\verb#`\``#               & backquote (\verb#`#)\\
\verb#`\n`#       & newline (LF)\\
\verb#`\r`#       & return (CR)\\
\verb#`\t`#       & horizontal tabulation (TAB)\\
\verb#`\b`#       & backspace (BS)\\
\verb#`\^#{\it c\/}\verb#`#      & the ASCII character control-{\it c\/}\\
\verb#`\#{\it ddd\/}\verb#`#     & the character with ASCII code {\it ddd\/} in
decimal\\\hline 
\end{tabular}
\end{quot}

\noindent 
A \emph{string constant} is a (possibly empty) sequence of characters
delimited by {\tt "} (double quote) characters.

\begin{quot}
\begin{tabular}{lcll}
  {\it string-literal\/} & ::= & {\tt "}{\it strcharseq\/}{\tt "}
        & non-empty string\\
  & &                            {\tt ""} & empty string\\[2ex]

{\it strcharseq\/} & ::= & {\it strchar\/} $\langle${\it
  strcharseq\/}$\rangle$ & character sequence
\end{tabular}
\end{quot}

\noindent A string character {\it strchar\/} is a space, or a
printable character {\it c\/} (except {\tt "} and \verb#\#), or an
escape sequence:

\begin{quot}
\begin{tabular}{@{}|l|l|}\hline
Sequence & Character denoted \\\hline
{\it c\/}       & the character {\it c\/}\\
\verb#\\#       & backslash (\verb#\#)\\
\verb#\"#       & double quote (\verb#"#)\\
\verb#\n#       & newline (LF)\\
\verb#\r#       & return (CR)\\
\verb#\t#       & horizontal tabulation (TAB)\\
\verb#\b#       & backspace (BS)\\
\verb#\^#{\it c\/}      & the ASCII character control-{\it c\/}\\
\verb#\#{\it ddd\/}     & the character with ASCII code {\it ddd\/} in
decimal\\\hline 
\end{tabular}
\end{quot}

\newpage

\section{A parser generator: mosmlyac}
\label{sec-mosmlyac}

This section describes {\tt mosmlyac}, a simple parser generator which
is closely based on {\tt camlyacc} from the Caml Light implementation
by Xavier Leroy; {\tt camlyacc} in turn is based on Bob Corbett's
public domain Berkeley {\tt yacc}.  This documentation is based on
that in the Caml Light reference manual.


\subsection{Overview}

Given a context-free grammar specification with attached semantic
actions, {\tt mosmlyac} produces a parser, in the style of {\tt yacc}.
If file {\tt grammar.grm} contains a grammar specification, then
executing

\begin{program}
mosmlyac grammar.grm  
\end{program}

\noindent produces a file {\tt grammar.sml} containing a Moscow ML
unit with code for a parser and a file {\tt grammar.sig} containing
its interface.

The generated unit defines a parsing function {\tt S} for each start
symbol {\tt S} declared in the grammar.  Each parsing function takes
as arguments a lexical analyser (a function from lexer buffers to
tokens) and a lexer buffer, and returns the semantic attribute of the
corresponding entry point.  Lexical analyser functions are usually
generated from a lexer specification by the {\tt mosmllex} program.
Lexer buffers are an abstract data type implemented in the library
unit {\tt Lexing}.  Tokens are values from the datatype {\tt token},
defined in the signature file {\tt grammar.sig} produced by running
{\tt mosmlyac}.

Example uses of {\tt mosmlyac} can be found in directories {\tt calc}
and {\tt lexyacc} under {\tt mosml/examples}.


\subsection{The format of grammar definitions}

\begin{program}
\%\verb#{#
  {\rm header}
\%\verb#}#
  {\rm declarations}
\%\%
  {\rm rules}
\%\%
  {\rm trailer}
\end{program}

\noindent Comments in the declarations and rules sections are enclosed
in C comment delimiters {\tt /*} and {\tt */}, whereas comments in the
header and trailer sections are enclosed in ML comment delimiters {\tt
  (*} and {\tt *)}.


\subsubsection{Header and trailer}

Any SML code in the header is copied to the beginning of file {\tt
  grammar.sml}, after the {\tt token} datatype declaration; it usually
contains {\tt open} declarations required by the semantic actions of
the rules.  Any SML code in the trailer is copied to the end of file
{\tt grammar.sml}.  Both sections are optional.


\subsubsection{Declarations}

Declarations are given one per line.  They all start with a \verb#%# sign.

\begin{description}
\item[{\tt \%token {\rm symbol \ldots\ symbol}}]\mbox{ }

  Declare the given symbols as tokens (terminal symbols).  These
  symbols become constructors (without arguments) in the {\tt token}
  datatype.

\item[{\tt \%token < {\rm type} >  {\rm symbol \ldots\ symbol}}]\mbox{
    }

  Declare the given symbols as tokens with an attached attribute of
  the given type.  These symbols become constructors (with arguments
  of the given type) in the {\tt token} datatype.  The type part is an
  arbitrary Moscow ML type expression, but all type constructor names
  must be fully qualified (e.g.\ {\tt Unitname.typename}) for all
  types except standard built-in types, even if the proper {\tt open}
  declarations (e.g.\ {\tt open Unitname}) were given in the header
  section.  

\item[{\tt \%start {\rm symbol}}]\mbox{ }

  Declare the given symbol as entry point for the grammar.  For each
  entry point, a parsing function with the same name is defined in the
  output file {\tt grammar.sml}.  Non-terminals that are not declared
  as entry points have no such parsing function.  

\item[{\tt \%type < {\rm type} >  {\rm symbol \ldots\ symbol}}]\mbox{
    }

  Specify the type of the semantic attributes for the given symbols.
  Every non-terminal symbol, including the start symbols, must have
  the type of its semantic attribute declared this way.  This ensures
  that the generated parser is type-safe.  The type part may be an
  arbitrary Moscow ML type expression, but all type constructor names
  must be fully qualified (e.g.\ {\tt Unitname.typename}) for all
  types except standard built-in types, even if the proper {\tt open}
  declaration (e.g.\ {\tt open Unitname}) were given in the header
  section.  

\item[{\tt \%left {\rm symbol \ldots\ symbol}}]\mbox{ }
\item[{\tt \%right {\rm symbol \ldots\ symbol}}]\mbox{ }
\item[{\tt \%nonassoc {\rm symbol \ldots\ symbol}}]\mbox{ }

  Declare the precedence and associativity of the given symbols.  All
  symbols on the same line are given the same precedence.  They have
  higher precedence than symbols declared in previous {\tt \%left},
  {\tt \%right} or {\tt \%nonassoc} lines.  They have lower precedence
  than symbols declared in subsequent {\tt \%left}, {\tt \%right} or
  {\tt \%nonassoc} lines.  The symbols are declared to associate to
  the left ({\tt \%left}), to the right ({\tt \%right}), or to be
  non-associative ({\tt \%nonassoc}).  The symbols are usually tokens,
  but can also be dummy nonterminals, for use with the {\tt \%prec}
  directive inside the rules.
\end{description}


\subsubsection{The format of grammar rules}

\begin{program}
{\rm nonterminal} :
    {\rm symbol \ldots\ symbol} \verb#{# {\rm semantic-action} \verb#}#
  | \ldots
  | {\rm symbol \ldots\ symbol} \verb#{# {\rm semantic-action} \verb#}#
;
\end{program}

\noindent Each right-hand side consists of a (possibly empty) sequence
of symbols, followed by a semantic action.  

The directive `{\tt \%prec} symbol' may occur among the symbols in a
rule right-hand side, to specify that the rule has the same precedence
and associativity as the given symbol.

Semantic actions are arbitrary Moscow ML expressions, which are
evaluated to produce the semantic attribute attached to the defined
nonterminal.  The semantic actions can access the semantic attributes
of the symbols in the right-hand side of the rule with the \verb#$#
notation: \verb#$1# is the attribute of the first (leftmost) symbol,
\verb#$2# is the attribute of the second symbol, etc.  An empty
semantic action evaluates to {\tt () :\ unit}.

Actions occurring in the middle of rules are not supported.  Error
recovery is not implemented.


\subsection{Command-line options of mosmlyac}
\label{sec-mosmlyac-options}

\begin{description}
\item[{\tt -v}]\mbox{ }

  Generate a description of the parsing tables and a report on
  conflicts resulting from ambiguities in the grammar.  The
  description is put in file {\tt grammar.output}.

\item[{\tt -b{\rm prefix}}]\mbox{ }

  Name the output files {\tt prefix.sml}, {\tt prefix.sig}, {\tt
    prefix.output}, instead of using the default naming convention.
\end{description}


\subsection{Reporting lexer and parser errors}

Lexical errors (e.g.\ illegal symbols) and syntax errors can be
reported in an intelligible way by using the {\tt Location} module
from the Moscow ML library.  It provides functions to print out
fragments of a source text, using location information from the lexer
and parser.  Try {\tt help "Location"} for more information.  See file
{\tt mosml/examples/lexyacc/Main.sml} for an example.

\newpage

\section{Copyright and credits}
\label{sec-copyright}

\begin{description}
\item[Copyright notice] Moscow ML - a lightweight implementation of
  Standard ML\@.  Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999,
  2000.  Sergei Romanenko, Moscow, Russia and Peter Sestoft,
  Copenhagen, Denmark.
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.  This program is distributed in
  the hope that it will be useful, but WITHOUT ANY WARRANTY; without
  even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  PARTICULAR PURPOSE.  See the GNU General Public License (in file
  mosml/copyrght/gpl2) for more details.    

Note that a number of source files are derived from the Caml Light
distribution, copyright (C) 1993 INRIA, Rocquencourt, France.
Thus charging money for redistributing Moscow ML may require prior
permission from INRIA; see the INRIA copyright notice in file
copyrght/copyrght.cl.\\[2ex]


\item[Main Moscow ML contributors]\mbox{ }
  \begin{itemize}
  \item Doug Currie (e@flavors.com), Flavors Technology, USA.
  \item Sergei Romanenko (roman@keldysh.ru), Keldysh Institute of
    Applied Mathematics, Russian Academy of Sciences, Russia.
  \item Claudio V.\ Russo (Claudio.Russo@cl.cam.ac.uk), University of
    Cambridge.  Thanks to Don Sannella at LFCS, Division of
    Informatics, University of Edinburgh for funding under EPSRC grant
    GR/K63795.
  \item Peter Sestoft (sestoft@dina.kvl.dk), Department of Mathematics
    and Physics, Royal Veterinary and Agricultural University, Denmark
    and The IT University of Copenhagen, Denmark.  Part of the work
    was done while at the Department of Computer Science at the
    Technical University of Denmark, and while visiting AT\&T 
    Bell Laboratories, Murray Hill, New Jersey, USA.
  \end{itemize}

\item[Moscow ML owes much to]\mbox{ }
\begin{itemize}
\item The Caml Light implementation by Xavier Leroy and Damien Doligez
  (INRIA, Rocquencourt, France).  It was instrumental in creating
  Moscow ML, which uses its runtime system, essentially the same
  bytecode generator, and many other aspects of its design
  \cite{Leroy:1990:TheZinc,Leroy:1993:TheCaml}.
\item The Definition of Standard ML, unbeatably precise and concise.
\item The ML Kit by Lars Birkedal, Martin Elsman, Niels Hallenberg,
  Nick Rothwell, Mads Tofte and David Turner (University of
  Copenhagen, Denmark, and University of Edinburgh, Scotland), which
  helped solving problems of parsing, infix resolution, and type
  inference \cite{Birkedal:1993:TheML}.
\item Inspiration from the SML/NJ compiler developed at Princeton
  University and AT\&T/Lucent Bell Laboratories, New Jersey,
  USA.
\item Feedback, contributions, and useful suggestions, in particular
  from Ken Friis Larsen, but also from Jonas Barklund, Mike Gordon,
  Michael Norrish, Konrad Slind, Jakob Lichtenberg, Hans Molin, and 
  numerous other people.
\end{itemize}
\end{description}


\section{How to get Moscow ML}
\label{sec-how-to-get}

\begin{itemize}
\item The Moscow ML home page is
        \url{http://www.dina.kvl.dk/~sestoft/mosml.html}
\item The Linux executables are in
        \url{ftp://ftp.dina.kvl.dk/pub/mosml/linux-mos20bin.tar.gz}
\item The MS Windows executables are in 
        \url{ftp://ftp.dina.kvl.dk/pub/mosml/win32-mos20bin.zip}
\item The Macintosh/MacOS (68k and PPC) executables are in\\
        \url{ftp://ftp.dina.kvl.dk/pub/mosml/mac-mos20bin.sea.hqx}
\item The Unix and MS Windows source files are in 
        \url{ftp://ftp.dina.kvl.dk/pub/mosml/mos20src.tar.gz}
\item The MacOS modified source files (relative to Unix) are in\\
        \url{ftp://ftp.dina.kvl.dk/pub/mosml/mac-mos20src.sea.hqx}
\end{itemize}

%You will need gcc, make, and perl to recompile Moscow ML for Unix.
%You will need djgpp, perl, and Borland C++ version 2.0 (or later) to
%recompile Moscow MLs for DOS\@.  Djgpp and go32 are found at
%ftp://oak.oakland.edu/pub/simtelnet/gnu/djgpp/ or
%ftp://ftp.sunet.se/pub/pc/mirror/simtelnet/gnu/djgpp/ or any other
%SimTel mirror site.  You will need MetroWERKS to recompile Moscow ML
%for the Macintosh.


\newpage
\section{Books and other materials on Standard ML}
\label{sec-books}

%\subsubsection*{The Definition and Commentary}

The 1997 Definition \cite{Milner:1997:TheDefinition} is the
authoritative description of Standard ML, revised from the 1990
Definition \cite{Milner:1990:TheDefinition}\@.  The Commentary
\cite{Milner:1991:Commentary} explains many finer points in the 1990
Definition.

% \begin{itemize}
% \item Robin Milner, Mads Tofte and Robert Harper, {\em The Definition of
%   Standard ML\/}, MIT Press 1990, ISBN 0-262-63132-6.  
% \item Robin Milner, Mads Tofte, Robert Harper, and David B. MacQueen,
%   {\em The Definition of Standard ML (Revised)\/}, MIT Press 1997,
%   ISBN 0-262-63181-4.
% \item Robin Milner and Mads Tofte, {\em Commentary on Standard ML\/},
%   MIT Press 1991, ISBN 0-262-63137-7.
% \end{itemize}

\subsubsection*{Textbooks available from publishers}

\begin{itemize}
\item Richard Bosworth, {\em A Practical Course in Functional
    Programming Using Standard ML}, McGraw-Hill 1995, ISBN
  0-07-707625-7.
\item Michael R. Hansen and Hans Rischel, \emph{Introduction to
    Programming using SML}, Addison-Wesley 1999, ISBN 0-201-39820-6.
\item Greg Michaelson, {\em Elementary Standard ML\/}, UCL Press 1995,
  ISBN 1-85728-398-8.
\item Colin Myers, Chris Clack, and Ellen Poon, {\em Programming with
    Standard ML\/}, Prentice Hall 1993, ISBN 0-13-722075-8.
\item Lawrence C. Paulson, {\em ML for the Working Programmer\/},
  Second edition.  Cambridge University Press 1996, ISBN
  0-521-56543-X.  
\item Chris Reade, {\em Elements of Functional Programming\/},
  Addison-Wesley 1989, ISBN 0-201-12915-9.
\item Ryan Stansifer, {\em ML Primer\/}, Prentice Hall 1992, ISBN
  0-13-561721-9.
\item Jeffrey D. Ullman, {\em Elements of ML Programming\/}, Prentice
  Hall 1994, ISBN 0-13-184854-2.
\item {\AA}ke Wikstr{\"o}m, {\em Functional Programming Using Standard
    ML\/}, Prentice Hall 1987, ISBN 0-13-331661-0.
\end{itemize}

\subsubsection*{Texts available on the net}

\begin{itemize}
\item Andrew Cumming, \emph{A Gentle Introduction to ML}, Napier
  University.  At\\
  \url{http://www.dcs.napier.ac.uk/course-notes/sml/manual.html}

\item Emden Gansner and John Reppy (editors): Standard ML Basis
  Library, hypertext version:\\ 
  \url{http://www.cs.bell-labs.com/~jhr/sml/basis/index.html} \\
and  \url{http://www.dina.kvl.dk/~sestoft/sml/sml-std-basis.html}
  (mirror site)
  
\item Stephen Gilmore, \emph{Programming in Standard ML'97}, report
  ECS-LFCS-97-364, University of Edinburgh.  At
  \url{http://www.dcs.ed.ac.uk/lfcsreps/EXPORT/97/ECS-LFCS-97-364}
  
\item Robert Harper, {\em Introduction to Standard ML\/}, report
  ECS-LFCS-86-14, University of Edinburgh, November 1986 (revised
  1989).  At
  \url{ftp://ftp.cs.cmu.edu/afs/cs/project/fox/mosaic/intro-notes.ps}

\item Robert Harper, \emph{Programming in Standard ML}, Carnegie
        Mellon University.  At
        \url{http://www.cs.cmu.edu/~rwh/introsml}

\item Mads Tofte, {\em Tutorial on Standard ML\/}, Technical Report
  91/18, DIKU, University of Copenhagen, December 1991.  At 
  \url{ftp://ftp.diku.dk/pub/diku/users/tofte/FPCA-Tutorial}
\end{itemize}

\bibliographystyle{plain}
\bibliography{books,mosml}

\end{document}


