Iteration.html 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on December 10, 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.12 Iteration</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 2.7.12 Iteration">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 2.7.12 Iteration">
  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="Iteration"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Member.html#Member" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" 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="Iteration-1"></a>
  58. <h3 class="subsection">2.7.12 Iteration</h3>
  59. <a name="index-recursion-1"></a>
  60. <a name="index-iterate"></a>
  61. <p>One of many alternatives to recursion provided by the virtual machine is
  62. iteration, which allows an operation to be repeated until a condition is
  63. met. If the source language is imperative, this feature provides an easy
  64. means of translating loop statements to virtual code. In languages that allow
  65. functions to be treated as data, iteration can be regarded as a function
  66. that takes a predicate and a function as arguments, and returns a
  67. function that applies the given function repeatedly to its argument
  68. until the predicate is refuted.
  69. </p>
  70. <p>Iterative applications are expressed in virtual code by the pattern shown below.
  71. </p>
  72. <dl compact="compact">
  73. <dt> <em>T21</em></dt>
  74. <dd><p>[[<code>iterate</code>]] <code>(<var>p</var>,<var>f</var>)</code> = <code>((nil,nil),(nil,(<var>p</var>,<var>f</var>)))</code>
  75. </p></dd>
  76. </dl>
  77. <p>In the <code>silly</code> language, the <code>iterate</code> mnemonic plays the role
  78. of the function that takes the virtual code for a predicate
  79. <code><var>p</var></code> and a function <code><var>f</var></code> as arguments, and returns
  80. the virtual code for an iterating function.
  81. </p>
  82. <p>The code for an iterating function is recognized as such by the virtual
  83. machine emulator only if the subtrees <code><var>f</var></code> and <code><var>p</var></code> are other
  84. than <code>nil</code>. The resulting function tests the argument
  85. <code><var>x</var></code> with <code><var>p</var></code> and returns <code><var>x</var></code> if the
  86. predicate is false.
  87. </p>
  88. <dl compact="compact">
  89. <dt> <em>P22</em></dt>
  90. <dd><p>([[<code>iterate</code>]] <code>(<var>p</var>,<var>f</var>)</code>) <code><var>x</var></code> = <code><var>x</var></code> if <code><var>p</var> <var>x</var></code> = <code>nil</code>
  91. </p></dd>
  92. </dl>
  93. <p>If the predicate turns out to be true, <code><var>f</var></code> is applied to
  94. <code><var>x</var></code>, and then another iteration is performed.
  95. </p>
  96. <dl compact="compact">
  97. <dt> <em>P23</em></dt>
  98. <dd><p>([[<code>iterate</code>]] <code>(<var>p</var>,<var>f</var>)</code>) <code><var>x</var></code> =
  99. ([[<code>iterate</code>]] <code>(<var>p</var>,<var>f</var>)</code>) <code><var>f</var> <var>x</var></code> if <code><var>p</var> <var>x</var></code> is a non-<code>nil</code> tree
  100. </p></dd>
  101. </dl>
  102. <hr size="1">
  103. <table cellpadding="1" cellspacing="1" border="0">
  104. <tr><td valign="middle" align="left">[<a href="Member.html#Member" title="Previous section in reading order"> &lt; </a>]</td>
  105. <td valign="middle" align="left">[<a href="List-Combinators.html#List-Combinators" title="Next section in reading order"> &gt; </a>]</td>
  106. <td valign="middle" align="left"> &nbsp; </td>
  107. <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>
  108. <td valign="middle" align="left">[<a href="Virtual-Code-Semantics.html#Virtual-Code-Semantics" title="Up section"> Up </a>]</td>
  109. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Next chapter"> &gt;&gt; </a>]</td>
  110. <td valign="middle" align="left"> &nbsp; </td>
  111. <td valign="middle" align="left"> &nbsp; </td>
  112. <td valign="middle" align="left"> &nbsp; </td>
  113. <td valign="middle" align="left"> &nbsp; </td>
  114. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  115. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  116. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  117. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  118. </tr></table>
  119. <p>
  120. <font size="-1">
  121. This document was generated on <i>December 10, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  122. </font>
  123. <br>
  124. </p>
  125. </body>
  126. </html>