section{Modules}

The module system in pH is identical to the one used in Haskell.

\section{Basic Types}

\subsection*{Initial commentary}

The existing basic types in Haskell exist essentially unchanged in pH.
This section will briefly discuss the differences which do exist, and
which have not been mentioned in preceding sections on syntax.
The ultimate reference on such matters continues to be the Standard
Prelude to pH, which is presented (skeletally) in Appendix A.

\subsubsection*{Implementation decisions are not implied}

Note that there are a few places where Haskell has made design
decisions which might overly constrain the implementation of the
resulting functions.  For example, the Haskell report gives the
following definition of the boolean and operation \verb+(&&)+:

\begin{verbatim}
>  True  && x              =  x
>  False && x              =  False
\end{verbatim}

This definition implies (though it is not explicitly stated) that
\verb+(&&)+ is strict in its first argument and non-strict in its
second.  This has implications for the error behavior of programs.  In
this case, we cannot assume from the above definition that the
following expression has the value False, since x may never be well
defined:

\begin{verbatim}
x && False
\end{verbatim}

In general, overspecifying the behavior of such functions is to be
avoided.  Thus, the behavior of the code in exceptional cases should
always be suspect, and if several correct implementations will give
different results then the programmer should assume that any such
implementation might be used.  Thus, in the above example, the
programmer cannot assume that either of the following are False unless
she knows that x will produce a value:
\begin{verbatim}
x && False
False && x
\end{verbatim}

Conversely, the implementor is free to choose any correct
implementation of the functions given in the Prelude (for example, a
parallel {\em and} which would cause {\em both} of the above
expressions to terminate).

\subsubsection*{New Basic Types}

Two new (and useful) basic types have been added to the pH prelude.
They express common ``either/or'' values.  Both types are slated to
appear in Haskell 1.3, and the pH prelude will incorporate the
operations on both types which appear in the new Haskell prelude.  At
the moment, the provided functionality is a best guess based on
existing implementations and upon what was useful in actual code.
\begin{verbatim}
In PreludeCore:
>  data Maybe a    = Nothing | Just a   deriving (Eq, Ord, Text)
>  data Either a b = Left a  | Right b  deriving (Eq, Ord, Text)

In Prelude:
>  errMaybe                    :: String -> Maybe a -> a
>  errMaybe msg Nothing        =  error msg
>  errMaybe _   (Just r)       =  r
>  
>  lift                        :: (a -> b) -> (Maybe a -> Maybe b)
>  lift _ Nothing              =  Nothing
>  lift f (Just x)             =  Just (f x)
>  
>  lift2                       :: (a -> a -> a) -> (Maybe a -> Maybe a -> Maybe a)
>  lift2 _ Nothing r           =  r
>  lift2 _ l Nothing           =  l
>  lift2 f (Just l) (Just r)   =  Just (f l r)
>  
>  maybe                       :: b -> (a -> b) -> (Maybe a -> b)
>  maybe b _ Nothing           =  b
>
>  either                      :: (a -> c) -> (b -> c) -> (Either a b -> c)
>  either f _ (Left a)         =  f a
>  either _ g (Right b)        =  f b
\end{verbatim}

\subsection{Lists}

In the interests of efficiency, pH includes a number of functions on
lists which did not exist in Haskell; in the interests of correctness,
several functions leading to infinite computations have been omitted.

Because pH is a parallel programming language, and because lists are
inherently linear data structures, a large proportion of list
operations are not terribly parallel.  Several functions are provided
which are intended to make it simpler to write parallel list
operations by placing the construction and traversal of lists under
wraps.  List comprehension syntax makes it particularly easy to
generate efficient code when using lists.  Implementations should use
the most efficient means available to compile code with lists, and
should eliminate them whenever possible, most notably in the case of
array comprehensions.

Of the new list functions, the most confusing is {\tt reduce}.  It has
the following signature:
\begin{verbatim}
>  reduce                       :: (a -> a -> a) -> a -> [a] -> a
\end{verbatim}
{\tt reduce} is in effect a directionless fold---its first argument
must be an associative function, and the secod argument must be a zero
of that function.  The elements of the list are combined so that the
following identities hold:
\begin{verbatim}
reduce f z (a ++ b)     ==     (reduce f z a) `f` (reduce f z b)
reduce f z [e]          ==     e
reduce f z []           ==     z
\end{verbatim}
The implementation is permitted to perform the reduction in any order
(thus the requirement that the function provided be associative) and
is permitted to introduce the zero at any point in the computation, or
may ignore it entirely (thus the requirement that the zero be an
actual zero of the given function).  These restrictions permit a large
number of compiler optimizations.  The programmer should be able to
assume that {\tt reduce} is always {\em at least} as efficient as the
equivalent code written using {\tt foldl} or {\tt
foldr}.\footnote{Note that a naive implementation may perform no
optimization at all and simply define {\tt reduce} to be the faster of
these operations.}

