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