DVI version pat.dvi

We here describe a simple transformation on join definitions, which does not rely on a full semantical analysis (such as name usage analysis), but only on a simple, local, syntactical analysis of join-patterns.

Let us take a simple example:

let S(x) | m_1(y) = P_1(x,y) and S(x) | m_2(y) = P_2(x,y) .... and S(x) | m_n(y) = P_n(x,y) ;;

In this example, a match occurs only when there are messages pending
both on S and on one of the methods m_{1}, m_{2},…Thus, from the
synchronization
point of view, all the methods are equivalent. And indeed, we can
regroup them into one, single method channel m by
transforming this join definition into:

let S(x) | m(p,y) = P[p] (x,y);; let m_1(y) = m(1,y);; let m_2(y) = m(2,y);; .... let m_n(y) = m(n,y);;

Where P is the vector of processes [P_{1},P_{2},...,P_{n}].

Methods m_{1} m_{2},…are now simple wrappers. Method m_{i} now
calls m with an additional i argument, which basically is the
index of P_{i} in array P. At this point, we must emphasize that we
describe this technique as a source to source transformation only for
clarity. However, the produced source code may not be correct with
respect to the join type system, when the types of methods are
different. Anyhow, this optimization is implemented using ad hoc
mechanisms, this both improves efficiency and solves the typing
problem.

Currently, this optimization is performed by the jocaml compiler. This leads to a new interpretation of name indexes by the “join” library. The least significant bits in name indexes still encode names that actually take part to synchronization (here S and m), while their most significant bits (which were previously unused) now encode the extra i argument. This yields two benefits. First, the number of status checks decreases, as the number of matching statuses decreases. Second, the number of channels that can be defined in one definition can now exceed the hosting system integer size, provided some names can be grouped together for synchronization.

In the join compiler, this technique might be used to reduce
automata size, since it lowers the number of non-matching statuses, by
reducing the number of synchronizing names. Code entries for methods
m_{1}, m_{2},…would still be contained in the definition
structure, they would only stack the index of the process to fire, and
then call the code for method m. Moreover, they do not need to be
updated after each transition of the automaton.

Finally, this technique can also be applied to more complex
synchronizations. Given a definition that defines names x_{1}, x_{2},
…, x_{n}, using patterns J_{1}, J_{2}, …J_{m}. We say that
two names are equivalent, when swapping them in the patterns yields
the same set of patterns. We then replace equivalent names by a
single name, plus an index.

Consider the following definition

let S_1(x) | m_1(y) = P_1(x,y) and S_1(x) | m_2(y) = P_2(x,y) and S_2(x) | m_1(y) = P_3(x,y) and S_2(x) | m_2(y) = P_4(x,y) ;;

Then the set of defined names {S_{1}, S_{2}, m_{1}, m_{2}} can be
partitioned into {S_{1}, S_{2}} and {m_{1}, m_{2}}.
Then, the above program can be transformed into:

let S(p,x) | m(q,y) = P[p,q] (x,y);; let m_1(y) = m(1,y);; let m_2(y) = m(2,y);; let S_1(y) = S(1,y);; let S_2(y) = S(2,y);;

(with P[1,1] = P_{1}, P[1,2] = P_{2}, P[2,1] = P_{3} and P[2,2] = P_{4})

DVI version pat.dvi