3.8.3 Instruction Stacks

A header file named ‘instruct.h’ declares a number of memory management and stack operations on a data structure of the following form.

struct instruction_node
{
  port client;
  score sheet;
  struct avm_packet actor;
  struct avm_packet datum;
  instruction dependents;
};

In this structure, an instruction is a pointer to an instruction_node, a score is a pointer to a profile database entry as discussed in Profiling, and the port and avm_packet types are as described in Ports and Packets.

This data structure is appropriate for a simple virtual machine code evaluation strategy involving no concurrency. The strategy to evaluate an expression f x would be based on a stack of these nodes threaded through the dependents field, and would proceed something like this.

1. The stack is initialized to contain a single node having f in its actor.contents field, and x in its datum.contents field.
2. The client in this node would refer to a static packet to whose contents field the final result will be delivered.
3. The evaluator examines the actor.contents field on the top of the stack, detects by its form the operation it represents, and decides whether it corresponds to one that can be evaluated immediately by way of a canned function available in the library. List reversal, transposition, and comparison would be examples of such operations.
4. If the operation can be performed in this way, the result is computed and assigned to the destination indicated by the client field.
5. If the operation is not easy enough to perform immediately but is of a form recognizable as a combination of simpler operations, it is decomposed into the simpler operations, and each of them is strategically positioned on the stack so as to effect the evaluation of the combination. For example, if f were of the form compose(g,h) (silly notation), the node with f and x would be popped, but a node with g as its actor.contents would be pushed, and then a node with h as its actor.contents and x as its datum.contents would be pushed. Furthermore, the client field of the latter node would point to the datum.contents of the one with g, and the client field of the one with g would point wherever the client of the popped node used to point.
6. If the operation indicated by the top actor.contents is neither implemented by a canned operation in the library nor easily decomposable into some that are, the evaluator can either give up or use virtual code to execute other virtual code. The latter trick is accomplished by pushing a node with f as its datum.contents, and a copy of a hard coded virtual code interpreter V as its actor.contents. The client of this node will point to the f in the original node so as to overwrite it when a simplified version is subsequently computed. The implementation of V is a straightforward exercise in silly programming.
7. In any case, the evaluator would continue working on the stack until everything on it has been popped, at which time the result of the entire computation will be found in the packet addressed by the client in the original instruction node.

What makes this strategy feasible to implement is the assumption of a sequential language, wherein synchronization incurs no cost and is automatic. The availability of any operand is implied by its position at the top of the stack. If you are reading this section with a view to implementing a concurrent or multi-threaded evaluation strategy, it will be apparent that further provisions would need to be made, such as that of a data_ready flag added to the avm_packet structure.

The following functions support the use of stacks of instruction nodes that would be needed in an evaluation strategy such as the one above.

Function: int avm_scheduled (list actor_contents, counter datum_errors, list datum_contents, port client, instruction *next, score sheet)

This function performs the memory allocation for instruction nodes. It attempts to create one and to initialize the fields with the given parameters, returning a pointer to it if successful. It returns a NULL pointer if the storage could not be allocated.

Copies of the list parameters actor_contents and data_contents are made by this function using avm_copied, so the originals still exist as far as the caller is concerned and will have to be deallocated separately from this structure. The copies are made only if the allocation succeeds.

Any fields other than those indicated by the parameters to this function are filled with zeros in the result.

Function: void avm_retire (instruction *done)

This function performs the storage reclamation of instructions, taking as its argument the instruction to be reclaimed. The list fields in the structure corresponding to the list parameters used when it was created are specifically reclaimed as well, using avm_dispose.

The argument to this function is the address of an instruction rather than just an instruction so that the instruction whose address is given may be reassigned as the dependents field of the deallocated node. In this way, the instructions can form a stack that is popped by this function.

This function cooperates with avm_scheduled in the use of a local cache of instruction nodes in the interest of better performance. Client modules should not attempt to allocate or reclaim instructions directly with malloc or free, but use only these functions.

It causes a fatal internal error to pass a NULL pointer to this function.

Function: void avm_reschedule (instruction *next)

Given the address of an instruction pointer that may be regarded as the top of a stack of instructions threaded through the dependents field, this function exchanges the positions of the top instruction and the one below it. A fatal internal error is caused if there are fewer than two instructions in the stack.

A use for this function arises in the course of evaluating virtual code applications of the form conditional(p,(f,g)) (in silly notation). The evaluation strategy would require pushing nodes for all three constituents, but with p pushed last (therefore evaluated first). The result of the evaluation of p would require either the top one or the one below it to be popped without being evaluated, depending on whether the result is empty.

Function: void avm_initialize_instruct ()

This function should be called before any of the instruction memory management functions is called in order to initialize some local data structures. Results are unpredictable without it.

Function: void avm_count_instruct ()

This function should 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 them. A warning message will be written to standard error if any unreclaimed instructions remain. This function relies on the assumption that the memory management has been done only by way of the above functions.

This document was generated on November 8, 2012 using texi2html 1.82.