Semantics of pH: A parallel dialect of Haskell^{∗}

Shail Aditya^{a} MIT

Arvind^{a} ; MIT

Lennart Augustsson^{b} Chalmers University

Jan-Willem Maessen^{a} MIT Rishiyur S. Nikhil^{c} DEC, CRL

Abstract The semantics of kernel pH are defined in the form of a parallel, normalizing interpreter. A description of I-structure and M-structure operators is also given within the same framework. Semantics of barriers in pH are presented by translation into the kernel language without barriers. The framework presented is also suitable for multithreaded compilation of pH.

1 What is pH?

pH [11] is a parallel variant of the Haskell programming language [8] 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 [11] 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 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 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 [10], 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.

∗The research described in this paper was funded in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-92-J-1310.

aMIT Laboratory for Computer Science, Cambridge, MA 02139. Email: {shail,arvind,earwig}@lcs.mit.edu.

bDepartment of Computer Science, Chalmers University, Göteborg, Sweden. Email: augustss@cs.chalmers.se.

cCambridge Research Laboratory, Digital Equipment Corporation, One Kendall Square, Building 700, Cambridge, MA 02139. Email: nikhil@crl.dec.com.

pH = Haskell syntax and type system + Id evaluation strategy + Id side-effect operators

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.

1.1 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 [7]). 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.

1.2 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.

Example 1:

  let sum = 0
   in for i <- [1..n] do
        next sum = sum + i
      finally sum

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 [4] to pH(F). I-structures are single-assignment data structures that allow fine-grain producer-consumer synchronization among parallel tasks. pH(I) preserves determinacy, i.e., confluence, although the language is no longer referentially transparent.

pH(M) adds M-structures [6] to pH(I). M-structures are 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 barriers in order to avoid unwanted race conditions among side-effect operations.

Full pH is the same as pH(M).

1.3 Outline

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

c  ∈ Constant
f, t, x, y, z …  ∈ Identifier
SE, X, Y, Z, … ∈ Simple Expression
E  ∈ Expression
PF^{n}  ∈ Primitive Fn. with n arguments
CF^{n}  ∈ Data Constructor with n arguments
S  ∈ Statement
Constant  ::= Integer | Float | Boolean | Nil
SE  ::= Identifier | Constant

PF^{1}  ::= hd | tl | select k

PF^{2}  ::= + | − | ⋯ |<|>| ⋯
CF^{2}  ::= Cons

CF^{n}  ::= make n tuple

E  ::= SE | PF^{n}(x_{1}, …, x_{n}) | CF^{n}(x_{1}, …, x_{n})

| λx. E | case(x, E_{1}, …, E_{n}) | ap(f, z) | sap(f, z) | Block

Block  ::= { S in x }
S  ::= ϵ | x = E | S_{1}; …; S_{n}
Program  ::= Block

Figure 1: The kernel pH language.

2 Parallel Evaluation Order

pH follows an eager evaluation strategy: all tasks execute in parallel, restricted only by the data dependencies among them. This strategy automatically exposes large amounts of parallelism both within and across procedures. This is in contrast with a lazy evaluation strategy followed by Haskell: only those tasks are evaluated which are required to produce the result. This strategy imposes a sequential constraint on the overall computation, although the exact ordering of tasks is decided dynamically.

In this section we describe the eager evaluation model of pH by giving a parallel interpreter for the kernel language of pH. Our interpreter is based on a parallel abstract machine, which is in the spirit of the G-machine and its later variants [9, 5, 12]. We first describe the kernel language (Section 2.1) and then our parallel abstract machine (Section 2.2) and its instruction set (Section 2.3). It is followed by a description of the interpreter (Section 2.4).

2.1 The Kernel pH Language

The abstract syntax of the kernel pH language is shown in Figure 1. The kernel language ensures that every intermediate result of a complex expression is explicitly named using an identifier. This is convenient for expressing and preserving the sharing of subexpressions within a computation [3]. In order to simplify the description of the evaluation rules in this paper, we do not allow constants to appear as arguments to primitive functions.

Aside from the usual arithmetic primitives, the kernel language provides functions for constructing and selecting elements of lists and n-ary tuples. The language also provides n-ary case

ι ∈ Instruction
ℓ ∈ Location
ν ∈ Value  ::= Constant | Location | ⟨λx. E, ρ⟩
ρ ∈ Environment Frame = Identifier → Location
σ ∈ Store  = Location → {⟨full ν⟩ | ⟨defer δs⟩}
ω ∈ Thread  = Code × Environments
δ ∈ Suspension  = Thread
δs ∈ Suspensions  = List(Thread)
ωs ∈ Work Queue  = List(Thread)
Accumulator  = Value
ιs ∈ Code  = List(Instruction)
ρs ∈ Environment  = List(Environment Frame)
Processor  = Accumulator × Code × Environment
Machine  = List(Processor) × Work Queue × Store
Processor  Global Memory
State  Accumulator Code Environment Work Queue Store

Initial (starting proc.)

ιs_{0}

[ ]  [ ]  {}
Initial (other proc.)  [ ]  [ ]  [ ]  {}
Final (all proc.)  [ ]  [ ]  [ ]  σ

Error (any proc.)

                             storerr

ιs

ρs

ωs

σ

Where ιs_{0} = [eval(Program), print, schedule]

Figure 2: Dynamic entities used by the abstract machine.

expressions which select one of the branches based on the value of the dispatch identifier, nested λ-expressions which may contain free identifiers, a general function application operator ap, and a parallel block construct that controls lexical scoping and enables precise sharing of subexpression values. The order of bindings in a block is not significant. The identifier following the in keyword in a block expression denotes the result of the block.

2.2 A Parallel Abstract Machine

