123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190 |
- <!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: 2.7.10 Assignment</title>
- <meta name="description" content="avram - a virtual machine code interpreter: 2.7.10 Assignment">
- <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.10 Assignment">
- <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="Assignment"></a>
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Refer.html#Refer" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Predicates.html#Predicates" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Virtual-Code-Semantics.html#Virtual-Code-Semantics" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" 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="Assignment-1"></a>
- <h3 class="subsection">2.7.10 Assignment</h3>
- <a name="index-assignment"></a>
- <a name="index-imperative-programming"></a>
- <p>In an imperative programming paradigm, a machine consists partly of an
- ensemble of addressable storage locations, whose contents are changed
- over time by assignment statements. An assignment statement includes
- some computable function of the global machine state, and the address of
- the location whose contents will be overwritten with the value computed
- from the function when it is evaluated.
- </p>
- <p>Compiling a language containing assignment statements into virtual
- machine code suitable for <code>avram</code> might be facilitated by
- exploiting the following property.
- </p>
- <dl compact="compact">
- <dt> <em>P16</em></dt>
- <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>
- </p></dd>
- </dl>
- <p>The identifier <code>assign</code> is used in <code>silly</code> to express a
- virtual code fragment having the form shown below, and <code>replace</code>
- corresponds to a further operation to be explained presently.
- <a name="index-assign"></a>
- </p>
- <dl compact="compact">
- <dt> <em>T18</em></dt>
- <dd><p>[[<code>assign</code>]] <code>(<var>p</var>,<var>f</var>)</code> = <code>(((<var>p</var>,<var>f</var>),nil),nil)</code>
- </p></dd>
- </dl>
- <p>This feature simulates assignment statements in the following way. The
- variable <code><var>x</var></code> in <em>P16</em> corresponds intuitively to the set
- of addressable locations in the machine. The variable <code><var>f</var></code>
- corresponds to the function whose value will be stored in the location
- addressed by <code><var>p</var></code>. The result of a function expressed using
- <code>assign</code> is a new store similar to the argument <code><var>x</var></code>, but
- with the part of it in location <code><var>p</var></code> replaced by <code><var>f</var>
- <var>x</var></code>. A source text with a sequence of assignment statements could
- therefore be translated directly into a functional composition of trees
- in this form.
- </p>
- <a name="index-storage-locations"></a>
- <p>The way storage locations are modeled in virtual code using this feature
- would be as nested pairs, and the address <code><var>p</var></code> of a location
- is a tree interpreted similarly to the trees used as operands to the
- <code>field</code> operator described in <a href="Field.html#Field">Field</a>, to specify
- deconstructions. In fact, <code>replace</code> can be defined as a minimal
- solution to the following equation.
- <a name="index-replace"></a>
- </p>
- <dl compact="compact">
- <dt> <em>E0</em></dt>
- <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>
- </p></dd>
- </dl>
- <p>This equation regrettably does
- not lend itself to inferring the <code>silly</code> source for <code>replace</code>
- <a name="index-isolate-1"></a>
- using the <code>isolate</code> algorithm in <a href="Variable-Freedom.html#Variable-Freedom">Variable Freedom</a>, so an explicit
- construction is given in <a href="Replace.html#Replace">Replace</a>. This construction need not concern a
- reader who considers the equation a sufficiently precise specification
- in itself.
- </p>
- <p>In view of the way addresses for deconstruction are represented as
- trees, it would be entirely correct to infer from this equation that a
- tuple of values computed together can be assigned to a tuple of
- locations. The locations don’t even have to be “contiguous”, but could
- be anywhere in the tree representing the store, and the function is
- computed from the contents of all of them prior to the update. Hence,
- this simulation of assignment fails to capture the full inconvenience of
- imperative programming except in the special case of a single value
- assigned to a single location, but fortunately this case is the only one
- most languages allow.
- </p>
- <p>There is another benefit to this feature besides running languages with
- assignment statements in them, which is the support of abstract or
- opaque data structures. A function that takes an abstract data structure
- as an argument and returns something of the same type can be coded in a
- way that is independent of the fields it doesn’t use. For example, a
- data structure with three fields having the field identifiers
- <code>foo</code>, <code>bar</code>, and <code>baz</code> in some source language might be
- represented as a tuple <code>((<var>foo contents</var>,<var>bar
- contents</var>),<var>baz contents</var>)</code> on the virtual code level. Compile time
- constants like <code>bar = ((nil,(nil,nil)),nil)</code> could be defined in an
- effort to hide the details of the representation, so that the virtual
- code <code>field bar</code> is used instead of <code>compose(right,left)</code>.
- Using field identifiers appropriately, a function that transforms such a
- structure by operating on the <code>bar</code> field could have the virtual
- <a name="index-field-1"></a>
- code <code>couple(couple(field foo,compose(f,field bar)),field
- baz)</code>. However, this code does not avoid depending on the representation
- of the data structure, because it relies on the assumption of the <code>foo</code>
- field being on the left of the left, and the <code>baz</code> field being on
- the right. On the other hand, the code <code>assign(bar,compose(f,field
- bar))</code> does the same job without depending on anything but the position
- of the <code>bar</code> field. Furthermore, if this position were to change
- relative to the others, the code maintenance would be limited to a
- recompilation.
- </p>
- <hr size="1">
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Refer.html#Refer" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Predicates.html#Predicates" title="Next section in reading order"> > </a>]</td>
- <td valign="middle" align="left"> </td>
- <td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Beginning of this chapter or previous chapter"> << </a>]</td>
- <td valign="middle" align="left">[<a href="Virtual-Code-Semantics.html#Virtual-Code-Semantics" title="Up section"> Up </a>]</td>
- <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" 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>
|