# Improper Nesting Example

## Introduction

One of the limits on the use of parbegin/parend, and any related constructs, is that the program involved must be properly nested. Not all programs are. For example, consider the program represented by the following graphs.

## The Program as Graphs ## Using fork/join Primitives

The program equivalent to these precedence and process flow graphs is:

```    t6 := 2;
t8 := 3;
S1; fork p2; fork p5; fork p7; quit;
p2: S2; fork p3; fork p4; quit;
p5: S5; join t6, p6; quit;
p7: S7; join t8, p8; quit;
p3: S3; join t8, p8; quit;
p4: S4; join t6, p6; quit;
p6: S6; join t8, p8; quit;
p8: S8; quit
```
where Si is the program for pi.

## Using parbegin/parend Primitives

To see if this is possible, we must determine if the above program is properly nested. If not, we clearly cannot represent it using parbegin and parend, which require a block structure, and hence proper nesting.

Let S(a,b) represent the serial execution of processes a and b, and P(a,b) the parallel execution of processes a and b. Then a process flow graph is properly nested if it can be described by P, S, and functional composition. For example, the program

```parbegin
p1:a := b + 1;
p2:c := d + 1;
parend
p3:e := a + c;
```
would be written as
S(P(p1,p2),p3)

We now prove:

Claim: The example is not properly nested.
Proof: For something to be properly nested, it must be of the form S(pi, pj) or P(pi, pj) at the most interior level. Clearly the example's most interior level is not P(pi, pj) as there are no constructs of that form in the graph In the graph, all serially connected processes pi and pj have at least 1 more process pk starting or finishing at the node nij between pi and pj; but if S(pi,pj) is in the innermost level, there can be no such pk (else a more interior P or S is needed, contradiction). Hence, it's not S(pi,pj)) either. Send email to cs150@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562