Our parallel abstract machine consists of a number of sequential processors connected to a global shared memory. The important features of our machine are described in Figure 2. Each memory location can hold a value or a list of suspended threads, and is tagged with its status. A full location contains a value. A newly allocated location is tagged with defer and it is initialized to be empty. A value is either a constant, an allocated store location, or a function closure. The global memory holds three types of entities: heap storage, activation frames and a work queue which is a list of threads, that is, (code, environment) pairs.

The processor state consists of code, environment, and an accumulator which can hold a value. Any idle processor can get work by dequeuing a thread from the work queue and loading its code and environment space from the thread. Initially, it is assumed that the whole machine is empty. A program E is started by executing the following code on some processor in the empty environment.

[eval(E), print, schedule]

The eval instruction interprets an expression by structural decomposition in a given environment. Environments map program identifiers to frame locations, and are structured in a stack like manner. eval of a block allocates a new activation frame in the global memory to store the values of the bound identifiers of the block. It also creates a new environment frame for these identifiers and pushes it on the processor environment. The bound identifiers of the block point to locations in the newly allocated activation frame. New environment frames (but not activation frames) are also created in case of λ-expressions and function applications. The sharing of computations is achieved entirely through the activation frame locations: all references to an identifier within the scope of its definition lead to the same frame location. The separation of environment frames and activation frames permits environments to be copied freely and therefore allows us to treat function closures in the same way as simple values.

At each step, the processor executes the instruction at the head of the current code sequence, modifying the processor state in the process. The instruction set of the processor has instructions to load and store the accumulator, perform arithmetic and logic operations on store locations, and suspend the current thread in case of missing values. This is in contrast with lazy functional languages where unevaluated locations contain thunks that compute its value on-demand. Typically an instruction is popped from the code sequence after execution, but some instructions may also add new instructions to the code sequence. This is the primary way to alter the control flow. There are also instructions to push and pop environment frames, and enqueue and dequeue threads from the work queue.

The work queue is maintained as a FIFO queue in order to guarantee fair scheduling. This queue must be manipulated atomically. It is easy to modify the machine so that each processor has its own work queue which is maintained in a FIFO manner. In case a processor goes idle, it can pick up a thread from the back of the work queue of any other processor. As long as we do not arbitrarily suspend the currently running thread on any processor, this strategy still implements a fair schedule while considerably reducing the contention due to the atomic manipulation of the work queue.

The overall state of our parallel machine is described by the state of all the processors and the global memory and the work queue. Figure 2 also shows the initial, the final and the error states of the processors of our machine. The machine starts by scheduling an initial sequence of instructions on some processor that evaluates the program, prints the result present in the accumulator^{1}, and then continues to schedule the remaining work present in the work queue. This emphasizes the non-strict nature of this evaluation model: the program may print a result before final termination. The machine halts when both the code sequence and the work queue are empty. The machine is said to be deadlocked when there are suspended computations in the store but there is no work to be done. If there are no suspended computations, then the machine is said to have terminated normally. An error may be generated during execution due to exceptional conditions such as a type mismatch, an arithmetic overflow, or out of bounds access to data structures. However, if an attempt is made to write into a memory location that is already full then the whole machine is said to have reached an error state as shown in Figure 2.

2.3 Instruction Set

Figure 3 shows the instructions used by our interpreter. We will describe the semantics of these instructions in terms of a state transition involving a 5-tuple (ν, ιs, ρs, ωs, σ). The first three eval(E) :: Evaluate E in the current environment and leave the result in the

1The main thread is the only place where a print instruction may appear.

accumulator

touch(ℓ)  :: Check if the location ℓ is full, if not suspend the current thread

rtouch(ℓ) :: Check if the location ℓ is full, if not suspend the current thread including the rtouch instruction. (Thus, rtouch can be retried when the thread is activated again).

load(ℓ) :: Load the accumulator with the value present in the location ℓ (the

location must be full)

take(ℓ) :: Load the accumulator with the value present in the location ℓ and

mark the location empty (the location must be full)

loadi k(ℓ) :: Load the accumulator with the value in the location at an offset k from the location pointed to by ℓ, or suspend the thread if the location is empty

store(ℓ) :: Store the value in the accumulator in the location ℓ and reactivate

any suspensions

storerr(ℓ)  :: Generate an error if the location ℓ is full

PF^{n}(ℓ_{1}, …, ℓ_{n}) :: Apply strict primitive operator PF^{n} (such as +) to the values at

locations ℓ_{1}, …, ℓ_{n} (the locations must be full)

switch(ℓ_{x}, ιs_{1}, …, ιs_{n}) :: Switch to the branch indexed by the value at location ℓ_{x}
pushenv(ρ)  :: Push the environment frame ρ onto the environment stack
popenv  :: Pop the top-level environment frame from the environment stack
schedule  :: Schedule the next thread from the work queue
print  :: Print the accumulator contents

Figure 3: The instruction set of the parallel abstract machine.

elements of the tuple refer to the accumulator carrying a value ν, the code sequence ιs, and the environment ρs on the processor where the instruction is executed. The last two elements of the tuple are the work queue ωs, and the dynamic store σ which are shared amongst all processors.

All the instructions that modify the global store must be executed atomically. That is, while a processor reads and modifies a given location within the store, no other processor should be allowed to read or write that location. Transactions on different locations may proceed in parallel. In case where an instruction sequence ιs has to be executed atomically, we will indicate that by writing atomic(ιs).

Touch Instructions

The touch instruction tests the status of a location. If the status is full, it does nothing. Otherwise, (status is defer) the code sequence following the current instruction is suspended at that location along with the current environment. The rtouch instruction is similar except that the touch operation is retried. touch:

\frac{⟨ touch(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨full ν⟩]⟩}{⟨ ιs ρs ωs σ⟩}

\frac{⟨ touch(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨defer δs⟩]⟩}{⟨ [schedule] ρs ωs σ[ℓ ↦ ⟨defer (ιs, ρs) : δs⟩]⟩}

