123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207 |
- <!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.1 Raw Material</title>
- <meta name="description" content="avram - a virtual machine code interpreter: 2.1 Raw Material">
- <meta name="keywords" content="avram - a virtual machine code interpreter: 2.1 Raw Material">
- <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="Raw-Material"></a>
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" 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-Machine-Specification.html#Virtual-Machine-Specification" 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="Raw-Material-1"></a>
- <h2 class="section">2.1 Raw Material</h2>
- <p>The purpose of this section is to instill some basic concepts about the
- way information is stored or communicated by the virtual machine, which
- may be necessary for an understanding of subsequent sections.
- </p>
- <p>The virtual machine represents both programs and data as members of a
- semantic domain that is straightforward to describe. Lisp users and
- functional programmers may recognize familiar concepts of atoms and
- <a name="index-lists"></a>
- lists in this description. However, these terms are avoided for the
- moment, in order to keep this presentation self contained and to prevent
- knowledgeable readers from inferring any unintended meanings.
- </p>
- <p>As a rule, it is preferable to avoid overspecifying any theoretical
- artifact. In this spirit, the set of entities with which the virtual
- machine is concerned can be defined purely in terms of the properties we
- need it to have.
- </p>
- <dl compact="compact">
- <dt> <em>A distinguished element</em></dt>
- <dd><p>A particular element of the set is designated, arbitrarily or otherwise,
- as a distinguished element. Given any element of the set, it is
- always possible to decide whether or not it is the distinguished
- element. The set is non-empty and such an element exists.
- </p></dd>
- <dt> <em>A binary operator</em></dt>
- <dd><p>A map from pairs of elements of the set to elements of the set exists
- and meets these conditions.
- </p>
- <ul>
- <li> It associates a <em>unique</em> element of the set with any given
- ordered pair of elements from the set.
- </li><li> It does not associate the distinguished element with any pair of elements.
- </li></ul>
- </dd>
- </dl>
- <p>For the sake of concreteness, an additional constraint is needed:
- <em>the set has no proper subset satisfying the above conditions</em>. Any
- number of constructions remain within these criteria, but there is no
- need to restrict them further, because they are all equivalent for our
- purposes.
- </p>
- <p>To see that these properties provide all the structure we need for
- general purpose computation, we may suppose some given set <code>S</code> and
- an operator <code>cons</code> having them are fixed, and infer the following
- points.
- </p>
- <ul>
- <li> <code>S</code> contains at least one element, the distinguished
- element. Call it <code>nil</code>.
- <a name="index-nil"></a>
- </li><li> The pair <code>(nil,nil)</code> is a pair of
- elements of <code>S</code>, so there must be an element of <code>S</code> that
- <code>cons</code> associates with it. We can denote this element
- <code>cons(nil,nil)</code>.
- <a name="index-cons"></a>
- </li><li> As no pair of elements is associated with the
- distinguished element, <code>cons(nil,nil)</code> must differ from <code>nil</code>, so
- <code>S</code> contains at least two distinct elements.
- </li><li> The pair <code>(nil,cons(nil,nil))</code> therefore differs from <code>(nil,nil)</code>,
- but because it is yet another pair of elements from <code>S</code>, there
- must be an element associated with it by the operator. We can denote
- this element as <code>cons(nil,cons(nil,nil))</code>.
- </li><li> Inasmuch as the operator
- associates every pair of elements with a <em>unique</em> element,
- <code>cons(nil,cons(nil,nil))</code> must differ from the element associated
- with any other pair of elements, so it must differ from
- <code>cons(nil,nil)</code>, and we conclude that <code>nil</code>,
- <code>cons(nil,nil)</code> and <code>cons(nil,cons(nil,nil))</code> constitute three
- distinct elements of the set <code>S</code>.
- </li><li> By defining <code>cons(cons(nil,nil),nil)</code>
- and <code>cons(cons(nil,nil),cons(nil,nil))</code> analogously and following a
- similar line of reasoning, one may establish the existence of two more
- distinct elements of <code>S</code>.
- </li></ul>
- <p>It is not difficult to see that an argument in more general terms could
- show that the inclusion of infinitely many elements in <code>S</code> is
- mandated by the properties of the <code>cons</code> operator. Furthermore,
- every element of <code>S</code> other than <code>nil</code> owes its inclusion to
- being associated with some other pair of elements by <code>cons</code>,
- because if it were not, its exclusion would permit a proper subset of
- <code>S</code> to meet all of the above conditions. We can conclude that
- <code>S</code> contains exactly <code>nil</code> and the countable infinitude of
- elements of the form <code>cons(x,y)</code>, where <code>x</code> and <code>y</code> are
- either <code>nil</code> or something of the form <code>cons(…)</code> themselves.
- </p>
- <p>Some specific examples of sets and operators that have the required
- properties are as follows.
- </p>
- <ul>
- <li> the set of natural numbers, with <code>0</code> as the distinguished element,
- and the <code>cons</code> operator defined by <code>cons(<var>x</var>,<var>y</var>) =
- ((<var>x</var>+<var>y</var>)(<var>x</var>+<var>y</var>+1))/2 + <var>y</var> + 1</code>
- </li><li> a set of balanced strings of parentheses, with <code>()</code> as the
- distinguished element, and <code>cons</code> defined as string concatenation
- followed by enclosure in parentheses
- </li><li> a set of ordered binary trees, with the empty tree as the distinguished
- element, and the <code>cons</code> operator as that which takes an ordered
- pair of trees to the tree having them as its descendents
- </li><li> a set containing only its own Cartesian product and an arbitrary
- but fixed element <code>nil</code>, with <code>cons</code> being the identity
- function
- </li></ul>
- <p>Each of these models may suggest a different implementation, some of which
- are more practical than others. The remainder of this document is
- phrased somewhat imprecisely in terms of a combination of the latter
- two. The nature of the set in question is not considered further, and
- elements of the set are described as “trees” or “lists”. The
- <a name="index-trees"></a>
- <a name="index-lists-1"></a>
- distinguished element is denoted by <code>nil</code> and the operator by
- <code>cons</code>. Where no ambiguity results, <code>cons(x,y)</code> may be written
- simply as <code>(x,y)</code>. These terms should not be seen as constraints
- on the implementation.
- </p>
- <hr size="1">
- <table cellpadding="1" cellspacing="1" border="0">
- <tr><td valign="middle" align="left">[<a href="Virtual-Machine-Specification.html#Virtual-Machine-Specification" title="Previous section in reading order"> < </a>]</td>
- <td valign="middle" align="left">[<a href="Concrete-Syntax.html#Concrete-Syntax" 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-Machine-Specification.html#Virtual-Machine-Specification" 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>
|