The remaining list functions are straightforward.  The {\tt someOrder}
function returns a (not necessarily random) permutation of its
argument and is essentially a declaration to permit compiler
optimization and to make ordering dependencies (or the lack thereof)
obvious to human readers.  {\tt reduce1} is a version of {\tt reduce}
which works on non-empty lists.  {\tt unfold} produces a list
systematically from left to right.  Definitions for all of these
functions are given in Appendix A.  A detailed discussion of these
functions, their importance, and the ability of the compiler to
optimize them can be found in \cite{Maessen95}.

All of the omitted functions produce infinite lists.  Of these, the
most frequently used are {\tt enumFrom} and {\tt enumFromBy}.  When
porting existing Haskell code to pH, upper bounds should be given in
uses of these constructs.  In reality, implementations are free to
implement either of these functions on finite types, in which case
they should halt when the reach the largest (or smallest as appropriate)
element of the type.  The remaining function on infinite lists is
{\tt iterate}.  The functions {\tt repeat} and {\tt cycle} can be
defined using circular lists, and were thus left in for compatibility
with Haskell.

\subsection{Binary Datatype}

The {\tt Bin} datatype is not required by pH---indeed, very few
Haskell compilers implement it as specified.  Its primary purpose is
to enable efficient I/O; a later section describes the current state
of I/O in pH.

\subsection{Numbers}

The Haskell type system specifies a large numeric hierarchy.  While
the functionality provided is laudable, it should be recognized that
existing implementations of pH do not support all of it.  However,
implementations must provide the types Int and Float.

\subsection{Arrays}

The semantics of arrays in pH were discussed earlier.  Again it is
only when errors occur that pH and Haskell take different positions on
the behavior of arrays.  The guiding principle is to {\em make as much
of the array available as is possible despite the presence of errors}.
This means that while undefined, multiply defined, or out of range
assignments should signal an error, the values of the remaining
elements of the array ought to be well-defined.

\subsubsection{The Class Ix}

A new method, {\tt sizeRange}, has been added to the Ix class in pH.
It has the following definition:
\begin{verbatim}
>          sizeRange :: (a,a) -> Int
\end{verbatim}
Note that the behavior of the {\tt Ix} class is somewhat different in pH.
In particular, the following identity {\em \bf does not necessarily hold}:
% I'm a little leery about setting it out in the text like this
% as a result!  It might be mistaken for something which _is_ true!
\begin{verbatim}
range (l,u) !! index (l,u) i == i
\end{verbatim}
This permits implementations of arrays that are NOT mapped to storage
in a perfectly linear fashion.  Instead, the following identities take
its place:
\begin{verbatim}
inRange (l,u) i == index i < rangeSize (l,u)
inRange (l,u) i == 0 <= index i 
rangeSize (l,u) == length (range (l,u))
\end{verbatim}

\subsubsection{Array Construction}

The {\tt Assoc} type does not exist in pH.  Instead, tuple notation is
used for the construction of arrays, so the Haskell expression
\verb+i := v+ would be written in pH as \verb+(i,v)+.  Note that
Haskell 1.3 will almost certainly use the latter notation.

\subsubsection{Incremental Array Updates}

