The I-structure Layer
As noted in Figure 1.11 previously, the second layer of pH adds "I-Structures" to the functional core. I-Structures are a limited but benign form of state-benign, because it is still impossible to write a program with a race condition and programs are still guaranteed to be determinate. Data structures in pH can contain I-structure components.

What this means is that when the data structure is allocated, the component is initially left empty. Later, a computation can assign a value into that component, making it full. Any other computation that tries to read that component automatically blocks until the value is available.

We have already mentioned this type of synchronization in the context of producer-consumer parallelism in nonstrict functional data structures. The difference here is this: in functional data structures, the allocation of the data structure and the values that fill its components are always specified syntactically together, as a single construct.

For this reason, in functional data structures we never even think of the action of filling in a component as an assignment-that is something inside the implementation. In I-structures, on the other hand, the computation that fills in an empty component may be in some syntactically unrelated part of the program and is thus always expressed explicitly as an assignment.

One common use of I-structures is to implement pure functions efficiently. For example, most functional languages provide a map_array primitive that transforms one array into another by applying a given function to each element and a foldl_array primitive that computes some overall property of an array, such as the sum of all elements, or the maximum element.

Now, suppose we want to both transform an array as well as compute an overall property. This map_foldl operation is a perfectly well-defined, pure function, and it is of course possible to define it by simply applying both the map and the fold primitives; however, this involves two array traversals. With I-structures, it is possible for the programmer to implement this function directly as a new primitive, using a single array traversal.

I-structures retain determinacy in pH precisely because of their "write-once" semantics: an I-structure component makes a single transition from empty to full with a value, and no computation can observe this transition because any attempt to read an empty component will simply block the computation until the component is full and then return the value.

In other words, there is only one possible value that can be obtained by reading an I-structure component, and so there is no chance of nondeterminism.

I-structures are closely related to logic variables in logic programming languages. In fact, I-structures may be used in the same way that logic variables are often used-to implement difference lists, mailboxes, and so on.