\hdivider

\section{Introduction}

pH is a parallel language obtained by extending Haskell.  This
document must be read in conjunction with the Haskell Report
{\cite{Hudak92a}} since it describes only the extensions.

In Section \ref{sec-extensions} we present the syntax extensions
proper.  In Section \ref{sec-examples} we present some examples to
give a flavor of the language.  In Section \ref{sec-commentary} we
present commentary and rationale.

Future versions of this document will address topics such as loop
pragmas, data and work distribution, \etc\

\subsection*{Background}

Haskell appears to be achieving its original goal of becoming the
standard non-strict functional programming language.  Current
implementations of Haskell are based on sequential, lazy evaluation
(except for the parallel implementation at Glasgow on GRIP).

Id \cite{Nikhil91a} is, and has always been, a parallel language.  It
is not a purely functional language, but has a non-strict functional
language at its core, and the style of programming is predominantly
the same as in Haskell.  Id has a so-called ``lenient'' evaluation
order rather than lazy evaluation, for two reasons: for more
parallelism, and to give meaning to its side-effecting constructs
(I-structures, M-structures).

In August 1993, a group of people-- Arvind (MIT), Lennart Augustsson
(Chalmers), James Hicks (Motorola MCRC), Simon Peyton Jones (Glasgow),
Rishiyur Nikhil (DEC CRL), Joe Stoy (Oxford) and John Williams (IBM
Research)-- met in Cambridge, Mass., to discuss the possibility of
merging Id and Haskell into a parallel dialect of Haskell, in order to
improve the dialogue between the Id and Haskell communities, to share
infrastructure (compilers, systems, application programs), and to
facilitate interesting research topics, such as comparing lazy
evaluation \vs\ lenient evaluation, parallel programming in a pure
functional language \vs\ in a language with I- and M-structures, \etc\

After extensive discussions on the differences between Id and Haskell,
we decided that such a merger was feasible, and we decided to pursue
it, calling this new dialect ``pH''.

% ================================================================

\section{Haskell Extensions for pH}

\label{sec-extensions}

The extensions here are expressed as changes to the formal syntax in
Appendix B of the Haskell Report.

pH is layered (like Id):
\begin{itemize}
\item Functional core
\item I-structure extensions
\item M-structure extensions
\end{itemize}
These layers are distinguished syntactically and by type rules (like
Id), so that it is easy for a compilation system to force programs to
be restricted to a desired layer (purely functional, purely functional
with I-structures, or unrestricted).

% ----------------

\subsection{Functional core of pH: Haskell plus loop notation}

The notation for the functional core of pH is identical to Haskell,
with a few extensions for loops.

Haskell:
{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
exp$^{10}$ \> \IS \> \verb"\" ... \\
           \> \OR \> {\tt let} \verb"{" decls [{\tt ;}] \verb"}" {\tt in} exp \> {\rm (let expression)} \\
           \> \OR \> {\tt if} ... \\
           \> \OR \> {\tt case} ... \\
           \> \OR \> fexp \\
\\
aexp       \> \IS \> var \> {\rm (variable)} \\
           \> \OR \> ... \\
\\
apat       \> \IS \> var [ \verb"@" apat ] \\
           \> \OR \> ...
\end{tabbing}
}

Extensions for pH:
{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
exp$^{10}$ \> \IS \> ... \\
           \> \OR \> {\tt while} exp {\tt do} \verb"{" decls [{\tt ;}] \verb"}" {\tt finally} exp \> {\rm (while expression)} \\
           \> \OR \> {\tt for} pat {\tt <-} exp {\tt do} \verb"{" decls [{\tt ;}] \verb"}" {\tt finally} exp \> {\rm (for expression)} \\
\\
aexp       \> \IS \> ... \\
           \> \OR \> {\tt next} var \> {\rm (loop-carried var)} \\
\\
apat       \> \IS \> ... \\
           \> \OR \> {\tt next} var \> {\rm (loop-carried var)}
\end{tabbing}
}

\subsubsection*{Semantics of loops}

We explain for-loops in terms of a translation to while-loops, and we
explain while-loops in terms of a translation to a tail-recursive
function definition and invocation.

