Ports and Packets - avram - a virtual machine code interpreter

Next: Instruction Stacks, Previous: Lists of Pairs of Ports, Up: Emulation Primitives

3.8.2 Ports and Packets

A pointer type declared as a port points to a structure in the following form, where a flag is an unsigned short integer type, and a counter is an unsigned long integer.

     struct avm_packet
     {
       port parent;
       counter errors;
       portal descendents;
       list impetus, contents;
       flag predicating;
     };

For reasons that make sense to C, the avm_packet and port types are declared in lists.h, but a few memory management operations on them are available by way of functions declared in ports.h. The intended meaning of this structure is described presently, but first the memory management functions are as follows.

— Function: port avm_newport (counter errors, port parent, int predicating)

This function attempts to allocate storage for a new packet structure and returns its address if successful. If storage can not be allocated, a NULL pointer is returned. The errors, parent, and predicating fields are initialized with the parameters supplied by the caller. The rest of the structure is filled with zeros. A local memory cache is used for improved performance.

— Function: void avm_sever (port appendage)

This function reclaims the storage associated with a port, either freeing it entirely or holding it in a local cache. None of the entities that may be referenced by pointers within the structure are affected. Only this function should be used by client programs for disposing of ports, not the free function directly, or some internal bookkeeping will be disrupted. An internal error results if the argument is a NULL pointer.

— Function: void avm_initialize_ports ()

This function must be called prior to calling either of the two above, in order to initialize some static variables.

— Function: void avm_count_ports ()

This function may be called after the last call to any of the other functions in this section in order to detect and report unreclaimed storage associated with ports. A non-fatal warning will be written to standard error if any is detected, but otherwise there is no effect.

The interesting aspect of this data structure is the role it plays in capturing the state of a computation. For this purpose, it corresponds to a single node in a partially computed result to be represented by a list when it's finished. The nodes should be envisioned as a doubly-linked binary tree, except that the pair of descendents for each node is not yet known with certainty, so a list of alternatives must be maintained.

Because the computation is not completed while this data structure exists, there are always some empty fields in it. For example, the descendents and the contents fields embody the same information, the latter doing so in a compact as opposed to a more expanded form. Hence, it would be redundant for both fields to be non-empty at the same time. The data structure is built initially with descendents and no contents, only to be transformed into one with contents and no descendents.

The significance of each field in the structure can be summarized as follows.

contents: If the computational result destined for the port pointing to this packet is not complete, then this field is NULL and the descendents are being computed. Otherwise, it contains the result of the computation.
descendents: This field points to a list of pairs of ports serving as the destinations for an ensemble of concurrent computations.¹ The head and tail of the contents are to be identified respectively with the contents of the left and right port in the first pair to finish being computed.
parent: If this packet is addressed by the left or the right of port in one of the descendents of some other packet, then this field points to that packet.
errors: A non-zero value in this field indicates that the result destined for the contents of this packet is expected to be an error message. If the exact level of error severity incurred in the computation of the contents matches this number, then the contents can be assigned the result, but otherwise the result should propagate to the contents of the parent.
predicating: A non-zero value in this field implies that the result destined for the contents of this packet is being computed in order to decide which arm of a conditional function should be chosen. I.e., a NULL result calls for the one that is invoked when the predicate is false.
impetus: If the result destined for the contents of this packet is being computed in order to transform a virtual code fragment from its original form to an equivalent representation capable of being evaluated more directly, this field points to a list node at the root of the virtual code in its original form.

One of the hitherto undocumented fields in a list node structure declared in lists.h is called the interpretation, and is of type list. A client program delving into sufficient depth of detail to be concerned with ports and packets may reasonably assign the interpretation field of the list referenced by the impetus field in a packet to be a copy of the contents of the packet when they are eventually obtained. Doing so will save some time by eliminating the need for it to be recomputed if the same virtual code should be executed again.

If this course is taken, the facilitator field in a list node, also hitherto undocumented, should contain the address of the packet referring to the list node as its impetus. The reason for this additional link is so that it can be followed when the impetus of the packet is be cleared by avm_dispose in the event that the list node is freed before the computation completes. This action is performed in order to preclude a dangling pointer in the impetus field.

Footnotes

[1] Earlier versions of avram included a bottom avoiding choice combinator that required this feature, but which has been withdrawn. A single pair of descendent ports would now suffice.