% -*- Mode: LaTeX -*-

\section{What is pH?}
\label{sec:intro}

pH \cite{pH-doc} is a parallel variant of the Haskell programming
language \cite{Haskell90} with extensions for loops, synchronized
side-effect operations, and explicit sequentialization. This paper
discusses the operational semantics of these variations and
extensions. The concrete syntax of pH is presented in the preliminary
pH manual \cite{pH-doc} and will track future Haskell versions.

There is more than one approach to parallel implementations of
functional languages.  For example, it is possible to exploit the
implicit parallelism of a Haskell program by concurrent evaluation of
the arguments of strict operators.  The absence of side effects
ensures that this concurrent evaluation cannot change the result.
Strictness analysis techniques widen the scope of this idea, by
allowing parallel evaluation of any strict function argument.
Further, it is possible to provide programmer annotations to indicate
sub-expressions which should be evaluated in parallel, even when the
compiler cannot prove that the value of all the sub-expressions will
be required.  Unlike similar annotations in imperative languages, the
annotations can only affect termination, and not the results (if any).
All these approaches take {\em demand-driven\/} evaluation as the
starting point: in the absence of annotations, an expression is
evaluated only if its value is required.

An alternative approach is to use a {\em parallel\/} evaluation order
which reduces all redexes in parallel, not only those whose value is
required.  This strategy also implements non-strict semantics,
provided that no redex has its evaluation delayed indefinitely.  A
parallel evaluation strategy is followed by the Id programming
language \cite{Id90.1}, in which any redex not in the body of a
conditional or lambda abstraction is reduced.  pH follows the same
strategy. A brief description of pH may be given as follows.

\begin{quote}
pH = Haskell syntax and type system + Id evaluation strategy + Id
side-effect operators
\end{quote}

In practice, implementations of pH may not guarantee that every redex
is reduced eventually. This will imply that some pH programs may fail
to give a result and terminate when they would do so in
``traditional'' Haskell.  However, if pH gives a proper (non-error,
non-bottom) result for a particular program then so does
``traditional'' Haskell, and these results are the same.

\subsection{Why pH?}

pH is an attempt to bring together the lazy functional community (as
represented by Haskell) and the dataflow community (as represented by
Id and Sisal \cite{Sisal91}).  It is hoped that by sharing a common
base language, it will be easier to share ideas and implementations
and freely exchange programs.  By doing so, programmers need only
master a single syntax and type system.  There are important
differences between pH and Haskell, however.  By choosing Haskell as a
framework, it becomes easier to isolate and therefore understand the
differences between the two.

\subsection{Structure of pH}

pH is a layered language.  pH(F) is the purely-functional subset of
pH.  Its main addition to Haskell is for- and while-loops.  For
example, one could compute the sum of the integers between 1 and $n$
as follows.

\begin{myexample}{ex:sum}
let sum = 0
 in for i <- [1..n] do 
      next sum = sum + i
    finally sum
\end{myexample}

Loops are purely functional, and can easily be translated into
tail-recursive functions. The eager semantics of pH permits
tail-recursion to be implemented more efficiently than lazy semantics.

pH(I) adds I-structures \cite{Arvind89} to pH(F). I-structures are
{\em single-assignment\/} data structures that allow fine-grain
producer-consumer synchronization among parallel tasks. pH(I)
preserves determinacy, \ie, \ibx{confluence}, although the language is
no longer referentially transparent.

pH(M) adds M-structures \cite{Barth91} to pH(I). M-structures are {\em
multiple-assignment\/} data structures that allow mutual exclusion
synchronization. M-structures introduce side-effects and
non-determinacy. pH(M) also provides the ability to group statements
for sequential execution using {\em barriers\/} in order to avoid
unwanted race conditions among side-effect operations.

Full pH is the same as pH(M).

\subsection{Outline}

The rest of this paper concentrates on semantic issues in which pH
differs from Haskell. \sec{eager} describes the parallel evaluation
order of pH in the context of a kernel language and its multithreaded
interpreter. In \sec{side} we extend the kernel language with
I-structure and M-structure operations. \sec{barrier} defines the
semantics of barriers by translating them into the kernel language
using explicit termination signals from side-effect operations.
Finally, \sec{conclude} concludes with some notes about current
implementations. 