rtouch:

\frac{⟨ rtouch(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨full ν⟩]⟩}{⟨ ιs ρs ωs σ⟩}

\frac{⟨ rtouch(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨defer δs⟩]⟩}{⟨ [schedule] ρs ωs σ[ℓ ↦ ⟨defer (rtouch(ℓ) : ιs, ρs) : δs⟩]⟩}

Note that these instructions do not start the evaluation of the expression that will fill the location being touched. In lazy evaluation this expression is always known and a thunk for it can be stored in this location. In that case, the above instructions can be easily generalized to enqueue the thunk into the work queue.

Load and Store Instructions

The load instruction loads the contents of a given location into the accumulator. The location must already be full. The take instruction is similar to load except that it leaves the location empty.

load:

\frac{⟨ load(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨full ν⟩]⟩}{⟨ν ιs ρs ωs σ⟩}

take:

\frac{⟨ take(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨full ν⟩]⟩}{⟨ν ιs ρs ωs σ[ℓ ↦ ⟨defer [ ]⟩]⟩}

loadi k is an indexed, indirect load instruction. It desugars into touching an indexed location and then loading its value into the accumulator.

loadi k:

\frac{⟨ loadi k(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ℓ⟩]⟩}{⟨ touch(ℓ + k) : load(ℓ + k) : ιs ρs ωs σ⟩}

The store instruction stores the contents of the accumulator into the given location. It also reactivates any suspensions waiting in the location by enqueuing them in the work queue.

store:

\frac{⟨ν store(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨defer δs⟩]⟩}{⟨ν ιs ρs ωs ++ δs σ[ℓ ↦ ⟨full ν⟩]⟩}

Storing in a location that is already full is regarded as an error. The storerr instruction tests the status of a location and produces an error if it is already full. This instruction can precede a store instruction to avoid multiple stores to the same location. storerr:

\frac{⟨ storerr(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨full ν⟩]⟩}{⟨storerr ιs ρs ωs σ⟩}

\frac{⟨ storerr(ℓ) : ιs ρs ωs σ[ℓ ↦ ⟨defer δs⟩]⟩}{⟨ ιs ρs ωs σ⟩}

Arithmetic and Logic Instructions

The standard arithmetic and logic primitives are straightforward. All of them leave the result in the accumulator. +:

\frac{⟨ +(ℓ_{1}, ℓ_{2}) : ιs ρs ωs σ[ℓ_{1} ↦ ⟨full \underline{m}⟩, ℓ_{2} ↦ ⟨full \underline{n}⟩]⟩}{⟨\underline{m + n} ιs ρs ωs σ⟩}

Switch Instruction

The switch instruction selects one of its branches based on the value present in the location being dispatched upon. switch (1 ≤ m ≤ n):

\frac{⟨ switch(ℓ_{x}, ιs_{1}, …, ιs_{n}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full \underline{m}⟩]⟩}{⟨ ιs_{m} ++ ιs ρs ωs σ⟩}

Environment Manipulation Instructions

The pushenv instructions pushes the given environment frame onto the local environment stack of a processor, while the popenv instruction pops one frame from the top. The contents of the accumulator are not disturbed while popping. pushenv:

\frac{⟨ pushenv(ρ) : ιs ρs ωs σ⟩}{⟨ ιs ρ : ρs ωs σ⟩}

popenv:

\frac{⟨ν popenv : ιs ρ : ρs ωs σ⟩}{⟨ν ιs ρs ωs σ⟩}

Thread Scheduling Instruction

The execution of a schedule instruction on a processor signifies either the termination or the suspension of a thread. The processor schedules a new thread from the head of the work queue or starts idling if the work queue is empty. The machine halts when all processors are idling. schedule:

\frac{⟨ [schedule] ρs (ιs′, ρs′) : ωs σ⟩}{⟨ ιs′ ρs′ ωs σ⟩}

\frac{⟨ [schedule] ρs [ ] σ⟩}{⟨ [ ] ρs [ ] σ⟩}

2.4 Expression Evaluation

In this section we describe the eval instruction which is used to destructure and evaluate expressions. It leaves the value of the expression in the accumulator.

Evaluation of a constant simply loads that constant into the accumulator.

eval constant:

\frac{⟨ eval(c) : ιs ρs ωs σ⟩}{⟨c ιs ρs ωs σ⟩}

Evaluation of an identifier first touches it and then loads its value in the accumulator. eval identifier:

\frac{⟨ eval(x) : ιs ρs ωs σ⟩}{⟨ touch(ρs(x)) : load(ρs(x)) : ιs ρs ωs σ⟩}

In case of a strict primitive function, we touch all its arguments before executing the primitive application.

eval strict PF:

\frac{⟨ eval(PF^{n}(x_{1}, …, x_{n})) : ιs ρs ωs σ⟩}{⟨ touch(ρs(x_{1})) : …: touch(ρs(x_{n})) : PF^{n}(ρs(x_{1}), …, ρs(x_{n})) : ιs ρs ωs σ⟩}

All data selector functions such as hd, tl, and select k are directly implemented using the indexed, indirect load instruction loadi k.

The non-strict constructor Cons allocates a pair of empty locations in the store and immediately returns the pointer to the first location as its value. It also pushes work into the work queue to evaluate the arguments of Cons and to fill these locations eagerly. The n-ary tuple constructor make n tuple operates in the same fashion. Note that under lazy evaluation we would have stored thunks into these locations which would be evaluated on demand. eval Cons:

\frac{⟨ eval(Cons(x_{1}, x_{2})) : ιs ρs ωs σ⟩}{⟨ℓ ιs ρs ωs ++ [ω_{1}, ω_{2}] σ′⟩}

