Previous Up Next
DVI version pat.dvi

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.


DVI version pat.dvi

Previous Up Next