The M-structure Layer
The final level of pH adds "M-structures" to the functional and I-structure layers. M-structures allow reuse of storage and, thus, arbitrary manipulation of state.

However, the main difference from assignment statements in imperative languages is that access to M-structure data is implicitly synchronized. This has two advantages.

First, it permits more economical expression of shared state manipulation and, second, it can usually be implemented more efficiently. For example, consider many parallel computations that are all updating components of a shared array h. With explicit synchronization (e.g., with threads and locks), each update would be expressed as follows:

wait(locks[j]);
H[j] = f(H[j]);
signal(locks[j]);

In other words, we wait for exclusive access to the j'th component, using a companion array of locks. After performing the update, we release the lock to allow other similar parallel computations to proceed. In pH, we express it as follows:

h!j := f (h !& j)

where the h!j notation means "wait until Full, read, and leave Empty," and the assigment means "write, and make Full."

In addition to simplifying the notation (we don't have to declare an array of locks and explicitly perform waits and signals), the implementation can also be more efficient because of the combined synchronization and data access. For example, in the conventional imperative language code, each of the operations-wait, update h, and signal-is likely to be a separate transaction with memory.

In the M-structure version, the wait and read h can be combined into a single transaction, as can the write h and signal, resulting in two transactions, the minimum possible.

In the functional and I-structure layers, there is no sequencing of operations other than that which is naturally implied by data dependencies. With M-structures, however, sequencing may be necessary to control nondeterminism.

For example, if we want to ensure that a bank deposit computation completes before we perform a withdrawal computation on a shared M-structure, data dependencies are no longer adequate; for this, pH provides ways to explicitly sequence computations.

As discussed earlier in Part 6, several languages such as ML and Scheme also have purely functional cores augmented with operations to manipulate state. However, in those languages, state manipulation comes at the expense of parallelism; unwanted race conditions are made into a nonissue by making the entire language strict and totally sequential.

Of course, many researchers have reintroduced limited, user-specified parallelism by extending these languages with traditional parallel constructs such as threads, locks and message-passing.

Also, as discussed earlier, a recent development in nonstrict functional languages such as Haskell is a technique called monads, which is a way to encapsulate state manipulation. While this is done without making the entire language sequential, the state manipulation operations are still completely sequenced, so that one cannot have a parallel, state-manipulating program.

In pH, on the other hand, despite the addition of M-structures, the overall programming style remains implicitly parallel unless otherwise specified. Unlike other parallel languages which are implicitly sequential unless otherwise specified, the difference is qualitative, but noticeable - implicit parallelism makes it significantly easier to write massively parallel programs.

The parallelism in pH is pervasive. Not only does it occur at a very fine grain (e.g., reading the head and tail fields of a list record proceed in parallel), but also at a larger grain (e.g., two functions or loop iterations can execute in parallel). Both of these are important for parallel computer architectures. The large-grain parallelism allows easy distribution of work across the multiple processors of a parallel machine.

The fine-grain parallelism allows each processor to exploit instruction level parallelism (i.e., the ability to execute instructions of a thread in parallel) and multithreading (i.e., the ability to execute another fine grain thread while one of its fine grain threads has to wait, perhaps to access a datum on a different processor).

We know of no other programming language that exposes as much parallelism as effortlessly as pH.