where σ′ = σ + { ℓ ↦ ⟨defer [ ]⟩, (ℓ + 1) ↦ ⟨defer [ ]⟩ } ω_{1} = ([eval(x_{1}), store(ℓ), schedule], ρs) ω_{2} = ([eval(x_{2}), store(ℓ + 1), schedule], ρs)

λ-expressions are evaluated to a closure value. The closure records the locations for the free identifiers of the λ-body in a new environment frame.

eval λ-expression:

\frac{⟨ eval(λx.E) : ιs ρs ωs σ⟩}{⟨⟨λx. E, ρ⟩ ιs ρs ωs σ⟩}

where \begin{matrix}y_{1}, …, y_{m} = FV (λx.E) \\ ρ = \{ y_{1} ↦ ρs(y_{1}), …, y_{m} ↦ ρs(y_{m}) \} \end{matrix}

Evaluation of a function application proceeds by first touching the function and then applying the resulting closure to the argument. The function argument is touched prior to application only if the function application is strict (sap). eval ap:

\frac{⟨ eval(ap(f, z)) : ιs ρs ωs σ⟩}{⟨ touch(ρs(f)) : ap(ρs(f), ρs(z)) : ιs ρs ωs σ⟩}

eval sap:

\frac{⟨ eval(sap(f, z)) : ιs ρs ωs σ⟩}{⟨ touch(ρs(f)) : touch(ρs(z)) : ap(ρs(f), ρs(z)) : ιs ρs ωs σ⟩}

Given a closure, the ap instruction extends the closure environment frame with the given argument location and starts the evaluation of the function body after pushing the new environment frame onto the current environment. The old environment is restored after the evaluation of the body produces a result in the accumulator^{2}. ap:

\frac{⟨ ap(ℓ_{f}, ℓ_{z}) : ιs ρs ωs σ[ℓ_{f} ↦ ⟨full ⟨λx. E, ρ⟩⟩]⟩}{⟨ pushenv(ρ′) : eval(E) : popenv : ιs ρs ωs σ⟩}

where ρ′ = ρ + { x ↦ ℓ_{z} }

The evaluation of the case expression proceeds by first touching the dispatch expression. This must yield an integer within the range of the dispatch which is used to select the appropriate branch. eval case:

\frac{⟨ eval(case(x, E_{1}, …, E_{n})) : ιs ρs ωs σ⟩}{⟨ touch(ρs(x)) : switch(ρs(x), [eval(E_{1})], …, [eval(E_{n})]) : ιs ρs ωs σ⟩}

The evaluation of a block expression allocates a new activation frame in the store with a fresh location for each bound identifier of the block. It also allocates new environment frame which points to the locations in the new activation frame. This environment frame is pushed onto the current environment. Following eager evaluation, auxiliary threads are added to the work queue to evaluate each of the right-hand side expressions in the extended environment. The result identifier is also evaluated under this extended environment. eval block:

\frac{⟨ eval(\{ x_{1} = E_{1}; …; x_{n} = E_{n} in x \}) : ιs ρs ωs σ⟩}{⟨ pushenv(ρ) : eval(x) : popenv : ιs ρs ωs ++ ωs′ σ′⟩}

where ρ = { x_{1} ↦ ℓ_{1}, …, x_{n} ↦ ℓ_{n} } σ′ = σ + { ℓ_{1} ↦ ⟨defer [ ]⟩, …, ℓ_{n} ↦ ⟨defer [ ]⟩ } ωs′ = [([eval(E_{1}), store(ℓ_{1}), schedule], ρ : ρs), ⋯ ([eval(E_{n}), store(ℓ_{n}), schedule], ρ : ρs)]

It is also possible to initialize the newly allocated block locations with the thunks for their respective right-hand side expressions, and not enqueue threads into the work queue. These thunks will be enqueued when the locations are touched.

3 Side-Effect Operations

Functional programming languages purposely do not permit assignment or mutable storage. Instead, such features are often offered through various implementation tricks such as by using

2Note that restoring the environment does not imply that the function environment can be deallocated because some threads of the function body may not have terminated yet.

Constant ::= ⋯ | •

                PF^{1}  ::= · · · | iAlloc | mAlloc | iFetch | mFetch | W
                PF^{2}  ::= · · · | iStore | mStore | &

S  ::= ⋯ | (S_{1} --- S_{2})

Figure 4: Kernel language extensions for side-effect operations.

monadic programming techniques. Alternatively, side-effects may be introduced via the traditional assignment operator after specifying a precise sequential ordering on all operations (e.g., Scheme and ML). Id, motivated by concerns for parallelism, offers yet another alternative for incorporating side-effects. In Id, it is possible to specify only a partial order on side-effect operations and still retain an overall consistent picture of the computation.

pH supports imperative operations on I-structure [4] and M-structure [6] objects. I-structures allow the creation of a data structure to be separated from the definition of its components: attempts to use the value of a component are automatically delayed until that component is defined; attempts to redefine a component lead to an error state. M-structures, on the other hand, are fully mutable data structures whose components can be redefined repeatedly: an mFetch operation reads and empties a full component; an mStore operation (re)defines it; two successive mStore operations on the same component lead to an error state unless separated by an mFetch operation.

For some programs in pH we need a way to sequentialize M-structure operations in order to avoid race conditions implied by its parallel evaluation order. This is accomplished by the use of control regions and barriers [2]. A control region is informally defined as a set of concurrent threads that are under the same control dependence and therefore always execute together. Threads within the same control region may execute in any order or in an interleaved manner as long as the data dependencies among them are respected. Barriers provide a mechanism to detect the termination of a set of parallel activities enclosed within a control region. A barrier (---) creates two sub-regions within a given control region — one above the barrier called the pre-region and the other below the barrier called the post-region. Intuitively, no computation within the post-region is allowed to proceed until all the side-effect computations within the pre-region have terminated. This semantics is different from those proposed in [2] where a barrier waits for the termination of all computations rather than just those which cause side-effects.