The introduction of I-structure and M-structure arrays include
incremental update-in-place operations directly analogous to the
Haskell's incremental update operations, \verb+(\\)+ and {\tt accum}.
They are:
\begin{verbatim}
>   (//=)    :: (Ix a) => IArray a b -> [(a,b)] -> ()
>   (//^=)   :: (Ix a) => MArray a b -> [(a,b)] -> ()
>   (//^^=)  :: (Ix a) => MArray a b -> [(a,b)] -> ()
>   mAccum   :: (Ix a) => (b -> c -> b) -> MArray a b -> [(a,c)] -> MArray a b
\end{verbatim}
% These are ugly!!  Especially //^^= !!!  Ugh.

\subsection{Errors}

Not all errors in pH are semantically equivalent to $\bot$.  Indeed,
things like multiply defined array elements and multiply written
I-structures are semantically equivalent to $\top$, the opposite
extreme of the value domain.  Nonetheless, an application of {\tt
error} must still display the provided string and should terminate the
program.
% Should termination really be specified here?

\section{Input/Output}

I/O in pH is based upon the new monadic definition from Haskell 1.3.
At the moment only a stripped-down version of this definition exists.
The implementation is based on the more general notion of a state
transformer, which is discussed in the next section.

\section{State Transformers}

State transformers can be used to manipulate state---in particular, I-
and M-structure cells and vectors, and external files.  Programs which
manipulate state using state transformers rather than raw I- or M-
structures, and which are written without {\tt par} and {\tt seq}
constructs, can be run under Haskell if libraries are provided to
simulate the state transformer functions.  This will permit
state-manipulating code to be written portably.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix
\section{Changes to the Standard Prelude}

This appendix lists the portions of the pH prelude which are different
from the corresponding Haskell definitions.

\hdivider

\begin{verbatim}
module Prelude(
    PreludePHArray.., PreludePH.., 
    errMaybe, lift, lift2, maybe,
\end{verbatim}
{\em The remaining Prelude exports have not changed.}

\begin{verbatim}
import PreludePHArray
import PreludePH
\end{verbatim}

{\em The remaining imports are the same, as is the code with the
following addition:}

\begin{verbatim}
thenMaybe                   :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing `thenMaybe` _       = Nothing
Just a  `thenMaybe` f       = f a

errMaybe                :: String -> Maybe a -> a
errMaybe msg Nothing    = error msg
errMaybe _   (Just r)   = r

lift                        :: (a -> b) -> Maybe a -> Maybe b
lift _ Nothing              = Nothing
lift f (Just x)             = Just (f x)

lift2                       :: (a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
lift2 _ Nothing r           = r
lift2 _ l Nothing           = l
lift2 f (Just l) (Just r)   = Just (f l r)

maybe                       :: b -> (a -> b) -> (Maybe a -> b)
maybe b _ Nothing           =  b

either                      :: (a -> c) -> (b -> c) -> (Either a b -> c)
either f _ (Left a)         =  f a
either _ g (Right b)        =  f b
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludeCore}}

\begin{verbatim}
module PreludeCore (
    Maybe(..), Either(..), 
    Ix(range, index, inRange, sizeRange),
    Enum(enumFromTo, enumFromThenTo),
\end{verbatim}

{\em Remaining exports as before, omitting Assoc.}

\begin{verbatim}
import PreludeArray(Array)
\end{verbatim}

{\em Do not import {\tt Assoc} from {\tt PreludeArray}.  Remaining
imports are unchanged.}

\begin{verbatim}

data Maybe a    = Nothing | Just a   deriving (Eq, Ord, Text)
data Either a b = Left a  | Right b  deriving (Eq, Ord, Text)


class  (Ord a) => Ix a  where
    range               :: (a,a) -> [a]
    index               :: (a,a) -> a -> Int
    inRange             :: (a,a) -> a -> Bool
    sizeRange           :: (a,a) -> Bool

    sizeRange           = length . range

class  (Ord a) => Enum a    where
    enumFromTo          :: a -> a -> [a]
    enumFromThenTo      :: a -> a -> a -> [a]
\end{verbatim}

{\em omit class {\tt Binary}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludeList}}

\begin{verbatim}
module PreludeList where
\end{verbatim}

{\em Again much the same as before, with the following additions:}

The following identities must hold for reduce; its implementation
is otherwise unconstrained:
\begin{verbatim}
reduce f z (a ++ b)     ==     (reduce f z a) `f` (reduce f z b)
reduce f z [e]          ==     e
reduce f z []           ==     z
\end{verbatim}

\begin{verbatim}
reduce          :: (a -> a) -> a -> [a] -> a
\end{verbatim}

Note that many of the functions in the prelude can be defined using
{\tt reduce} rather than {\tt foldl}, {\tt foldr}, or explicit
recursion.  For example, we can define {\tt sum} as follows:
\begin{verbatim}
sum = reduce (+) 0
\end{verbatim}

{\tt someOrder} returns a permutation (perhaps fixed) of its argument.

\begin{verbatim}
someOrder       :: [a] -> [a]
\end{verbatim}

{\tt unfold} generates a list systematically given a function.
\begin{verbatim}
unfold :: (a->Bool) -> (a->(b,a)) -> a -> [b]
unfold p f v = h v
         where h v | p v       = []
                   | True      = case f v of (a,b) -> a:h b

concatMap :: (a->[b]) -> [a] -> [b]
concatMap f l =
    let h1 [] = []
        h1 (y:ys) =
            let h2 [] = h1 ys
                h2 (x:xs) = x : h2 xs
            in  h2 (f y)
    in  h1 l
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludeArray}}

This portion of the prelude much the same as in Haskell; however, the
semantics of some array operations is different in pH.  See the main
text for more details.  The Haskell report gives an implementation
which ``specifies the semantics of arrays only''.  Such a definition
for pH will eventually appear here.  Note that the Assoc type has been
replaced with 2-tuples throughout.

\begin{verbatim}
interface  PreludeArray where

infixl 9  !
infixl 9  //
\end{verbatim}

{\em Obligatory definitions of classes {\tt Eq}, {\tt Ord}, and {\tt
Ix} must appear in a proper interface file, but are omitted for
clarity.}

\begin{verbatim}
data  (Ix a)    => Array a b

array           :: (Ix a) => (a,a) -> [(a, b)] -> Array a b
listArray       :: (Ix a) => (a,a) -> [b] -> Array a b
(!)             :: (Ix a) => Array a b -> a -> b
bounds          :: (Ix a) => Array a b -> (a,a)
indices         :: (Ix a) => Array a b -> [a]
elems           :: (Ix a) => Array a b -> [b]
assocs          :: (Ix a) => Array a b -> [(a, b)]
accumArray      :: (Ix a, Eq a) => (b -> c -> b) -> b -> (a,a) -> [(a, c)] -> Array a b
(//)            :: (Eq a, Ix a) => Array a b -> [(a, b)] -> Array a b
accum           :: (Ix a, Eq a) => (b -> c -> b) -> Array a b -> [(a, c)] -> Array a b
amap            :: (Ix a) => (b -> c) -> Array a b -> Array a c
ixmap           :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c

instance  (Ix a, Eq b)  => Eq (Array a b)

instance  (Ix a, Ord b) => Ord (Array a b)

instance  (Ix a, Text a, Text b) => Text (Array a b)
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludeIO}}

