Assignment.html 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190
  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.10 Assignment</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.10 Assignment">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.10 Assignment">
  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="Assignment"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Refer.html#Refer" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="Predicates.html#Predicates" 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="Virtual-Code-Semantics.html#Virtual-Code-Semantics" 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="Assignment-1"></a>
  58. <h3 class="subsection">2.7.10 Assignment</h3>
  59. <a name="index-assignment"></a>
  60. <a name="index-imperative-programming"></a>
  61. <p>In an imperative programming paradigm, a machine consists partly of an
  62. ensemble of addressable storage locations, whose contents are changed
  63. over time by assignment statements. An assignment statement includes
  64. some computable function of the global machine state, and the address of
  65. the location whose contents will be overwritten with the value computed
  66. from the function when it is evaluated.
  67. </p>
  68. <p>Compiling a language containing assignment statements into virtual
  69. machine code suitable for <code>avram</code> might be facilitated by
  70. exploiting the following property.
  71. </p>
  72. <dl compact="compact">
  73. <dt> <em>P16</em></dt>
  74. <dd><p>([[<code>assign</code>]] <code>(<var>p</var>,<var>f</var>)</code>) <code><var>x</var></code> = [[<code>replace</code>]] <code>((<var>p</var>,<var>f</var> <var>x</var>),<var>x</var>)</code>
  75. </p></dd>
  76. </dl>
  77. <p>The identifier <code>assign</code> is used in <code>silly</code> to express a
  78. virtual code fragment having the form shown below, and <code>replace</code>
  79. corresponds to a further operation to be explained presently.
  80. <a name="index-assign"></a>
  81. </p>
  82. <dl compact="compact">
  83. <dt> <em>T18</em></dt>
  84. <dd><p>[[<code>assign</code>]] <code>(<var>p</var>,<var>f</var>)</code> = <code>(((<var>p</var>,<var>f</var>),nil),nil)</code>
  85. </p></dd>
  86. </dl>
  87. <p>This feature simulates assignment statements in the following way. The
  88. variable <code><var>x</var></code> in <em>P16</em> corresponds intuitively to the set
  89. of addressable locations in the machine. The variable <code><var>f</var></code>
  90. corresponds to the function whose value will be stored in the location
  91. addressed by <code><var>p</var></code>. The result of a function expressed using
  92. <code>assign</code> is a new store similar to the argument <code><var>x</var></code>, but
  93. with the part of it in location <code><var>p</var></code> replaced by <code><var>f</var>
  94. <var>x</var></code>. A source text with a sequence of assignment statements could
  95. therefore be translated directly into a functional composition of trees
  96. in this form.
  97. </p>
  98. <a name="index-storage-locations"></a>
  99. <p>The way storage locations are modeled in virtual code using this feature
  100. would be as nested pairs, and the address <code><var>p</var></code> of a location
  101. is a tree interpreted similarly to the trees used as operands to the
  102. <code>field</code> operator described in <a href="Field.html#Field">Field</a>, to specify
  103. deconstructions. In fact, <code>replace</code> can be defined as a minimal
  104. solution to the following equation.
  105. <a name="index-replace"></a>
  106. </p>
  107. <dl compact="compact">
  108. <dt> <em>E0</em></dt>
  109. <dd><p>([[<code>field</code>]] <code><var>p</var></code>) [[<code>replace</code>]] <code>((<var>p</var>,<var>y</var>),<var>x</var>)</code> = <code><var>y</var></code>
  110. </p></dd>
  111. </dl>
  112. <p>This equation regrettably does
  113. not lend itself to inferring the <code>silly</code> source for <code>replace</code>
  114. <a name="index-isolate-1"></a>
  115. using the <code>isolate</code> algorithm in <a href="Variable-Freedom.html#Variable-Freedom">Variable Freedom</a>, so an explicit
  116. construction is given in <a href="Replace.html#Replace">Replace</a>. This construction need not concern a
  117. reader who considers the equation a sufficiently precise specification
  118. in itself.
  119. </p>
  120. <p>In view of the way addresses for deconstruction are represented as
  121. trees, it would be entirely correct to infer from this equation that a
  122. tuple of values computed together can be assigned to a tuple of
  123. locations. The locations don&rsquo;t even have to be &ldquo;contiguous&rdquo;, but could
  124. be anywhere in the tree representing the store, and the function is
  125. computed from the contents of all of them prior to the update. Hence,
  126. this simulation of assignment fails to capture the full inconvenience of
  127. imperative programming except in the special case of a single value
  128. assigned to a single location, but fortunately this case is the only one
  129. most languages allow.
  130. </p>
  131. <p>There is another benefit to this feature besides running languages with
  132. assignment statements in them, which is the support of abstract or
  133. opaque data structures. A function that takes an abstract data structure
  134. as an argument and returns something of the same type can be coded in a
  135. way that is independent of the fields it doesn&rsquo;t use. For example, a
  136. data structure with three fields having the field identifiers
  137. <code>foo</code>, <code>bar</code>, and <code>baz</code> in some source language might be
  138. represented as a tuple <code>((<var>foo contents</var>,<var>bar
  139. contents</var>),<var>baz contents</var>)</code> on the virtual code level. Compile time
  140. constants like <code>bar = ((nil,(nil,nil)),nil)</code> could be defined in an
  141. effort to hide the details of the representation, so that the virtual
  142. code <code>field bar</code> is used instead of <code>compose(right,left)</code>.
  143. Using field identifiers appropriately, a function that transforms such a
  144. structure by operating on the <code>bar</code> field could have the virtual
  145. <a name="index-field-1"></a>
  146. code <code>couple(couple(field foo,compose(f,field bar)),field
  147. baz)</code>. However, this code does not avoid depending on the representation
  148. of the data structure, because it relies on the assumption of the <code>foo</code>
  149. field being on the left of the left, and the <code>baz</code> field being on
  150. the right. On the other hand, the code <code>assign(bar,compose(f,field
  151. bar))</code> does the same job without depending on anything but the position
  152. of the <code>bar</code> field. Furthermore, if this position were to change
  153. relative to the others, the code maintenance would be limited to a
  154. recompilation.
  155. </p>
  156. <hr size="1">
  157. <table cellpadding="1" cellspacing="1" border="0">
  158. <tr><td valign="middle" align="left">[<a href="Refer.html#Refer" title="Previous section in reading order"> &lt; </a>]</td>
  159. <td valign="middle" align="left">[<a href="Predicates.html#Predicates" title="Next section in reading order"> &gt; </a>]</td>
  160. <td valign="middle" align="left"> &nbsp; </td>
  161. <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>
  162. <td valign="middle" align="left">[<a href="Virtual-Code-Semantics.html#Virtual-Code-Semantics" title="Up section"> Up </a>]</td>
  163. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  164. <td valign="middle" align="left"> &nbsp; </td>
  165. <td valign="middle" align="left"> &nbsp; </td>
  166. <td valign="middle" align="left"> &nbsp; </td>
  167. <td valign="middle" align="left"> &nbsp; </td>
  168. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  169. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  170. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  171. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  172. </tr></table>
  173. <p>
  174. <font size="-1">
  175. This document was generated on <i>November 8, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  176. </font>
  177. <br>
  178. </p>
  179. </body>
  180. </html>