In the rest of this section we describe the pH extensions to deal with I-structure and M-structure operations. The semantics of barriers is described in Section 4.

3.1 Kernel Language Extensions

We extend the kernel language to incorporate side-effect operations and barriers as shown in Figure 4. We add primitives to allocate, read, and write I-structures and M-structures. The fetch and store operations directly address store locations: indexed addressing is handled separately in the kernel language.

We also extend the syntax for block bindings to allow barriers—two sets of parallel block bindings may now be sequentialized by using a barrier (---) between them. Additional constants (•), primitive operators (W and &) and strict function application (sap) are used to translate barriers into an ordinary set of bindings.

3.2 Evaluation Rules for Side-Effect Operations

In this section we describe additional evaluation rules for internal primitive operators involving I-structures, M-structures, and barriers. All these operators are strict on all their inputs.

I-structure Instructions

The iAlloc instruction allocates an empty I-structure array. The iFetch and iStore instructions address an I-structure location directly; all address arithmetic must be done separately. The iFetch instruction is similar to loadi k. The iStore instruction updates an empty location with a value and reactivates any suspended continuations. Storing to an already full location is considered to be an error. iAlloc:

\frac{⟨ iAlloc(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full \underline{n}⟩]⟩}{⟨ℓ ιs ρs ωs σ′⟩}

where σ′ = σ + { ℓ ↦ ⟨defer [ ]⟩, …, (ℓ + n − 1) ↦ ⟨defer [ ]⟩ }

iFetch:

\frac{⟨ iFetch(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ℓ⟩]⟩}{⟨ touch(ℓ) : load(ℓ) : ιs ρs ωs σ⟩}

iStore:

\frac{⟨ iStore(ℓ_{x}, ℓ_{z}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ℓ⟩]⟩}{⟨ atomic([storerr(ℓ), load(ℓ_{z}), store(ℓ)]) : ιs ρs ωs σ⟩}

M-structure Instructions

The mAlloc and mStore instructions are identical to the corresponding instructions for I-structures. The mFetch instruction is similar to the iFetch except that it empties the location being accessed and has to be retried if the location is already empty.

mAlloc:

\frac{⟨ mAlloc(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full \underline{n}⟩]⟩}{⟨ℓ ιs ρs ωs σ′⟩}

where σ′ = σ + { ℓ ↦ ⟨defer [ ]⟩, …, (ℓ + n − 1) ↦ ⟨defer [ ]⟩ }

mFetch:

\frac{⟨ mFetch(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ℓ⟩]⟩}{⟨ atomic([rtouch(ℓ), take(ℓ)]) : ιs ρs ωs σ⟩}

mStore:

\frac{⟨ mStore(ℓ_{x}, ℓ_{z}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ℓ⟩]⟩}{⟨ atomic([storerr(ℓ), load(ℓ_{z}), store(ℓ)]) : ιs ρs ωs σ⟩}

4 Semantics of M-Barriers

In this section we describe the semantics of barriers by translating them into ordinary block bindings. The idea is to systematically construct a composite termination signal from all the side-effect

Expressions

TE  :: Expression → Expression
TE[[c]]  = c, •
TE[[x]]  = x, •
TE[[mFetch(x)]]  = { y = mFetch(x);

in y, W(y) }

TE[[mStore(x, z)]]  = { y = mStore(x, z);

in y, W(y) }

TE[[PF^{n}(x_{1}, …, x_{n})]]  = PF^{n}(x_{1}, …, x_{n}), •
TE[[λx. E]]  = λx. TE[[E]], •
TE[[case (x, E_{1}, …, E_{n})]] = case (x, TE[[E_{1}]], …, TE[[E_{n}]])
TE[[ap(f, x)]]  = ap(f, x)
TE[[{ S in x }]]  = { S′ in x, s }

where S′, s = TS[[S]]

Statements

TS[[]]  :: Statement → List(Statement) × Identifier
TS[[ϵ]]  = (s = •), s
TS[[x = E]]  = (x, s = TE[[E]]), s
TS[[S_{1}; …; S_{n}]]  = (S′_{1}; …; S′_{n}; s = s_{1} & ⋯ & s_{n}), s

where S′_{i}, s_{i} = TS[[S_{i}]] 1 ≤ i ≤ n

TS[[S_{1} --- S_{2}]]  = (S′_{1};

f = λs.{ S′_{2} in y_{1}, …, y_{m}, s_{2} }; y_{1}, …, y_{m}, s′_{2} = sap(f, s_{1})), s′_{2}

where \begin{aligned}S′_{i}, s_{i} & = & TS[[S]] 1 ≤ i ≤ 2 \\ y_{1}, …, y_{m} & = & BV (S_{2}) \end{aligned}

Figure 5: Semantics of M-barriers.

operations taking place within the pre-region of a barrier (including its child regions) which would then be used to trigger the operations present in the post-region of the barrier. The notion of signal generation and composition may be understood by looking at the translation of a simple parallel block as shown below.

\begin{matrix}TE[[ \{ x_{1} = E_{1}; \\ ⋯ \\ x_{n} = E_{n}; \\ in x \} ]] \end{matrix} = \begin{matrix}\{ x_{1}, s_{1} & = & TE[[E_{1}]]; \\ ⋯ \\ x_{n}, s_{n} & = & TE[[E_{n}]]; \\ in x, s_{1} & ⋯ & s_{n} \} \end{matrix}

An expression E_{i} is translated as TE[[E_{i}]] which dynamically returns a value (bound to x_{i}) along with an explicit termination signal s_{i}. The operator W is used to detect the termination of each side-effect operation (mFetch and mStore) within E_{i}. The value of s_{i} would become • as soon as all the side-effect operations in E_{i} have terminated. The operator & is then used to combine all such signals into a single signal for the whole block.