Given a for-loop:
{\tt
\begin{tabbing}
\hmm \= \hmm \= \kill
>    \> for  {\it pat} <- {\it exp}  do \{ \\
>    \>      \> {\it decls} \\
>    \> \} \\
>    \> finally {\it exp} \\
\end{tabbing}
}
Let {\tt xs} be a new variable.  Then the for-loop is equivalent to:
{\tt
\begin{tabbing}
\hmm \= let \= \hmm \= \kill
>    \> let \\
>    \>     \> xs = {\it exp} \\
>    \> in \\
>    \>     \> while (xs /= []) do \{ \\
>    \>     \>      \> {\it pat\/}:next xs = xs \\
>    \>     \>      \> {\it decls} \\
>    \>     \> \} \\
>    \>     \> finally {\it exp}
\end{tabbing}
}

The {\it decls\/} list in a loop is called the ``loop body''.  A {\tt
next} var may only be bound in a top-level {\it decl\/} of a loop body
(in an {\it apat\/}).  Such variables are called ``next-ified'',
``circulating'' or ``loop-carried'' variables.  Their scope, like any
other var bound in a top-level {\it decl\/} in the loop body, is the
entire loop body.  A {\tt next} var may also be used in an expression
like a normal variable.

Given a while-loop:
{\tt
\begin{tabbing}
\hmm \= \hmm \= \kill
>    \> while  {\it ePred\/}  do \{ \\
>    \>      \> {\it decls} \\
>    \> \} \\
>    \> finally  {\it eFinal}
\end{tabbing}
}

Let $x_1$, ..., $x_N$ be the next-ified variables bound in {\it
apat\/}'s in the top-level of {\it decls\/}.  For each $x_i$, let {\it
next\_x$_i$} be a corresponding new variable.  Also, let {\tt loop} be
a new variable.  Then the while-loop is equivalent to:

