[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

### 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.

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

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