The primitive W operator produces a signal • when a given identifier becomes a value. The general evaluation rule for strict primitive functions would ensure that the identifier being tested is touched before applying the W operator. Similarly, the primitive & operator is used to combine signals from two subexpressions into one signal after they have been touched.

W: ; \frac{⟨ W(ℓ_{x}) : ιs ρs ωs σ[ℓ_{x} ↦ ⟨full ν⟩]⟩}{⟨• ιs ρs ωs σ⟩}

&:

\frac{⟨ &(ℓ_{1}, ℓ_{2}) : ιs ρs ωs σ[ℓ_{1} ↦ ⟨full •⟩, ℓ_{2} ↦ ⟨full •⟩]⟩}{⟨• ιs ρs ωs σ⟩}

The complete barrier translation appears in Figure 5. Note that tuple return values and nonrefutable pattern matching is used only for clarity—these operations are directly desugared into primitive operators in the obvious way. The only non-trivial base cases for signal generation are those for the mFetch and mStore primitive operators. The mFetch operation is considered to have terminated when the value of the location being fetched is returned. Similarly, the mStore operation is considered to have terminated when it returns the value being stored.

In the translation of S_{1} --- S_{2}, note that S_{2} gets protected by a λ-expression, so that it does not get evaluated until the λ-expression is applied to something. That something is the termination signal of S_{1}, and we use sap to ensure that the application does not commence until the termination signal is available. Finally, since the bound variables of S_{2} have now gone into an inner scope (in the λ-expression), we return them all and rebind them again in the outer scope.

The barrier semantics shown here are different from the semantics presented in [2] in that here we are concerned only with the termination of the side-effect operations present within the preregion of a barrier, while the semantics presented in [2] waited for the termination of the entire computation within the pre-region.

5 Conclusion

In this paper we have presented the various semantic issues in the design of pH at which it differs from or extends the Haskell programming language. The major difference is that pH uses a parallel eager evaluation strategy as opposed to the lazy evaluation strategy of Haskell. First, we described the kernel pH language and a normalizing interpreter for it that implements this parallel evaluation order. Next, we extended the language and the interpreter with synchronizing side-effect operations, I-structures and M-structures. Finally, we described a notion of sequentialization of side-effects using barriers. We showed a systematic translation of a kernel pH program with barriers into one without barriers using primitive termination detection operators.

The readers may note that our interpreter used an explicit instruction stream rather than directly evaluating kernel language expressions. This organization allows us to define a multithreaded compilation scheme for the kernel language within the same framework. The process of compilation can be defined as simply generating all the threads statically instead of manipulating the instruction stream dynamically. It essentially gets rid of the eval instruction. Such a compilation scheme for the kernel language is described in [1].

Currently, there is a working implementation of the pH language using the Haskell/pH HBCC front-end (written in Haskell) from Chalmers University and the Id compiler Monsoon back-end (written in Lisp) from MIT. The HBCC front-end produces a kernel pH intermediate format that is converted into dataflow graphs and fed into the Monsoon back-end. Currently, we have exercised this compiler with purely functional Haskell programs or pH programs derived by automatically transliterating Id programs. At MIT, we are currently working on a new pH back-end for commercial uniprocessor and multiprocessor architectures that is closer in spirit to the interpretation scheme described in this paper.

References

[1] Shail Aditya. Normalizing Strategies for Multithreaded Interpretation and Compilation of Non-Strict Languages. CSG Memo 374, MIT Laboratory for Computer Science, Cambridge, MA 02139, May 1995.

[2] Shail Aditya, Arvind, and Joseph E. Stoy. Semantics of Barriers in a Non-Strict, Implicitly-Parallel Language. In Proc. Functional Programming Languages and Computer Architecture, La Jolla, CA, Cambridge, MA 02139, June 1995. Also available as CSG Memo 367-1, MIT Lab. for Computer Sc., Cambridge, MA 02139.

[3] Zena M. Ariola and Arvind. Properties of a First-order Functional Language with Sharing. CSG Memo 347-1, Laboratory for Computer Science, MIT, Cambridge, MA 02139, June 1994. To appear in Theoretical Computer Science, September 1995.

[4] Arvind, Rishiyur S. Nikhil, and Keshav K. Pingali. I-Structures: Data Structures for Parallel Computing. ACM Transactions on Programming Languages and Systems, 11(4):598–632, 1989.

[5] Lennart Augustsson and Thomas Johnsson. Parallel Graph Reduction with the < ν, G >- machine. In Proc. Fourth Intl. Conf. on Functional Programming Languages and Computer Architecture, London, pages 202–213. ACM Press, September 1989.

[6] Paul S. Barth, Rishiyur S. Nikhil, and Arvind. M-Structures: Extending a Parallel, Non-Strict, Functional Language with State. In Proc. Functional Programming Languages and Computer Architecture, pages 538–568. Springer-Verlag, 1991. LNCS 523.

[7] A. P. W. Böhm, D. C. Cann, J. T. Feo, and R. R. Oldehoeft. SISAL 2.0 Reference Manual. Technical Report UCRL-MA-109098, Lawrence Livermore National Laboratory, December 1991.

[8] Paul Hudak, Simon Peyton Jones, and Philip Wadler (editors). Report on the Programming Language Haskell: A Non-strict Purely Functional Language, Version 1.2. ACM SIGPLAN Notices, 27(5), May 1992.

[9] Thomas Johnsson. Efficient Compilation of Lazy Evaluation. Proc. ACM SIGPLAN ’84 Symposium on Compiler Construction, SIGPLAN Notices, 19(6):58–69, June 1984.