{\tt
\begin{tabbing}
\hmm \= let \= loop $x_1$ ... $x_N$ = \= \hmm \= \hmm \= \kill
>    \> let \\
>    \>     \> loop $x_1$ ... $x_N$ = \> if {\it ePred\/} then \\
>    \>     \>                        \>      \> let \\
>    \>     \>                        \>      \>      \> {\it decls'} \\
>    \>     \>                        \>      \> in \\
>    \>     \>                        \>      \>      \> loop {\it next\_x$_1$} ... {\it next\_x$_N$} \\
>    \>     \>                        \> else \\
>    \>     \>                        \>      \> {\it eFinal} \\
>    \> in \\
>    \>     \> loop $x_1$ ... $x_N$
\end{tabbing}
}

where {\it decls'\/} is identical to {\it decls\/} except that each
occurrence of {\tt next $x_i$} is replaced by {\it next\_x$_i$}, both
in {\it apat}'s and in {\it exp}'s.

% ----------------

\subsection{I- and M-structure extensions}

\subsubsection{I- and M-structure semantics}

An I- or M-structure field in a data structure is an updateable field.
However, unlike the ``raw'' reads and writes in conventional
languages, the accesses are combined with synchronization, so that
they are relatively easy to use in a parallel environment.

For both I- and M-structure fields, the field may be in one of two
states: Full and Empty.

An I-field is initially in the Empty state.  When assigned, it goes to
the Full state.  If a second assignment to an I-field is attempted,
the entire program is in error.  An expression that reads an I-field
simply returns the value when it becomes Full.  The use of I-structure
fields does not compromise the Church-Rosser property--- programs are
still guaranteed to be deterministic.

An M-field is initially in the Empty state.  When assigned, it is in
the Full state.  An expression that reads an M-field performs two
actions atomically: it returns the value in the field when it becomes
Full, and resets it to the Empty state.  Thus, amongst multiple
expressions attempting to read a Full M-field, only one of them can
succeed in reading the value (it is non-deterministic as to which one
succeeds).  The other reads must wait until the field is assigned
again.  M-fields allow one-at-a-time access to its contents.
Assignments are only allowed on Empty fields; if a second assignment
to a Full M-field is attempted, the entire program is in error.  The
Church-Rosser property no longer holds when M-structure fields are
used.

M-fields have two additional operations that are convenient
compositions of normal M-field reads and writes.  The {\it examine\/}
operation returns the value of the field when Full, and leaves it
Full.  This is equivalent to a read and a write that just writes back
the value.  The {\it replace\/} operation replaces the value in a Full
field by a new value.  This is equivalent to a read followed by a
write that writes back the new value.  Note that these are not
conventional ``raw'' reads and writes--- they both respect the
synchronization semantics of M-fields, and will both wait on an Empty
M-field.

Referential transparency no longer holds with the use of I-structures
and/or M-structures.  Further, the polymorphism of I- and M-fields is
restricted in exactly the same way as ``{\tt ref}'' types in SML
(although SML's updateable cells do not have any synchronization
semantics).

\subsubsection{Single I- and M-structure cells}

The following primitives are for constructing, reading from, and
writing to single cells with I-structure and M-structure
semantics:\footnote{Single assignable cells are reminiscent of {\tt
ref} cells in SML.}
\begin{verbatim}
>    -- New prelude primitives
>
>    data ICell a
>
>    iCell    :: a        -> ICell a                -- Constructor
>
>    iFetch   :: ICell a  -> a
>
>    iStore   :: ICell a  -> a        -> ()
>
>
>    data MCell a
>
>    mCell    :: a        -> MCell a                -- Constructor
>
>    mFetch   :: MCell a  -> a
>    mStore   :: MCell a  -> a        -> ()
>
>    mExamine :: MCell a  -> a
>    mReplace :: MCell a  -> a        -> ()
\end{verbatim}

\paragraph{Empty cell construction}

The {\tt iCell} and {\tt mCell} constructors each take a single
argument $v$ and produce an I-structure object and M-structure object,
respectively, containing $v$.

Optionally, the cells may be constructed in an ``empty'' state by
applying them to the special expression ``{\tt \_}'', described by the
following syntactic extension.

Haskell:
{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
aexp       \> \IS \> var \> {\rm (variable)} \\
           \> \OR \> ... \\
\end{tabbing}
}

Extension for pH:
{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
aexp       \> \IS \> ... \\
           \> \OR \> \verb"_" \> {\rm (Empty field)} \\
\end{tabbing}
}

\subsubsection{I- and M-structure array construction}

There are two new ``array comprehension'' contructor functions in the
prelude, for I- and M-structure arrays:
\begin{verbatim}
>    data    (Ix a) => Iarray a b
>    data    (Ix a) => Marray a b
>
>    iarray        ::  (Ix a) => (a,a) -> [Assoc a b] -> Iarray a b
>    marray        ::  (Ix a) => (a,a) -> [Assoc a b] -> Marray a b
\end{verbatim}
An empty I- or M-structure array can be constructed simply by applying
these constructors to an empty list of index-value associations.

The semantics of the {\tt array} ``array comprehension'' constructor
function is changed for pH:

In Haskell:
\begin{itemize}
\item 
If there is more than one index-value pair for the same index, that
element goes to $\bot$
\item
If any index-value pair has its index out of bounds, the entire array
goes to $\bot$
\end{itemize}

In pH:
\begin{itemize}
\item 
If there is more than one index-value pair for the same index, the entire
program goes to $\top$
\item
If any index-value pair has its index out of bounds, then that assignment
goes to $\bot$
\end{itemize}

% ----------------

\subsubsection{I- and M-structure array component selection}

New prelude infix operators for array component selection:
\begin{verbatim}
>    infixl  9  !.         -- I-structure fetch
>    infixl  9  !^         -- M-structure fetch
>    infixl  9  !^^        -- M-structure examine
>
>    (!.)    :: Iarray a b  ->  a  ->  b
>    (!^)    :: Marray a b  ->  a  ->  b
>    (!^^)   :: Marray a b  ->  a  ->  b
\end{verbatim}

% ----------------

\subsubsection{I- and M-structure array component assignment}

New prelude functions for array component assignment:
\begin{verbatim}
>    iastore   :: Iarray a b  ->  a  ->  b  ->  ()
>    mastore   :: Marray a b  ->  a  ->  b  ->  ()
>    mareplace :: Marray a b  ->  a  ->  b  ->  ()
\end{verbatim}

% ----------------

\subsubsection{Syntax extensions for I- and M-structure array component assignment}

One frequently finds an I- or M-structure assignment as part of a
``dummy'' binding in a declaration:

{\tt
\begin{tabbing}
\hmm \= let \= \kill
>    \> let \\
>    \>     \> {\it decls} \\
>    \>     \> ... \\
>    \>     \> \_ = iastore  {\it eA\/}  {\it eJ\/}  {\it eV} \\
>    \>     \> ... \\
>    \>     \> {\it decls} \\
>    \> in \\
>    \>     \> $e$
\end{tabbing}
}

The following syntax extension allows us to omit the annoying ``{\tt
\_ =}'' prefix.

Haskell:

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decl \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
     \> \OR \> valdef
\end{tabbing}
}

Extensions for pH:

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decl \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
     \> \OR \> valdef \\
     \> \OR \> exp                      \> {\rm for effect only} \\
\end{tabbing}
}

