\documentclass[11pt]{article}
\usepackage{code}

% \topmargin=0in
% \headheight=0in
% \headsep=0in
% \textheight=9in
% \oddsidemargin=0in
% \evensidemargin=0in
% \textwidth=6.5in

\parindent=0in
\parskip=10pt

%%% Binding colon stuff
\mathchardef\col="003A  % \col for binding colon (mathcode ordinary: less space)
\mathchardef\semi="603B % \semi for (regular) semicolon
\mathchardef\bang="6021 % \bang for exclamation point
%% this breaks \' for some reason
%\mathchardef\accent="0060 % \accent for accent
%% use \semicolonforbindingcolon to redefine ; to stand for binding colon
\newcommand{\semicolonforbindingcolon}{\mathcode`;="003A}
\newcommand{\semicolonforsemicolon}{\mathcode`;="603B}
%% use \bangforbindingcolon to redefine ! to stand for binding colon
\newcommand{\bangforbindingcolon}{\mathcode`!="003A}
\newcommand{\bangforbang}{\mathcode`!="6021}
%% use \accentforbindingcolon to redefine ` to stand for binding colon
\newcommand{\accentforbindingcolon}{\mathcode``="003A}
\newcommand{\accentforaccent}{\mathcode``="0060}

%%% Angle bracket stuff
\mathchardef\lt="313C  % \lt for <
\mathchardef\gt="313E  % \gt for >
%% use \ltgtforanglebrackets to redefine <,> to stand for \langle, \rangle
\newcommand{\ltgtforanglebrackets}{\mathcode`<="4268 \mathcode`>="5269}
\newcommand{\ltgtforltgt}{\mathcode`<="313C\mathcode`>="313E}

%%% Cascaded items for math mode
%% start with \begin{cascade}
%% new line at previous indentation with \cascline
%% new line with greater indentation with \cascitem
%% new line with N increments less indentation with \cascback{N}
%% end with \end{cascade}
%% default indentation is 2em, adjust with \cascadeindent
\newdimen\cascadeindent
\cascadeindent=2em
\newdimen\cascdimen
\newcommand{\cascitem}{\\\global\advance\cascdimen by\cascadeindent\hspace{\cascdimen}}
\newcommand{\cascline}{\\\hspace{\cascdimen}}
\newcommand{\cascback}[1]{\\\global\advance\cascdimen by-#1.0\cascadeindent\hspace{\cascdimen}}
\newenvironment{cascade}{\begin{array}[t]{@{}l@{}}\global\cascdimen=0em}{\end{array}}

%%% Stacking stuff
%% \shiftright{dimen}{A}{B} stacks A on B, with B shifted right by dimen
\newenvironment{stack}{\begin{array}[t]{@{}l@{}}}{\end{array}}
\newenvironment{stackc}{\begin{array}[t]{@{}c@{}}}{\end{array}}
\newenvironment{stackr}{\begin{array}[t]{@{}r@{}}}{\end{array}}
\newcommand{\shiftright}[3]{\begin{array}[t]{@{}r@{}}{#2}\\{#3}\hspace{-#1}\mbox{}\end{array}}
\newcommand{\bigleft}{\left(\begin{array}{@{}l@{}}}
\newcommand{\bigright}{\end{array}\right)}

%%% Proof mode
\newdimen\proofadjustabove
\newdimen\proofadjustbelow
\proofadjustabove=-10pt
\proofadjustbelow=-15pt
\newenvironment{proof}{\setcounter{proofcase}{0}\vspace{\proofadjustabove}\rm{\bf Proof}\vspace{\proofadjustbelow}\begin{list}{}{\leftmargin=1.5em\labelsep=1.5em\labelwidth=0pt}\item}{\end{list}}
\newenvironment{proofsketch}{\setcounter{proofcase}{0}\vspace{\proofadjustabove}\rm{\bf Proof Sketch}\vspace{\proofadjustbelow}\begin{list}{}{\leftmargin=1.5em\labelsep=1.5em\labelwidth=0pt}\item}{\end{list}}
\newcounter{proofcase}
\newcommand{\proofcase}{{\addtocounter{proofcase}{1}\setcounter{proofsubcase}{0}\bf Case \arabic{proofcase}:\quad}}
\newcounter{proofsubcase}
\newcommand{\proofsubcase}{{\addtocounter{proofsubcase}{1}\bf Subcase \arabic{proofcase}.\arabic{proofsubcase}:\quad}}

%%% Theorem-like environments
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}

\newtheorem{definition}[theorem]{Definition}
\newenvironment{defn}{\begin{definition}\rm}{\end{definition}}

%%% Misc definitions
\chardef\at="40
\chardef\tilde="7E
\newcommand{\canbreak}{\discretionary{}{}{}}

%%% Math definitions
\newcommand{\alt}{\mathrel{|}}
\newcommand{\arrow}{\mathbin{\rightarrow}}
\newcommand{\defeq}{\stackrel{\rm def}{=}}
\newcommand{\eqv}{\simeq}
\newcommand{\evalto}{\mapsto}
\newcommand{\hold}{\mathord{\relax}}
\newcommand{\is}{\equiv}
\newcommand{\lolli}{\multimap} % need amssymbols
\newcommand{\lsem}{{[\![}}
\newcommand{\nturn}{\nvdash} % need amssymbols
\newcommand{\rsem}{{]\!]}}
\newcommand{\tensor}{\otimes}
\newcommand{\turn}{\vdash}

%%% Misc definitions
\newcommand{\figfoot}{\vspace{1ex}\hrule}
\newcommand{\fighead}{\hrule\vspace{1.5ex}}
\newcommand{\zilch}{\mbox{}}


\title{Assignment 8 \\ Implementing Concurrent ML}
\author{Karl Crary \\ 15-312: Foundations of Programming Languages}
\date{Out: Sunday, April 17, 2005 \\ Due: Friday, April 29, 2005 (11:59 pm)}

\begin{document}

\maketitle{}

\section{Introduction}

In this project, you will implement a fragment of Concurrent ML\@,
including threads, channels, and first-class synchronization.  You are
provided code implementing continuations, timer interrupts, and
thread-safe printing.  You are also provided with signatures for the code
that you write.
Figure~\ref{fig:files} lists the files you are provided and their
contents.

\begin{figure}[t]
\fighead
\begin{tabular}{lll}
File & Sig./Struct.\ & Description \\\hline
{\tt cont.sig} & {\tt CONT} & Interface for continuations \\
{\tt timer.sig} & {\tt TIMER} & Interface for timer interrupts \\
{\tt print.sig} & {\tt PRINT} & Interface for thread-safe print \\
{\tt queue.sig} & {\tt QUEUE} & Interface for ephemeral queues \\
{\tt thread.sig} & {\tt THREAD} & Interface for threads \\
{\tt condition.sig} & {\tt CONDITION} & Interface for condition signals \\
{\tt event.sig} & {\tt EVENT} & Interface for events \\
{\tt channel.sig} & {\tt CHANNEL} & Interface for channels \\
{\tt cml.sig} & {\tt CML} & Interface for CML as a whole \\
\\
{\tt cont.sml} & {\tt Cont} & Implementation of continuations \\
{\tt timer.sml} & {\tt Timer} & Implementation of timer interrupts \\
{\tt print.sml} & {\tt Print} & Implementation of thread-safe print \\
{\tt cml.sml} & {\tt CML} & Glue combining your implementation \\
\\
{\tt queue.sml} & {\tt Queue} & Template for queues \\
{\tt thread.sml} & {\tt Thread} & Template for threads \\
{\tt condition.sml} & {\tt Condition} & Template for condition signals \\
{\tt event.sml} & {\tt Event} & Template for events \\
{\tt channel.sml} & {\tt Channel} & Template for channels \\
{\tt demo.sml} & {\tt Demo} & Template for demonstration code \\
\\
{\tt sources.cm} && SML/NJ configuration management file
\end{tabular}
\caption{Provided files}
\label{fig:files}
\figfoot
\end{figure}

You may work together in teams of at most two.  The deliverables for
this project include (1) the code, (2) a brief report, and (3) a demo
for the instructor and/or TA.

To assist you in the development of this project, it is broken into
several pieces and each piece is given a signature.  Each piece is
designed to provide the necessary tools for later pieces.  Do not
change the signatures!  If you have any questions about the
interfaces, consult the instructor or TAs.

This document will walk you through the provided code, and the
interfaces you are to implement.  A full listing of all signatures
appears at the end of this document.

Be sure to read the {\em entire\/} assignment carefully before you
begin!

\section{Provided Code}

You are provided four pieces of code:

\begin{itemize}
\item
\textcd{Cont : CONT} provides first-class continuations.

\item
\textcd{Timer : TIMER} provides operations for managing timer
interrupts and atomic regions.  These are discussed in the next
two sections.

\item
\textcd{Print : PRINT} provides a thread-safe printing function.  Do
not use the ordinary print function while timer interrupts are
active.

\item
\textcd{CML : CML} provides code that glues your implementation
pieces together into a CML implementation.  You can use this to
implement concurrent applications, and we will use it to test your
implementation.

For your convenience, \textcd{CML} also provides a function
\textcd{activate} that you can use to start up concurrent programs.
Its two arguments are the size of the timeslice and a function to
call.
\end{itemize}

{\bf Important Note:} You must use Standard ML of New Jersey for
\textcd{Cont}, \textcd{Timer}, or \textcd{Print} to work.  It is not
possible to use other SML compilers with this assignment.


\section{Timer Interrupts}

To assist you with the implementation of preemptive scheduling, we
have provided a package for managing timer interrupts.  There are two
main functions, \textcd{startTimer} and \textcd{stopTimer}, which
start and stop the timer.

The \textcd{startTimer} function takes three arguments that you
provide, packaged in a record:

\begin{itemize}
\item
\textcd{timeslice} gives the size of the timeslice, in milliseconds.

\item
\textcd{tickHandler} gives the system a function for handing timer
interrupts, which are raised once per timeslice.

\item
\textcd{interruptHandler} gives the system a function for handling
interruption interrupts (that is, for handling control-C).  This is
useful because the ordinary SML/NJ handler for control-C does not work
very gracefully while timer interrupts are active so you will wish to
install a new control-C handler.
\end{itemize}

Each interrupt handler you provide has the type \textcd{unit cont ->
unit cont}.  Each time the timeslice expires, the interrupt handler is
called with a continuation representing the current thread of
control.  The interrupt handler processes that continuation then
returns another continuation representing the new thread of control.
SML/NJ then continues the program using the new continuation.

To make this more concrete, suppose SML is about to execute the
expression \textcd{..expr..} when an interrupt occurs.  In the place
of \textcd{..expr..} we could execute the equivalent expression:
\begin{code}
( () ; ..expr.. )\end{code}
Now suppose the interrupt handler is
\textcd{handlerfn : unit cont -> unit cont}.  Then instead of the
above expression, SML executes:
\begin{code}
( callcc (fn k => throw (handlerfn k) ()) ; ..expr.. )\end{code}

If \textcd{handlerfn} is the identity function, then the
\textcd{throw} expression simply throws \textcd{()} to the
continuation \textcd{k}, resulting in the entire \textcd{callcc}
expression simply returning \textcd{()}.  Thus, an interrupt has no
effect if its handler is the identity function.

However, a handler can also switch to a new thread by storing the old
continuation and returning a new one.  Thus, we can implement
preemptive threads by putting code very similar to the code for
\textcd{Thread.yield} (which you will implement) into the timer
interrupt handler.


\section{Atomic Sections}

A standard problem with preemptive multitasking is that many (or
perhaps most) data structures must be accessed exclusively by at most one
thread at a time.  For example, if multiple threads attempt to access
a queue at once, it is likely that they will simultaneously attempt to
perform inconsistent writes to the queue's state, thereby corrupting
the queue.

To prevent this problem, one ordinarily implements mutual exclusion
primitives such as semaphores, mutexes, or monitors.  These ensure
that only one thread is dealing with the data structure at one time.

However, in a single-processor concurrent setting, there is a simpler
solution.  A thread that requires exclusive access to a data structure
may enter an {\em atomic section,} during which is it impossible for
that thread to be preempted.  When it is done accessing the data
structure, it leaves the atomic section, allowing preemption once
more.

\begin{quote}
{\bf Note:} atomic sections are {\em not\/} a good solution to the
general problem of mutual exclusions.  There are (at least!) two
reasons why not:  First, atomic sections are not usually possible to
begin with on a multi-processor platform.  Second, even on a single
processor, if very much time is spent in atomic sections, the
concurrent performance of the system is seriously degraded.

Therefore, atomic sections are a reasonable means to ensure mutual
exclusion to the data structures that implement the concurrency
system, since all concurrency primitives should execute quickly and
therefore little time will be spent in atomic sections.  However,
atomic sections should {\em never\/} be used in user code.
Consequently, no atomic section utilities are provided in the
\textcd{CML} signature.
\end{quote}

Support for atomic sections is provided by two functions in
\textcd{TIMER}: \textcd{beginAtomic} enters an atomic section, and
\textcd{endAtomic} leaves an atomic section.  {\em Interrupt handlers
are automatically executed atomically; calls to
\textcd{beginAtomic} and \textcd{endAtomic} are not necessary and
should not be used.}

{\bf Note:} calls to \textcd{beginAtomic} and \textcd{endAtomic} must
be matched properly.  For example, the following code fragments may be
correct:
\begin{code}
beginAtomic ();
..expr 1..;
endAtomic ()\end{code}
\begin{code}
beginAtomic ();
if ..expr 2.. then
   (
   ..expr 3..;
   endAtomic ()
   )
else
   (
   endAtomic ();
   ..expr 4..;
   )\end{code}
These are correct provided the only one of the elided expressions that
can raise an exception is \textcd{..expr 4..}  If, for example,
\textcd{..expr 1..} can raise an exception, one must instead write
something like:
\begin{code}
beginAtomic ();
(..expr 1.. handle ex => (endAtomic (); raise ex));
endAtomic ()
\end{code}

To assist in diagnosing unmatched atomic section entries and
departures, the atomic section functions will raise the exception
\textcd{Atomic} if one attempts either to enter an atomic section while
already in one, or to leave an atomic section while not in one, or to
enter or leave an atomic section while in an interrupt handler.
(However, you may find this to be of limited helpfulness if your
implementation of threads allows threads that raise uncaught
exceptions to disappear silently.)

\subsection{Atomicity Assumptions}

Many of your functions will need to make assumptions regarding whether
or not they are in an atomic section when called.  For example, many
functions will need to enter an atomic section to ensure exclusive
access to their data structures, and so they must assume that they are
not called in an atomic section.

Similarly, in order to write correct code, we must know whether we are
in an atomic section when a function returns.  For example, some
functions that begin in an atomic section will end still in an atomic
section, whereas others will terminate the atomic section before
returning.  Finally, many functions do not care about atomicity.  They
can be called in or out of an atomic section and return the same way.

\subsection{Documenting Atomicity Assumptions}

Making invalid assumptions about atomicity is a very likely source of
errors, so you must be very careful to document all our atomicity
assumptions.  In each of the signatures you are provided, all of the
functions are grouped under comments that indicate their atomicity
assumptions, such as ``\textcd{begins atomic, ends non-atomic}''.
Functions (such as those in \textcd{QUEUE}) that make no assumptions
about atomicity are not labelled.  (A few functions that must be
called with preemption inactive, or that disable preemption are simply
marked ``\textcd{special}''.)

For any code that we provide, you should assume that the stated
atomicity assumptions are satisfied.  For any code that you are to
provide, you must ensure that the stated assumptions are accurate.
For example, in a function with no stated assumption (which therefore
makes no assumption), one should not call \textcd{beginAtomic} or
\textcd{endAtomic}.  As another example, in a function that begins and
ends non-atomic, one may call \textcd{beginAtomic}, provided one
ensures a matching \textcd{endAtomic} is called.  (Note that a
function that begins and ends atomic is not {\em required\/} to enter an
atomic section, but it may.)

{\bf Note:} Since atomic sections are not available to user code, the
\textcd{CML} signature does not list any atomicity assumptions.
Implicitly, all \textcd{CML} functions are ``\textcd{begins and
ends non-atomic}'' (except for \textcd{activate} which would be ``\textcd{special}'').

\section{Your Implementation}

Your implementation is broken into five pieces: queues, threads,
condition signals, pure events, and channels.  You will also provide a
small demonstration program.

\subsection{Queues}

First you should implement ephemeral FIFO queues, with the signature
\textcd{QUEUE}.  The \textcd{reset} operation empties a queue.  The
\textcd{front} operation returns the front element of the queue
without deleting it; \textcd{remove} returns it and deletes it.  The
other functions are self-explanatory.

\subsection{Threads}

Next you should implement a thread package.  Providing the following
functions:

\begin{itemize}
\item
\textcd{spawn}: spawns a new thread and makes it ready.

\item
\textcd{yield}: causes the current thread to yield to another ready
thread.

\item
\textcd{exit}: causes the current thread to exit immediately.  If no
ready threads remain, it throws to the top-level continuation (see
below).

\item
\textcd{shutdown}: shuts down the thread system and throws to the
top-level continuation (see below).

\item
\textcd{spawnAtomic}: like \textcd{spawn}, but for use within an
atomic section.

\item
\textcd{beginPreemption}: initializes the thread system and activates
timer interrupts.  The first argument is the size of the timeslice in
milliseconds.  The second argument is a {\em top-level continuation\/}
to throw to in the event that either all threads die or there is an
interruption interrupt ({\em i.e.,} control-C).  You may assume that
the top-level continuation calls \textcd{endPreemption}.  (The
function \textcd{CML.activate}, which we provide, supplies an
appropriate top-level continuation when it calls
\textcd{beginPreemption}.)

\item
\textcd{endPreemption}: does any necessary final cleanup when shutting
down the thread system, such as stopping the timer.  The top-level
continuation must call \textcd{endPreemption}.
\end{itemize}

\pagebreak
{\bf Suggestions:}
\begin{itemize}
\item
Your \textcd{Thread} implementation does not need to know anything
about blocked threads.  As far as \textcd{Thread} is concerned,
blocked threads have exited.

\item
Try implementing non-preemptive threads first.  Then adapt your
\textcd{yield} code to an appropriate timer interrupt handler.

\item
When threads that raise uncaught exceptions die silently, it can be
difficult to diagnose bugs.  Rather than allowing them to die
silently, have your \textcd{spawn} function cause threads to print a
message before they die.  The built-in functions \textcd{exnName} or
\textcd{exnMessage} may be helpful.

\end{itemize}

\subsection{Condition Signals}

The key synchronization mechanism you will use internally when
implementing events and channels is {\em condition signals.}  (Note
that condition signals are for internal use only, and are not made
available to user code.)  For those who are familiar with condition
variables, condition signals are like condition variables, except that
only a single thread can ever wait on any particular condition signal.

Condition signals are created by the \textcd{wait} function.  When
\textcd{wait} is called with an argument function \textcd{f},
\textcd{wait} (1) creates a new condition signal, (2) passes the
condition signal to \textcd{f}, which typically places it into various
queues, then, when \textcd{f} has returned, (3) blocks until the
condition is signalled.  Once the condition is signalled,
\textcd{wait}'s return value is a value passed to \textcd{signal} (see
below).

A thread is awakened using the \textcd{signal} function.  If the
thread is still blocked (that is, if the condition has not already
been signalled) then the thread is awakened and \textcd{signal}
returns true.  If the thread has already been awakened, then
\textcd{signal} returns false.  When \textcd{signal} awakens a waiting
thread, \textcd{signal}'s second argument becomes the awakened
thread's return value for \textcd{wait}.  The function \textcd{query}
determines whether a thread is still waiting (returning true if so),
without awakening it.

Finally, the function \textcd{wrapCond} composes a function with a
condition signal.  Thus, if \textcd{wrapCond (c,f)} is signalled with
value \textcd{v}, the waiting thread receives \textcd{f(v)}.  The
argument function is assumed never to raise an exception.

{\bf Important Note:} Be careful to make sure that your \textcd{wait}
function can only return once.  Later calls to \textcd{signal} should
return false, they should {\em not\/} reawaken or respawn a formerly
blocked thread.

{\bf Suggestions:}
\begin{itemize}
\item
You will need to use \textcd{callcc} and \textcd{throw} to implement
condition signals.

\item
You may wish to use the following code (from class) for composing a
function with a continuation:
\begin{bigcode}
fun compose (k : 'a cont, f : 'b -> 'a) : 'b cont =
    callcc
    (fn escape =>
           throw k (f (callcc (fn k' => throw escape k'))))\end{bigcode}
Recall that this code works only when the function \textcd{f} never
raises an exception.

\item
A good way to block a thread is simply to have it exit, and to rely on
the signaller to respawn the thread once it is awakened.  The thread
mechanism should not need to know anything about the condition signal
mechanism.

\item
Be sure to note that all the condition signal functions except
\textcd{wrapCond} are intended to be called within an atomic section;
\textcd{signal} and \textcd{query} return still in the atomic section,
but \textcd{wait} ends it.
\end{itemize}

\subsection{Events}

Using condition signals, you will implement events.  The functions
\textcd{sync}, \textcd{select}, \textcd{wrap}, \textcd{guard},
\textcd{choose}, \textcd{never}, and \textcd{alwaysEvt} are as
described in class.

The \textcd{Event} structure must also provide a back door so that
other structures (such as \textcd{Channel}) can create events.  This
back door is called \textcd{makeEvt}, which builds an event from a
base event.  A base event contains three functions that are used to
synchronize on the event:

\begin{itemize}
\item
\textcd{poll} returns true if the event is currently enabled (that is,
it can be synchronized immediately without blocking).
\item
\textcd{perform} immediately synchronizes the event and returns its
value.
\item
\textcd{block} takes a condition signal and records it in an
appropriate queue to be signalled when the event becomes enabled.  If
and when the condition is signalled, it is passed the event's value.
\end{itemize}

All of the three functions are assumed to begin and end in an atomic
section, and all are assumed never to raise an exception.  You may
wish to establish some additional invariants regarding their usage,
particularly in conjunction with each other.  You may do so, provided
that the invariants are properly documented.


{\bf Suggestions:}

\begin{itemize}
\item
Think carefully about the best representation for the \textcd{event}
type.  The right representation will make your implementation {\bf much}
easier.
\end{itemize}

\subsubsection{Wrap and Pure Events}

There are to be two implementations of the \textcd{EVENT} signature,
one called \textcd{PureEvent} and one called \textcd{Event}:

\begin{itemize}
\item
In the \textcd{PureEvent} structure, you may assume that the function
argument to \textcd{wrap} never raises an exception, and never calls
any CML utilities.  This may be useful, because it means that the
function can be called in any context, including within an atomic
section (where many CML utilities cannot be called since they may
attempt to enter an atomic section), or in a context where exception
raises are not permitted.

\item
In the \textcd{Event} structure, the function argument to
\textcd{wrap} is permitted to be arbitrary code.
\end{itemize}

You will implement the \textcd{PureEvent} structure.  The
\textcd{Event} structure is provided.  It uses your implementation of
pure events to implement general events.

\subsection{Channels}

Using the tools you have built so far, you will implement channels.
Each of the channel functions are as described in class.

\subsection{Demonstration Code}

The \textcd{CML} structure you are provided combines all of your code
into a (hopefully!)\ working implementation of Concurrent ML\@.  The
last thing you will implement is a small concurrent program that
demonstrates your system in an interesting manner.

Your demonstration program need not use every single feature of the
system, but at a minimum it should illustrate multiple threads,
channels, \textcd{select} or \textcd{choose}, and \textcd{wrap}.  Of
course, the more it uses the more fun it is.  (Also keep in mind that,
in any case, all the features of the system will be tested by our
code.)

To assist you in calibrating how much time to spent on this part of
the assignment, the demonstration code will be worth no more than five
percent of the full assignment.


\section{What to Hand In}

You are to hand in two things with this assignment:

\begin{enumerate}
\item
The code for your implementation.  In order to ensure that your code
can link with ours, you must be sure:
\begin{itemize}
\item
{\bf not} to alter any signatures,
\item
{\bf not} to change the names of any files, and
\item
{\bf not} to rely on any files other than those listed in Figure~\ref{fig:files}.
\end{itemize}

\item
A brief report (no more than 2 or 3 pages) documenting your design
decisions and invariants.  Your report should be named {\tt
report.txt} and included with your code.
\end{enumerate}

You will also sign up for a project demo to be held on Monday, May 3.
Students for whom this date causes a hardship may make special
arrangements with the instructor.

\section{Conclusion}

Have fun!


\appendix

\section{A Resource and a Warning}

You may find {\em Concurrent Programming in ML\/} by John H. Reppy
(Cambridge University Press, 1999) to be a useful reference for
Concurrent ML\@.  However you will probably {\em not\/} find its
chapter on implementing concurrency very helpful, and you may even
find it confusing, as the implementation discussed there is quite
different from the one you are to undertake.

\section{Signatures}

\begin{code}
signature CONT =
   sig
      type 'a cont
         
      val callcc : ('a cont -> 'a) -> 'a
      val throw : 'a cont -> 'a -> 'b
   end

structure Cont :> CONT\end{code}
\begin{code}
signature TIMER =
   sig
      (* special *)
      val startTimer : \{
                       timeslice : int,
                       tickHandler
                         : unit Cont.cont -> unit Cont.cont,
                       interruptHandler
                         : unit Cont.cont -> unit Cont.cont
                       \} -> unit
      val stopTimer : unit -> unit

      exception Atomic

      (* begins non-atomic, ends atomic (of course) *)
      val beginAtomic : unit -> unit

      (* begins atomic, ends non-atomic (of course) *)
      val endAtomic : unit -> unit
   end

structure Timer :> TIMER\end{code}
\begin{code}
signature PRINT =
   sig
      (* begins and ends non-atomic *)
      val print : string -> unit

      (* begins and ends atomic *)
      val printAtomic : string -> unit
   end

structure Print :> PRINT\end{code}
\begin{code}
signature QUEUE =
   sig
      type 'a queue

      val queue : unit -> 'a queue
      val reset : 'a queue -> unit

      val is_empty : 'a queue -> bool
      val insert : 'a queue * 'a -> unit

      exception EmptyQueue
      val remove : 'a queue -> 'a
      val front : 'a queue -> 'a
   end\end{code}
\begin{code}
signature THREAD =
   sig
      (* begins and ends non-atomic *)
      val spawn : (unit -> unit) -> unit
      val yield : unit -> unit
      val exit : unit -> 'a
      val shutdown : unit -> 'a

      (* begins and ends atomic *)
      val spawnAtomic : (unit -> unit) -> unit

      (* special *)
      val beginPreemption : int -> unit Cont.cont -> unit
      val endPreemption : unit -> unit
   end\end{code}
\begin{code}
signature CONDITION =
   sig
      type 'a cond

      (* arg fn must not raise an exception *)
      val wrapCond : 'a cond * ('b -> 'a) -> 'b cond

      (* begins and ends atomic *)
      val signal : 'a cond * 'a -> bool
      val query : 'a cond -> bool

      (* begins atomic, ends non-atomic, arg is called atomically *)
      val wait : ('a cond -> unit) -> 'a
   end\end{code}
\begin{code}
signature EVENT =
   sig
      type 'a event

      (* begins and ends non-atomic *)
      val sync : 'a event -> 'a
      val select : 'a event list -> 'a
      val wrap : 'a event * ('a -> 'b) -> 'b event
      val guard : (unit -> 'a event) -> 'a event
      val choose : 'a event list -> 'a event
      val never : 'a event
      val alwaysEvt : 'a -> 'a event

      (* for each function belonging to a baseEvt we assume:
         - the function begins and ends atomic
         - the function never raises an exception *)
      type 'a baseEvt = \{
                        poll : unit -> bool,
                        perform : unit -> 'a,
                        block : 'a Condition.cond -> unit
                        \}

      (* begins and ends non-atomic *)
      val makeEvt : 'a baseEvt -> 'a event
   end\end{code}
\begin{code}
signature CHANNEL =
   sig
      type 'a chan

      val channel : unit -> 'a chan

      (* begins and ends non-atomic *)
      val send : 'a chan * 'a -> unit
      val recv : 'a chan -> 'a
      val sendEvt : 'a chan * 'a -> unit Event.event
      val recvEvt : 'a chan -> 'a Event.event
   end\end{code}
\begin{code}
signature CML =
   sig
      type 'a event
      type 'a chan

      val spawn : (unit -> unit) -> unit
      val yield : unit -> unit
      val exit : unit -> 'a

      val sync : 'a event -> 'a
      val select : 'a event list -> 'a

      val wrap : 'a event * ('a -> 'b) -> 'b event
      val guard : (unit -> 'a event) -> 'a event
      val choose : 'a event list -> 'a event
      val never : 'a event
      val alwaysEvt : 'a -> 'a event

      val channel : unit -> 'a chan
      val send : 'a chan * 'a -> unit
      val recv : 'a chan -> 'a
      val sendEvt : 'a chan * 'a -> unit event
      val recvEvt : 'a chan -> 'a event

      val shutdown : unit -> 'a

      val activate : int -> (unit -> 'a) -> unit
   end\end{code}
\begin{code}
\end{code}
\begin{code}
\end{code}

\end{document}