[10] Rishiyur S. Nikhil. Id Language Reference Manual Version 90.1. Technical Report CSG Memo 284-2, Laboratory for Computer Science, MIT, Cambridge, MA 02139, July 15 1991.

[11] Rishiyur S. Nikhil, Arvind, James Hicks, Shail Aditya, Lennart Augustsson, Jan-Willem Maessen, and Yuli Zhou. pH Language Reference Manual, Version 1.0—preliminary. CSG Memo 369, Laboratory for Computer Science, MIT, Cambridge, MA 02139, January 1995.

[12] Simon L. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine. Journal of Functional Programming, 2(2):127–202, April 1992.

τ  ∈ Threadmap = Identifier → Code
α ∈ Identmap = Identifier → (Integer × Integer)
ρ  ∈ Environment = (Integer × Integer) → Location
TExp[[ ]] :: Expression → Identmap → (Code × Threadmap)
Compilation: (ιs_{0}, τ) = TExp[[Program]] { }

Figure 6: Compile-time Objects.

A Compilation of Kernel pH

The compilation process involves separating program control from the data it manipulates at runtime. Essentially, this involves a systematic elimination of all eval instructions from the program, replacing them with compiled sequences of low-level instructions that compute the values of the original expressions. We also need to define the layout of environments and the mapping from identifier names to environment slots at compile-time.

In this section we will define a compiler for kernel pH programs based on the same machinery as described in Section 2. Instead of dynamically generating and interpreting code sequences as in Section 2, we will now generate a fixed set of code sequences called threads at compile-time. The compiler is defined in three phases: first, we describe the extensions to the abstract machine and its instruction set; next, we describe the compilation scheme for the source program transforming them into a collection of threads; and finally, we describe how these code sequences are executed on the abstract machine by giving additional execution rules for the new instructions.

A.1 Compilation Machinery

The semantic categories and translation functions used during compilation are shown in Figure 6 and are discussed below.

Every program expression bound to an identifier is compiled into a single primary thread that computes the value of that identifier. Other identifiers bound within that computation give rise to their own threads that are collected into a compile-time mapping from identifiers to threads (τ). The precise compilation rule for each source language construct appear in Section A.2.

The run-time environment mapping from identifier names to locations is split into two mappings: one compile-time mapping (α) from identifier names to a pair of index offsets ⟨i, j⟩ into the current environment stack, and another run-time mapping (ρ) from index-offset pairs to locations. The first index i in a pair ⟨i, j⟩ refers to the position of the environment frame from the top of the current environment stack (zero based). The second index j gives the offset within that frame (zero based) that carries the store location for that identifier.

During compilation, we may sometimes need to refer to some of the components of the current machine state. We use ◇ for the accumulator and stack for the environment stack.

Finally, the additional machine instructions are shown in Figure 7. The detailed explanations appear along with the execution rules given in Section A.3.

loadc(c)  :: Load a constant into the accumulator
makeclsr(ιs, ρ)  :: Make a closure for the thread ιs with the environment ρ
apply(⟨i_{f}, j_{f}⟩ , ⟨i_{z}, j_{z}⟩)  :: Apply the closure f to the argument z

pushwork(ιs, ρs) :: Make and push work with the thread ιs, and the environment

stack ρs

copyenv(⟨i_{0}, j_{0}⟩ … ⟨i_{n−1}, j_{n−1}⟩) :: Allocate an environment using existing identifier locations
allocenv(\underline{n})  :: Allocate an environment with n new identifier locations

Figure 7: Additional Compiler Instructions.

A.2 Compilation Rules

In this section we describe the compilation process of kernel language expressions into a collection of threads.

Constants

An immediate constant is simply loaded into the accumulator.

TExp[[c]] α = [loadc(c)], ϕ

Identifiers

An identifier reference compiles into a sequence of touch and load instructions that touch the preassigned environment slot and load its value into the accumulator.

TExp[[x]] α = [touch(α(x)), load(α(x))], ϕ

Primitive Functions

For strict primitives, we first touch their arguments and then apply the primitive function. The identifier translation gives the precise coordinates of each argument being applied to the primitive function.

TExp[[PF^{n}(x_{1} … x_{n})]] α = [touch(α(x_{1})), …, touch(α(x_{n})), PF^{n}(α(x_{1}), …, α(x_{n}))], ϕ

Data selector functions such as hd,tl and select k are implemented using the indirect load instruction loadi k.

TExp[[select k(x)]] α = [touch(α(x)), loadi k(α(x))], ϕ

The Cons operator is no longer considered as a primitive for compilation purposes. It is desugared into a block of statements that allocate an I-structure and fill it as shown below.

Cons(x_{1}, x_{2}) ⟹ \{ \begin{matrix}t_{1} = iAlloc(2); \\ t_{2} = iStore(t_{1}, x_{1}); \\ t_{3} = t_{1} + 1; \\ t_{4} = iStore(t_{3}, x_{2}); \\ in t_{1} \} \end{matrix}

make n tuple is desugared similarly. λ-abstraction

The compilation of a function must ensure that both the free identifiers of the function and the dynamically bound identifiers at an application can be accessed properly from within the function body. Since there is no return stack in our machine, we must also explicitly provide a place to save the caller continuation at the time of function application which is reactivated by storing the result of the callee.

TExp[[λx. E]] α = \{ \begin{matrix}ιs_{b}, τ_{b} = TExp[[E]] α_{b}; \\ ιs_{d} = ιs_{b} ++ [store(⟨0, 0⟩) : popenv : schedule]; \\ in [copyenv(α(y_{1}), …, α(y_{m})) : makeclsr(ιs_{d}, ◇)], τ_{b} \} \end{matrix}

where

\begin{matrix}y_{1} … y_{m} = FV (λx.E) \\ α_{b} = \{ x ↦ ⟨0, 1⟩ , y_{1} ↦ ⟨0, 2⟩ , …, y_{m} ↦ ⟨0, \underline{m + 1}⟩ \} \end{matrix}