The following syntax extension goes further and makes the assignment
really look like an assignment.

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
\\
exp  \> \IS \> lval sel {\tt =} exp \\
\\
lval \> \IS \> lval sel \\
     \> \OR \> exp \\
\\
sel  \> \IS \> {\tt !.} exp        \> {\rm Array I-str} \\
     \> \OR \> \verb|!^| exp       \> {\rm Array M-str store} \\
     \> \OR \> \verb|!^^| exp      \> {\rm Array M-str replace} \\
\end{tabbing}
}

In particular,
\begin{tabbing}
\verb|eA!^^eJ = eV| \hmm \= is equivalent to \hmm \= \verb|mareplace  eA  eJ  eV| \kill
\verb|eA!.eJ  = eV|      \> is equivalent to      \> \verb|iastore    eA  eJ  eV| \\
\verb|eA!^eJ  = eV|      \> is equivalent to      \> \verb|mastore    eA  eJ  eV| \\
\verb|eA!^^eJ = eV|      \> is equivalent to      \> \verb|mareplace  eA  eJ  eV|
\end{tabbing}

% ----------------

\subsection{Sequencing in decl lists}

Haskell:

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decls \> \IS \> decl$_1$ {\tt ;} ... {\tt ;} decl$_n$ \> {\rm $n \ge 0$} \\
\\
decl  \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
      \> \OR \> valdef
\end{tabbing}
}

Extension for pH:

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decl  \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
      \> \OR \> valdef \\
      \> \OR \> {\tt par} \verb"{" decls \verb"}" \\
      \> \OR \> {\tt seq} \verb"{" decls \verb"}"
\end{tabbing}
}

{\tt seq} and {\tt par} are only control constructs; they do not
introduce any new scope.

By default, the top-level decl lists (in {\tt let} and {\tt where}
blocks and loop bodies) are parallel.

% ----------------

\subsection{Layout (``off-side'' rule)}

The layout rule of Haskell allows one to omit braces and semicolons in
a decl list.  Decl lists follow the {\tt where}, {\tt let} and {\tt
of} reservedids.

Extension for pH: The lay-out rule also applies to the decl lists that
follow these new reservedids:
\begin{tabbing}
\hmm \= {\tt do}   \hmmmm  \= (in loops) \\
     \> {\tt seq}          \> (sequenced declarations) \\
     \> {\tt par}          \> (parallel declarations)
\end{tabbing}

% ================================================================

\section{Examples}

\label{sec-examples}

This section shows a number of program fragments so the reader can get
a flavor of the syntax extensions.

% ----------------

\subsection*{Loops}

Integration of a function {\tt f} in the range {\tt x1} to {\tt x2}:
\begin{verbatim}
>    let s = 0.0
>        x = x1
>    in
>        while (x <= x2) do
>           next s = s + f(x)
>           next x = x + delta_x
>        finally s
\end{verbatim}

Factorial of {\tt n}
\begin{verbatim}
>    let  f = 1
>    in
>       for j <- [1..n] do
>          next f = f * j
>       finally f
\end{verbatim}

% ----------------

\subsection*{I-structure cells}

``Open lists'' (related to ``difference lists'' in Prolog):
\begin{verbatim}
>    data  olist a  = ONil | OCons    a    (iCell (olist a))
>
>    is_OCons             :: olist a -> Bool
>    is_OCons  ONil        = False
>    is_OCons  (OCons x y) = True
>
>    grow_olist                   :: olist a -> olist a -> olist a
>    grow_olist  (OCons x y)  ol2  = let
>                                      iStore  y  ol2
>                                    in
>                                      ol2
\end{verbatim}