This module is based on the Haskell 1.3 IO proposal\cite{HaskellIO95a}.
It is thus monadic in structure.  It is built on a state transformer
substrate (see the discussion of {\tt PreludeST}, below).  This
enables operations on state and IO operations to be freely intermixed.
The implementation of IO should, of course, be hidden from view.
The extensions described here permit parallel I/O (beyond simple
parallel file read/write) with some loss of safety.

The function {\tt doST} changes an arbitrary state transformer
computation (whose state is constrained to type {\tt IOState}, rather
than being fully polymorphic) into a computation of type {\tt IO}. 
\begin{verbatim}
doST :: ST IOState a -> IO a
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludePH}}

Primitive functions and types which implement I- and M- structures.
These functions will not behave correctly under Haskell.

\begin{verbatim}
interface PreludePH where
\end{verbatim}

{\em Again, obligatory definitions of classes {\tt Eq}, {\tt Ord}, and
{\tt Ix} must appear in a proper interface file, but are omitted for
clarity.}

Dummy class to express the fact that a type variable is imperative.
The compiler knows about this class.

\begin{verbatim}
class Imperative a
\end{verbatim}

The {\tt unboxed} declaration is used in many compilers to keep a
datatype from being used polymorphically.  This permits {\tt ICell}
and {\tt MCell} to be implemented at no additional space cost.  

\begin{verbatim}
data unboxed ICell a
iCell :: (Imperative a) => a -> ICell a
iFetch :: ICell a -> a
iAssign :: ICell a -> a -> ()

data unboxed MCell a
mCell :: (Imperative a) => a -> MCell a
mFetch :: MCell a -> a
mExamine :: MCell a -> a
mStore :: MCell a -> a -> ()
mReplace :: MCell a -> a -> ()
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{Prelude {\tt PreludePHArray}}

Functions and types to implement I- and M-structure arrays.  The
non-updating functions should have the same observable behavior as the
equivalent functions on ordinary arrays.

These are canonical definitions for I- and M- structure arrays in
terms of arrays of {\tt ICell} and {\tt MCell}.  Places where
implementations can be more flexible are duly noted.