We compile the function body under the assumption that its argument and all its free identifiers are accessible through the top-level environment frame as reflected in the identifier map α_{b}. The first slot in the top-level frame points to the location where the return continuation of the caller function is stored. This environment structure and the location to store the return continuation will be setup during function application. Note that the return continuation is reactivated at the end of the function body by updating this slot with the final result.

The λ-abstraction itself compiles to produce a closure which carries an environment frame pointing to its free identifiers.

Function Application

A function application first evaluates the function and then applies it to the given argument. The application rule is described later in Section A.3.

TExp[[ap(f, z)]] α = [touch(α(f)) : apply(α(f), α(z),]), ϕ

Case Expression

For case expressions, we simply compile threads for each branch and generate a switch instruction to select the appropriate one.

TExp[[case(x, E_{1}, …, E_{n})]] α =

\{ \begin{matrix}ιs_{1}, τ_{1} = TExp[[E_{1}]] α; \\ ⋯ \\ ιs_{n}, τ_{n} = TExp[[E_{n}]] α; \\ in [touch(α(x)) : switch(α(x), ιs_{1}, …, ιs_{n})], τ_{1} + ⋯ + τ_{n} \} \end{matrix}

Block Expression

For a block, first we need to allocate an environment to hold all the bound identifiers. Each of the right-hand sides are compiled into threads that update the appropriate environment slots with their respective values. These threads are pushed into the work queue for evaluation. The “letrec” semantics of the block are maintained by allowing the new threads being compiled to refer to themselves via an extended thread map. The identifier map is also adjusted to reflect the new environment frame being pushed onto the environment stack.

TExp[[{ x_{1} = E_{1}; ⋯; x_{n} = E_{n} in x }]] α =

\{ \begin{matrix}ιs_{1}, τ_{1} = TExp[[E_{1}]] α′; \\ ιs′_{1} = ιs_{1} ++ [store(⟨0, 0⟩) : schedule]; \\ ⋯ \\ ιs_{n}, τ_{n} = TExp[[E_{n}]] α′; \\ ιs′_{n} = ιs_{n} ++ [store(⟨0, \underline{n − 1}⟩]) : schedule]; \\ in [allocenv(\underline{n}) : pushenv(◇) : pushwork(ιs′_{1}, stack) : …: \\ pushwork(ιs′_{n}, stack) : enter(α′(x)) : popenv], τ_{b} + τ_{1} + ⋯ + τ_{n} \} \end{matrix}

where

τ_{b} = {x_{1} ↦ ιs′_{1}, …, x_{n} ↦ ιs′_{n} }
α′(x) = if x = x_{k} (1 ≤ k ≤ n) then ⟨0, k⟩ else ⟨fst(α(x) + 1), snd(α(x))⟩

A.3 Execution Rules for Additional Instructions

In this section we provide the execution rules for the additional instructions given in Figure 7. Note that identifier names have been translated into index-offset pairs ⟨i, j⟩ pointing into the environment stack that must be dereferenced at run-time to access the store location.

Loading Accumulator

The loadc instruction is used to load an immediate constant into the accumulator. loadc:

\frac{⟨ loadc(c) : ιs ρs ωs σ⟩}{⟨c ιs ρs ωs σ⟩}

Closure Creation

The makeclsr instruction simply creates a new closure from the given thread and the environment stack. makeclsr:

\frac{⟨ makeclsr(ιs, ρ) : ιs ρs ωs σ⟩}{⟨⟨clsr (1). ιs, ρ⟩ ιs ρs ωs σ⟩}

Function Application

Function application first allocates a flat argument environment for the function call, copying the closure environment into it. It also copies the current argument mapping and allocates a new location to save the return continuation of the caller. The return continuation would enable the callee to resume the caller after the function call has completed. Finally, the entry point present within the closure is scheduled. apply:

\frac{⟨ apply(⟨i_{f}, j_{f}⟩ , ⟨i_{z}, j_{z}⟩) : ιs ρs ωs σ[ρs[i_{f}, j_{f}] ↦ ⟨full ⟨clsr (1). ιs′, ρ′⟩⟩]⟩}{⟨ ιs′ [ρ_{b}] ωs σ′⟩}

where \begin{matrix}ρ_{b} = ℓ : ρs[i_{z}, j_{z}] : ρ′ \\ σ′ = σ + \{ ℓ ↦ ⟨defer [(ιs, ρs)]⟩ \} \end{matrix}

Resource Management

The pushwork instruction creates a thread with the given instruction thread and the environment chain. pushwork:

\frac{⟨ pushwork(ιs′, ρs′) : ιs ρs ωs σ⟩}{⟨ ιs ρs ωs ++ [(ιs′, ρs′)] σ⟩}

The copyenv and allocenv instructions construct environments. copyenv is used to create a new environment mapping from existing identifier locations such as those for the free identifiers of a function. allocenv is used for new identifiers bindings in a block. It allocates new locations in the store and initializes them to be empty.

copyenv:

\frac{⟨ copyenv(⟨i_{0}, j_{0}⟩ … ⟨i_{n−1}, j_{n−1}⟩) : ιs ρs ωs σ⟩}{⟨ρ ιs ρs ωs σ⟩}

where ρ = [ρs[i_{0}, j_{0}], …, ρs[i_{n−1}, j_{n−1}]]

allocenv:

\frac{⟨ allocenv(\underline{n}) : ιs ρs ωs σ⟩}{⟨ρ ιs ρs ωs σ′⟩}

where ρ = [ℓ_{0}, …, ℓ_{n−1}] σ′ = σ + { ℓ_{0} ↦ ⟨defer [ ]⟩, …, ℓ_{n−1} ↦ ⟨defer [ ]⟩ }