Mercurial > dylan
diff categorical/imperative.html @ 2:b4de894a1e2e
initial import
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Fri, 28 Oct 2011 00:03:05 -0700 |
| parents | |
| children |
line wrap: on
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/categorical/imperative.html Fri Oct 28 00:03:05 2011 -0700 1.3 @@ -0,0 +1,1207 @@ 1.4 +<?xml version="1.0" encoding="utf-8"?> 1.5 +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 1.6 + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 1.7 +<html xmlns="http://www.w3.org/1999/xhtml" 1.8 +lang="en" xml:lang="en"> 1.9 +<head> 1.10 +<title>LAMBDA: The Ultimate Imperative</title> 1.11 +<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/> 1.12 +<meta name="generator" content="Org-mode"/> 1.13 +<meta name="generated" content="2011-07-15 02:49:04 EDT"/> 1.14 +<meta name="author" content="Guy Lewis Steele Jr. and Gerald Jay Sussman"/> 1.15 +<meta name="description" content=""/> 1.16 +<meta name="keywords" content=""/> 1.17 +<style type="text/css"> 1.18 + <!--/*--><![CDATA[/*><!--*/ 1.19 + html { font-family: Times, serif; font-size: 12pt; } 1.20 + .title { text-align: center; } 1.21 + .todo { color: red; } 1.22 + .done { color: green; } 1.23 + .tag { background-color: #add8e6; font-weight:normal } 1.24 + .target { } 1.25 + .timestamp { color: #bebebe; } 1.26 + .timestamp-kwd { color: #5f9ea0; } 1.27 + .right {margin-left:auto; margin-right:0px; text-align:right;} 1.28 + .left {margin-left:0px; margin-right:auto; text-align:left;} 1.29 + .center {margin-left:auto; margin-right:auto; text-align:center;} 1.30 + p.verse { margin-left: 3% } 1.31 + pre { 1.32 + border: 1pt solid #AEBDCC; 1.33 + background-color: #F3F5F7; 1.34 + padding: 5pt; 1.35 + font-family: courier, monospace; 1.36 + font-size: 90%; 1.37 + overflow:auto; 1.38 + } 1.39 + table { border-collapse: collapse; } 1.40 + td, th { vertical-align: top; } 1.41 + th.right { text-align:center; } 1.42 + th.left { text-align:center; } 1.43 + th.center { text-align:center; } 1.44 + td.right { text-align:right; } 1.45 + td.left { text-align:left; } 1.46 + td.center { text-align:center; } 1.47 + dt { font-weight: bold; } 1.48 + div.figure { padding: 0.5em; } 1.49 + div.figure p { text-align: center; } 1.50 + textarea { overflow-x: auto; } 1.51 + .linenr { font-size:smaller } 1.52 + .code-highlighted {background-color:#ffff00;} 1.53 + .org-info-js_info-navigation { border-style:none; } 1.54 + #org-info-js_console-label { font-size:10px; font-weight:bold; 1.55 + white-space:nowrap; } 1.56 + .org-info-js_search-highlight {background-color:#ffff00; color:#000000; 1.57 + font-weight:bold; } 1.58 + /*]]>*/--> 1.59 +</style> 1.60 +<script type="text/javascript"> 1.61 +<!--/*--><![CDATA[/*><!--*/ 1.62 + function CodeHighlightOn(elem, id) 1.63 + { 1.64 + var target = document.getElementById(id); 1.65 + if(null != target) { 1.66 + elem.cacheClassElem = elem.className; 1.67 + elem.cacheClassTarget = target.className; 1.68 + target.className = "code-highlighted"; 1.69 + elem.className = "code-highlighted"; 1.70 + } 1.71 + } 1.72 + function CodeHighlightOff(elem, id) 1.73 + { 1.74 + var target = document.getElementById(id); 1.75 + if(elem.cacheClassElem) 1.76 + elem.className = elem.cacheClassElem; 1.77 + if(elem.cacheClassTarget) 1.78 + target.className = elem.cacheClassTarget; 1.79 + } 1.80 +/*]]>*///--> 1.81 +</script> 1.82 +<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js"> 1.83 +<!--/*--><![CDATA[/*><!--*/ 1.84 + MathJax.Hub.Config({ 1.85 + // Only one of the two following lines, depending on user settings 1.86 + // First allows browser-native MathML display, second forces HTML/CSS 1.87 + // config: ["MMLorHTML.js"], jax: ["input/TeX"], 1.88 + jax: ["input/TeX", "output/HTML-CSS"], 1.89 + extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js", 1.90 + "TeX/noUndefined.js"], 1.91 + tex2jax: { 1.92 + inlineMath: [ ["\\(","\\)"] ], 1.93 + displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ], 1.94 + skipTags: ["script","noscript","style","textarea","pre","code"], 1.95 + ignoreClass: "tex2jax_ignore", 1.96 + processEscapes: false, 1.97 + processEnvironments: true, 1.98 + preview: "TeX" 1.99 + }, 1.100 + showProcessingMessages: true, 1.101 + displayAlign: "center", 1.102 + displayIndent: "2em", 1.103 + 1.104 + "HTML-CSS": { 1.105 + scale: 100, 1.106 + availableFonts: ["STIX","TeX"], 1.107 + preferredFont: "TeX", 1.108 + webFont: "TeX", 1.109 + imageFont: "TeX", 1.110 + showMathMenu: true, 1.111 + }, 1.112 + MMLorHTML: { 1.113 + prefer: { 1.114 + MSIE: "MML", 1.115 + Firefox: "MML", 1.116 + Opera: "HTML", 1.117 + other: "HTML" 1.118 + } 1.119 + } 1.120 + }); 1.121 +/*]]>*///--> 1.122 +</script> 1.123 +</head> 1.124 +<body> 1.125 + 1.126 +<div id="content"> 1.127 + 1.128 + 1.129 + 1.130 +<div id="table-of-contents"> 1.131 +<h2>Table of Contents</h2> 1.132 +<div id="text-table-of-contents"> 1.133 +<ul> 1.134 +<li><a href="#sec-1">1 Abstract </a></li> 1.135 +<li><a href="#sec-2">2 Introduction </a> 1.136 +<ul> 1.137 +<li><a href="#sec-2-1">2.1 Simple Loops </a> 1.138 +<ul> 1.139 +<li><a href="#sec-2-1-1">2.1.1 Simple Recursion </a></li> 1.140 +<li><a href="#sec-2-1-2">2.1.2 Iteration </a></li> 1.141 +</ul></li> 1.142 +</ul> 1.143 +</li> 1.144 +<li><a href="#sec-3">3 Imperative Programming </a> 1.145 +<ul> 1.146 +<li><a href="#sec-3-1">3.1 Compound Statements </a></li> 1.147 +<li><a href="#sec-3-2">3.2 2.2. The G0 TO Statement </a></li> 1.148 +<li><a href="#sec-3-3">3.3 2.3. Simple Assignment </a></li> 1.149 +<li><a href="#sec-3-4">3.4 Compound Expressions ' </a></li> 1.150 +</ul> 1.151 +</li> 1.152 +<li><a href="#sec-4">4 Continuations </a> 1.153 +<ul> 1.154 +<li><a href="#sec-4-1">4.1 Continuation-Passing Recursion </a></li> 1.155 +<li><a href="#sec-4-2">4.2 Escape Expressions </a></li> 1.156 +</ul> 1.157 +</li> 1.158 +</ul> 1.159 +</div> 1.160 +</div> 1.161 + 1.162 +<div id="outline-container-1" class="outline-2"> 1.163 +<h2 id="sec-1"><span class="section-number-2">1</span> Abstract </h2> 1.164 +<div class="outline-text-2" id="text-1"> 1.165 + 1.166 + 1.167 +<p> 1.168 +We demonstrate how to model the following common programming constructs in 1.169 +terms of an applicative order language similar to LISP: 1.170 +</p><ul> 1.171 +<li>Simple Recursion 1.172 +</li> 1.173 +<li>Iteration 1.174 +</li> 1.175 +<li>Compound Statements and Expressions 1.176 +</li> 1.177 +<li>GO TO and Assignment 1.178 +</li> 1.179 +<li>Continuation—Passing 1.180 +</li> 1.181 +<li>Escape Expressions 1.182 +</li> 1.183 +<li>Fluid Variables 1.184 +</li> 1.185 +<li>Call by Name, Call by Need, and Call by Reference 1.186 +</li> 1.187 +</ul> 1.188 + 1.189 +<p>The models require only (possibly self-referent) lambda application, 1.190 +conditionals, and (rarely) assignment. No complex data structures such as 1.191 +stacks are used. The models are transparent, involving only local syntactic 1.192 +transformations. 1.193 +Some of these models, such as those for GO TO and assignment, are already well 1.194 +known, and appear in the work of Landin, Reynolds, and others. The models for 1.195 +escape expressions, fluid variables, and call by need with side effects are 1.196 +new. This paper is partly tutorial in intent, gathering all the models 1.197 +together for purposes of context. 1.198 +This report describes research done at the Artificial Intelligence Laboratory 1.199 +of the Massachusetts Institute of Teehnology. Support for the laboratory's 1.200 +artificial intelligence research is provided in part by the Advanced Research 1.201 +Projects Agency of the Department of Defense under Office of Naval Research 1.202 +contract N000l4-75-C-0643. 1.203 +</p> 1.204 +</div> 1.205 + 1.206 +</div> 1.207 + 1.208 +<div id="outline-container-2" class="outline-2"> 1.209 +<h2 id="sec-2"><span class="section-number-2">2</span> Introduction </h2> 1.210 +<div class="outline-text-2" id="text-2"> 1.211 + 1.212 + 1.213 +<p> 1.214 + We catalogue a number of common programming constructs. For each 1.215 +construct we examine "typical" usage in well-known programming languages, and 1.216 +then capture the essence of the semantics of the construct in terms of a 1.217 +common meta-language. 1.218 +The lambda calculus {Note Alonzowins} is often used as such a meta- 1.219 +language. Lambda calculus offers clean semantics, but it is clumsy because it 1.220 +was designed to be a minimal language rather than a convenient one. All 1.221 +lambda calculus "functions" must take exactly one "argument"; the only "data 1.222 +type" is lambda expressions; and the only "primitive operation‘ is variable‘ 1.223 +substitution. While its utter simplicity makes lambda calculus ideal for 1.224 +logicians, it is too primitive for use by programmers. The meta-language we 1.225 +use is a programming language called SCHEME {Note Schemepaper) which is based 1.226 +on lambda calculus. 1.227 +SCHEME is a dialect of LISP. [McCarthy 62] It is an expression- 1.228 +oriented, applicative order, interpreter-based language which allows one to 1.229 +manipulate programs as data. It differs from most current dialects of LISP in 1.230 +that it closes all lambda expressions in the environment of their definition 1.231 +or declaration, rather than in the execution environment. {Note Closures} 1.232 +This preserves the substitution semantics of lambda calculus, and has the 1.233 +consequence that all variables are lexically scoped, as in ALGOL. [Naur 63] 1.234 +Another difference is that SCHEME is implemented in such a way that tail- 1.235 +recursions execute without net growth of the interpreter stack. {Note 1.236 +Schemenote} We have chosen to use LISP syntax rather than, say, ALGOL syntax 1.237 +because we want to treat programs as data for the purpose of describing 1.238 +transformations on the code. LISP supplies names for the parts of an 1.239 +executable expression and standard operators for constructing expressions and 1.240 +extracting their components. The use of LISP syntax makes the structure of 1.241 +such expressions manifest. We use ALGOL as an expository language, because it 1.242 +is familiar to many people, but ALGOL is not sufficiently powerful to express 1.243 +the necessary concepts; in particular, it does not allow functions to return 1.244 +functions as values. we are thus forced to use a dialect of LISP in many 1.245 +cases. 1.246 +We will consider various complex programming language constructs and 1.247 +show how to model them in terms of only a few simple ones. As far as possible 1.248 +we will use only three control constructs from SCHEME: LAMBDA expressions, as 1.249 +in LISP, which are Just functions with lexically scoped free variables; 1.250 +LABELS, which allows declaration of mutually recursive procedures (Note 1.251 +Labelsdef}; and IF, a primitive conditional expression. For more complex 1.252 +modelling we will introduce an assignment primitive (ASET).i We will freely 1.253 +assume the existence of other comon primitives, such as arithmetic functions. 1.254 +The constructs we will examine are divided into four broad classes. 1.255 +The first is sfinph?Lo0pl; this contains simple recursions and iterations, and 1.256 +an introduction to the notion of continuations. The second is hmponflivo 1.257 +Connrucls; this includes compound statements, G0 T0, and simple variable 1.258 +assignments. The third is continuations, which encompasses the distinction between statements and expressions, escape operators (such as Landin's J- 1.259 +operator [Landin 65] and Reynold's escape expression [Reynolds 72]). and fluid 1.260 +(dynamically bound) variables. The fourth is Parameter Passing Mechanisms, such 1.261 +as ALGOL call—by-name and FORTRAN call-by-location. 1.262 +Some of the models presented here are already well-known, particularly 1.263 +those for G0 T0 and assignment. [McCarthy 60] [Landin 65] [Reynolds 72] 1.264 +Those for escape operators, fluid variables, and call-by-need with side 1.265 +effects are new. 1.266 +</p> 1.267 +</div> 1.268 + 1.269 +<div id="outline-container-2-1" class="outline-3"> 1.270 +<h3 id="sec-2-1"><span class="section-number-3">2.1</span> Simple Loops </h3> 1.271 +<div class="outline-text-3" id="text-2-1"> 1.272 + 1.273 +<p>By <i>simple loops</i> we mean constructs which enable programs to execute the 1.274 +same piece of code repeatedly in a controlled manner. Variables may be made 1.275 +to take on different values during each repetition, and the number of 1.276 +repetitions may depend on data given to the program. 1.277 +</p> 1.278 +</div> 1.279 + 1.280 +<div id="outline-container-2-1-1" class="outline-4"> 1.281 +<h4 id="sec-2-1-1"><span class="section-number-4">2.1.1</span> Simple Recursion </h4> 1.282 +<div class="outline-text-4" id="text-2-1-1"> 1.283 + 1.284 +<p>One of the easiest ways to produce a looping control structure is to 1.285 +use a recursive function, one which calls itself to perform a subcomputation. 1.286 +For example, the familiar factorial function may be written recursively in 1.287 +ALGOL: ' 1.288 +</p> 1.289 + 1.290 + 1.291 +<pre class="src src-algol">integer procedure fact(n) value n: integer n: 1.292 +fact := if n=0 then 1 else n*fact(n-1); 1.293 + 1.294 +</pre> 1.295 + 1.296 + 1.297 + 1.298 + 1.299 +<p> 1.300 +The invocation <code>fact(n)</code> computes the product of the integers from 1 to n using 1.301 +the identity n!=n(n-1)! (n>0). If \(n\) is zero, 1 is returned; otherwise <code>fact</code>: 1.302 +calls itself recursively to compute \((n-1)!\) , then multiplies the result by \(n\) 1.303 +and returns it. 1.304 +</p> 1.305 +<p> 1.306 +This same function may be written in Clojure as follows: 1.307 +</p> 1.308 + 1.309 + 1.310 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.imperative) 1.311 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact</span>[n] 1.312 + (<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)))) 1.313 +) 1.314 + 1.315 +</pre> 1.316 + 1.317 + 1.318 + 1.319 + 1.320 + 1.321 +<p> 1.322 +Clojure does not require an assignment to the ``variable'' fan: to return a value 1.323 +as ALGOL does. The IF primitive is the ALGOL if-then-else rendered in LISP 1.324 +syntax. Note that the arithmetic primitives are prefix operators in SCHEME. 1.325 +</p> 1.326 +</div> 1.327 + 1.328 +</div> 1.329 + 1.330 +<div id="outline-container-2-1-2" class="outline-4"> 1.331 +<h4 id="sec-2-1-2"><span class="section-number-4">2.1.2</span> Iteration </h4> 1.332 +<div class="outline-text-4" id="text-2-1-2"> 1.333 + 1.334 +<p>There are many other ways to compute factorial. One important way is 1.335 +through the use of <i>iteration</i>. 1.336 +A comon iterative construct is the DO loop. The most general form we 1.337 +have seen in any programming language is the MacLISP DO [Moon 74]. It permits 1.338 +the simultaneous initialization of any number of control variables and the 1.339 +simultaneous stepping of these variables by arbitrary functions at each 1.340 +iteration step. The loop is terminated by an arbitrary predicate, and an 1.341 +arbitrary value may be returned. The DO loop may have a body, a series of 1.342 +expressions executed for effect on each iteration. A version of the MacLISP 1.343 +DO construct has been adopted in SCHEME. 1.344 +</p> 1.345 +<p> 1.346 +The general form of a SCHEME DO is: 1.347 +</p> 1.348 + 1.349 + 1.350 +<pre class="src src-nothing">(DO ((<var1> (init1> <stepl>) 1.351 +((var2> <init2> <step2>) 1.352 +(<varn> <intn> (stepn>)) 1.353 +(<pred> (value>) 1.354 +(optional body>) 1.355 + 1.356 +</pre> 1.357 + 1.358 + 1.359 + 1.360 +<p> 1.361 +The semantics of this are that the variables are bound and initialized to the 1.362 +values of the <initi> expressions, which must all be evaluated in the 1.363 +environment outside the D0; then the predicate <pred> is evaluated in the new 1.364 +environment, and if TRUE, the (value) is evaluated and returned. Otherwise 1.365 +the (optional body) is evaluated, then each of the steppers <stepi> is 1.366 +evaluated in the current environment, all the variables made to have the 1.367 +results as their values, the predicate evaluated again, and so on. 1.368 +Using D0 loops in both ALGOL and SCHEME, we may express FACT by means 1.369 +of iteration. 1.370 +</p> 1.371 + 1.372 + 1.373 +<pre class="src src-algol">integer procedure fact(n); value n; integer n: 1.374 +begin 1.375 +integer m, ans; 1.376 +ans := 1; 1.377 +for m := n step -l until 0 do ans := m*ans; 1.378 +fact := ans; 1.379 +end; 1.380 + 1.381 +</pre> 1.382 + 1.383 + 1.384 + 1.385 + 1.386 + 1.387 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative) 1.388 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do</span>[n] 1.389 +) 1.390 + 1.391 +</pre> 1.392 + 1.393 + 1.394 + 1.395 + 1.396 +<p> 1.397 +Note that the SCHEME D0 loop in FACT has no body – the stepping functions do 1.398 +all the work. The ALGOL DO loop has an assignment in its body; because an 1.399 +ALGOL DO loop can step only one variable, we need the assignment to step the 1.400 +the variable "manually'. 1.401 +In reality the SCHEME DO construct is not a primitive; it is a macro 1.402 +which expands into a function which performs the iteration by tail—recursion. 1.403 +Consider the following definition of FACT in SCHEME. Although it appears to 1.404 +be recursive, since it "calls itself", it is entirely equivalent to the DO 1.405 +loop given above, for it is the code that the DO macro expands into! It 1.406 +captures the essence of our intuitive notion of iteration, because execution 1.407 +of this program will not produce internal structures (e.g. stacks or variable 1.408 +bindings) which increase in size with the number of iteration steps. 1.409 +</p> 1.410 + 1.411 + 1.412 + 1.413 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative) 1.414 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do-expand</span>[n] 1.415 + (<span style="color: #f0dfaf; font-weight: bold;">let</span> [fact1 1.416 + (<span style="color: #8cd0d3;">fn</span>[m ans] 1.417 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? m) ans 1.418 + (<span style="color: #f0dfaf; font-weight: bold;">recur</span> (<span style="color: #8cd0d3;">dec</span> m) (<span style="color: #8cd0d3;">*</span> m ans))))] 1.419 + (fact1 n 1))) 1.420 + 1.421 +</pre> 1.422 + 1.423 + 1.424 + 1.425 + 1.426 +<p> 1.427 +From this we can infer a general way to express iterations in SCHEME in 1.428 +a manner isomorphic to the HacLISP D0. The expansion of the general D0 loop 1.429 +</p> 1.430 + 1.431 + 1.432 +<pre class="src src-nothing">(DO ((<varl> <init1> <step1>) 1.433 +(<var2> (init2) <step2>) 1.434 +... 1.435 +(<varn> <initn> <stepn>)) 1.436 +(<pred> <va1ue>) 1.437 +<body>) 1.438 + 1.439 +</pre> 1.440 + 1.441 + 1.442 + 1.443 +<p> 1.444 +is this: 1.445 +</p> 1.446 + 1.447 + 1.448 +<pre class="src src-nothing">(let [doloop 1.449 +(fn [dummy <var1> <var2> ... <varn>) 1.450 +(if <pred> <value> 1.451 +(recur <body> <step1> <step2> ... <stepn>)))] 1.452 + 1.453 +(doloop nil <init1> <init2> ... <initn>)) 1.454 + 1.455 +</pre> 1.456 + 1.457 + 1.458 + 1.459 +<p> 1.460 +The identifiers <code>doloop</code> and <code>dummy</code> are chosen so as not to conflict with any 1.461 +other identifiers in the program. 1.462 +Note that, unlike most implementations of D0, there are no side effects 1.463 +in the steppings of the iteration variables. D0 loops are usually modelled 1.464 +using assignment statements. For example: 1.465 +</p> 1.466 + 1.467 + 1.468 +<pre class="src src-nothing">for r :1 0 step b until c do <statement>; 1.469 + 1.470 +</pre> 1.471 + 1.472 + 1.473 + 1.474 + 1.475 +<p> 1.476 +can be modelled as follows: [Naur 63] 1.477 +</p> 1.478 + 1.479 + 1.480 +<pre class="src src-nothing">begin 1.481 +x := a; 1.482 +L: if (x-c)*sign(n) > 0 then go to Endloop; 1.483 +<statement>; 1.484 +x := x+b; 1.485 +go to L: 1.486 +Endloop: 1.487 +end; 1.488 + 1.489 +</pre> 1.490 + 1.491 + 1.492 + 1.493 +<p> 1.494 +Later we will see how such assignment statements can in general be 1.495 +modelled without using side effects. 1.496 +</p> 1.497 +</div> 1.498 +</div> 1.499 +</div> 1.500 + 1.501 +</div> 1.502 + 1.503 +<div id="outline-container-3" class="outline-2"> 1.504 +<h2 id="sec-3"><span class="section-number-2">3</span> Imperative Programming </h2> 1.505 +<div class="outline-text-2" id="text-3"> 1.506 + 1.507 +<p>Lambda calculus (and related languages, such as ``pure LISP'') is often 1.508 +used for modelling the applicative constructs of programming languages. 1.509 +However, they are generally thought of as inappropriate for modelling 1.510 +imperative constructs. In this section we show how imperative constructs may 1.511 +be modelled by applicative SCHEME constructs. 1.512 +</p> 1.513 +</div> 1.514 + 1.515 +<div id="outline-container-3-1" class="outline-3"> 1.516 +<h3 id="sec-3-1"><span class="section-number-3">3.1</span> Compound Statements </h3> 1.517 +<div class="outline-text-3" id="text-3-1"> 1.518 + 1.519 +<p>The simplest kind of imperative construct is the statement sequencer, 1.520 +for example the compound statement in ALGOL: 1.521 +</p> 1.522 + 1.523 + 1.524 +<pre class="src src-algol">begin 1.525 +S1; 1.526 +S2; 1.527 +end 1.528 + 1.529 +</pre> 1.530 + 1.531 + 1.532 + 1.533 + 1.534 +<p> 1.535 +This construct has two interesting properties: 1.536 +</p><ul> 1.537 +<li>(1) It performs statement S1 before S2, and so may be used for 1.538 + sequencing. 1.539 +</li> 1.540 +<li>(2) S1 is useful only for its side effects. (In ALGOL, S2 must also 1.541 + be a statement, and so is also useful only for side effects, but 1.542 + other languages have compound expressions containing a statement 1.543 + followed by an expression.) 1.544 +</li> 1.545 +</ul> 1.546 + 1.547 + 1.548 +<p> 1.549 +The ALGOL compound statement may actually contain any number of statements, 1.550 +but such statements can be expressed as a series of nested two-statement 1.551 +compounds. That is: 1.552 +</p> 1.553 + 1.554 + 1.555 +<pre class="src src-algol">begin 1.556 +S1; 1.557 +S2; 1.558 +... 1.559 +Sn-1; 1.560 +Sn; 1.561 +end 1.562 + 1.563 +</pre> 1.564 + 1.565 + 1.566 + 1.567 +<p> 1.568 +is equivalent to: 1.569 +</p> 1.570 + 1.571 + 1.572 + 1.573 +<pre class="src src-algol">begin 1.574 +S1; 1.575 +begin 1.576 +S2; 1.577 +begin 1.578 +... 1.579 + 1.580 +begin 1.581 +Sn-1; 1.582 +Sn; 1.583 +end; 1.584 +end; 1.585 +end: 1.586 +end 1.587 + 1.588 +</pre> 1.589 + 1.590 + 1.591 + 1.592 + 1.593 +<p> 1.594 +It is not immediately apparent that this sequencing can be expressed in a 1.595 +purely applicative language. We can, however, take advantage of the implicit 1.596 +sequencing of applicative order evaluation. Thus, for example, we may write a 1.597 +two-statement sequence as follows: 1.598 +</p> 1.599 + 1.600 + 1.601 + 1.602 +<pre class="src src-clojure">((<span style="color: #8cd0d3;">fn</span>[dummy] S2) S1) 1.603 + 1.604 +</pre> 1.605 + 1.606 + 1.607 + 1.608 + 1.609 +<p> 1.610 +where <code>dummy</code> is an identifier not used in S2. From this it is 1.611 +manifest that the value of S1 is ignored, and so is useful only for 1.612 +side effects. (Note that we did not claim that S1 is expressed in a 1.613 +purely applicative language, but only that the sequencing can be so 1.614 +expressed.) From now on we will use the form <code>(BLOCK S1 S2)</code> as an 1.615 +abbreviation for this expression, and <code>(BLOCK S1 S2...Sn-1 Sn)</code> as an 1.616 +abbreviation for 1.617 +</p> 1.618 + 1.619 + 1.620 + 1.621 +<pre class="src src-algol">(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...))) 1.622 + 1.623 +</pre> 1.624 + 1.625 + 1.626 + 1.627 + 1.628 +</div> 1.629 + 1.630 +</div> 1.631 + 1.632 +<div id="outline-container-3-2" class="outline-3"> 1.633 +<h3 id="sec-3-2"><span class="section-number-3">3.2</span> 2.2. The G0 TO Statement </h3> 1.634 +<div class="outline-text-3" id="text-3-2"> 1.635 + 1.636 + 1.637 +<p> 1.638 +A more general imperative structure is the compound statement with 1.639 +labels and G0 T0s. Consider the following code fragment due to 1.640 +Jacopini, taken from Knuth: [Knuth 74] 1.641 +</p> 1.642 + 1.643 + 1.644 +<pre class="src src-algol">begin 1.645 +L1: if B1 then go to L2; S1; 1.646 + if B2 then go to L2; S2; 1.647 + go to L1; 1.648 +L2: S3; 1.649 + 1.650 +</pre> 1.651 + 1.652 + 1.653 + 1.654 + 1.655 +<p> 1.656 +It is perhaps surprising that this piece of code can be <i>syntactically</i> 1.657 +transformed into a purely applicative style. For example, in SCHEME we 1.658 +could write: 1.659 +</p> 1.660 + 1.661 + 1.662 + 1.663 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative) 1.664 +(<span style="color: #f0dfaf; font-weight: bold;">let</span> 1.665 + [L1 (<span style="color: #8cd0d3;">fn</span>[] 1.666 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> B1 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S1 1.667 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> B2 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S2 (L1)))))) 1.668 + L2 (<span style="color: #8cd0d3;">fn</span>[] S3)] 1.669 + (L1)) 1.670 + 1.671 +</pre> 1.672 + 1.673 + 1.674 + 1.675 + 1.676 +<p> 1.677 +As with the D0 loop, this transformation depends critically on SCHEME's 1.678 +treatment of tail-recursion and on lexical scoping of variables. The labels 1.679 +are names of functions of no arguments. In order to ‘go to" the labeled code, 1.680 +we merely call the function named by that label. 1.681 +</p> 1.682 +</div> 1.683 + 1.684 +</div> 1.685 + 1.686 +<div id="outline-container-3-3" class="outline-3"> 1.687 +<h3 id="sec-3-3"><span class="section-number-3">3.3</span> 2.3. Simple Assignment </h3> 1.688 +<div class="outline-text-3" id="text-3-3"> 1.689 + 1.690 +<p>Of course, all this sequencing of statements is useless unless the 1.691 +statements have side effects. An important side effect is assignment. For 1.692 +example, one often uses assignment to place intermediate results in a named 1.693 +location (i.e. a variable) so that they may be used more than once later 1.694 +without recomputing them: 1.695 +</p> 1.696 + 1.697 + 1.698 + 1.699 +<pre class="src src-algol">begin 1.700 +real a2, sqrtdisc; 1.701 +a2 := 2*a; 1.702 +sqrtdisc := sqrt(b^2 - 4*a*c); 1.703 +root1 := (- b + sqrtdisc) / a2; 1.704 +root2 := (- b - sqrtdisc) / a2; 1.705 +print(root1); 1.706 +print(root2); 1.707 +print(root1 + root2); 1.708 +end 1.709 + 1.710 +</pre> 1.711 + 1.712 + 1.713 + 1.714 + 1.715 +<p> 1.716 +It is well known that such naming of intermediate results may be accomplished 1.717 +by calling a function and binding the formal parameter variables to the 1.718 +results: 1.719 +</p> 1.720 + 1.721 + 1.722 + 1.723 +<pre class="src src-clojure">(<span style="color: #8cd0d3;">fn</span> [a2 sqrtdisc] 1.724 + ((<span style="color: #8cd0d3;">fn</span>[root1 root2] 1.725 + (<span style="color: #f0dfaf; font-weight: bold;">do</span> (<span style="color: #8cd0d3;">println</span> root1) 1.726 + (<span style="color: #8cd0d3;">println</span> root2) 1.727 + (<span style="color: #8cd0d3;">println</span> (<span style="color: #8cd0d3;">+</span> root1 root2)))) 1.728 + (<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">+</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2) 1.729 + (<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2)) 1.730 + 1.731 + (<span style="color: #8cd0d3;">*</span> 2 a) 1.732 + (sqrt (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">*</span> b b) (<span style="color: #8cd0d3;">*</span> 4 a c)))) 1.733 + 1.734 +</pre> 1.735 + 1.736 + 1.737 + 1.738 +<p> 1.739 +This technique can be extended to handle all simple variable assignments which 1.740 +appear as statements in blocks, even if arbitrary G0 T0 statements also appear 1.741 +in such blocks. {Note Mccarthywins} 1.742 +</p> 1.743 +<p> 1.744 +For example, here is a program which uses G0 TO statements in the form 1.745 +presented before; it determines the parity of a non-negative integer by 1.746 +counting it down until it reaches zero. 1.747 +</p> 1.748 + 1.749 + 1.750 + 1.751 +<pre class="src src-algol">begin 1.752 +L1: if a = 0 then begin parity := 0; go to L2; end; 1.753 + a := a - 1; 1.754 + if a = 0 then begin parity := 1; go to L2; end; 1.755 + a := a - 1; 1.756 + go to L1; 1.757 +L2: print(parity); 1.758 + 1.759 +</pre> 1.760 + 1.761 + 1.762 + 1.763 + 1.764 +<p> 1.765 +This can be expressed in SCHEME: 1.766 +</p> 1.767 + 1.768 + 1.769 + 1.770 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">let</span> 1.771 + [L1 (<span style="color: #8cd0d3;">fn</span> [a parity] 1.772 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 0) 1.773 + (L3 (<span style="color: #8cd0d3;">dec</span> a) parity))) 1.774 + L3 (<span style="color: #8cd0d3;">fn</span> [a parity] 1.775 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 1) 1.776 + (L1 (<span style="color: #8cd0d3;">dec</span> a) parity))) 1.777 + L2 (<span style="color: #8cd0d3;">fn</span> [a parity] 1.778 + (<span style="color: #8cd0d3;">println</span> parity))] 1.779 + (L1 a parity)) 1.780 + 1.781 +</pre> 1.782 + 1.783 + 1.784 + 1.785 + 1.786 +<p> 1.787 +The trick is to pass the set of variables which may be altered as arguments to 1.788 +the label functions. {Note Flowgraph} It may be necessary to introduce new 1.789 +labels (such as L3) so that an assignment may be transformed into the binding 1.790 +for a function call. At worst, one may need as many labels as there are 1.791 +statements (not counting the eliminated assignment and GO TO statements). 1.792 +</p> 1.793 +</div> 1.794 + 1.795 +</div> 1.796 + 1.797 +<div id="outline-container-3-4" class="outline-3"> 1.798 +<h3 id="sec-3-4"><span class="section-number-3">3.4</span> Compound Expressions ' </h3> 1.799 +<div class="outline-text-3" id="text-3-4"> 1.800 + 1.801 +<p>At this point we are almost in a position to model the most general 1.802 +form of compound statement. In LISP, this is called the 'PROG feature". In 1.803 +addition to statement sequencing and G0 T0 statements, one can return a <i>value</i> 1.804 +from a PROG by using the RETURN statement. 1.805 +</p> 1.806 +<p> 1.807 +Let us first consider the simplest compound statement, which in SCHEME 1.808 +we call BLOCK. Recall that 1.809 +<code>(BLOCK s1 sz)</code> is defined to be <code>((lambda (dummy) s2) s1)</code> 1.810 +</p> 1.811 +<p> 1.812 +Notice that this not only performs Sl before S2, but also returns the value of 1.813 +S2. Furthermore, we defined <code>(BLOCK S1 S2 ... Sn)</code> so that it returns the value 1.814 +of <code>Sn</code>. Thus BLOCK may be used as a compound expression, and models a LISP 1.815 +PROGN, which is a PROG with no G0 T0 statements and an implicit RETURN of the 1.816 +last ``statement'' (really an expression). 1.817 +</p> 1.818 +<p> 1.819 +Host LISP compilers compile D0 expressions by macro-expansion. We have 1.820 +already seen one way to do this in SCHEME using only variable binding. A more 1.821 +common technique is to expand the D0 into a PROG, using variable assignments 1.822 +instead of bindings. Thus the iterative factorial program: 1.823 +</p> 1.824 + 1.825 + 1.826 + 1.827 +<pre class="src src-clojure">(oarxnz FACT . 1.828 +(LAMaoA (n) . 1.829 +(D0 ((M N (<span style="color: #8cd0d3;">-</span> H 1)) 1.830 +(Ans 1 (<span style="color: #8cd0d3;">*</span> M Ans))) 1.831 +((<span style="color: #8cd0d3;">-</span> H 0) A<span style="color: #cc9393;">"$))))</span> 1.832 + 1.833 +</pre> 1.834 + 1.835 + 1.836 + 1.837 + 1.838 +<p> 1.839 +would expand into: 1.840 +</p> 1.841 + 1.842 + 1.843 + 1.844 +<pre class="src src-clojure">(DEFINE FACT 1.845 +. (LAMeoA (M) 1.846 +(PRO6 (M Ans) 1.847 +(sszro M n 1.848 +Ans 1) ~ 1.849 +LP (tr (<span style="color: #8cd0d3;">-</span> M 0) (RETURN Ans)) 1.850 +(ssero M (<span style="color: #8cd0d3;">-</span> n 1) 1.851 +Ans (' M Ans)) 1.852 +(60 LP)))) 1.853 + 1.854 +</pre> 1.855 + 1.856 + 1.857 + 1.858 + 1.859 +<p> 1.860 +where SSETQ is a simultaneous multiple assignment operator. (SSETQ is not a 1.861 +SCHEME (or LISP) primitive. It can be defined in terms of a single assignment 1.862 +operator, but we are more interested here in RETURN than in simultaneous 1.863 +assignment. The SSETQ's will all be removed anyway and modelled by lambda 1.864 +binding.) We can apply the same technique we used before to eliminate G0 T0 1.865 +statements and assignments from compound statements: 1.866 +</p> 1.867 + 1.868 + 1.869 + 1.870 +<pre class="src src-clojure">(DEFINE FACT 1.871 +(LAHBOA (I) 1.872 +(LABELS ((L1 (LAManA (M Ans) 1.873 +(LP n 1))) 1.874 +(LP (LAMaoA (M Ans) 1.875 +(IF (<span style="color: #8cd0d3;">-</span> M o) (nztunn Ans) 1.876 +(£2 H An$)))) 1.877 +(L2 (LAMaoA (M An ) 1.878 +(LP (<span style="color: #8cd0d3;">-</span> <span style="color: #cc9393;">" 1) (' H flN$)))))</span> 1.879 +<span style="color: #e37170; background-color: #332323;">(</span><span style="color: #cc9393;">L1 NIL NlL))))</span> 1.880 + 1.881 +</pre> 1.882 + 1.883 + 1.884 +<p> 1.885 + clojure 1.886 +</p> 1.887 +<p> 1.888 +We still haven't done anything about RETURN. Let's see… 1.889 +</p><ul> 1.890 +<li>==> the value of (FACT 0) is the value of (Ll NIL NIL) 1.891 +</li> 1.892 +<li>==> which is the value of (LP 0 1) 1.893 +</li> 1.894 +<li>==> which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1)) 1.895 +</li> 1.896 +<li>==> which is the value of (RETURN 1) 1.897 +</li> 1.898 +</ul> 1.899 + 1.900 + 1.901 +<p> 1.902 +Notice that if RETURN were the <i>identity function</i> (LAMBDA (X) X), we would get the right answer. This is in fact a 1.903 +general truth: if we Just replace a call to RETURN with its argument, then 1.904 +our old transformation on compound statements extends to general compound 1.905 +expressions, i.e. PROG. 1.906 +</p> 1.907 +</div> 1.908 +</div> 1.909 + 1.910 +</div> 1.911 + 1.912 +<div id="outline-container-4" class="outline-2"> 1.913 +<h2 id="sec-4"><span class="section-number-2">4</span> Continuations </h2> 1.914 +<div class="outline-text-2" id="text-4"> 1.915 + 1.916 +<p>Up to now we have thought of SCHEME's LAMBDA expressions as functions, 1.917 +and of a combination such as <code>(G (F X Y))</code> as meaning ``apply the function F to 1.918 +the values of X and Y, and return a value so that the function G can be 1.919 +applied and return a value …'' But notice that we have seldom used LAMBDA 1.920 +expressions as functions. Rather, we have used them as control structures and 1.921 +environment modifiers. For example, consider the expression: 1.922 +<code>(BLOCK (PRINT 3) (PRINT 4))</code> 1.923 +</p> 1.924 +<p> 1.925 +This is defined to be an abbreviation for: 1.926 +<code>((LAMBDA (DUMMY) (PRINT 4)) (PRINT 3))</code> 1.927 +</p> 1.928 +<p> 1.929 +We do not care about the value of this BLOCK expression; it follows that we 1.930 +do not care about the value of the <code>(LAMBDA (DUMMY) ...)</code>. We are not using 1.931 +LAMBDA as a function at all. 1.932 +</p> 1.933 +<p> 1.934 +It is possible to write useful programs in terms of LAHBDA expressions 1.935 +in which we never care about the value of <i>any</i> lambda expression. We have 1.936 +already demonstrated how one could represent any "FORTRAN" program in these 1.937 +terms: all one needs is PROG (with G0 and SETQ), and PRINT to get the answers 1.938 +out. The ultimate generalization of this imperative programing style is 1.939 +<i>continuation-passing</i>. (Note Churchwins} . 1.940 +</p> 1.941 + 1.942 +</div> 1.943 + 1.944 +<div id="outline-container-4-1" class="outline-3"> 1.945 +<h3 id="sec-4-1"><span class="section-number-3">4.1</span> Continuation-Passing Recursion </h3> 1.946 +<div class="outline-text-3" id="text-4-1"> 1.947 + 1.948 +<p>Consider the following alternative definition of FACT. It has an extra 1.949 +argument, the continuation, which is a function to call with the answer, when 1.950 +we have it, rather than return a value 1.951 +</p> 1.952 + 1.953 + 1.954 + 1.955 +<pre class="src src-algol.">procedure Inc!(n, c); value n, c; 1.956 +integer n: procedure c(integer value); 1.957 +if n-=0 then c(l) else 1.958 +begin 1.959 +procedure l(!mp(d) value a: integer a; 1.960 +c(mm); 1.961 +Iacl(n-1, romp): 1.962 +end; 1.963 + 1.964 +</pre> 1.965 + 1.966 + 1.967 + 1.968 + 1.969 + 1.970 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative) 1.971 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-cps</span>[n k] 1.972 + (<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? n) (k 1) 1.973 + (<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)))))) 1.974 + 1.975 +</pre> 1.976 + 1.977 + 1.978 +<p> 1.979 + clojure 1.980 +It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to 1.981 +do something like this: 1.982 +</p> 1.983 + 1.984 + 1.985 + 1.986 +<pre class="src src-algol">begin 1.987 +integer ann 1.988 +procedure :emp(x); value 2:; integer x; 1.989 +ans :1 x; 1.990 +]'act(3. temp); 1.991 +comment Now the variable <span style="color: #cc9393;">"am"</span> has 6; 1.992 +end; 1.993 + 1.994 +</pre> 1.995 + 1.996 + 1.997 + 1.998 + 1.999 +<p> 1.1000 +Procedure <code>fact</code> does not return a value, nor does <code>temp</code>; we must use a side 1.1001 +effect to get the answer out. 1.1002 +</p> 1.1003 +<p> 1.1004 +<code>FACT</code> is somewhat easier to use in SCHEME. We can call it like an 1.1005 +ordinary function in SCHEME if we supply an identity function as the second 1.1006 +argument. For example, <code>(FACT 3 (LAMBDA (X) X))</code> returns 6. Alternatively, we 1.1007 +could write <code>(FACT 3 (LAHBDA (X) (PRINT X)))</code>; we do not care about the value 1.1008 +of this, but about what gets printed. A third way to use the value is to 1.1009 +write 1.1010 +<code>(FACT 3 (LAMBDA (x) (SQRT x)))</code> 1.1011 +instead of 1.1012 +<code>(SQRT (FACT 3 (LAMBDA (x) x)))</code> 1.1013 +</p> 1.1014 +<p> 1.1015 +In either of these cases we care about the value of the continuation given to 1.1016 +FACT. Thus we care about the value of FACT if and only if we care about the 1.1017 +value of its continuation! 1.1018 +</p> 1.1019 +<p> 1.1020 +We can redefine other functions to take continuations in the same way. 1.1021 +For example, suppose we had arithmetic primitives which took continuations; to 1.1022 +prevent confusion, call the version of "+" which takes a continuation '++", 1.1023 +etc. Instead of writing 1.1024 +<code>(- (+ B Z)(* 4 A C))</code> 1.1025 +we can write 1.1026 +</p> 1.1027 + 1.1028 + 1.1029 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative) 1.1030 +(<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] 1.1031 + (<span style="color: #8cd0d3;">fn</span>[& 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)) )) 1.1032 +(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">+&</span> (enable-continuation +)) 1.1033 +(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">*&</span> (enable-continuation *)) 1.1034 +(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">-&</span> (enable-continuation -)) 1.1035 + 1.1036 + 1.1037 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">quadratic</span>[a b c k] 1.1038 +(*& b b 1.1039 + (<span style="color: #8cd0d3;">fn</span>[x] (*& 4 a c 1.1040 + (<span style="color: #8cd0d3;">fn</span>[y] 1.1041 + (-& x y k)))))) 1.1042 + 1.1043 +</pre> 1.1044 + 1.1045 + 1.1046 + 1.1047 + 1.1048 +<p> 1.1049 +where <code>k</code> is the continuation for the entire expression. 1.1050 +</p> 1.1051 +<p> 1.1052 +This is an obscure way to write an algebraic expression, and we would 1.1053 +not advise writing code this way in general, but continuation-passing brings 1.1054 +out certain important features of the computation: 1.1055 +</p><ul> 1.1056 +<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 1.1057 +</li> 1.1058 +</ul> 1.1059 + 1.1060 +<p>performed. In fact, they <i>must</i> be performed in this 1.1061 +order. Continuation- passing removes the need for the rule about 1.1062 +left-to-right argument evaluation{Note Evalorder) 1.1063 +</p><ul> 1.1064 +<li><sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup> In the usual applicative expression there are two implicit 1.1065 + temporary values: those of <code>(* B B)</code> and <code>(* 4 A C)</code>. The first of 1.1066 + these values must be preserved over the computation of the second, 1.1067 + whereas the second is used as soon as it is produced. These facts 1.1068 + are <i>manifest</i> in the appearance and use of the variable X and Y in 1.1069 + the continuation-passing version. 1.1070 +</li> 1.1071 +</ul> 1.1072 + 1.1073 + 1.1074 +<p> 1.1075 +In short, the continuation-passing version specifies <i>exactly</i> and 1.1076 + explicitly what steps are necessary to compute the value of the 1.1077 + expression. One can think of conventional functional application 1.1078 + for value as being an abbreviation for the more explicit 1.1079 + continuation-passing style. Alternatively, one can think of the 1.1080 + interpreter as supplying to each function an implicit default 1.1081 + continuation of one argument. This continuation will receive the 1.1082 + value of the function as its argument, and then carry on the 1.1083 + computation. In an interpreter this implicit continuation is 1.1084 + represented by the control stack mechanism for function returns. 1.1085 + Now consider what computational steps are implied by: 1.1086 +</p> 1.1087 +<p> 1.1088 +<code>(LAMBDA (A B C ...) (F X Y Z ...))</code> when we "apply" the LAMBDA 1.1089 + expression we have some values to apply it to; we let the names A, 1.1090 + B, C … refer to these values. We then determine the values of X, 1.1091 + Y, Z … and pass these values (along with "the buck", 1.1092 + i.e. control!) to the lambda expression F (F is either a lambda 1.1093 + expression or a name for one). Passing control to F is an 1.1094 + unconditional transfer. (Note Jrsthack) {Note Hewitthack) Note that 1.1095 + we want values from X, Y, Z, … If these are simple expressions, 1.1096 + such as variables, constants, or LAMBDA expressions, the evaluation 1.1097 + process is trivial, in that no temporary storage is required. In 1.1098 + pure continuation-passing style, all evaluations are trivial: no 1.1099 + combination is nested within another, and therefore no ‘hidden 1.1100 + temporaries" are required. But if X is a combination, say (G P Q), 1.1101 + then we want to think of G as a function, because we want a value 1.1102 + from it, and we will need an implicit temporary place to keep the 1.1103 + result while evaluating Y and Z. (An interpreter usually keeps these 1.1104 + temporary places in the control stack!) On the other hand, we do not 1.1105 + necessarily need a value from F. This is what we mean by tail- 1.1106 + recursion: F is called tail-recursively, whereas G is not. A better 1.1107 + name for tail-recursion would be "tail-transfer", since no real 1.1108 + recursion is implied. This is why we have made such a fuss about 1.1109 + tail-recursion: it can be used for transfer of control without 1.1110 + making any commitment about whether the expression expected to 1.1111 + return a value. Thus it can be used to model statement-like control 1.1112 + structures. Put another way, tail—recursion does not require a 1.1113 + control stack as nested recursion does. In our models of iteration 1.1114 + and imperative style all the LAMBDA expressions used for control (to 1.1115 + simulate GO statements, for example) are called in tail-recursive 1.1116 + fashion. 1.1117 +</p> 1.1118 +</div> 1.1119 + 1.1120 +</div> 1.1121 + 1.1122 +<div id="outline-container-4-2" class="outline-3"> 1.1123 +<h3 id="sec-4-2"><span class="section-number-3">4.2</span> Escape Expressions </h3> 1.1124 +<div class="outline-text-3" id="text-4-2"> 1.1125 + 1.1126 +<p>Reynolds [Reynolds 72] defines the construction 1.1127 += escape x in r = 1.1128 +</p> 1.1129 +<p> 1.1130 +to evaluate the expression \(r\) in an environment such that the variable \(x\) is 1.1131 +bound to an escape function. If the escape function is never applied, then 1.1132 +the value of the escape expression is the value of \(r\). If the escape function 1.1133 +is applied to an argument \(a\), however, then evaluation of \(r\) is aborted and the 1.1134 +escape expression returns \(a\). {Note J-operator} (Reynolds points out that 1.1135 +this definition is not quite accurate, since the escape function may be called 1.1136 +even after the escape expression has returned a value; if this happens, it 1.1137 +“returns again"!) 1.1138 +</p> 1.1139 +<p> 1.1140 +As an example of the use of an escape expression, consider this 1.1141 +procedure to compute the harmonic mean of an array of numbers. If any of the 1.1142 +numbers is zero, we want the answer to be zero. We have a function hannaunl 1.1143 +which will sum the reciprocals of numbers in an array, or call an escape 1.1144 +function with zero if any of the numbers is zero. (The implementation shown 1.1145 +here is awkward because ALGOL requires that a function return its value by 1.1146 +assignment.) 1.1147 +</p> 1.1148 + 1.1149 + 1.1150 +<pre class="src src-algol">begin 1.1151 +real procedure Imrmsum(a, n. escfun)§ p 1.1152 +real array at integer n; real procedure esciun(real); 1.1153 +begin 1.1154 +real sum; 1.1155 +sum := 0; 1.1156 +for i :1 0 until n-l do 1.1157 +begin 1.1158 +if a[i]=0 then cscfun(0); 1.1159 +sum :1 sum ¢ I/a[i]; 1.1160 +enm 1.1161 +harmsum SI sum; 1.1162 +end: . 1.1163 +real array b[0:99]: 1.1164 +print(escape x in I00/hm-m.mm(b, 100, x)); 1.1165 +end 1.1166 + 1.1167 +</pre> 1.1168 + 1.1169 + 1.1170 + 1.1171 + 1.1172 +<p> 1.1173 +If harmsum exits normally, the number of elements is divided by the sum and 1.1174 +printed. Otherwise, zero is returned from the escape expression and printed 1.1175 +without the division ever occurring. 1.1176 +This program can be written in SCHEME using the built-in escape 1.1177 +operator <code>CATCH</code>: 1.1178 +</p> 1.1179 + 1.1180 + 1.1181 + 1.1182 +<pre class="src src-clojure">abc 1.1183 + 1.1184 +</pre> 1.1185 + 1.1186 + 1.1187 + 1.1188 +<div id="footnotes"> 1.1189 +<h2 class="footnotes">Footnotes: </h2> 1.1190 +<div id="text-footnotes"> 1.1191 +<p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> DEFINITION NOT FOUND: 1 1.1192 +</p> 1.1193 + 1.1194 +<p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> DEFINITION NOT FOUND: 2 1.1195 +</p> 1.1196 +</div> 1.1197 +</div> 1.1198 +</div> 1.1199 + 1.1200 +</div> 1.1201 +</div> 1.1202 +<div id="postamble"> 1.1203 +<p class="date">Date: 2011-07-15 02:49:04 EDT</p> 1.1204 +<p class="author">Author: Guy Lewis Steele Jr. and Gerald Jay Sussman</p> 1.1205 +<p class="creator">Org version 7.6 with Emacs version 23</p> 1.1206 +<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a> 1.1207 +</div> 1.1208 +</div> 1.1209 +</body> 1.1210 +</html>