\begin{verbatim}
module  PHArray (IArray(..), MArray(..), 
                 iArray, mArray, 
                 iBounds, mBounds,
                 (!.), iAStore, (//=)
                 (!^), mAStore, (//^=)
                 (!^^), mAReplace, (//^^=)
                 iToArray, mToArray
                 ) where

import PreludeCore
import PreludeUtil
import Prelude(error, and)
import PreludePHVector
import PreludePH(Imperative(..))
import PreludeArray(Array(..))

infixl 9 !.
infixl 9 !^
infixl 9 !^^
infixl 9 //=
infixl 9 //^=
infixl 9 //^^=

data (Ix a) => IArray a b = MkIArray (Array a (IVar b))
data (Ix a) => MArray a b = MkMArray (Array a (MVar b))

iArray          :: (Ix a, Imperative b) => (a,a) -> [(a, b)] -> IArray a b
iBounds         :: (Ix a) => IArray a b -> (a,a)
(!.)            :: (Ix a) => IArray a b -> a -> b
iAStore         :: (Ix a) => IArray a b -> a -> b -> ()
(//=)           :: (Ix a) => IArray a b -> [(a, b)] -> ()
iToArray        :: (Ix a) => IArray a b -> Array a b

mArray          :: (Ix a, Imperative b) => (a,a) -> [(a, b)] -> MArray a b
mBounds         :: (Ix a) => MArray a b -> (a,a)
(!^)            :: (Ix a) => MArray a b -> a -> b
(!^^)           :: (Ix a) => MArray a b -> a -> b
mAStore         :: (Ix a) => MArray a b -> a -> b -> ()
mAReplace       :: (Ix a) => MArray a b -> a -> b -> ()
(//^=)          :: (Ix a) => MArray a b -> [(a, b)] -> ()
(//^^=)         :: (Ix a) => MArray a b -> [(a, b)] -> ()
mAccum          :: (Ix a) => (b -> c -> b) -> MArray a b -> [(a,c)] -> MArray a b
mToArray        :: (Ix a) => MArray a b -> Array a b
\end{verbatim}

IArray functions:
\begin{verbatim}
iArray b ivs = MkIArray a
        where a = array b [(i,iCell _) | i <- range b]
              _ = a //= ivs

iBounds (MkIArray a) = bounds a

(MkIArray a)!.i = iFetch (a!i)

iAStore (MkIArray a) i x = iStore (a!i) x

(MkIArray a) //= ivs =
        -- Do vector writes into the appropriate places.
        for (i,s) <- ivs do
            _ = iAStore a i x             -- store the values
        finally ()
\end{verbatim}

This version will not have the constructed array shadow the value of
the IArray.  The function will deadlock if any of the cells of the
IArray remain empty.  It is perfectly legal to allow this function to
terminate regardless of the state of the IArray.

\begin{verbatim}
iToArray (MkIArray a) = amap iFetch a
\end{verbatim}

MArray operations:
\begin{verbatim}
mArray b ivs = MkMArray a
        where a = array b [(i,mCell _) | i <- range b]
              _ = a //^= ivs


mBounds (MkMArray a) = bounds a

(MkMArray a)!^i = mFetch (a!i)

(MkMArray a)!^^i = mExamine (a!i)

mAStore (MkMArray a) i x = mStore (a!i) x

mAReplace (MkMArray a) i x = mReplace (a!i) x
\end{verbatim}

Note that the following will probably need to be followed by a barrier
whenever it is used!!  It behaves like mAReplace---so the function can
return a value immediately, before all the replacements have taken
place.

\begin{verbatim}
(MkMArray a) //^^= ivs =
        -- Do vector writes into the appropriate places.
        for (i,s) <- ivs do
            _ = mAReplace a i x             -- store the values
        finally ()
\end{verbatim}

Note that {\tt mAccum} actually returns a value of type {\tt MArray}.
It should be the same value as was passed in, but must not be made
available until all fetches have taken place.  Thus, uses of the
result will be properly synchronized by simple data dependency.

\begin{verbatim}
mAccum f inp@(MkMArray a) ivs =
      let
        -- Do updates into appropriate places.
        flag = ()
        flag' = for (i,s) <- ivs do
                  seq val = mAFetch v i
                      par _   = mAStore v i val'
                          next flag = flag
                  val' = f val s
                finally flag
        seq _ = flag'
            res = inp
      in res
\end{verbatim}
            
This particular implementation of mToArray produces an array whose value 
is fixed as the value of the mArray as the array is being constructed.  Actual
implementations are encouraged to have the value of the array shadow the current
value of the mArray if that is possible.  In any case, this function screws 
referential transparency no matter how you slice it.  MArrays just aren't refer-
entially transparent to begin with.
Note also that this implementation can deadlock if any element of the MArray is 
unfilled. 

\begin{verbatim}
mToArray (MkMArray a) = amap iExamine a
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

\subsection{State Transformers}

State transformers can be used in the implementation of I/O.  In
addition, they can be used to encapsulate any state-manipulating
function---this means that programs manipulating state using only the
functions in {\tt PreludeST} and {\tt PreludeMutable} can be run in
both Haskell and pH.

\begin{verbatim}
interface PreludeST where

infixr 1 >#>, >#., <>=

data ST s a
\end{verbatim}
{\tt ST s a} is a State Transformer computation returning a result of
type {\tt a}.  The type variable {\tt s} is used to represent the
state being manipulated.

{\tt gate} is similar to the {\tt strict} construct in many languages.
It evaluates its second argument to weak head normal form, then
returns its first argument.
\begin{verbatim}
gate :: a -> b -> a
\end{verbatim}

Monadic binding, non-strict and strict in the state.
\begin{verbatim}
(<>=) :: ST a b -> (b -> ST a c) -> ST a c
(>#>) :: ST a b -> (b -> ST a c) -> ST a c
\end{verbatim}

Sequencing, non-strict (actually runs computations in parallel) and
strict in the state.
\begin{verbatim}
(<||>) :: ST a b -> ST a c -> ST a c
(>#.)  :: ST a b -> ST a c -> ST a c
\end{verbatim}

Encapsulating state manipulations.  Note that in order to gaurantee
safety, {\tt runST} must actually possess the type $\forall\verb|a|.(\forall
\verb|b|. \verb|ST a b|) {\tt \verb|->|} \verb|b|$.
\begin{verbatim}
runST            :: ST a b -> b
_unsafePerformST :: ST a b -> b
\end{verbatim}

Fixed point of the value portion of the state.
\begin{verbatim}
fixST :: (a -> ST b a) -> ST b a
\end{verbatim}

Arbitrary parallel state manipulation.  Results are combined using the
provided function.
\begin{verbatim}
joining :: (a -> b -> c) -> ST d a -> ST d b -> ST d c
\end{verbatim}

Sequence a large number of computations.
\begin{verbatim}
seqST :: [ST a ()] -> ST a ()
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\hdivider

The functions shown here produce state transformers which can
manipulate mutable objects, either strictly or non-strictly.

\begin{verbatim}
interface PreludeMutable where

import PreludeST
\end{verbatim}

The type {\tt MutVar} describes a memory location which always
contains a meaningful value.  Note that using {\tt writeVar} in
parallel with itself introduces non-strictness into the program, and
either value written may be available to later computations.
\begin{verbatim}
data MutVar s a

newVar   :: (Imperative s, Imperative a) => a -> ST s (MutVar s a)
readVar  :: MutVar s a -> ST s a
writeVar :: MutVar s a -> a -> ST s ()
\end{verbatim}

The type {\tt MutVector} describes a vector of {\tt MutVars}.  The
function {\tt \verb|_|unsafeFreezeMutVector} permits {\tt MutVector} to be
used to implement arrays.
\begin{verbatim}
data MutVector s a = MutVector (MVector a)
data Vector a = Vec (MVector a)

newMutVector           :: (Imperative s) => Int -> a -> ST s (MutVector s a)
readMutVector          :: MutVector s a -> Int -> ST s a
writeMutVector         :: MutVector s a -> Int -> a -> ST s ()
_unsafeFreezeMutVector :: MutVector s a -> ST s (MVector a)
readVector             :: Vector a -> Int -> a
\end{verbatim}

I-structure variables.
\begin{verbatim}
data IVar s a = IVar (ICell a) {-# STRICT #-}

newIVar   :: ST s (IVar s a)
readIVar  :: IVar s a -> ST s a
writeIVar :: IVar s a -> a -> ST s ()
\end{verbatim}

M-structure variables.
\begin{verbatim}
data MVar s a = MVar (MCell a) {-# STRICT #-}

newMVar     :: ST s (MVar s a)
takeMVar    :: MVar s a -> ST s a
putMVar     :: MVar s a -> a -> ST s ()
examineMVar :: MVar s a -> ST s a
replaceMVar :: MVar s a -> a -> ST s ()
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%