txlyre
/
avram


			
							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"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </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"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </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 &lsquo;<tt>instruct.h</tt>&rsquo; 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>&nbsp;</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"> &lt; </a>]</td>
<td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> &gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </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"> &gt;&gt; </a>]</td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </td>
<td valign="middle" align="left"> &nbsp; </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>