Mercurial > dylan

annotate categorical/imperative.html @ 11:1f112b4f9e8f tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed what was baroque.
author Dylan Holmes <ocsenave@gmail.com>
date Tue, 01 Nov 2011 02:30:49 -0500
parents b4de894a1e2e
children
rev   line source
rlm@2 1 <?xml version="1.0" encoding="utf-8"?>
rlm@2 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
rlm@2 3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
rlm@2 4 <html xmlns="http://www.w3.org/1999/xhtml"
rlm@2 5 lang="en" xml:lang="en">
rlm@2 6 <head>
rlm@2 7 <title>LAMBDA: The Ultimate Imperative</title>
rlm@2 8 <meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
rlm@2 9 <meta name="generator" content="Org-mode"/>
rlm@2 10 <meta name="generated" content="2011-07-15 02:49:04 EDT"/>
rlm@2 11 <meta name="author" content="Guy Lewis Steele Jr. and Gerald Jay Sussman"/>
rlm@2 12 <meta name="description" content=""/>
rlm@2 13 <meta name="keywords" content=""/>
rlm@2 14 <style type="text/css">
rlm@2 15 <!--/*--><![CDATA[/*><!--*/
rlm@2 16 html { font-family: Times, serif; font-size: 12pt; }
rlm@2 17 .title { text-align: center; }
rlm@2 18 .todo { color: red; }
rlm@2 19 .done { color: green; }
rlm@2 20 .tag { background-color: #add8e6; font-weight:normal }
rlm@2 21 .target { }
rlm@2 22 .timestamp { color: #bebebe; }
rlm@2 23 .timestamp-kwd { color: #5f9ea0; }
rlm@2 24 .right {margin-left:auto; margin-right:0px; text-align:right;}
rlm@2 25 .left {margin-left:0px; margin-right:auto; text-align:left;}
rlm@2 26 .center {margin-left:auto; margin-right:auto; text-align:center;}
rlm@2 27 p.verse { margin-left: 3% }
rlm@2 28 pre {
rlm@2 29 border: 1pt solid #AEBDCC;
rlm@2 30 background-color: #F3F5F7;
rlm@2 31 padding: 5pt;
rlm@2 32 font-family: courier, monospace;
rlm@2 33 font-size: 90%;
rlm@2 34 overflow:auto;
rlm@2 35 }
rlm@2 36 table { border-collapse: collapse; }
rlm@2 37 td, th { vertical-align: top; }
rlm@2 38 th.right { text-align:center; }
rlm@2 39 th.left { text-align:center; }
rlm@2 40 th.center { text-align:center; }
rlm@2 41 td.right { text-align:right; }
rlm@2 42 td.left { text-align:left; }
rlm@2 43 td.center { text-align:center; }
rlm@2 44 dt { font-weight: bold; }
rlm@2 45 div.figure { padding: 0.5em; }
rlm@2 46 div.figure p { text-align: center; }
rlm@2 47 textarea { overflow-x: auto; }
rlm@2 48 .linenr { font-size:smaller }
rlm@2 49 .code-highlighted {background-color:#ffff00;}
rlm@2 50 .org-info-js_info-navigation { border-style:none; }
rlm@2 51 #org-info-js_console-label { font-size:10px; font-weight:bold;
rlm@2 52 white-space:nowrap; }
rlm@2 53 .org-info-js_search-highlight {background-color:#ffff00; color:#000000;
rlm@2 54 font-weight:bold; }
rlm@2 55 /*]]>*/-->
rlm@2 56 </style>
rlm@2 57 <script type="text/javascript">
rlm@2 58 <!--/*--><![CDATA[/*><!--*/
rlm@2 59 function CodeHighlightOn(elem, id)
rlm@2 60 {
rlm@2 61 var target = document.getElementById(id);
rlm@2 62 if(null != target) {
rlm@2 63 elem.cacheClassElem = elem.className;
rlm@2 64 elem.cacheClassTarget = target.className;
rlm@2 65 target.className = "code-highlighted";
rlm@2 66 elem.className = "code-highlighted";
rlm@2 67 }
rlm@2 68 }
rlm@2 69 function CodeHighlightOff(elem, id)
rlm@2 70 {
rlm@2 71 var target = document.getElementById(id);
rlm@2 72 if(elem.cacheClassElem)
rlm@2 73 elem.className = elem.cacheClassElem;
rlm@2 74 if(elem.cacheClassTarget)
rlm@2 75 target.className = elem.cacheClassTarget;
rlm@2 76 }
rlm@2 77 /*]]>*///-->
rlm@2 78 </script>
rlm@2 79 <script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js">
rlm@2 80 <!--/*--><![CDATA[/*><!--*/
rlm@2 81 MathJax.Hub.Config({
rlm@2 82 // Only one of the two following lines, depending on user settings
rlm@2 83 // First allows browser-native MathML display, second forces HTML/CSS
rlm@2 84 // config: ["MMLorHTML.js"], jax: ["input/TeX"],
rlm@2 85 jax: ["input/TeX", "output/HTML-CSS"],
rlm@2 86 extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",
rlm@2 87 "TeX/noUndefined.js"],
rlm@2 88 tex2jax: {
rlm@2 89 inlineMath: [ ["\\(","\\)"] ],
rlm@2 90 displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],
rlm@2 91 skipTags: ["script","noscript","style","textarea","pre","code"],
rlm@2 92 ignoreClass: "tex2jax_ignore",
rlm@2 93 processEscapes: false,
rlm@2 94 processEnvironments: true,
rlm@2 95 preview: "TeX"
rlm@2 96 },
rlm@2 97 showProcessingMessages: true,
rlm@2 98 displayAlign: "center",
rlm@2 99 displayIndent: "2em",
rlm@2 100
rlm@2 101 "HTML-CSS": {
rlm@2 102 scale: 100,
rlm@2 103 availableFonts: ["STIX","TeX"],
rlm@2 104 preferredFont: "TeX",
rlm@2 105 webFont: "TeX",
rlm@2 106 imageFont: "TeX",
rlm@2 107 showMathMenu: true,
rlm@2 108 },
rlm@2 109 MMLorHTML: {
rlm@2 110 prefer: {
rlm@2 111 MSIE: "MML",
rlm@2 112 Firefox: "MML",
rlm@2 113 Opera: "HTML",
rlm@2 114 other: "HTML"
rlm@2 115 }
rlm@2 116 }
rlm@2 117 });
rlm@2 118 /*]]>*///-->
rlm@2 119 </script>
rlm@2 120 </head>
rlm@2 121 <body>
rlm@2 122
rlm@2 123 <div id="content">
rlm@2 124
rlm@2 125
rlm@2 126
rlm@2 127 <div id="table-of-contents">
rlm@2 128 <h2>Table of Contents</h2>
rlm@2 129 <div id="text-table-of-contents">
rlm@2 130 <ul>
rlm@2 131 <li><a href="#sec-1">1 Abstract </a></li>
rlm@2 132 <li><a href="#sec-2">2 Introduction </a>
rlm@2 133 <ul>
rlm@2 134 <li><a href="#sec-2-1">2.1 Simple Loops </a>
rlm@2 135 <ul>
rlm@2 136 <li><a href="#sec-2-1-1">2.1.1 Simple Recursion </a></li>
rlm@2 137 <li><a href="#sec-2-1-2">2.1.2 Iteration </a></li>
rlm@2 138 </ul></li>
rlm@2 139 </ul>
rlm@2 140 </li>
rlm@2 141 <li><a href="#sec-3">3 Imperative Programming </a>
rlm@2 142 <ul>
rlm@2 143 <li><a href="#sec-3-1">3.1 Compound Statements </a></li>
rlm@2 144 <li><a href="#sec-3-2">3.2 2.2. The G0 TO Statement </a></li>
rlm@2 145 <li><a href="#sec-3-3">3.3 2.3. Simple Assignment </a></li>
rlm@2 146 <li><a href="#sec-3-4">3.4 Compound Expressions ' </a></li>
rlm@2 147 </ul>
rlm@2 148 </li>
rlm@2 149 <li><a href="#sec-4">4 Continuations </a>
rlm@2 150 <ul>
rlm@2 151 <li><a href="#sec-4-1">4.1 Continuation-Passing Recursion </a></li>
rlm@2 152 <li><a href="#sec-4-2">4.2 Escape Expressions </a></li>
rlm@2 153 </ul>
rlm@2 154 </li>
rlm@2 155 </ul>
rlm@2 156 </div>
rlm@2 157 </div>
rlm@2 158
rlm@2 159 <div id="outline-container-1" class="outline-2">
rlm@2 160 <h2 id="sec-1"><span class="section-number-2">1</span> Abstract </h2>
rlm@2 161 <div class="outline-text-2" id="text-1">
rlm@2 162
rlm@2 163
rlm@2 164 <p>
rlm@2 165 We demonstrate how to model the following common programming constructs in
rlm@2 166 terms of an applicative order language similar to LISP:
rlm@2 167 </p><ul>
rlm@2 168 <li>Simple Recursion
rlm@2 169 </li>
rlm@2 170 <li>Iteration
rlm@2 171 </li>
rlm@2 172 <li>Compound Statements and Expressions
rlm@2 173 </li>
rlm@2 174 <li>GO TO and Assignment
rlm@2 175 </li>
rlm@2 176 <li>Continuation—Passing
rlm@2 177 </li>
rlm@2 178 <li>Escape Expressions
rlm@2 179 </li>
rlm@2 180 <li>Fluid Variables
rlm@2 181 </li>
rlm@2 182 <li>Call by Name, Call by Need, and Call by Reference
rlm@2 183 </li>
rlm@2 184 </ul>
rlm@2 185
rlm@2 186 <p>The models require only (possibly self-referent) lambda application,
rlm@2 187 conditionals, and (rarely) assignment. No complex data structures such as
rlm@2 188 stacks are used. The models are transparent, involving only local syntactic
rlm@2 189 transformations.
rlm@2 190 Some of these models, such as those for GO TO and assignment, are already well
rlm@2 191 known, and appear in the work of Landin, Reynolds, and others. The models for
rlm@2 192 escape expressions, fluid variables, and call by need with side effects are
rlm@2 193 new. This paper is partly tutorial in intent, gathering all the models
rlm@2 194 together for purposes of context.
rlm@2 195 This report describes research done at the Artificial Intelligence Laboratory
rlm@2 196 of the Massachusetts Institute of Teehnology. Support for the laboratory's
rlm@2 197 artificial intelligence research is provided in part by the Advanced Research
rlm@2 198 Projects Agency of the Department of Defense under Office of Naval Research
rlm@2 199 contract N000l4-75-C-0643.
rlm@2 200 </p>
rlm@2 201 </div>
rlm@2 202
rlm@2 203 </div>
rlm@2 204
rlm@2 205 <div id="outline-container-2" class="outline-2">
rlm@2 206 <h2 id="sec-2"><span class="section-number-2">2</span> Introduction </h2>
rlm@2 207 <div class="outline-text-2" id="text-2">
rlm@2 208
rlm@2 209
rlm@2 210 <p>
rlm@2 211 We catalogue a number of common programming constructs. For each
rlm@2 212 construct we examine "typical" usage in well-known programming languages, and
rlm@2 213 then capture the essence of the semantics of the construct in terms of a
rlm@2 214 common meta-language.
rlm@2 215 The lambda calculus {Note Alonzowins} is often used as such a meta-
rlm@2 216 language. Lambda calculus offers clean semantics, but it is clumsy because it
rlm@2 217 was designed to be a minimal language rather than a convenient one. All
rlm@2 218 lambda calculus "functions" must take exactly one "argument"; the only "data
rlm@2 219 type" is lambda expressions; and the only "primitive operation‘ is variable‘
rlm@2 220 substitution. While its utter simplicity makes lambda calculus ideal for
rlm@2 221 logicians, it is too primitive for use by programmers. The meta-language we
rlm@2 222 use is a programming language called SCHEME {Note Schemepaper) which is based
rlm@2 223 on lambda calculus.
rlm@2 224 SCHEME is a dialect of LISP. [McCarthy 62] It is an expression-
rlm@2 225 oriented, applicative order, interpreter-based language which allows one to
rlm@2 226 manipulate programs as data. It differs from most current dialects of LISP in
rlm@2 227 that it closes all lambda expressions in the environment of their definition
rlm@2 228 or declaration, rather than in the execution environment. {Note Closures}
rlm@2 229 This preserves the substitution semantics of lambda calculus, and has the
rlm@2 230 consequence that all variables are lexically scoped, as in ALGOL. [Naur 63]
rlm@2 231 Another difference is that SCHEME is implemented in such a way that tail-
rlm@2 232 recursions execute without net growth of the interpreter stack. {Note
rlm@2 233 Schemenote} We have chosen to use LISP syntax rather than, say, ALGOL syntax
rlm@2 234 because we want to treat programs as data for the purpose of describing
rlm@2 235 transformations on the code. LISP supplies names for the parts of an
rlm@2 236 executable expression and standard operators for constructing expressions and
rlm@2 237 extracting their components. The use of LISP syntax makes the structure of
rlm@2 238 such expressions manifest. We use ALGOL as an expository language, because it
rlm@2 239 is familiar to many people, but ALGOL is not sufficiently powerful to express
rlm@2 240 the necessary concepts; in particular, it does not allow functions to return
rlm@2 241 functions as values. we are thus forced to use a dialect of LISP in many
rlm@2 242 cases.
rlm@2 243 We will consider various complex programming language constructs and
rlm@2 244 show how to model them in terms of only a few simple ones. As far as possible
rlm@2 245 we will use only three control constructs from SCHEME: LAMBDA expressions, as
rlm@2 246 in LISP, which are Just functions with lexically scoped free variables;
rlm@2 247 LABELS, which allows declaration of mutually recursive procedures (Note
rlm@2 248 Labelsdef}; and IF, a primitive conditional expression. For more complex
rlm@2 249 modelling we will introduce an assignment primitive (ASET).i We will freely
rlm@2 250 assume the existence of other comon primitives, such as arithmetic functions.
rlm@2 251 The constructs we will examine are divided into four broad classes.
rlm@2 252 The first is sfinph?Lo0pl; this contains simple recursions and iterations, and
rlm@2 253 an introduction to the notion of continuations. The second is hmponflivo
rlm@2 254 Connrucls; this includes compound statements, G0 T0, and simple variable
rlm@2 255 assignments. The third is continuations, which encompasses the distinction between statements and expressions, escape operators (such as Landin's J-
rlm@2 256 operator [Landin 65] and Reynold's escape expression [Reynolds 72]). and fluid
rlm@2 257 (dynamically bound) variables. The fourth is Parameter Passing Mechanisms, such
rlm@2 258 as ALGOL call—by-name and FORTRAN call-by-location.
rlm@2 259 Some of the models presented here are already well-known, particularly
rlm@2 260 those for G0 T0 and assignment. [McCarthy 60] [Landin 65] [Reynolds 72]
rlm@2 261 Those for escape operators, fluid variables, and call-by-need with side
rlm@2 262 effects are new.
rlm@2 263 </p>
rlm@2 264 </div>
rlm@2 265
rlm@2 266 <div id="outline-container-2-1" class="outline-3">
rlm@2 267 <h3 id="sec-2-1"><span class="section-number-3">2.1</span> Simple Loops </h3>
rlm@2 268 <div class="outline-text-3" id="text-2-1">
rlm@2 269
rlm@2 270 <p>By <i>simple loops</i> we mean constructs which enable programs to execute the
rlm@2 271 same piece of code repeatedly in a controlled manner. Variables may be made
rlm@2 272 to take on different values during each repetition, and the number of
rlm@2 273 repetitions may depend on data given to the program.
rlm@2 274 </p>
rlm@2 275 </div>
rlm@2 276
rlm@2 277 <div id="outline-container-2-1-1" class="outline-4">
rlm@2 278 <h4 id="sec-2-1-1"><span class="section-number-4">2.1.1</span> Simple Recursion </h4>
rlm@2 279 <div class="outline-text-4" id="text-2-1-1">
rlm@2 280
rlm@2 281 <p>One of the easiest ways to produce a looping control structure is to
rlm@2 282 use a recursive function, one which calls itself to perform a subcomputation.
rlm@2 283 For example, the familiar factorial function may be written recursively in
rlm@2 284 ALGOL: '
rlm@2 285 </p>
rlm@2 286
rlm@2 287
rlm@2 288 <pre class="src src-algol">integer procedure fact(n) value n: integer n:
rlm@2 289 fact := if n=0 then 1 else n*fact(n-1);
rlm@2 290
rlm@2 291 </pre>
rlm@2 292
rlm@2 293
rlm@2 294
rlm@2 295
rlm@2 296 <p>
rlm@2 297 The invocation <code>fact(n)</code> computes the product of the integers from 1 to n using
rlm@2 298 the identity n!=n(n-1)! (n&gt;0). If \(n\) is zero, 1 is returned; otherwise <code>fact</code>:
rlm@2 299 calls itself recursively to compute \((n-1)!\) , then multiplies the result by \(n\)
rlm@2 300 and returns it.
rlm@2 301 </p>
rlm@2 302 <p>
rlm@2 303 This same function may be written in Clojure as follows:
rlm@2 304 </p>
rlm@2 305
rlm@2 306
rlm@2 307 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.imperative)
rlm@2 308 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact</span>[n]
rlm@2 309 (<span style="color: #f0dfaf; font-weight: bold;">if</span> (<span style="color: #8cd0d3;">=</span> n 0) 1 (<span style="color: #8cd0d3;">*</span> n (fact (<span style="color: #8cd0d3;">dec</span> n))))
rlm@2 310 )
rlm@2 311
rlm@2 312 </pre>
rlm@2 313
rlm@2 314
rlm@2 315
rlm@2 316
rlm@2 317
rlm@2 318 <p>
rlm@2 319 Clojure does not require an assignment to the ``variable'' fan: to return a value
rlm@2 320 as ALGOL does. The IF primitive is the ALGOL if-then-else rendered in LISP
rlm@2 321 syntax. Note that the arithmetic primitives are prefix operators in SCHEME.
rlm@2 322 </p>
rlm@2 323 </div>
rlm@2 324
rlm@2 325 </div>
rlm@2 326
rlm@2 327 <div id="outline-container-2-1-2" class="outline-4">
rlm@2 328 <h4 id="sec-2-1-2"><span class="section-number-4">2.1.2</span> Iteration </h4>
rlm@2 329 <div class="outline-text-4" id="text-2-1-2">
rlm@2 330
rlm@2 331 <p>There are many other ways to compute factorial. One important way is
rlm@2 332 through the use of <i>iteration</i>.
rlm@2 333 A comon iterative construct is the DO loop. The most general form we
rlm@2 334 have seen in any programming language is the MacLISP DO [Moon 74]. It permits
rlm@2 335 the simultaneous initialization of any number of control variables and the
rlm@2 336 simultaneous stepping of these variables by arbitrary functions at each
rlm@2 337 iteration step. The loop is terminated by an arbitrary predicate, and an
rlm@2 338 arbitrary value may be returned. The DO loop may have a body, a series of
rlm@2 339 expressions executed for effect on each iteration. A version of the MacLISP
rlm@2 340 DO construct has been adopted in SCHEME.
rlm@2 341 </p>
rlm@2 342 <p>
rlm@2 343 The general form of a SCHEME DO is:
rlm@2 344 </p>
rlm@2 345
rlm@2 346
rlm@2 347 <pre class="src src-nothing">(DO ((&lt;var1&gt; (init1&gt; &lt;stepl&gt;)
rlm@2 348 ((var2&gt; &lt;init2&gt; &lt;step2&gt;)
rlm@2 349 (&lt;varn&gt; &lt;intn&gt; (stepn&gt;))
rlm@2 350 (&lt;pred&gt; (value&gt;)
rlm@2 351 (optional body&gt;)
rlm@2 352
rlm@2 353 </pre>
rlm@2 354
rlm@2 355
rlm@2 356
rlm@2 357 <p>
rlm@2 358 The semantics of this are that the variables are bound and initialized to the
rlm@2 359 values of the &lt;initi&gt; expressions, which must all be evaluated in the
rlm@2 360 environment outside the D0; then the predicate &lt;pred&gt; is evaluated in the new
rlm@2 361 environment, and if TRUE, the (value) is evaluated and returned. Otherwise
rlm@2 362 the (optional body) is evaluated, then each of the steppers &lt;stepi&gt; is
rlm@2 363 evaluated in the current environment, all the variables made to have the
rlm@2 364 results as their values, the predicate evaluated again, and so on.
rlm@2 365 Using D0 loops in both ALGOL and SCHEME, we may express FACT by means
rlm@2 366 of iteration.
rlm@2 367 </p>
rlm@2 368
rlm@2 369
rlm@2 370 <pre class="src src-algol">integer procedure fact(n); value n; integer n:
rlm@2 371 begin
rlm@2 372 integer m, ans;
rlm@2 373 ans := 1;
rlm@2 374 for m := n step -l until 0 do ans := m*ans;
rlm@2 375 fact := ans;
rlm@2 376 end;
rlm@2 377
rlm@2 378 </pre>
rlm@2 379
rlm@2 380
rlm@2 381
rlm@2 382
rlm@2 383
rlm@2 384 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
rlm@2 385 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do</span>[n]
rlm@2 386 )
rlm@2 387
rlm@2 388 </pre>
rlm@2 389
rlm@2 390
rlm@2 391
rlm@2 392
rlm@2 393 <p>
rlm@2 394 Note that the SCHEME D0 loop in FACT has no body &ndash; the stepping functions do
rlm@2 395 all the work. The ALGOL DO loop has an assignment in its body; because an
rlm@2 396 ALGOL DO loop can step only one variable, we need the assignment to step the
rlm@2 397 the variable "manually'.
rlm@2 398 In reality the SCHEME DO construct is not a primitive; it is a macro
rlm@2 399 which expands into a function which performs the iteration by tail—recursion.
rlm@2 400 Consider the following definition of FACT in SCHEME. Although it appears to
rlm@2 401 be recursive, since it "calls itself", it is entirely equivalent to the DO
rlm@2 402 loop given above, for it is the code that the DO macro expands into! It
rlm@2 403 captures the essence of our intuitive notion of iteration, because execution
rlm@2 404 of this program will not produce internal structures (e.g. stacks or variable
rlm@2 405 bindings) which increase in size with the number of iteration steps.
rlm@2 406 </p>
rlm@2 407
rlm@2 408
rlm@2 409
rlm@2 410 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
rlm@2 411 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do-expand</span>[n]
rlm@2 412 (<span style="color: #f0dfaf; font-weight: bold;">let</span> [fact1
rlm@2 413 (<span style="color: #8cd0d3;">fn</span>[m ans]
rlm@2 414 (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? m) ans
rlm@2 415 (<span style="color: #f0dfaf; font-weight: bold;">recur</span> (<span style="color: #8cd0d3;">dec</span> m) (<span style="color: #8cd0d3;">*</span> m ans))))]
rlm@2 416 (fact1 n 1)))
rlm@2 417
rlm@2 418 </pre>
rlm@2 419
rlm@2 420
rlm@2 421
rlm@2 422
rlm@2 423 <p>
rlm@2 424 From this we can infer a general way to express iterations in SCHEME in
rlm@2 425 a manner isomorphic to the HacLISP D0. The expansion of the general D0 loop
rlm@2 426 </p>
rlm@2 427
rlm@2 428
rlm@2 429 <pre class="src src-nothing">(DO ((&lt;varl&gt; &lt;init1&gt; &lt;step1&gt;)
rlm@2 430 (&lt;var2&gt; (init2) &lt;step2&gt;)
rlm@2 431 ...
rlm@2 432 (&lt;varn&gt; &lt;initn&gt; &lt;stepn&gt;))
rlm@2 433 (&lt;pred&gt; &lt;va1ue&gt;)
rlm@2 434 &lt;body&gt;)
rlm@2 435
rlm@2 436 </pre>
rlm@2 437
rlm@2 438
rlm@2 439
rlm@2 440 <p>
rlm@2 441 is this:
rlm@2 442 </p>
rlm@2 443
rlm@2 444
rlm@2 445 <pre class="src src-nothing">(let [doloop
rlm@2 446 (fn [dummy &lt;var1&gt; &lt;var2&gt; ... &lt;varn&gt;)
rlm@2 447 (if &lt;pred&gt; &lt;value&gt;
rlm@2 448 (recur &lt;body&gt; &lt;step1&gt; &lt;step2&gt; ... &lt;stepn&gt;)))]
rlm@2 449
rlm@2 450 (doloop nil &lt;init1&gt; &lt;init2&gt; ... &lt;initn&gt;))
rlm@2 451
rlm@2 452 </pre>
rlm@2 453
rlm@2 454
rlm@2 455
rlm@2 456 <p>
rlm@2 457 The identifiers <code>doloop</code> and <code>dummy</code> are chosen so as not to conflict with any
rlm@2 458 other identifiers in the program.
rlm@2 459 Note that, unlike most implementations of D0, there are no side effects
rlm@2 460 in the steppings of the iteration variables. D0 loops are usually modelled
rlm@2 461 using assignment statements. For example:
rlm@2 462 </p>
rlm@2 463
rlm@2 464
rlm@2 465 <pre class="src src-nothing">for r :1 0 step b until c do &lt;statement&gt;;
rlm@2 466
rlm@2 467 </pre>
rlm@2 468
rlm@2 469
rlm@2 470
rlm@2 471
rlm@2 472 <p>
rlm@2 473 can be modelled as follows: [Naur 63]
rlm@2 474 </p>
rlm@2 475
rlm@2 476
rlm@2 477 <pre class="src src-nothing">begin
rlm@2 478 x := a;
rlm@2 479 L: if (x-c)*sign(n) &gt; 0 then go to Endloop;
rlm@2 480 &lt;statement&gt;;
rlm@2 481 x := x+b;
rlm@2 482 go to L:
rlm@2 483 Endloop:
rlm@2 484 end;
rlm@2 485
rlm@2 486 </pre>
rlm@2 487
rlm@2 488
rlm@2 489
rlm@2 490 <p>
rlm@2 491 Later we will see how such assignment statements can in general be
rlm@2 492 modelled without using side effects.
rlm@2 493 </p>
rlm@2 494 </div>
rlm@2 495 </div>
rlm@2 496 </div>
rlm@2 497
rlm@2 498 </div>
rlm@2 499
rlm@2 500 <div id="outline-container-3" class="outline-2">
rlm@2 501 <h2 id="sec-3"><span class="section-number-2">3</span> Imperative Programming </h2>
rlm@2 502 <div class="outline-text-2" id="text-3">
rlm@2 503
rlm@2 504 <p>Lambda calculus (and related languages, such as ``pure LISP'') is often
rlm@2 505 used for modelling the applicative constructs of programming languages.
rlm@2 506 However, they are generally thought of as inappropriate for modelling
rlm@2 507 imperative constructs. In this section we show how imperative constructs may
rlm@2 508 be modelled by applicative SCHEME constructs.
rlm@2 509 </p>
rlm@2 510 </div>
rlm@2 511
rlm@2 512 <div id="outline-container-3-1" class="outline-3">
rlm@2 513 <h3 id="sec-3-1"><span class="section-number-3">3.1</span> Compound Statements </h3>
rlm@2 514 <div class="outline-text-3" id="text-3-1">
rlm@2 515
rlm@2 516 <p>The simplest kind of imperative construct is the statement sequencer,
rlm@2 517 for example the compound statement in ALGOL:
rlm@2 518 </p>
rlm@2 519
rlm@2 520
rlm@2 521 <pre class="src src-algol">begin
rlm@2 522 S1;
rlm@2 523 S2;
rlm@2 524 end
rlm@2 525
rlm@2 526 </pre>
rlm@2 527
rlm@2 528
rlm@2 529
rlm@2 530
rlm@2 531 <p>
rlm@2 532 This construct has two interesting properties:
rlm@2 533 </p><ul>
rlm@2 534 <li>(1) It performs statement S1 before S2, and so may be used for
rlm@2 535 sequencing.
rlm@2 536 </li>
rlm@2 537 <li>(2) S1 is useful only for its side effects. (In ALGOL, S2 must also
rlm@2 538 be a statement, and so is also useful only for side effects, but
rlm@2 539 other languages have compound expressions containing a statement
rlm@2 540 followed by an expression.)
rlm@2 541 </li>
rlm@2 542 </ul>
rlm@2 543
rlm@2 544
rlm@2 545 <p>
rlm@2 546 The ALGOL compound statement may actually contain any number of statements,
rlm@2 547 but such statements can be expressed as a series of nested two-statement
rlm@2 548 compounds. That is:
rlm@2 549 </p>
rlm@2 550
rlm@2 551
rlm@2 552 <pre class="src src-algol">begin
rlm@2 553 S1;
rlm@2 554 S2;
rlm@2 555 ...
rlm@2 556 Sn-1;
rlm@2 557 Sn;
rlm@2 558 end
rlm@2 559
rlm@2 560 </pre>
rlm@2 561
rlm@2 562
rlm@2 563
rlm@2 564 <p>
rlm@2 565 is equivalent to:
rlm@2 566 </p>
rlm@2 567
rlm@2 568
rlm@2 569
rlm@2 570 <pre class="src src-algol">begin
rlm@2 571 S1;
rlm@2 572 begin
rlm@2 573 S2;
rlm@2 574 begin
rlm@2 575 ...
rlm@2 576
rlm@2 577 begin
rlm@2 578 Sn-1;
rlm@2 579 Sn;
rlm@2 580 end;
rlm@2 581 end;
rlm@2 582 end:
rlm@2 583 end
rlm@2 584
rlm@2 585 </pre>
rlm@2 586
rlm@2 587
rlm@2 588
rlm@2 589
rlm@2 590 <p>
rlm@2 591 It is not immediately apparent that this sequencing can be expressed in a
rlm@2 592 purely applicative language. We can, however, take advantage of the implicit
rlm@2 593 sequencing of applicative order evaluation. Thus, for example, we may write a
rlm@2 594 two-statement sequence as follows:
rlm@2 595 </p>
rlm@2 596
rlm@2 597
rlm@2 598
rlm@2 599 <pre class="src src-clojure">((<span style="color: #8cd0d3;">fn</span>[dummy] S2) S1)
rlm@2 600
rlm@2 601 </pre>
rlm@2 602
rlm@2 603
rlm@2 604
rlm@2 605
rlm@2 606 <p>
rlm@2 607 where <code>dummy</code> is an identifier not used in S2. From this it is
rlm@2 608 manifest that the value of S1 is ignored, and so is useful only for
rlm@2 609 side effects. (Note that we did not claim that S1 is expressed in a
rlm@2 610 purely applicative language, but only that the sequencing can be so
rlm@2 611 expressed.) From now on we will use the form <code>(BLOCK S1 S2)</code> as an
rlm@2 612 abbreviation for this expression, and <code>(BLOCK S1 S2...Sn-1 Sn)</code> as an
rlm@2 613 abbreviation for
rlm@2 614 </p>
rlm@2 615
rlm@2 616
rlm@2 617
rlm@2 618 <pre class="src src-algol">(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...)))
rlm@2 619
rlm@2 620 </pre>
rlm@2 621
rlm@2 622
rlm@2 623
rlm@2 624
rlm@2 625 </div>
rlm@2 626
rlm@2 627 </div>
rlm@2 628
rlm@2 629 <div id="outline-container-3-2" class="outline-3">
rlm@2 630 <h3 id="sec-3-2"><span class="section-number-3">3.2</span> 2.2. The G0 TO Statement </h3>
rlm@2 631 <div class="outline-text-3" id="text-3-2">
rlm@2 632
rlm@2 633
rlm@2 634 <p>
rlm@2 635 A more general imperative structure is the compound statement with
rlm@2 636 labels and G0 T0s. Consider the following code fragment due to
rlm@2 637 Jacopini, taken from Knuth: [Knuth 74]
rlm@2 638 </p>
rlm@2 639
rlm@2 640
rlm@2 641 <pre class="src src-algol">begin
rlm@2 642 L1: if B1 then go to L2; S1;
rlm@2 643 if B2 then go to L2; S2;
rlm@2 644 go to L1;
rlm@2 645 L2: S3;
rlm@2 646
rlm@2 647 </pre>
rlm@2 648
rlm@2 649
rlm@2 650
rlm@2 651
rlm@2 652 <p>
rlm@2 653 It is perhaps surprising that this piece of code can be <i>syntactically</i>
rlm@2 654 transformed into a purely applicative style. For example, in SCHEME we
rlm@2 655 could write:
rlm@2 656 </p>
rlm@2 657
rlm@2 658
rlm@2 659
rlm@2 660 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
rlm@2 661 (<span style="color: #f0dfaf; font-weight: bold;">let</span>
rlm@2 662 [L1 (<span style="color: #8cd0d3;">fn</span>[]
rlm@2 663 (<span style="color: #f0dfaf; font-weight: bold;">if</span> B1 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S1
rlm@2 664 (<span style="color: #f0dfaf; font-weight: bold;">if</span> B2 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S2 (L1))))))
rlm@2 665 L2 (<span style="color: #8cd0d3;">fn</span>[] S3)]
rlm@2 666 (L1))
rlm@2 667
rlm@2 668 </pre>
rlm@2 669
rlm@2 670
rlm@2 671
rlm@2 672
rlm@2 673 <p>
rlm@2 674 As with the D0 loop, this transformation depends critically on SCHEME's
rlm@2 675 treatment of tail-recursion and on lexical scoping of variables. The labels
rlm@2 676 are names of functions of no arguments. In order to ‘go to" the labeled code,
rlm@2 677 we merely call the function named by that label.
rlm@2 678 </p>
rlm@2 679 </div>
rlm@2 680
rlm@2 681 </div>
rlm@2 682
rlm@2 683 <div id="outline-container-3-3" class="outline-3">
rlm@2 684 <h3 id="sec-3-3"><span class="section-number-3">3.3</span> 2.3. Simple Assignment </h3>
rlm@2 685 <div class="outline-text-3" id="text-3-3">
rlm@2 686
rlm@2 687 <p>Of course, all this sequencing of statements is useless unless the
rlm@2 688 statements have side effects. An important side effect is assignment. For
rlm@2 689 example, one often uses assignment to place intermediate results in a named
rlm@2 690 location (i.e. a variable) so that they may be used more than once later
rlm@2 691 without recomputing them:
rlm@2 692 </p>
rlm@2 693
rlm@2 694
rlm@2 695
rlm@2 696 <pre class="src src-algol">begin
rlm@2 697 real a2, sqrtdisc;
rlm@2 698 a2 := 2*a;
rlm@2 699 sqrtdisc := sqrt(b^2 - 4*a*c);
rlm@2 700 root1 := (- b + sqrtdisc) / a2;
rlm@2 701 root2 := (- b - sqrtdisc) / a2;
rlm@2 702 print(root1);
rlm@2 703 print(root2);
rlm@2 704 print(root1 + root2);
rlm@2 705 end
rlm@2 706
rlm@2 707 </pre>
rlm@2 708
rlm@2 709
rlm@2 710
rlm@2 711
rlm@2 712 <p>
rlm@2 713 It is well known that such naming of intermediate results may be accomplished
rlm@2 714 by calling a function and binding the formal parameter variables to the
rlm@2 715 results:
rlm@2 716 </p>
rlm@2 717
rlm@2 718
rlm@2 719
rlm@2 720 <pre class="src src-clojure">(<span style="color: #8cd0d3;">fn</span> [a2 sqrtdisc]
rlm@2 721 ((<span style="color: #8cd0d3;">fn</span>[root1 root2]
rlm@2 722 (<span style="color: #f0dfaf; font-weight: bold;">do</span> (<span style="color: #8cd0d3;">println</span> root1)
rlm@2 723 (<span style="color: #8cd0d3;">println</span> root2)
rlm@2 724 (<span style="color: #8cd0d3;">println</span> (<span style="color: #8cd0d3;">+</span> root1 root2))))
rlm@2 725 (<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">+</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2)
rlm@2 726 (<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2))
rlm@2 727
rlm@2 728 (<span style="color: #8cd0d3;">*</span> 2 a)
rlm@2 729 (sqrt (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">*</span> b b) (<span style="color: #8cd0d3;">*</span> 4 a c))))
rlm@2 730
rlm@2 731 </pre>
rlm@2 732
rlm@2 733
rlm@2 734
rlm@2 735 <p>
rlm@2 736 This technique can be extended to handle all simple variable assignments which
rlm@2 737 appear as statements in blocks, even if arbitrary G0 T0 statements also appear
rlm@2 738 in such blocks. {Note Mccarthywins}
rlm@2 739 </p>
rlm@2 740 <p>
rlm@2 741 For example, here is a program which uses G0 TO statements in the form
rlm@2 742 presented before; it determines the parity of a non-negative integer by
rlm@2 743 counting it down until it reaches zero.
rlm@2 744 </p>
rlm@2 745
rlm@2 746
rlm@2 747
rlm@2 748 <pre class="src src-algol">begin
rlm@2 749 L1: if a = 0 then begin parity := 0; go to L2; end;
rlm@2 750 a := a - 1;
rlm@2 751 if a = 0 then begin parity := 1; go to L2; end;
rlm@2 752 a := a - 1;
rlm@2 753 go to L1;
rlm@2 754 L2: print(parity);
rlm@2 755
rlm@2 756 </pre>
rlm@2 757
rlm@2 758
rlm@2 759
rlm@2 760
rlm@2 761 <p>
rlm@2 762 This can be expressed in SCHEME:
rlm@2 763 </p>
rlm@2 764
rlm@2 765
rlm@2 766
rlm@2 767 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">let</span>
rlm@2 768 [L1 (<span style="color: #8cd0d3;">fn</span> [a parity]
rlm@2 769 (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 0)
rlm@2 770 (L3 (<span style="color: #8cd0d3;">dec</span> a) parity)))
rlm@2 771 L3 (<span style="color: #8cd0d3;">fn</span> [a parity]
rlm@2 772 (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 1)
rlm@2 773 (L1 (<span style="color: #8cd0d3;">dec</span> a) parity)))
rlm@2 774 L2 (<span style="color: #8cd0d3;">fn</span> [a parity]
rlm@2 775 (<span style="color: #8cd0d3;">println</span> parity))]
rlm@2 776 (L1 a parity))
rlm@2 777
rlm@2 778 </pre>
rlm@2 779
rlm@2 780
rlm@2 781
rlm@2 782
rlm@2 783 <p>
rlm@2 784 The trick is to pass the set of variables which may be altered as arguments to
rlm@2 785 the label functions. {Note Flowgraph} It may be necessary to introduce new
rlm@2 786 labels (such as L3) so that an assignment may be transformed into the binding
rlm@2 787 for a function call. At worst, one may need as many labels as there are
rlm@2 788 statements (not counting the eliminated assignment and GO TO statements).
rlm@2 789 </p>
rlm@2 790 </div>
rlm@2 791
rlm@2 792 </div>
rlm@2 793
rlm@2 794 <div id="outline-container-3-4" class="outline-3">
rlm@2 795 <h3 id="sec-3-4"><span class="section-number-3">3.4</span> Compound Expressions ' </h3>
rlm@2 796 <div class="outline-text-3" id="text-3-4">
rlm@2 797
rlm@2 798 <p>At this point we are almost in a position to model the most general
rlm@2 799 form of compound statement. In LISP, this is called the 'PROG feature". In
rlm@2 800 addition to statement sequencing and G0 T0 statements, one can return a <i>value</i>
rlm@2 801 from a PROG by using the RETURN statement.
rlm@2 802 </p>
rlm@2 803 <p>
rlm@2 804 Let us first consider the simplest compound statement, which in SCHEME
rlm@2 805 we call BLOCK. Recall that
rlm@2 806 <code>(BLOCK s1 sz)</code> is defined to be <code>((lambda (dummy) s2) s1)</code>
rlm@2 807 </p>
rlm@2 808 <p>
rlm@2 809 Notice that this not only performs Sl before S2, but also returns the value of
rlm@2 810 S2. Furthermore, we defined <code>(BLOCK S1 S2 ... Sn)</code> so that it returns the value
rlm@2 811 of <code>Sn</code>. Thus BLOCK may be used as a compound expression, and models a LISP
rlm@2 812 PROGN, which is a PROG with no G0 T0 statements and an implicit RETURN of the
rlm@2 813 last ``statement'' (really an expression).
rlm@2 814 </p>
rlm@2 815 <p>
rlm@2 816 Host LISP compilers compile D0 expressions by macro-expansion. We have
rlm@2 817 already seen one way to do this in SCHEME using only variable binding. A more
rlm@2 818 common technique is to expand the D0 into a PROG, using variable assignments
rlm@2 819 instead of bindings. Thus the iterative factorial program:
rlm@2 820 </p>
rlm@2 821
rlm@2 822
rlm@2 823
rlm@2 824 <pre class="src src-clojure">(oarxnz FACT .
rlm@2 825 (LAMaoA (n) .
rlm@2 826 (D0 ((M N (<span style="color: #8cd0d3;">-</span> H 1))
rlm@2 827 (Ans 1 (<span style="color: #8cd0d3;">*</span> M Ans)))
rlm@2 828 ((<span style="color: #8cd0d3;">-</span> H 0) A<span style="color: #cc9393;">"$))))</span>
rlm@2 829
rlm@2 830 </pre>
rlm@2 831
rlm@2 832
rlm@2 833
rlm@2 834
rlm@2 835 <p>
rlm@2 836 would expand into:
rlm@2 837 </p>
rlm@2 838
rlm@2 839
rlm@2 840
rlm@2 841 <pre class="src src-clojure">(DEFINE FACT
rlm@2 842 . (LAMeoA (M)
rlm@2 843 (PRO6 (M Ans)
rlm@2 844 (sszro M n
rlm@2 845 Ans 1) ~
rlm@2 846 LP (tr (<span style="color: #8cd0d3;">-</span> M 0) (RETURN Ans))
rlm@2 847 (ssero M (<span style="color: #8cd0d3;">-</span> n 1)
rlm@2 848 Ans (' M Ans))
rlm@2 849 (60 LP))))
rlm@2 850
rlm@2 851 </pre>
rlm@2 852
rlm@2 853
rlm@2 854
rlm@2 855
rlm@2 856 <p>
rlm@2 857 where SSETQ is a simultaneous multiple assignment operator. (SSETQ is not a
rlm@2 858 SCHEME (or LISP) primitive. It can be defined in terms of a single assignment
rlm@2 859 operator, but we are more interested here in RETURN than in simultaneous
rlm@2 860 assignment. The SSETQ's will all be removed anyway and modelled by lambda
rlm@2 861 binding.) We can apply the same technique we used before to eliminate G0 T0
rlm@2 862 statements and assignments from compound statements:
rlm@2 863 </p>
rlm@2 864
rlm@2 865
rlm@2 866
rlm@2 867 <pre class="src src-clojure">(DEFINE FACT
rlm@2 868 (LAHBOA (I)
rlm@2 869 (LABELS ((L1 (LAManA (M Ans)
rlm@2 870 (LP n 1)))
rlm@2 871 (LP (LAMaoA (M Ans)
rlm@2 872 (IF (<span style="color: #8cd0d3;">-</span> M o) (nztunn Ans)
rlm@2 873 (&#163;2 H An$))))
rlm@2 874 (L2 (LAMaoA (M An )
rlm@2 875 (LP (<span style="color: #8cd0d3;">-</span> <span style="color: #cc9393;">" 1) (' H &#64258;N$)))))</span>
rlm@2 876 <span style="color: #e37170; background-color: #332323;">(</span><span style="color: #cc9393;">L1 NIL NlL))))</span>
rlm@2 877
rlm@2 878 </pre>
rlm@2 879
rlm@2 880
rlm@2 881 <p>
rlm@2 882 clojure
rlm@2 883 </p>
rlm@2 884 <p>
rlm@2 885 We still haven't done anything about RETURN. Let's see&hellip;
rlm@2 886 </p><ul>
rlm@2 887 <li>==&gt; the value of (FACT 0) is the value of (Ll NIL NIL)
rlm@2 888 </li>
rlm@2 889 <li>==&gt; which is the value of (LP 0 1)
rlm@2 890 </li>
rlm@2 891 <li>==&gt; which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1))
rlm@2 892 </li>
rlm@2 893 <li>==&gt; which is the value of (RETURN 1)
rlm@2 894 </li>
rlm@2 895 </ul>
rlm@2 896
rlm@2 897
rlm@2 898 <p>
rlm@2 899 Notice that if RETURN were the <i>identity function</i> (LAMBDA (X) X), we would get the right answer. This is in fact a
rlm@2 900 general truth: if we Just replace a call to RETURN with its argument, then
rlm@2 901 our old transformation on compound statements extends to general compound
rlm@2 902 expressions, i.e. PROG.
rlm@2 903 </p>
rlm@2 904 </div>
rlm@2 905 </div>
rlm@2 906
rlm@2 907 </div>
rlm@2 908
rlm@2 909 <div id="outline-container-4" class="outline-2">
rlm@2 910 <h2 id="sec-4"><span class="section-number-2">4</span> Continuations </h2>
rlm@2 911 <div class="outline-text-2" id="text-4">
rlm@2 912
rlm@2 913 <p>Up to now we have thought of SCHEME's LAMBDA expressions as functions,
rlm@2 914 and of a combination such as <code>(G (F X Y))</code> as meaning ``apply the function F to
rlm@2 915 the values of X and Y, and return a value so that the function G can be
rlm@2 916 applied and return a value &hellip;'' But notice that we have seldom used LAMBDA
rlm@2 917 expressions as functions. Rather, we have used them as control structures and
rlm@2 918 environment modifiers. For example, consider the expression:
rlm@2 919 <code>(BLOCK (PRINT 3) (PRINT 4))</code>
rlm@2 920 </p>
rlm@2 921 <p>
rlm@2 922 This is defined to be an abbreviation for:
rlm@2 923 <code>((LAMBDA (DUMMY) (PRINT 4)) (PRINT 3))</code>
rlm@2 924 </p>
rlm@2 925 <p>
rlm@2 926 We do not care about the value of this BLOCK expression; it follows that we
rlm@2 927 do not care about the value of the <code>(LAMBDA (DUMMY) ...)</code>. We are not using
rlm@2 928 LAMBDA as a function at all.
rlm@2 929 </p>
rlm@2 930 <p>
rlm@2 931 It is possible to write useful programs in terms of LAHBDA expressions
rlm@2 932 in which we never care about the value of <i>any</i> lambda expression. We have
rlm@2 933 already demonstrated how one could represent any "FORTRAN" program in these
rlm@2 934 terms: all one needs is PROG (with G0 and SETQ), and PRINT to get the answers
rlm@2 935 out. The ultimate generalization of this imperative programing style is
rlm@2 936 <i>continuation-passing</i>. (Note Churchwins} .
rlm@2 937 </p>
rlm@2 938
rlm@2 939 </div>
rlm@2 940
rlm@2 941 <div id="outline-container-4-1" class="outline-3">
rlm@2 942 <h3 id="sec-4-1"><span class="section-number-3">4.1</span> Continuation-Passing Recursion </h3>
rlm@2 943 <div class="outline-text-3" id="text-4-1">
rlm@2 944
rlm@2 945 <p>Consider the following alternative definition of FACT. It has an extra
rlm@2 946 argument, the continuation, which is a function to call with the answer, when
rlm@2 947 we have it, rather than return a value
rlm@2 948 </p>
rlm@2 949
rlm@2 950
rlm@2 951
rlm@2 952 <pre class="src src-algol.">procedure Inc!(n, c); value n, c;
rlm@2 953 integer n: procedure c(integer value);
rlm@2 954 if n-=0 then c(l) else
rlm@2 955 begin
rlm@2 956 procedure l(!mp(d) value a: integer a;
rlm@2 957 c(mm);
rlm@2 958 Iacl(n-1, romp):
rlm@2 959 end;
rlm@2 960
rlm@2 961 </pre>
rlm@2 962
rlm@2 963
rlm@2 964
rlm@2 965
rlm@2 966
rlm@2 967 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
rlm@2 968 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-cps</span>[n k]
rlm@2 969 (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? n) (k 1)
rlm@2 970 (<span style="color: #f0dfaf; font-weight: bold;">recur</span> (<span style="color: #8cd0d3;">dec</span> n) (<span style="color: #8cd0d3;">fn</span>[a] (k (<span style="color: #8cd0d3;">*</span> n a))))))
rlm@2 971
rlm@2 972 </pre>
rlm@2 973
rlm@2 974
rlm@2 975 <p>
rlm@2 976 clojure
rlm@2 977 It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to
rlm@2 978 do something like this:
rlm@2 979 </p>
rlm@2 980
rlm@2 981
rlm@2 982
rlm@2 983 <pre class="src src-algol">begin
rlm@2 984 integer ann
rlm@2 985 procedure :emp(x); value 2:; integer x;
rlm@2 986 ans :1 x;
rlm@2 987 ]'act(3. temp);
rlm@2 988 comment Now the variable <span style="color: #cc9393;">"am"</span> has 6;
rlm@2 989 end;
rlm@2 990
rlm@2 991 </pre>
rlm@2 992
rlm@2 993
rlm@2 994
rlm@2 995
rlm@2 996 <p>
rlm@2 997 Procedure <code>fact</code> does not return a value, nor does <code>temp</code>; we must use a side
rlm@2 998 effect to get the answer out.
rlm@2 999 </p>
rlm@2 1000 <p>
rlm@2 1001 <code>FACT</code> is somewhat easier to use in SCHEME. We can call it like an
rlm@2 1002 ordinary function in SCHEME if we supply an identity function as the second
rlm@2 1003 argument. For example, <code>(FACT 3 (LAMBDA (X) X))</code> returns 6. Alternatively, we
rlm@2 1004 could write <code>(FACT 3 (LAHBDA (X) (PRINT X)))</code>; we do not care about the value
rlm@2 1005 of this, but about what gets printed. A third way to use the value is to
rlm@2 1006 write
rlm@2 1007 <code>(FACT 3 (LAMBDA (x) (SQRT x)))</code>
rlm@2 1008 instead of
rlm@2 1009 <code>(SQRT (FACT 3 (LAMBDA (x) x)))</code>
rlm@2 1010 </p>
rlm@2 1011 <p>
rlm@2 1012 In either of these cases we care about the value of the continuation given to
rlm@2 1013 FACT. Thus we care about the value of FACT if and only if we care about the
rlm@2 1014 value of its continuation!
rlm@2 1015 </p>
rlm@2 1016 <p>
rlm@2 1017 We can redefine other functions to take continuations in the same way.
rlm@2 1018 For example, suppose we had arithmetic primitives which took continuations; to
rlm@2 1019 prevent confusion, call the version of "+" which takes a continuation '++",
rlm@2 1020 etc. Instead of writing
rlm@2 1021 <code>(- (+ B Z)(* 4 A C))</code>
rlm@2 1022 we can write
rlm@2 1023 </p>
rlm@2 1024
rlm@2 1025
rlm@2 1026 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
rlm@2 1027 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">enable-continuation</span> <span style="color: #8fb28f;">"Makes f take a continuation as an additional argument."</span>[f]
rlm@2 1028 (<span style="color: #8cd0d3;">fn</span>[&amp; args] ((<span style="color: #8cd0d3;">fn</span>[k] (k (<span style="color: #8cd0d3;">apply</span> f (<span style="color: #8cd0d3;">reverse</span> (<span style="color: #8cd0d3;">rest</span> (<span style="color: #8cd0d3;">reverse</span> args)))))) (<span style="color: #8cd0d3;">last</span> args)) ))
rlm@2 1029 (<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">+&amp;</span> (enable-continuation +))
rlm@2 1030 (<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">*&amp;</span> (enable-continuation *))
rlm@2 1031 (<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">-&amp;</span> (enable-continuation -))
rlm@2 1032
rlm@2 1033
rlm@2 1034 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">quadratic</span>[a b c k]
rlm@2 1035 (*&amp; b b
rlm@2 1036 (<span style="color: #8cd0d3;">fn</span>[x] (*&amp; 4 a c
rlm@2 1037 (<span style="color: #8cd0d3;">fn</span>[y]
rlm@2 1038 (-&amp; x y k))))))
rlm@2 1039
rlm@2 1040 </pre>
rlm@2 1041
rlm@2 1042
rlm@2 1043
rlm@2 1044
rlm@2 1045 <p>
rlm@2 1046 where <code>k</code> is the continuation for the entire expression.
rlm@2 1047 </p>
rlm@2 1048 <p>
rlm@2 1049 This is an obscure way to write an algebraic expression, and we would
rlm@2 1050 not advise writing code this way in general, but continuation-passing brings
rlm@2 1051 out certain important features of the computation:
rlm@2 1052 </p><ul>
rlm@2 1053 <li><sup><a class="footref" name="fnr.1" href="#fn.1">1</a></sup> The operations to be performed appear in the order in which they are
rlm@2 1054 </li>
rlm@2 1055 </ul>
rlm@2 1056
rlm@2 1057 <p>performed. In fact, they <i>must</i> be performed in this
rlm@2 1058 order. Continuation- passing removes the need for the rule about
rlm@2 1059 left-to-right argument evaluation{Note Evalorder)
rlm@2 1060 </p><ul>
rlm@2 1061 <li><sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup> In the usual applicative expression there are two implicit
rlm@2 1062 temporary values: those of <code>(* B B)</code> and <code>(* 4 A C)</code>. The first of
rlm@2 1063 these values must be preserved over the computation of the second,
rlm@2 1064 whereas the second is used as soon as it is produced. These facts
rlm@2 1065 are <i>manifest</i> in the appearance and use of the variable X and Y in
rlm@2 1066 the continuation-passing version.
rlm@2 1067 </li>
rlm@2 1068 </ul>
rlm@2 1069
rlm@2 1070
rlm@2 1071 <p>
rlm@2 1072 In short, the continuation-passing version specifies <i>exactly</i> and
rlm@2 1073 explicitly what steps are necessary to compute the value of the
rlm@2 1074 expression. One can think of conventional functional application
rlm@2 1075 for value as being an abbreviation for the more explicit
rlm@2 1076 continuation-passing style. Alternatively, one can think of the
rlm@2 1077 interpreter as supplying to each function an implicit default
rlm@2 1078 continuation of one argument. This continuation will receive the
rlm@2 1079 value of the function as its argument, and then carry on the
rlm@2 1080 computation. In an interpreter this implicit continuation is
rlm@2 1081 represented by the control stack mechanism for function returns.
rlm@2 1082 Now consider what computational steps are implied by:
rlm@2 1083 </p>
rlm@2 1084 <p>
rlm@2 1085 <code>(LAMBDA (A B C ...) (F X Y Z ...))</code> when we "apply" the LAMBDA
rlm@2 1086 expression we have some values to apply it to; we let the names A,
rlm@2 1087 B, C &hellip; refer to these values. We then determine the values of X,
rlm@2 1088 Y, Z &hellip; and pass these values (along with "the buck",
rlm@2 1089 i.e. control!) to the lambda expression F (F is either a lambda
rlm@2 1090 expression or a name for one). Passing control to F is an
rlm@2 1091 unconditional transfer. (Note Jrsthack) {Note Hewitthack) Note that
rlm@2 1092 we want values from X, Y, Z, &hellip; If these are simple expressions,
rlm@2 1093 such as variables, constants, or LAMBDA expressions, the evaluation
rlm@2 1094 process is trivial, in that no temporary storage is required. In
rlm@2 1095 pure continuation-passing style, all evaluations are trivial: no
rlm@2 1096 combination is nested within another, and therefore no ‘hidden
rlm@2 1097 temporaries" are required. But if X is a combination, say (G P Q),
rlm@2 1098 then we want to think of G as a function, because we want a value
rlm@2 1099 from it, and we will need an implicit temporary place to keep the
rlm@2 1100 result while evaluating Y and Z. (An interpreter usually keeps these
rlm@2 1101 temporary places in the control stack!) On the other hand, we do not
rlm@2 1102 necessarily need a value from F. This is what we mean by tail-
rlm@2 1103 recursion: F is called tail-recursively, whereas G is not. A better
rlm@2 1104 name for tail-recursion would be "tail-transfer", since no real
rlm@2 1105 recursion is implied. This is why we have made such a fuss about
rlm@2 1106 tail-recursion: it can be used for transfer of control without
rlm@2 1107 making any commitment about whether the expression expected to
rlm@2 1108 return a value. Thus it can be used to model statement-like control
rlm@2 1109 structures. Put another way, tail—recursion does not require a
rlm@2 1110 control stack as nested recursion does. In our models of iteration
rlm@2 1111 and imperative style all the LAMBDA expressions used for control (to
rlm@2 1112 simulate GO statements, for example) are called in tail-recursive
rlm@2 1113 fashion.
rlm@2 1114 </p>
rlm@2 1115 </div>
rlm@2 1116
rlm@2 1117 </div>
rlm@2 1118
rlm@2 1119 <div id="outline-container-4-2" class="outline-3">
rlm@2 1120 <h3 id="sec-4-2"><span class="section-number-3">4.2</span> Escape Expressions </h3>
rlm@2 1121 <div class="outline-text-3" id="text-4-2">
rlm@2 1122
rlm@2 1123 <p>Reynolds [Reynolds 72] defines the construction
rlm@2 1124 = escape x in r =
rlm@2 1125 </p>
rlm@2 1126 <p>
rlm@2 1127 to evaluate the expression \(r\) in an environment such that the variable \(x\) is
rlm@2 1128 bound to an escape function. If the escape function is never applied, then
rlm@2 1129 the value of the escape expression is the value of \(r\). If the escape function
rlm@2 1130 is applied to an argument \(a\), however, then evaluation of \(r\) is aborted and the
rlm@2 1131 escape expression returns \(a\). {Note J-operator} (Reynolds points out that
rlm@2 1132 this definition is not quite accurate, since the escape function may be called
rlm@2 1133 even after the escape expression has returned a value; if this happens, it
rlm@2 1134 “returns again"!)
rlm@2 1135 </p>
rlm@2 1136 <p>
rlm@2 1137 As an example of the use of an escape expression, consider this
rlm@2 1138 procedure to compute the harmonic mean of an array of numbers. If any of the
rlm@2 1139 numbers is zero, we want the answer to be zero. We have a function hannaunl
rlm@2 1140 which will sum the reciprocals of numbers in an array, or call an escape
rlm@2 1141 function with zero if any of the numbers is zero. (The implementation shown
rlm@2 1142 here is awkward because ALGOL requires that a function return its value by
rlm@2 1143 assignment.)
rlm@2 1144 </p>
rlm@2 1145
rlm@2 1146
rlm@2 1147 <pre class="src src-algol">begin
rlm@2 1148 real procedure Imrmsum(a, n. escfun)&#167; p
rlm@2 1149 real array at integer n; real procedure esciun(real);
rlm@2 1150 begin
rlm@2 1151 real sum;
rlm@2 1152 sum := 0;
rlm@2 1153 for i :1 0 until n-l do
rlm@2 1154 begin
rlm@2 1155 if a[i]=0 then cscfun(0);
rlm@2 1156 sum :1 sum &#162; I/a[i];
rlm@2 1157 enm
rlm@2 1158 harmsum SI sum;
rlm@2 1159 end: .
rlm@2 1160 real array b[0:99]:
rlm@2 1161 print(escape x in I00/hm-m.mm(b, 100, x));
rlm@2 1162 end
rlm@2 1163
rlm@2 1164 </pre>
rlm@2 1165
rlm@2 1166
rlm@2 1167
rlm@2 1168
rlm@2 1169 <p>
rlm@2 1170 If harmsum exits normally, the number of elements is divided by the sum and
rlm@2 1171 printed. Otherwise, zero is returned from the escape expression and printed
rlm@2 1172 without the division ever occurring.
rlm@2 1173 This program can be written in SCHEME using the built-in escape
rlm@2 1174 operator <code>CATCH</code>:
rlm@2 1175 </p>
rlm@2 1176
rlm@2 1177
rlm@2 1178
rlm@2 1179 <pre class="src src-clojure">abc
rlm@2 1180
rlm@2 1181 </pre>
rlm@2 1182
rlm@2 1183
rlm@2 1184
rlm@2 1185 <div id="footnotes">
rlm@2 1186 <h2 class="footnotes">Footnotes: </h2>
rlm@2 1187 <div id="text-footnotes">
rlm@2 1188 <p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> DEFINITION NOT FOUND: 1
rlm@2 1189 </p>
rlm@2 1190
rlm@2 1191 <p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> DEFINITION NOT FOUND: 2
rlm@2 1192 </p>
rlm@2 1193 </div>
rlm@2 1194 </div>
rlm@2 1195 </div>
rlm@2 1196
rlm@2 1197 </div>
rlm@2 1198 </div>
rlm@2 1199 <div id="postamble">
rlm@2 1200 <p class="date">Date: 2011-07-15 02:49:04 EDT</p>
rlm@2 1201 <p class="author">Author: Guy Lewis Steele Jr. and Gerald Jay Sussman</p>
rlm@2 1202 <p class="creator">Org version 7.6 with Emacs version 23</p>
rlm@2 1203 <a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>
rlm@2 1204 </div>
rlm@2 1205 </div>
rlm@2 1206 </body>
rlm@2 1207 </html>