4 Runtime definitions
4.1 Basics
Names are the basic values of the join-calculus, and thus any
implementation of the join-calculus must supply a runtime
representation for them. For instance, a name can be sent on some
appropriate channel. At runtime, we must indeed send something.
However, names that are defined together in the same join definition
interact when matching is tested for and performed. Moreover, by the
very idea behind the join-calculus, matching is the only
synchronization primitive. In other words, only names that are
defined by the same join definition have some kind of interaction that
is of the runtime system responsibility.
This makes possible and desirable to compile a source definition into
a runtime “definition”, a single vector structure that groups all
the names defined in a given definition. Names must still exist as
individuals, they can be represented as infix pointers into their
definition (as in join), or as a definition pointer and an index
(as in jocaml).
Both the join and jocaml systems implement the automata of
the previous section. However, they do so in quite different manners.
The former focuses on minimizing runtime testing, while the latter
involves a systematic runtime testing of the current status at every
message arrival.
4.2 Definitions in join
Runtime definitions are vector structures. Every name defined in a
definition occupies two slots in the vector structure. The first
entry holds a code pointer that stands for the name itself, while the
second entry holds a pointer to a queue of pending messages, queues
being organized as linked lists. Runtime definitions include
additional slots that hold the values of the variables that are free
in guarded processes. This technique resembles much the one used by
the SML/NJ compiler [1] to represent mutually
recursive functions. Message sending on name x is performed by
stacking message values and then calling the code for name x. This
code is retrieved by dereferencing twice the infix pointer that
represents x at runtime.
However, there is a big difference between mutually recursive
functions and join definitions. The code for name x is automaton
code that reacts to the arrival of a new message on that name. The
compiler issues various versions of name code, one per possible status
of the definition that defines x. Typically, name code either saves
a message into the queue for x (in the non-matching case), or
retrieves messages from other queues before firing a guarded process
(in the matching case). In all cases, definition status may then
need an update, which is performed by updating all code entries in
the definition.
4.3 Definitions in jocaml
In the jocaml system, a name is a pointer to a definition plus
an index. Definitions are still vectors structures, but there is only
one entry per name for message queues. Additionally, definitions hold
guarded closures (i.e. guarded process code plus free variable
values), a status field and a matching data structure.
Status field holds the current status of the definition as a
bit-field. Each name status is encoded by a bit, using bit 1 for
N and bit 0 for 0, and bit position is given by name
index.
Message sending is performed by calling a generic C function from the
“join” library, taking message value, a definition pointer and a
name index as arguments. When a message is received on name x, the
bit for x is checked in the current status bit-field. If the bit is
set, some messages on name x are already present. Thus, definition
status does not change. Since the current status before message
sending is guaranteed to be a non-matching one, the message is queued
and the function is exited.
Otherwise, the current definition status is searched in the matching
structure for x. This matching structure is an array of pattern
encoding, guarded process index pairs. Pattern encodings are
bit-fields, just like status encodings.
corresponding to a join-pattern containing name x, from which name x has been removed. Using a sequential
search by a bitwise "and" with each pattern encoding, the current
status can be identified as matching or non-matching in at most Nx
tests, where Nx is the number of clauses whose pattern contains x.
If no match is found, the automaton state is updated and the message
value is queued in the queue for x. Otherwise, a guarded process
index has been found, and is used to retrieve the associated guarded
closure. Arguments to the guarded process are extracted from the
queues identified by the matching status found. Status is updated at
the same moment (when a queue becomes empty a bit is erased). Finally
the guarded process is fired.
Therefore, the performance of this technique much relies on fast
comparisons and modifications of definition statuses. The best result
is achieved when statuses are encoded by machine integers. In that
case, the number of names that a definition can define is limited by
the integer size of the hoisting Objective Caml system (which
typically is 31 or 63 bits). If this is not considered enough, then
statuses have to be encoded using several integers or one string. Both
kinds of status encodings can be mixed, using integers for small
definitions and strings for larger ones. However, in the current jocaml system, we use a single integer to hold status, and a
technique (described in section 6) is used to associate
several channels to a same bit in the status bit-field.