Instruction-Stacks.html 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on November 8, 2012 by texi2html 1.82
  4. texi2html was written by:
  5. Lionel Cons <[email protected]> (original author)
  6. Karl Berry <[email protected]>
  7. Olaf Bachmann <[email protected]>
  8. and many others.
  9. Maintained by: Many creative people.
  10. Send bugs and suggestions to <[email protected]>
  11. -->
  12. <head>
  13. <title>avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 3.8.3 Instruction Stacks">
  16. <meta name="resource-type" content="document">
  17. <meta name="distribution" content="global">
  18. <meta name="Generator" content="texi2html 1.82">
  19. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  20. <style type="text/css">
  21. <!--
  22. a.summary-letter {text-decoration: none}
  23. blockquote.smallquotation {font-size: smaller}
  24. pre.display {font-family: serif}
  25. pre.format {font-family: serif}
  26. pre.menu-comment {font-family: serif}
  27. pre.menu-preformatted {font-family: serif}
  28. pre.smalldisplay {font-family: serif; font-size: smaller}
  29. pre.smallexample {font-size: smaller}
  30. pre.smallformat {font-family: serif; font-size: smaller}
  31. pre.smalllisp {font-size: smaller}
  32. span.roman {font-family:serif; font-weight:normal;}
  33. span.sansserif {font-family:sans-serif; font-weight:normal;}
  34. ul.toc {list-style: none}
  35. -->
  36. </style>
  37. </head>
  38. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  39. <a name="Instruction-Stacks"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Ports-and-Packets.html#Ports-and-Packets" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> &gt; </a>]</td>
  43. <td valign="middle" align="left"> &nbsp; </td>
  44. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  45. <td valign="middle" align="left">[<a href="Emulation-Primitives.html#Emulation-Primitives" title="Up section"> Up </a>]</td>
  46. <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> &gt;&gt; </a>]</td>
  47. <td valign="middle" align="left"> &nbsp; </td>
  48. <td valign="middle" align="left"> &nbsp; </td>
  49. <td valign="middle" align="left"> &nbsp; </td>
  50. <td valign="middle" align="left"> &nbsp; </td>
  51. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  52. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  53. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  54. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  55. </tr></table>
  56. <hr size="1">
  57. <a name="Instruction-Stacks-1"></a>
  58. <h3 class="subsection">3.8.3 Instruction Stacks</h3>
  59. <p>A header file named &lsquo;<tt>instruct.h</tt>&rsquo; declares a number of memory
  60. management and stack operations on a data structure of the following
  61. form.
  62. <a name="index-instruction_005fnode"></a>
  63. </p>
  64. <table><tr><td>&nbsp;</td><td><pre class="example">struct instruction_node
  65. {
  66. port client;
  67. score sheet;
  68. struct avm_packet actor;
  69. struct avm_packet datum;
  70. instruction dependents;
  71. };
  72. </pre></td></tr></table>
  73. <p>In this structure, an <code>instruction</code> is a pointer to an
  74. <code>instruction_node</code>, a <code>score</code> is a pointer to a profile
  75. database entry as discussed in <a href="Profiling.html#Profiling">Profiling</a>, and the <code>port</code> and
  76. <code>avm_packet</code> types are as described in <a href="Ports-and-Packets.html#Ports-and-Packets">Ports and Packets</a>.
  77. </p>
  78. <p>This data structure is appropriate for a simple virtual machine code
  79. <a name="index-concurrency"></a>
  80. evaluation strategy involving no concurrency. The strategy to evaluate an
  81. expression <code><var>f</var> <var>x</var></code> would be based on a stack of these
  82. nodes threaded through the <code>dependents</code> field, and would proceed
  83. something like this.
  84. </p>
  85. <ol>
  86. <li>
  87. The stack is initialized to contain a single node having
  88. <code><var>f</var></code> in its <code>actor.contents</code> field, and <code><var>x</var></code> in
  89. its <code>datum.contents</code> field.
  90. </li><li>
  91. The <code>client</code> in this node would refer to a static packet to whose
  92. <code>contents</code> field the final result will be delivered.
  93. </li><li>
  94. The evaluator examines the <code>actor.contents</code> field on the top of the
  95. stack, detects by its form the operation it represents, and decides
  96. whether it corresponds to one that can be evaluated immediately by way
  97. of a canned function available in the library. List reversal,
  98. transposition, and comparison would be examples of such operations.
  99. </li><li>
  100. If the operation can be performed in this way, the result is computed
  101. and assigned to the destination indicated by the <code>client</code> field.
  102. </li><li>
  103. If the operation is not easy enough to perform immediately but is of a
  104. form recognizable as a combination of simpler operations, it is
  105. decomposed into the simpler operations, and each of them is
  106. strategically positioned on the stack so as to effect the evaluation of
  107. the combination. For example, if <code><var>f</var></code> were of the form
  108. <code>compose(<var>g</var>,<var>h</var>)</code> (<code>silly</code> notation), the node with
  109. <code><var>f</var></code> and <code><var>x</var></code> would be popped, but a node with
  110. <code><var>g</var></code> as its <code>actor.contents</code> would be pushed, and then a
  111. node with <code><var>h</var></code> as its <code>actor.contents</code> and <code><var>x</var></code>
  112. as its <code>datum.contents</code> would be pushed. Furthermore, the
  113. <code>client</code> field of the latter node would point to the
  114. <code>datum.contents</code> of the one with <code><var>g</var></code>, and the
  115. <code>client</code> field of the one with <code><var>g</var></code> would point
  116. wherever the <code>client</code> of the popped node used to point.
  117. </li><li>
  118. If the operation indicated by the top <code>actor.contents</code> is neither
  119. implemented by a canned operation in the library nor easily decomposable
  120. into some that are, the evaluator can either give up or use virtual code
  121. to execute other virtual code. The latter trick is accomplished by
  122. pushing a node with <code><var>f</var></code> as its <code>datum.contents</code>, and a
  123. copy of a hard coded virtual code interpreter <code><var>V</var></code> as its
  124. <code>actor.contents</code>. The <code>client</code> of this node will point to the
  125. <code><var>f</var></code> in the original node so as to overwrite it when a
  126. simplified version is subsequently computed. The implementation of
  127. <code><var>V</var></code> is a straightforward exercise in <code>silly</code>
  128. programming.
  129. </li><li>
  130. In any case, the evaluator would continue working on the stack until
  131. everything on it has been popped, at which time the result of the entire
  132. computation will be found in the packet addressed by the <code>client</code>
  133. in the original instruction node.
  134. </li></ol>
  135. <p>What makes this strategy feasible to implement is the assumption of a
  136. sequential language, wherein synchronization incurs no cost and is
  137. automatic. The availability of any operand is implied by its position at
  138. the top of the stack. If you are reading this section with a view to
  139. <a name="index-threads-1"></a>
  140. implementing a concurrent or multi-threaded evaluation strategy, it will
  141. be apparent that further provisions would need to be made, such as that
  142. of a <code>data_ready</code> flag added to the <code>avm_packet</code> structure.
  143. </p>
  144. <p>The following functions support the use of stacks of instruction nodes
  145. that would be needed in an evaluation strategy such as the one above.
  146. </p>
  147. <dl>
  148. <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>
  149. <dd>
  150. <p>This function performs the memory allocation for instruction nodes. It
  151. attempts to create one and to initialize the fields with the given
  152. parameters, returning a pointer to it if successful. It returns a
  153. <code>NULL</code> pointer if the storage could not be allocated.
  154. </p>
  155. <p>Copies of the <code>list</code> parameters <code>actor_contents</code> and
  156. <code>data_contents</code> are made by this function using <code>avm_copied</code>,
  157. so the originals still exist as far as the caller is concerned and will
  158. have to be deallocated separately from this structure. The copies are
  159. made only if the allocation succeeds.
  160. </p>
  161. <p>Any fields other than those indicated by the parameters to this function
  162. are filled with zeros in the result.
  163. </p></dd></dl>
  164. <dl>
  165. <dt><a name="index-avm_005fretire"></a><u>Function:</u> void <b>avm_retire</b><i> (instruction *<var>done</var>)</i></dt>
  166. <dd><p>This function performs the storage reclamation of instructions, taking
  167. as its argument the instruction to be reclaimed. The <code>list</code> fields
  168. in the structure corresponding to the <code>list</code> parameters used when
  169. it was created are specifically reclaimed as well, using
  170. <code>avm_dispose</code>.
  171. </p>
  172. <p>The argument to this function is the address of an <code>instruction</code>
  173. rather than just an <code>instruction</code> so that the <code>instruction</code>
  174. whose address is given may be reassigned as the <code>dependents</code> field
  175. of the deallocated node. In this way, the instructions can form a stack
  176. that is popped by this function.
  177. </p>
  178. <p>This function cooperates with <code>avm_scheduled</code> in the use of a local
  179. cache of instruction nodes in the interest of better performance. Client
  180. modules should not attempt to allocate or reclaim instructions directly
  181. with <code>malloc</code> or <code>free</code>, but use only these functions.
  182. </p>
  183. <p>It causes a fatal internal error to pass a <code>NULL</code> pointer to this
  184. function.
  185. </p></dd></dl>
  186. <dl>
  187. <dt><a name="index-avm_005freschedule"></a><u>Function:</u> void <b>avm_reschedule</b><i> (instruction *<var>next</var>)</i></dt>
  188. <dd><p>Given the address of an instruction pointer that may be regarded as the
  189. top of a stack of instructions threaded through the <code>dependents</code>
  190. field, this function exchanges the positions of the top instruction and
  191. the one below it. A fatal internal error is caused if there are fewer
  192. than two instructions in the stack.
  193. </p>
  194. <p>A use for this function arises in the course of evaluating virtual code
  195. applications of the form <code>conditional(<var>p</var>,(<var>f</var>,<var>g</var>))</code>
  196. (in <code>silly</code> notation). The evaluation strategy would require
  197. pushing nodes for all three constituents, but with <code><var>p</var></code> pushed
  198. last (therefore evaluated first). The result of the evaluation of
  199. <code><var>p</var></code> would require either the top one or the one below it to
  200. be popped without being evaluated, depending on whether the result is
  201. empty.
  202. </p></dd></dl>
  203. <dl>
  204. <dt><a name="index-avm_005finitialize_005finstruct"></a><u>Function:</u> void <b>avm_initialize_instruct</b><i> ()</i></dt>
  205. <dd><p>This function should be called before any of the instruction memory
  206. management functions is called in order to initialize some local data
  207. structures. Results are unpredictable without it.
  208. </p></dd></dl>
  209. <dl>
  210. <dt><a name="index-avm_005fcount_005finstruct"></a><u>Function:</u> void <b>avm_count_instruct</b><i> ()</i></dt>
  211. <dd><p>This function should be called after the last call to any of the
  212. other functions in this section in order to detect and report
  213. unreclaimed storage associated with them. A warning message will be
  214. written to standard error if any unreclaimed instructions remain. This
  215. function relies on the assumption that the memory management has been
  216. done only by way of the above functions.
  217. </p></dd></dl>
  218. <hr size="1">
  219. <table cellpadding="1" cellspacing="1" border="0">
  220. <tr><td valign="middle" align="left">[<a href="Ports-and-Packets.html#Ports-and-Packets" title="Previous section in reading order"> &lt; </a>]</td>
  221. <td valign="middle" align="left">[<a href="External-Library-Maintenance.html#External-Library-Maintenance" title="Next section in reading order"> &gt; </a>]</td>
  222. <td valign="middle" align="left"> &nbsp; </td>
  223. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  224. <td valign="middle" align="left">[<a href="Emulation-Primitives.html#Emulation-Primitives" title="Up section"> Up </a>]</td>
  225. <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> &gt;&gt; </a>]</td>
  226. <td valign="middle" align="left"> &nbsp; </td>
  227. <td valign="middle" align="left"> &nbsp; </td>
  228. <td valign="middle" align="left"> &nbsp; </td>
  229. <td valign="middle" align="left"> &nbsp; </td>
  230. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  231. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  232. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  233. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  234. </tr></table>
  235. <p>
  236. <font size="-1">
  237. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  238. </font>
  239. <br>
  240. </p>
  241. </body>
  242. </html>