Tail-recursive ``map'', using open lists:
\begin{verbatim}
>    omap                   ::  (a -> b) -> (olist a) -> (olist b)
>
>    omap  f  ONil           =  ONil
>    omap  f  (OCons x ixs)  =  let
>                                 ys     = OCons  x  (ICell _)
>                                 xs     = iFetch  ixs
>                                 lastys = while (is_OCons xs) do
>                                            OCons x ixs = xs
>                                            next xs     = iFetch ixs
>                                            next ys     = grow_olist  ys
>                                                                      (OCons x (iCell _)
>                                          finally ys
>                                 grow_olist  lastys  ONil
>                               in
>                                 ys
\end{verbatim}

% ----------------

\subsection*{M-structure cells}

Updateable lists
\begin{verbatim}
>    data  mlist a  = MNil | MCons    a    (mCell  (mlist a))
\end{verbatim}

Destructively insert an integer into a sorted list
\begin{verbatim}
>    insert                              :: a -> mlist a -> mlist a
>
>    insert  y  MNil                      = MCons  y  (mCell MNil)
>    insert  y  (MCons x mxs) | y <= x    = MCons  y  (MCons x mxs)
>                             | otherwise = let
>                                               xs'  =  mFetch mxs
>                                               mStore mxs (insert y xs')
>                                           in
>                                               Mcons x mxs
\end{verbatim}

% ----------------

\subsection*{I-structure arrays}

Given an Iarray A of integers, produce an Iarray
B containing all negative numbers followed by all non-negative numbers:
\begin{verbatim}
>    let
>       (l,u) = ibounds a
>       b     = iarray (l,u) []
>       kl    = l
>       ku    = u
>       for j <- [l..u] do
>          (j1, next kl, next ku)  = if (a!.j < 0) then (kl, kl+1, ku)
>                                                  else (ku, kl, ku-1)
>          b!.j1                   = a!.j
>       finally ()
>    in
>       b
\end{verbatim}

% ----------------

\subsection*{M-structure arrays}

Construct a histogram of a tree of numbers in the range 1 to 10:
\begin{verbatim}
>    data  tree = Empty | Node int tree tree
>
>    hist  t   =  let
>                    h = marray (1,10) [ (j := 0) | j <- [1..10]]
>                    traverse  t  h                                    -- for effect
>                 in
>                    h
>
>    traverse  Empty         h  =  ()
>    traverse  (Node j l r)  h  =  let
>                                    traverse  l  h                    -- for effect
>                                    traverse  r  h                    -- for effect
>                                    h!^j = h!^j + 1                   -- atomic incr
>                                  in
>                                    ()
\end{verbatim}
Note: all three statements in the last {\tt let} block execute in parallel.

% ----------------

\subsection*{Sequencing}

In the histogram program above (M-structure arrays), there is a
problem: we should not return the histogram until the traversal is
completed, else a consumer may read an intermediate value of the
histogram.  This can be accomplished using sequencing.

\begin{verbatim}
>    hist  xs  =  let
>                    h  = marray (1,10) [ (j := 0) | j <- [1..10]]
>                    seq  traverse  xs  h
>                         h1 = h
>                 in
>                    h1
\end{verbatim}

% ----------------------------------------------------------------

\section{Commentary}

\label{sec-commentary}

This section is a collection of comments on various aspects of pH, in
no particular order of importance.

% ----------------

\subsection{Comment: compatibility with Haskell}

{\em Will all Haskell programs {\em parse\/} as pH programs?}

Yes, except for the following situation.  Even though functional pH
uses Haskell notation with no changes, the addition of new {\em
reservedid\/}'s means that a normal Haskell program that happened to
use one of these as an ordinary identifier/symbol would have to be
modified.

New {\em reservedid\/}'s:
\begin{quote}
for \hm  while \hm   do \hm  finally \hm  next

par \hm  seq
\end{quote}

\bigskip

{\em Will all Haskell programs {\em run\/} as pH programs?}

This is mainly a termination issue, \ie\ when a program terminates
under both Haskell and pH, both implementations will produce the same
answer.

The termination issue is complicated, and we'd rather not get into it
here.  Briefly:
\begin{itemize}
\item
For a strict implementation of pH: some Haskell programs will deadlock
or not terminate.

\item
For a non-strict implementation of the functional core of pH with a
fair scheduler: all Haskell programs will terminate with the same
answers.

\item
For non-strict implementations of pH without a fair scheduler:
some Haskell programs will not terminate.
\end{itemize}

% ----------------

\subsection{Comment: sequencing}

{\em Why have sequencing at all?  Aren't they meaningless in a functional language?}

In the functional core and the I-structure layer, sequencing is only
important if you wish to control the space complexity (for which, of
course, you have to know something about the underlying
implementation).

With M-structures, sequencing is sometimes necessary to control
determinacy (and even absence of visible errors).

{\em Why sequencing in decl lists, rather than expr lists?}

In Scheme, Lisp and ML, there are typically two kinds of sequencing
constructs.  First, there is sequencing in expression lists: {\tt
(begin e1 ... eN)} in Scheme, {\tt (progn e1 ... eN)} in Lisp and {\tt
(e1;...;eN)} in SML; each contains a list of expressions to be
executed in sequence, and the value {\tt eN} is returned.  Second,
there is sequencing in declarations: {\tt let*} in Scheme and Lisp,
and semicolon-separated declarations in SML.

Both forms are useful, although we have generally found the latter to
be more so, as we often want to bind and use the results of
intermediate expressions in the sequence.  In a sense, our proposal
unifies the two: sequencing is done in decl lists, but a bare
expression is allowed in place of a decl when we don't wish to bind
its result to anything.  However, note that unlike sequenced
declarations in Scheme, Lisp and SML, our proposal does not involve
any new scope rules, \ie\ scoping is entirely orthogonal (controlled
only by the initial {\tt let}).

% ----------------

\subsection{Comment: Parseability}

The grammar, as shown in the proposals above, is almost certainly not
LALR(1).  However, the only place where parsing difficulties may arise
is in decl lists, where we now allow bare expressions in addition to
decls.  We repeat the proposed rule here, for reference:

{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decl \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
     \> \OR \> valdef \\
     \> \OR \> exp                      \> {\rm for effect only} \\
\end{tabbing}
}

In Id, we have been able to handle this as follows.  First, we use the
following grammar instead, which collapses the last three productions
above into one:
{\it
\begin{tabbing}
\tabL \= \tabM \=  \tabR \= \kill
decl \> \IS \> vars {\tt ::} [context {\tt =>}] type \\
     \> \OR \> exp
\end{tabbing}
} and treats ``{\tt =}'' initially as an ordinary infix operator (of
lowest precedence).  When the \mbox{\em decl \IS\ exp} rule is
reduced, the associated semantic action examines {\em exp\/} to see if
it has a ``{\tt =}'' at the toplevel, and fixes up the parse tree
accordingly.

% ----------------

\subsection{Comment: Strictness and semantics of array constructors}

The Haskell {\tt array} constructor function is strict in all the
indices of the array.  This is because {\tt array} has to
\begin{itemize}
\item
Check for out-of-bounds indices, which cause the whole array to go to $\bot$

\item
Check for duplicate indices, which cause that component to go to $\bot$

\end{itemize}

We have changed the semantics of {\tt array} in the interest of
parallelism.  The proposed semantics allows the implementation to
return the array before {\em any\/} index has been computed.

We expect very little practical difference to the programmer.  For an
out-of-bounds index, the programmer will always see an error, both in
Haskell and in pH.  For duplicate indices, the pH programmer will
always see an error.  The Haskell programmer will always see an error
if that component of the array is demanded, and in some
implementations may see that error even if that component of the array
is not demanded.

% ----------------

\subsection{Comment: Loops}

{\em Why introduce loop notation?  Isn't tail recursion enough?}

We make an analogy with list comprehensions, which do not add any
fundamental power to Haskell, but are convenient for certain common
computations on lists involving maps and filters.

Similarly, loops do not add any fundamental power to Haskell/pH, but
they are convenient for certain common computations involving
reductions (folds on lists, folds on arrays, and other reductions).

% ----------------

\subsection{Comment: Polymorphism and I- and M-structures}

{\em Is the Hindley-Milner type system used by Haskell still sound,
with the addition of I- and M-structures?}

No.  I- and M-structures introduce the problem of ``ref types'', which
is also seen in ML.  There are a variety of solutions in the
literature, in existing ML implementations, and in the existing Id
implementation, any of which should carry over directly.
