Transfer.html 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
  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: 2.7.13.5 Transfer</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.13.5 Transfer">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.13.5 Transfer">
  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="Transfer"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Sort.html#Sort" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Mapcur.html#Mapcur" 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="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  45. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
  46. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" 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="Transfer-1"></a>
  58. <h4 class="subsubsection">2.7.13.5 Transfer</h4>
  59. <a name="index-transfer"></a>
  60. <p>A particular interpretation is given to virtual code in the following form.
  61. </p>
  62. <dl compact="compact">
  63. <dt> <em>T26</em></dt>
  64. <dd><p>[[<code>transfer</code>]] <code><var>f</var></code> = <code>((nil,nil),(nil,(nil,<var>f</var>)))</code>
  65. </p></dd>
  66. </dl>
  67. <p>When code in this form is evaluated with an argument, the tree
  68. <a name="index-state-transition-function"></a>
  69. <code><var>f</var></code> is used as a state transition function, and the argument
  70. is used as a list to be traversed. The traversal begins with
  71. <code><var>f</var></code> being evaluated on <code>nil</code> to get the initial state
  72. and the initial output. Thereafter, each item of the list is paired with
  73. the current state to be evaluated with <code><var>f</var></code>, resulting in a
  74. list of output and the next state. The output resulting from the entire
  75. application is the cumulative concatenation of all outputs obtained in
  76. the course of evaluating <code><var>f</var></code>. The computation
  77. terminates when <code><var>f</var></code> yields a <code>nil</code> result. If the list
  78. of inputs runs out before the computation terminates, <code>nil</code> values
  79. are used as inputs.
  80. </p>
  81. <p>This behavior is specified more precisely in the following property
  82. of the operator, which applies in the case of non-<code>nil</code> <code><var>f</var></code>.
  83. <a name="index-transition"></a>
  84. </p>
  85. <dl compact="compact">
  86. <dt> <em>P33</em></dt>
  87. <dd><p>([[<code>transfer</code>]] <code><var>f</var></code>) <code><var>x</var></code> =
  88. ([[<code>transition</code>]] <code><var>f</var></code>) <code>(nil,(<var>f</var> nil,<var>x</var>))</code>
  89. </p></dd>
  90. </dl>
  91. <p>Much of the <code>transfer</code> semantics is implicit in the meaning of
  92. <code>transition</code>. For any given application <code><var>f</var></code>,
  93. [[<code>transition</code>]] <code><var>f</var></code> is the virtual code for a function
  94. that takes the list traversal from one configuration to the next.
  95. A configuration is represented as a tuple, usually in the form
  96. <code>(<var>previous outputs</var>,((<var>state</var>,<var>output</var>),(<var>next input</var>,<var>subsequent
  97. inputs</var>)))</code>. A terminal configuration has the form
  98. <code>(<var>previous outputs</var>,(nil,(<var>next input</var>,<var>subsequent
  99. inputs</var>)))</code>. A configuration may also have <code>nil</code> in place of the
  100. pair <code>(<var>next input</var>,<var>subsequent inputs</var>)</code> if no more input
  101. remains.
  102. </p>
  103. <p>In the non-degenerate case, the meaning of [[<code>transition</code>]]
  104. <code><var>f</var></code> is consistent with the following equation.
  105. </p>
  106. <dl compact="compact">
  107. <dt> <em>E7</em></dt>
  108. <dd><p>([[<code>transition</code>]] <code><var>f</var></code>) <code>(<var>y</var>,((<var>s</var>,<var>o</var>),(<var>i</var>,<var>x</var>)))</code> =<br>
  109. ([[<code>transition</code>]] <code><var>f</var></code>) <code>((<var>o</var>,<var>y</var>),(<var>f</var> (<var>s</var>,<var>i</var>),<var>x</var>))</code>
  110. </p></dd>
  111. </dl>
  112. <p>That is, the current output <code><var>o</var></code> is stored with previous outputs <code><var>y</var></code>, the next
  113. input <code><var>i</var></code> is removed from the configuration, and the next state and output
  114. are obtained from the evaluation of <code><var>f</var></code> with the state <code><var>s</var></code> and
  115. the next input <code><var>i</var></code>.
  116. </p>
  117. <p>In the case where no input remains, the transition function is
  118. consistent with the following equation.
  119. </p>
  120. <dl compact="compact">
  121. <dt> <em>E8</em></dt>
  122. <dd><p>([[<code>transition</code>]] <code><var>f</var></code>) <code>(<var>y</var>,((<var>s</var>,<var>o</var>),nil))</code> = <br>
  123. ([[<code>transition</code>]] <code><var>f</var></code>) <code>((<var>o</var>,<var>y</var>),(<var>f</var> (<var>s</var>,nil),nil))</code>
  124. </p></dd>
  125. </dl>
  126. <p>This case is similar to the previous one except that the <code>nil</code>
  127. value is used in place of the next input. Note that in either case,
  128. nothing about <code><var>f</var></code> depends on the particular way
  129. configurations are represented, except that it should have a state as
  130. its left argument and an input as its right argument.
  131. </p>
  132. <p>Finally, in the case of a terminal configuration, the transition
  133. function returns the cumulative output.
  134. </p>
  135. <dl compact="compact">
  136. <dt> <em>E9</em></dt>
  137. <dd><p>([[<code>transition</code>]] <code><var>f</var></code>) <code>(<var>y</var>,(nil,<var>x</var>))</code> =
  138. [[<code>reduce(cat,nil)</code>]] [[<code>reverse</code>]] <code><var>y</var></code>
  139. </p></dd>
  140. </dl>
  141. <p>The <code>silly</code> code <code>reduce(cat,nil)</code> has the effect of
  142. <a name="index-cat-1"></a>
  143. <a name="index-concatenation"></a>
  144. flattening a list of lists into one long list, which is necessary
  145. insofar as the transition function will have generated not necessarily a
  146. single output but a list of outputs on each iteration. The <code>cat</code>
  147. mnemonic stands for list concatenation and is explained in <a href="Cat.html#Cat">Cat</a>.
  148. The reversal is necessary to cause the first generated output to be at
  149. the head of the list. List reversal is a built in operation of the
  150. virtual machine and is described in <a href="Reverse.html#Reverse">Reverse</a>.
  151. </p>
  152. <p>If such a function as <code>transition</code> seems implausible, its
  153. implementation in <code>silly</code> can be found in <a href="Transition.html#Transition">Transition</a>.
  154. </p>
  155. <p>It is usually more awkward to express a function in terms of
  156. a <code>transfer</code> than to code it directly using recursion or other list
  157. operations. However, this feature is provided by the virtual machine for
  158. several reasons.
  159. </p>
  160. <ul>
  161. <li> Functions in this form may be an easier translation target if the
  162. source is an imperative language.
  163. </li><li> Translating from virtual code to asynchronous circuits or process
  164. <a name="index-asynchronous-circuits"></a>
  165. networks has been a research interest of the author, and code in this
  166. <a name="index-author-1"></a>
  167. form lends itself to easy recognition and mapping onto discrete components.
  168. </li><li> The &lsquo;<samp>--byte-transducer</samp>&rsquo; and &lsquo;<samp>--interactive</samp>&rsquo; command
  169. line options to <code>avram</code> cause an application to be invoked in a
  170. <a name="index-state-transition-function-1"></a>
  171. similar manner to the transition function in a <code>transfer</code>
  172. function, so this feature allows for easy simulation and troubleshooting
  173. of these applications without actually deploying them.
  174. </li></ul>
  175. <hr size="1">
  176. <table cellpadding="1" cellspacing="1" border="0">
  177. <tr><td valign="middle" align="left">[<a href="Sort.html#Sort" title="Previous section in reading order"> &lt; </a>]</td>
  178. <td valign="middle" align="left">[<a href="Mapcur.html#Mapcur" title="Next section in reading order"> &gt; </a>]</td>
  179. <td valign="middle" align="left"> &nbsp; </td>
  180. <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  181. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Up section"> Up </a>]</td>
  182. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  183. <td valign="middle" align="left"> &nbsp; </td>
  184. <td valign="middle" align="left"> &nbsp; </td>
  185. <td valign="middle" align="left"> &nbsp; </td>
  186. <td valign="middle" align="left"> &nbsp; </td>
  187. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  188. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  189. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  190. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  191. </tr></table>
  192. <p>
  193. <font size="-1">
  194. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  195. </font>
  196. <br>
  197. </p>
  198. </body>
  199. </html>