view categorical/imperative.org @ 11:1f112b4f9e8f tip

Fixed what was baroque.
author Dylan Holmes <ocsenave@gmail.com>
date Tue, 01 Nov 2011 02:30:49 -0500
parents b4de894a1e2e
children
line wrap: on
line source
1 #+TITLE: LAMBDA: The Ultimate Imperative
2 #+AUTHOR: Guy Lewis Steele Jr. and Gerald Jay Sussman
4 * Abstract
6 We demonstrate how to model the following common programming constructs in
7 terms of an applicative order language similar to LISP:
8 - Simple Recursion
9 - Iteration
10 - Compound Statements and Expressions
11 - GO TO and Assignment
12 - Continuation—Passing
13 - Escape Expressions
14 - Fluid Variables
15 - Call by Name, Call by Need, and Call by Reference
16 The models require only (possibly self-referent) lambda application,
17 conditionals, and (rarely) assignment. No complex data structures such as
18 stacks are used. The models are transparent, involving only local syntactic
19 transformations.
20 Some of these models, such as those for GO TO and assignment, are already well
21 known, and appear in the work of Landin, Reynolds, and others. The models for
22 escape expressions, fluid variables, and call by need with side effects are
23 new. This paper is partly tutorial in intent, gathering all the models
24 together for purposes of context.
25 This report describes research done at the Artificial Intelligence Laboratory
26 of the Massachusetts Institute of Teehnology. Support for the laboratory's
27 artificial intelligence research is provided in part by the Advanced Research
28 Projects Agency of the Department of Defense under Office of Naval Research
29 contract N000l4-75-C-0643.
31 * Introduction
33 We catalogue a number of common programming constructs. For each
34 construct we examine "typical" usage in well-known programming languages, and
35 then capture the essence of the semantics of the construct in terms of a
36 common meta-language.
37 The lambda calculus {Note Alonzowins} is often used as such a meta-
38 language. Lambda calculus offers clean semantics, but it is clumsy because it
39 was designed to be a minimal language rather than a convenient one. All
40 lambda calculus "functions" must take exactly one "argument"; the only "data
41 type" is lambda expressions; and the only "primitive operation‘ is variable‘
42 substitution. While its utter simplicity makes lambda calculus ideal for
43 logicians, it is too primitive for use by programmers. The meta-language we
44 use is a programming language called SCHEME {Note Schemepaper) which is based
45 on lambda calculus.
46 SCHEME is a dialect of LISP. [McCarthy 62] It is an expression-
47 oriented, applicative order, interpreter-based language which allows one to
48 manipulate programs as data. It differs from most current dialects of LISP in
49 that it closes all lambda expressions in the environment of their definition
50 or declaration, rather than in the execution environment. {Note Closures}
51 This preserves the substitution semantics of lambda calculus, and has the
52 consequence that all variables are lexically scoped, as in ALGOL. [Naur 63]
53 Another difference is that SCHEME is implemented in such a way that tail-
54 recursions execute without net growth of the interpreter stack. {Note
55 Schemenote} We have chosen to use LISP syntax rather than, say, ALGOL syntax
56 because we want to treat programs as data for the purpose of describing
57 transformations on the code. LISP supplies names for the parts of an
58 executable expression and standard operators for constructing expressions and
59 extracting their components. The use of LISP syntax makes the structure of
60 such expressions manifest. We use ALGOL as an expository language, because it
61 is familiar to many people, but ALGOL is not sufficiently powerful to express
62 the necessary concepts; in particular, it does not allow functions to return
63 functions as values. we are thus forced to use a dialect of LISP in many
64 cases.
65 We will consider various complex programming language constructs and
66 show how to model them in terms of only a few simple ones. As far as possible
67 we will use only three control constructs from SCHEME: LAMBDA expressions, as
68 in LISP, which are Just functions with lexically scoped free variables;
69 LABELS, which allows declaration of mutually recursive procedures (Note
70 Labelsdef}; and IF, a primitive conditional expression. For more complex
71 modelling we will introduce an assignment primitive (ASET).i We will freely
72 assume the existence of other comon primitives, such as arithmetic functions.
73 The constructs we will examine are divided into four broad classes.
74 The first is sfinph?Lo0pl; this contains simple recursions and iterations, and
75 an introduction to the notion of continuations. The second is hmponflivo
76 Connrucls; this includes compound statements, G0 T0, and simple variable
77 assignments. The third is continuations, which encompasses the distinction between statements and expressions, escape operators (such as Landin's J-
78 operator [Landin 65] and Reynold's escape expression [Reynolds 72]). and fluid
79 (dynamically bound) variables. The fourth is Parameter Passing Mechanisms, such
80 as ALGOL call—by-name and FORTRAN call-by-location.
81 Some of the models presented here are already well-known, particularly
82 those for G0 T0 and assignment. [McCarthy 60] [Landin 65] [Reynolds 72]
83 Those for escape operators, fluid variables, and call-by-need with side
84 effects are new.
85 ** Simple Loops
86 By /simple loops/ we mean constructs which enable programs to execute the
87 same piece of code repeatedly in a controlled manner. Variables may be made
88 to take on different values during each repetition, and the number of
89 repetitions may depend on data given to the program.
90 *** Simple Recursion
91 One of the easiest ways to produce a looping control structure is to
92 use a recursive function, one which calls itself to perform a subcomputation.
93 For example, the familiar factorial function may be written recursively in
94 ALGOL: '
95 #+begin_src algol
96 integer procedure fact(n) value n: integer n:
97 fact := if n=0 then 1 else n*fact(n-1);
98 #+end_src
100 The invocation =fact(n)= computes the product of the integers from 1 to n using
101 the identity n!=n(n-1)! (n>0). If $n$ is zero, 1 is returned; otherwise =fact=:
102 calls itself recursively to compute $(n-1)!$ , then multiplies the result by $n$
103 and returns it.
105 This same function may be written in Clojure as follows:
106 #+begin_src clojure
107 (ns categorical.imperative)
108 (defn fact[n]
109 (if (= n 0) 1 (* n (fact (dec n))))
110 )
111 #+end_src
113 #+results:
114 : #'categorical.imperative/fact
116 Clojure does not require an assignment to the ``variable'' fan: to return a value
117 as ALGOL does. The IF primitive is the ALGOL if-then-else rendered in LISP
118 syntax. Note that the arithmetic primitives are prefix operators in SCHEME.
120 *** Iteration
121 There are many other ways to compute factorial. One important way is
122 through the use of /iteration/.
123 A comon iterative construct is the DO loop. The most general form we
124 have seen in any programming language is the MacLISP DO [Moon 74]. It permits
125 the simultaneous initialization of any number of control variables and the
126 simultaneous stepping of these variables by arbitrary functions at each
127 iteration step. The loop is terminated by an arbitrary predicate, and an
128 arbitrary value may be returned. The DO loop may have a body, a series of
129 expressions executed for effect on each iteration. A version of the MacLISP
130 DO construct has been adopted in SCHEME.
132 The general form of a SCHEME DO is:
133 #+begin_src nothing
134 (DO ((<var1> (init1> <stepl>)
135 ((var2> <init2> <step2>)
136 (<varn> <intn> (stepn>))
137 (<pred> (value>)
138 (optional body>)
139 #+end_src
140 The semantics of this are that the variables are bound and initialized to the
141 values of the <initi> expressions, which must all be evaluated in the
142 environment outside the D0; then the predicate <pred> is evaluated in the new
143 environment, and if TRUE, the (value) is evaluated and returned. Otherwise
144 the (optional body) is evaluated, then each of the steppers <stepi> is
145 evaluated in the current environment, all the variables made to have the
146 results as their values, the predicate evaluated again, and so on.
147 Using D0 loops in both ALGOL and SCHEME, we may express FACT by means
148 of iteration.
149 #+begin_src algol
150 integer procedure fact(n); value n; integer n:
151 begin
152 integer m, ans;
153 ans := 1;
154 for m := n step -l until 0 do ans := m*ans;
155 fact := ans;
156 end;
157 #+end_src
159 #+begin_src clojure
160 (in-ns 'categorical.imperative)
161 (defn fact-do[n]
162 )
163 #+end_src
165 Note that the SCHEME D0 loop in FACT has no body -- the stepping functions do
166 all the work. The ALGOL DO loop has an assignment in its body; because an
167 ALGOL DO loop can step only one variable, we need the assignment to step the
168 the variable "manually'.
169 In reality the SCHEME DO construct is not a primitive; it is a macro
170 which expands into a function which performs the iteration by tail—recursion.
171 Consider the following definition of FACT in SCHEME. Although it appears to
172 be recursive, since it "calls itself", it is entirely equivalent to the DO
173 loop given above, for it is the code that the DO macro expands into! It
174 captures the essence of our intuitive notion of iteration, because execution
175 of this program will not produce internal structures (e.g. stacks or variable
176 bindings) which increase in size with the number of iteration steps.
178 #+begin_src clojure
179 (in-ns 'categorical.imperative)
180 (defn fact-do-expand[n]
181 (let [fact1
182 (fn[m ans]
183 (if (zero? m) ans
184 (recur (dec m) (* m ans))))]
185 (fact1 n 1)))
186 #+end_src
188 From this we can infer a general way to express iterations in SCHEME in
189 a manner isomorphic to the HacLISP D0. The expansion of the general D0 loop
190 #+begin_src nothing
191 (DO ((<varl> <init1> <step1>)
192 (<var2> (init2) <step2>)
193 ...
194 (<varn> <initn> <stepn>))
195 (<pred> <va1ue>)
196 <body>)
197 #+end_src
198 is this:
199 #+begin_src nothing
200 (let [doloop
201 (fn [dummy <var1> <var2> ... <varn>)
202 (if <pred> <value>
203 (recur <body> <step1> <step2> ... <stepn>)))]
205 (doloop nil <init1> <init2> ... <initn>))
206 #+end_src
207 The identifiers =doloop= and =dummy= are chosen so as not to conflict with any
208 other identifiers in the program.
209 Note that, unlike most implementations of D0, there are no side effects
210 in the steppings of the iteration variables. D0 loops are usually modelled
211 using assignment statements. For example:
212 #+begin_src nothing
213 for r :1 0 step b until c do <statement>;
214 #+end_src
216 can be modelled as follows: [Naur 63]
217 #+begin_src nothing
218 begin
219 x := a;
220 L: if (x-c)*sign(n) > 0 then go to Endloop;
221 <statement>;
222 x := x+b;
223 go to L:
224 Endloop:
225 end;
226 #+end_src
227 Later we will see how such assignment statements can in general be
228 modelled without using side effects.
230 * Imperative Programming
231 Lambda calculus (and related languages, such as ``pure LISP'') is often
232 used for modelling the applicative constructs of programming languages.
233 However, they are generally thought of as inappropriate for modelling
234 imperative constructs. In this section we show how imperative constructs may
235 be modelled by applicative SCHEME constructs.
236 ** Compound Statements
237 The simplest kind of imperative construct is the statement sequencer,
238 for example the compound statement in ALGOL:
239 #+begin_src algol
240 begin
241 S1;
242 S2;
243 end
244 #+end_src
246 This construct has two interesting properties:
247 - (1) It performs statement S1 before S2, and so may be used for
248 sequencing.
249 - (2) S1 is useful only for its side effects. (In ALGOL, S2 must also
250 be a statement, and so is also useful only for side effects, but
251 other languages have compound expressions containing a statement
252 followed by an expression.)
254 The ALGOL compound statement may actually contain any number of statements,
255 but such statements can be expressed as a series of nested two-statement
256 compounds. That is:
257 #+begin_src algol
258 begin
259 S1;
260 S2;
261 ...
262 Sn-1;
263 Sn;
264 end
265 #+end_src
266 is equivalent to:
268 #+begin_src algol
269 begin
270 S1;
271 begin
272 S2;
273 begin
274 ...
276 begin
277 Sn-1;
278 Sn;
279 end;
280 end;
281 end:
282 end
283 #+end_src
285 It is not immediately apparent that this sequencing can be expressed in a
286 purely applicative language. We can, however, take advantage of the implicit
287 sequencing of applicative order evaluation. Thus, for example, we may write a
288 two-statement sequence as follows:
290 #+begin_src clojure
291 ((fn[dummy] S2) S1)
292 #+end_src
294 where =dummy= is an identifier not used in S2. From this it is
295 manifest that the value of S1 is ignored, and so is useful only for
296 side effects. (Note that we did not claim that S1 is expressed in a
297 purely applicative language, but only that the sequencing can be so
298 expressed.) From now on we will use the form =(BLOCK S1 S2)= as an
299 abbreviation for this expression, and =(BLOCK S1 S2...Sn-1 Sn)= as an
300 abbreviation for
302 #+begin_src algol
303 (BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...)))
304 #+end_src
306 ** 2.2. The G0 TO Statement
308 A more general imperative structure is the compound statement with
309 labels and G0 T0s. Consider the following code fragment due to
310 Jacopini, taken from Knuth: [Knuth 74]
311 #+begin_src algol
312 begin
313 L1: if B1 then go to L2; S1;
314 if B2 then go to L2; S2;
315 go to L1;
316 L2: S3;
317 #+end_src
319 It is perhaps surprising that this piece of code can be /syntactically/
320 transformed into a purely applicative style. For example, in SCHEME we
321 could write:
323 #+begin_src clojure
324 (in-ns 'categorical.imperative)
325 (let
326 [L1 (fn[]
327 (if B1 (L2) (do S1
328 (if B2 (L2) (do S2 (L1))))))
329 L2 (fn[] S3)]
330 (L1))
331 #+end_src
333 As with the D0 loop, this transformation depends critically on SCHEME's
334 treatment of tail-recursion and on lexical scoping of variables. The labels
335 are names of functions of no arguments. In order to ‘go to" the labeled code,
336 we merely call the function named by that label.
338 ** 2.3. Simple Assignment
339 Of course, all this sequencing of statements is useless unless the
340 statements have side effects. An important side effect is assignment. For
341 example, one often uses assignment to place intermediate results in a named
342 location (i.e. a variable) so that they may be used more than once later
343 without recomputing them:
345 #+begin_src algol
346 begin
347 real a2, sqrtdisc;
348 a2 := 2*a;
349 sqrtdisc := sqrt(b^2 - 4*a*c);
350 root1 := (- b + sqrtdisc) / a2;
351 root2 := (- b - sqrtdisc) / a2;
352 print(root1);
353 print(root2);
354 print(root1 + root2);
355 end
356 #+end_src
358 It is well known that such naming of intermediate results may be accomplished
359 by calling a function and binding the formal parameter variables to the
360 results:
362 #+begin_src clojure
363 (fn [a2 sqrtdisc]
364 ((fn[root1 root2]
365 (do (println root1)
366 (println root2)
367 (println (+ root1 root2))))
368 (/ (+ (- b) sqrtdisc) a2)
369 (/ (- (- b) sqrtdisc) a2))
371 (* 2 a)
372 (sqrt (- (* b b) (* 4 a c))))
373 #+end_src
374 This technique can be extended to handle all simple variable assignments which
375 appear as statements in blocks, even if arbitrary G0 T0 statements also appear
376 in such blocks. {Note Mccarthywins}
378 For example, here is a program which uses G0 TO statements in the form
379 presented before; it determines the parity of a non-negative integer by
380 counting it down until it reaches zero.
382 #+begin_src algol
383 begin
384 L1: if a = 0 then begin parity := 0; go to L2; end;
385 a := a - 1;
386 if a = 0 then begin parity := 1; go to L2; end;
387 a := a - 1;
388 go to L1;
389 L2: print(parity);
390 #+end_src
392 This can be expressed in SCHEME:
394 #+begin_src clojure
395 (let
396 [L1 (fn [a parity]
397 (if (zero? a) (L2 a 0)
398 (L3 (dec a) parity)))
399 L3 (fn [a parity]
400 (if (zero? a) (L2 a 1)
401 (L1 (dec a) parity)))
402 L2 (fn [a parity]
403 (println parity))]
404 (L1 a parity))
405 #+end_src
407 The trick is to pass the set of variables which may be altered as arguments to
408 the label functions. {Note Flowgraph} It may be necessary to introduce new
409 labels (such as L3) so that an assignment may be transformed into the binding
410 for a function call. At worst, one may need as many labels as there are
411 statements (not counting the eliminated assignment and GO TO statements).
413 ** Compound Expressions '
414 At this point we are almost in a position to model the most general
415 form of compound statement. In LISP, this is called the 'PROG feature". In
416 addition to statement sequencing and G0 T0 statements, one can return a /value/
417 from a PROG by using the RETURN statement.
419 Let us first consider the simplest compound statement, which in SCHEME
420 we call BLOCK. Recall that
421 =(BLOCK s1 sz)= is defined to be =((lambda (dummy) s2) s1)=
423 Notice that this not only performs Sl before S2, but also returns the value of
424 S2. Furthermore, we defined =(BLOCK S1 S2 ... Sn)= so that it returns the value
425 of =Sn=. Thus BLOCK may be used as a compound expression, and models a LISP
426 PROGN, which is a PROG with no G0 T0 statements and an implicit RETURN of the
427 last ``statement'' (really an expression).
429 Host LISP compilers compile D0 expressions by macro-expansion. We have
430 already seen one way to do this in SCHEME using only variable binding. A more
431 common technique is to expand the D0 into a PROG, using variable assignments
432 instead of bindings. Thus the iterative factorial program:
434 #+begin_src clojure
435 (oarxnz FACT .
436 (LAMaoA (n) .
437 (D0 ((M N (- H 1))
438 (Ans 1 (* M Ans)))
439 ((- H 0) A"$))))
440 #+end_src
442 would expand into:
444 #+begin_src clojure
445 (DEFINE FACT
446 . (LAMeoA (M)
447 (PRO6 (M Ans)
448 (sszro M n
449 Ans 1) ~
450 LP (tr (- M 0) (RETURN Ans))
451 (ssero M (- n 1)
452 Ans (' M Ans))
453 (60 LP))))
454 #+end_src
456 where SSETQ is a simultaneous multiple assignment operator. (SSETQ is not a
457 SCHEME (or LISP) primitive. It can be defined in terms of a single assignment
458 operator, but we are more interested here in RETURN than in simultaneous
459 assignment. The SSETQ's will all be removed anyway and modelled by lambda
460 binding.) We can apply the same technique we used before to eliminate G0 T0
461 statements and assignments from compound statements:
463 #+begin_src clojure
464 (DEFINE FACT
465 (LAHBOA (I)
466 (LABELS ((L1 (LAManA (M Ans)
467 (LP n 1)))
468 (LP (LAMaoA (M Ans)
469 (IF (- M o) (nztunn Ans)
470 (£2 H An$))))
471 (L2 (LAMaoA (M An )
472 (LP (- " 1) (' H flN$)))))
473 (L1 NIL NlL))))
474 #+end_src clojure
476 We still haven't done anything about RETURN. Let's see...
477 - ==> the value of (FACT 0) is the value of (Ll NIL NIL)
478 - ==> which is the value of (LP 0 1)
479 - ==> which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1))
480 - ==> which is the value of (RETURN 1)
482 Notice that if RETURN were the /identity
483 function/ (LAMBDA (X) X), we would get the right answer. This is in fact a
484 general truth: if we Just replace a call to RETURN with its argument, then
485 our old transformation on compound statements extends to general compound
486 expressions, i.e. PROG.
488 * Continuations
489 Up to now we have thought of SCHEME's LAMBDA expressions as functions,
490 and of a combination such as =(G (F X Y))= as meaning ``apply the function F to
491 the values of X and Y, and return a value so that the function G can be
492 applied and return a value ...'' But notice that we have seldom used LAMBDA
493 expressions as functions. Rather, we have used them as control structures and
494 environment modifiers. For example, consider the expression:
495 =(BLOCK (PRINT 3) (PRINT 4))=
497 This is defined to be an abbreviation for:
498 =((LAMBDA (DUMMY) (PRINT 4)) (PRINT 3))=
500 We do not care about the value of this BLOCK expression; it follows that we
501 do not care about the value of the =(LAMBDA (DUMMY) ...)=. We are not using
502 LAMBDA as a function at all.
504 It is possible to write useful programs in terms of LAHBDA expressions
505 in which we never care about the value of /any/ lambda expression. We have
506 already demonstrated how one could represent any "FORTRAN" program in these
507 terms: all one needs is PROG (with G0 and SETQ), and PRINT to get the answers
508 out. The ultimate generalization of this imperative programing style is
509 /continuation-passing/. (Note Churchwins} .
511 ** Continuation-Passing Recursion
512 Consider the following alternative definition of FACT. It has an extra
513 argument, the continuation, which is a function to call with the answer, when
514 we have it, rather than return a value
516 #+begin_src algol.
517 procedure Inc!(n, c); value n, c;
518 integer n: procedure c(integer value);
519 if n-=0 then c(l) else
520 begin
521 procedure l(!mp(d) value a: integer a;
522 c(mm);
523 Iacl(n-1, romp):
524 end;
525 #+end_src
527 #+begin_src clojure
528 (in-ns 'categorical.imperative)
529 (defn fact-cps[n k]
530 (if (zero? n) (k 1)
531 (recur (dec n) (fn[a] (k (* n a))))))
532 #+end_src clojure
533 It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to
534 do something like this:
536 #+begin_src algol
537 begin
538 integer ann
539 procedure :emp(x); value 2:; integer x;
540 ans :1 x;
541 ]'act(3. temp);
542 comment Now the variable "am" has 6;
543 end;
544 #+end_src
546 Procedure =fact= does not return a value, nor does =temp=; we must use a side
547 effect to get the answer out.
549 =FACT= is somewhat easier to use in SCHEME. We can call it like an
550 ordinary function in SCHEME if we supply an identity function as the second
551 argument. For example, =(FACT 3 (LAMBDA (X) X))= returns 6. Alternatively, we
552 could write =(FACT 3 (LAHBDA (X) (PRINT X)))=; we do not care about the value
553 of this, but about what gets printed. A third way to use the value is to
554 write
555 =(FACT 3 (LAMBDA (x) (SQRT x)))=
556 instead of
557 =(SQRT (FACT 3 (LAMBDA (x) x)))=
559 In either of these cases we care about the value of the continuation given to
560 FACT. Thus we care about the value of FACT if and only if we care about the
561 value of its continuation!
563 We can redefine other functions to take continuations in the same way.
564 For example, suppose we had arithmetic primitives which took continuations; to
565 prevent confusion, call the version of "+" which takes a continuation '++",
566 etc. Instead of writing
567 =(- (+ B Z)(* 4 A C))=
568 we can write
569 #+begin_src clojure
570 (in-ns 'categorical.imperative)
571 (defn enable-continuation "Makes f take a continuation as an additional argument."[f]
572 (fn[& args] ((fn[k] (k (apply f (reverse (rest (reverse args)))))) (last args)) ))
573 (def +& (enable-continuation +))
574 (def *& (enable-continuation *))
575 (def -& (enable-continuation -))
578 (defn quadratic[a b c k]
579 (*& b b
580 (fn[x] (*& 4 a c
581 (fn[y]
582 (-& x y k))))))
583 #+end_src
585 where =k= is the continuation for the entire expression.
587 This is an obscure way to write an algebraic expression, and we would
588 not advise writing code this way in general, but continuation-passing brings
589 out certain important features of the computation:
590 - [1] The operations to be performed appear in the order in which they are
591 performed. In fact, they /must/ be performed in this
592 order. Continuation- passing removes the need for the rule about
593 left-to-right argument evaluation{Note Evalorder)
594 - [2] In the usual applicative expression there are two implicit
595 temporary values: those of =(* B B)= and =(* 4 A C)=. The first of
596 these values must be preserved over the computation of the second,
597 whereas the second is used as soon as it is produced. These facts
598 are /manifest/ in the appearance and use of the variable X and Y in
599 the continuation-passing version.
601 In short, the continuation-passing version specifies /exactly/ and
602 explicitly what steps are necessary to compute the value of the
603 expression. One can think of conventional functional application
604 for value as being an abbreviation for the more explicit
605 continuation-passing style. Alternatively, one can think of the
606 interpreter as supplying to each function an implicit default
607 continuation of one argument. This continuation will receive the
608 value of the function as its argument, and then carry on the
609 computation. In an interpreter this implicit continuation is
610 represented by the control stack mechanism for function returns.
611 Now consider what computational steps are implied by:
613 =(LAMBDA (A B C ...) (F X Y Z ...))= when we "apply" the LAMBDA
614 expression we have some values to apply it to; we let the names A,
615 B, C ... refer to these values. We then determine the values of X,
616 Y, Z ... and pass these values (along with "the buck",
617 i.e. control!) to the lambda expression F (F is either a lambda
618 expression or a name for one). Passing control to F is an
619 unconditional transfer. (Note Jrsthack) {Note Hewitthack) Note that
620 we want values from X, Y, Z, ... If these are simple expressions,
621 such as variables, constants, or LAMBDA expressions, the evaluation
622 process is trivial, in that no temporary storage is required. In
623 pure continuation-passing style, all evaluations are trivial: no
624 combination is nested within another, and therefore no ‘hidden
625 temporaries" are required. But if X is a combination, say (G P Q),
626 then we want to think of G as a function, because we want a value
627 from it, and we will need an implicit temporary place to keep the
628 result while evaluating Y and Z. (An interpreter usually keeps these
629 temporary places in the control stack!) On the other hand, we do not
630 necessarily need a value from F. This is what we mean by tail-
631 recursion: F is called tail-recursively, whereas G is not. A better
632 name for tail-recursion would be "tail-transfer", since no real
633 recursion is implied. This is why we have made such a fuss about
634 tail-recursion: it can be used for transfer of control without
635 making any commitment about whether the expression expected to
636 return a value. Thus it can be used to model statement-like control
637 structures. Put another way, tail—recursion does not require a
638 control stack as nested recursion does. In our models of iteration
639 and imperative style all the LAMBDA expressions used for control (to
640 simulate GO statements, for example) are called in tail-recursive
641 fashion.
643 ** Escape Expressions
644 Reynolds [Reynolds 72] defines the construction
645 = escape x in r =
647 to evaluate the expression $r$ in an environment such that the variable $x$ is
648 bound to an escape function. If the escape function is never applied, then
649 the value of the escape expression is the value of $r$. If the escape function
650 is applied to an argument $a$, however, then evaluation of $r$ is aborted and the
651 escape expression returns $a$. {Note J-operator} (Reynolds points out that
652 this definition is not quite accurate, since the escape function may be called
653 even after the escape expression has returned a value; if this happens, it
654 “returns again"!)
656 As an example of the use of an escape expression, consider this
657 procedure to compute the harmonic mean of an array of numbers. If any of the
658 numbers is zero, we want the answer to be zero. We have a function hannaunl
659 which will sum the reciprocals of numbers in an array, or call an escape
660 function with zero if any of the numbers is zero. (The implementation shown
661 here is awkward because ALGOL requires that a function return its value by
662 assignment.)
663 #+begin_src algol
664 begin
665 real procedure Imrmsum(a, n. escfun)§ p
666 real array at integer n; real procedure esciun(real);
667 begin
668 real sum;
669 sum := 0;
670 for i :1 0 until n-l do
671 begin
672 if a[i]=0 then cscfun(0);
673 sum :1 sum ¢ I/a[i];
674 enm
675 harmsum SI sum;
676 end: .
677 real array b[0:99]:
678 print(escape x in I00/hm-m.mm(b, 100, x));
679 end
680 #+end_src
682 If harmsum exits normally, the number of elements is divided by the sum and
683 printed. Otherwise, zero is returned from the escape expression and printed
684 without the division ever occurring.
685 This program can be written in SCHEME using the built-in escape
686 operator =CATCH=:
688 #+begin_src clojure
689 (in-ns 'categorical.imperative)
690 (defn harmonic-sum[coll escape]
691 ((fn [i sum]
692 (cond (= i (count coll) ) sum
693 (zero? (nth coll i)) (escape 0)
694 :else (recur (inc i) (+ sum (/ 1 (nth coll i))))))
695 0 0))
697 #+end_src
699 This actually works, but elucidates very little about the nature of ESCAPE.
700 We can eliminate the use of CATCH by using continuation-passing. Let us do
701 for HARMSUM what we did earlier for FACT. Let it take an extra argument C,
702 which is called as a function on the result.
704 #+begin_src clojure
705 (in-ns 'categorical.imperative)
706 (defn harmonic-sum-escape[coll escape k]
707 ((fn[i sum]
708 (cond (= i (count coll)) (k sum)
709 (zero? (nth coll i)) (escape 0)
710 (recur (inc i) (+ sum (/ 1 (nth coll i))))))
711 0 0))
713 (let [B (range 0 100)
714 after-the-catch println]
715 (harmonic-sum-escape B after-the-catch (fn[y] (after-the-catch (/ 100 y)))))
717 #+end_src
719 Notice that if we use ESCFUN, then C does not get called. In this way the
720 division is avoided. This example shows how ESCFUN may be considered to be an
721 "alternate continuation".
723 ** Dynamic Variable Scoping
724 In this section we will consider the problem of dynamically scoped, or
725 "fluid", variables. These do not exist in ALGOL, but are typical of many LISP
726 implementations, ECL, and APL. He will see that fluid variables may be
727 modelled in more than one way, and that one of these is closely related to
728 continuation—pass1ng.
730 *** Free (Global) Variables
731 Consider the following program to compute square roots:
733 #+begin_src clojure
734 (defn sqrt[x tolerance]
735 (
736 (DEFINE soar
737 (LAHBDA (x EPSILON)
738 (Pace (ANS)
739 (stro ANS 1.0)
740 A (coup ((< (ADS (-s x (~s ANS ANS))) EPSILON)
741 (nzruau ANS))) '
742 (sero ANS (//s (+5 x (//s x ANS)) 2.0))
743 (60 A)))) .
744 This function takes two arguments: the radicand and the numerical tolerance
745 for the approximation. Now suppose we want to write a program QUAD to compute
746 solutions to a quadratic equation; p
747 (perms QUAD
748 (LAHDDA (A a c)
749 ((LAHBDA (A2 sonmsc) '
750 (LIST (/ (+ (- a) SQRTDISC) AZ)
751 (/ (- (- B) SORTOISC) AZ)))
752 (' 2 A)
753 - (SORT (- (9 D 2) (' 4 A C)) (tolerance>))))
754 #+end_src
755 It is not clear what to write for (tolerance). One alternative is to pick
756 some tolerance for use by QUAD and write it as a constant in the code. This
757 is undesirable because it makes QUAD inflexible and hard to change. _Another
758 is to make QUAD take an extra argument and pass it to SQRT:
759 (DEFINE QUAD
760 (LANODA (A 8 C EPSILON)
761 (soar ... EPSILON) ...))
762 This is undesirable because EPSILDN is not really part of the problem QUAD is
763 supposed to solve, and we don't want the user to have to provide it.
764 Furthermore, if QUAD were built into some larger function, and that into
765 another, all these functions would have to pass EPSILON down as an extra
766 argument. A third.possibi1ity would be to pass the SQRT function as an
767 argument to QUAD (don't laugh!), the theory being to bind EPSILON at the
768 appropriate level like this: A U‘ A
769 (QUAD 3 A 5 (LAMBDA (X) (SORT X <toIerance>)))
770 where we define QUAD as:
771 (DEFINE QUAD
772 (LAMBDA (A a c soar) ...))