123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252 |
- <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
- <html>
- <!-- Created on November 8, 2012 by texi2html 1.82
- texi2html was written by:
- Lionel Cons <[email protected]> (original author)
- Karl Berry <[email protected]>
- Olaf Bachmann <[email protected]>
- and many others.
- Maintained by: Many creative people.
- Send bugs and suggestions to <[email protected]>
- -->
- <head>
- <title>avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks</title>
- <meta name="description" content="avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks">
- <meta name="keywords" content="avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks">
- <meta name="resource-type" content="document">
- <meta name="distribution" content="global">
- <meta name="Generator" content="texi2html 1.82">
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
- <style type="text/css">
- <!--
- a.summary-letter {text-decoration: none}
- blockquote.smallquotation {font-size: smaller}
- pre.display {font-family: serif}
- pre.format {font-family: serif}
- pre.menu-comment {font-family: serif}
- pre.menu-preformatted {font-family: serif}
- pre.smalldisplay {font-family: serif; font-size: smaller}
- pre.smallexample {font-size: smaller}
- pre.smallformat {font-family: serif; font-size: smaller}
- pre.smalllisp {font-size: smaller}
- span.roman {font-family:serif; font-weight:normal;}
- span.sansserif {font-family:sans-serif; font-weight:normal;}
- ul.toc {list-style: none}
- -->
- </style>
- </head>
- <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
- <a name="Instruction-Stacks"></a>
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Ports-and-Packets.html#Ports-and-Packets" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Emulation-Primitives.html#Emulation-Primitives" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> >> </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
- <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
- <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
- <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
- </tr></table>
- <hr size="1">
- <a name="Instruction-Stacks-1"></a>
- <h3 class="subsection">3.8.3 Instruction Stacks</h3>
- <p>A header file named ‘<tt>instruct.h</tt>’ declares a number of memory
- management and stack operations on a data structure of the following
- form.
- <a name="index-instruction_005fnode"></a>
- </p>
- <table><tr><td> </td><td><pre class="example">struct instruction_node
- {
- port client;
- score sheet;
- struct avm_packet actor;
- struct avm_packet datum;
- instruction dependents;
- };
- </pre></td></tr></table>
- <p>In this structure, an <code>instruction</code> is a pointer to an
- <code>instruction_node</code>, a <code>score</code> is a pointer to a profile
- database entry as discussed in <a href="Profiling.html#Profiling">Profiling</a>, and the <code>port</code> and
- <code>avm_packet</code> types are as described in <a href="Ports-and-Packets.html#Ports-and-Packets">Ports and Packets</a>.
- </p>
- <p>This data structure is appropriate for a simple virtual machine code
- <a name="index-concurrency"></a>
- evaluation strategy involving no concurrency. The strategy to evaluate an
- expression <code><var>f</var> <var>x</var></code> would be based on a stack of these
- nodes threaded through the <code>dependents</code> field, and would proceed
- something like this.
- </p>
- <ol>
- <li>
- The stack is initialized to contain a single node having
- <code><var>f</var></code> in its <code>actor.contents</code> field, and <code><var>x</var></code> in
- its <code>datum.contents</code> field.
- </li><li>
- The <code>client</code> in this node would refer to a static packet to whose
- <code>contents</code> field the final result will be delivered.
- </li><li>
- The evaluator examines the <code>actor.contents</code> 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.
- </li><li>
- If the operation can be performed in this way, the result is computed
- and assigned to the destination indicated by the <code>client</code> field.
- </li><li>
- 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 <code><var>f</var></code> were of the form
- <code>compose(<var>g</var>,<var>h</var>)</code> (<code>silly</code> notation), the node with
- <code><var>f</var></code> and <code><var>x</var></code> would be popped, but a node with
- <code><var>g</var></code> as its <code>actor.contents</code> would be pushed, and then a
- node with <code><var>h</var></code> as its <code>actor.contents</code> and <code><var>x</var></code>
- as its <code>datum.contents</code> would be pushed. Furthermore, the
- <code>client</code> field of the latter node would point to the
- <code>datum.contents</code> of the one with <code><var>g</var></code>, and the
- <code>client</code> field of the one with <code><var>g</var></code> would point
- wherever the <code>client</code> of the popped node used to point.
- </li><li>
- If the operation indicated by the top <code>actor.contents</code> 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 <code><var>f</var></code> as its <code>datum.contents</code>, and a
- copy of a hard coded virtual code interpreter <code><var>V</var></code> as its
- <code>actor.contents</code>. The <code>client</code> of this node will point to the
- <code><var>f</var></code> in the original node so as to overwrite it when a
- simplified version is subsequently computed. The implementation of
- <code><var>V</var></code> is a straightforward exercise in <code>silly</code>
- programming.
- </li><li>
- 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 <code>client</code>
- in the original instruction node.
- </li></ol>
- <p>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
- <a name="index-threads-1"></a>
- 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 <code>data_ready</code> flag added to the <code>avm_packet</code> structure.
- </p>
- <p>The following functions support the use of stacks of instruction nodes
- that would be needed in an evaluation strategy such as the one above.
- </p>
- <dl>
- <dt><a name="index-avm_005fscheduled"></a><u>Function:</u> int <b>avm_scheduled</b><i> (list <var>actor_contents</var>, counter <var>datum_errors</var>, list <var>datum_contents</var>, port <var>client</var>, instruction *<var>next</var>, score <var>sheet</var>)</i></dt>
- <dd>
- <p>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
- <code>NULL</code> pointer if the storage could not be allocated.
- </p>
- <p>Copies of the <code>list</code> parameters <code>actor_contents</code> and
- <code>data_contents</code> are made by this function using <code>avm_copied</code>,
- 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.
- </p>
- <p>Any fields other than those indicated by the parameters to this function
- are filled with zeros in the result.
- </p></dd></dl>
- <dl>
- <dt><a name="index-avm_005fretire"></a><u>Function:</u> void <b>avm_retire</b><i> (instruction *<var>done</var>)</i></dt>
- <dd><p>This function performs the storage reclamation of instructions, taking
- as its argument the instruction to be reclaimed. The <code>list</code> fields
- in the structure corresponding to the <code>list</code> parameters used when
- it was created are specifically reclaimed as well, using
- <code>avm_dispose</code>.
- </p>
- <p>The argument to this function is the address of an <code>instruction</code>
- rather than just an <code>instruction</code> so that the <code>instruction</code>
- whose address is given may be reassigned as the <code>dependents</code> field
- of the deallocated node. In this way, the instructions can form a stack
- that is popped by this function.
- </p>
- <p>This function cooperates with <code>avm_scheduled</code> 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 <code>malloc</code> or <code>free</code>, but use only these functions.
- </p>
- <p>It causes a fatal internal error to pass a <code>NULL</code> pointer to this
- function.
- </p></dd></dl>
- <dl>
- <dt><a name="index-avm_005freschedule"></a><u>Function:</u> void <b>avm_reschedule</b><i> (instruction *<var>next</var>)</i></dt>
- <dd><p>Given the address of an instruction pointer that may be regarded as the
- top of a stack of instructions threaded through the <code>dependents</code>
- 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.
- </p>
- <p>A use for this function arises in the course of evaluating virtual code
- applications of the form <code>conditional(<var>p</var>,(<var>f</var>,<var>g</var>))</code>
- (in <code>silly</code> notation). The evaluation strategy would require
- pushing nodes for all three constituents, but with <code><var>p</var></code> pushed
- last (therefore evaluated first). The result of the evaluation of
- <code><var>p</var></code> would require either the top one or the one below it to
- be popped without being evaluated, depending on whether the result is
- empty.
- </p></dd></dl>
- <dl>
- <dt><a name="index-avm_005finitialize_005finstruct"></a><u>Function:</u> void <b>avm_initialize_instruct</b><i> ()</i></dt>
- <dd><p>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.
- </p></dd></dl>
- <dl>
- <dt><a name="index-avm_005fcount_005finstruct"></a><u>Function:</u> void <b>avm_count_instruct</b><i> ()</i></dt>
- <dd><p>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.
- </p></dd></dl>
- <hr size="1">
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Ports-and-Packets.html#Ports-and-Packets" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Emulation-Primitives.html#Emulation-Primitives" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> >> </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
- <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
- <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
- <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
- </tr></table>
- <p>
- <font size="-1">
- This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
- </font>
- <br>
- </p>
- </body>
- </html>
|