dylan: categorical/imperative.org comparison

comparison categorical/imperative.org @ 2:b4de894a1e2e

initial import

author	Robert McIntyre <rlm@mit.edu>
date	Fri, 28 Oct 2011 00:03:05 -0700
parents
children

comparison

equal deleted inserted replaced

-:8d8278e09888
+:b4de894a1e2e
+#+TITLE: LAMBDA: The Ultimate Imperative
+#+AUTHOR: Guy Lewis Steele Jr. and Gerald Jay Sussman
+* Abstract
+We demonstrate how to model the following common programming constructs in
+terms of an applicative order language similar to LISP:
+- Simple Recursion
+- Iteration
+- Compound Statements and Expressions
+- GO TO and Assignment
+- Continuation—Passing
+- Escape Expressions
+- Fluid Variables
+- Call by Name, Call by Need, and Call by Reference
+The models require only (possibly self-referent) lambda application,
+conditionals, and (rarely) assignment. No complex data structures such as
+stacks are used. The models are transparent, involving only local syntactic
+transformations.
+Some of these models, such as those for GO TO and assignment, are already well
+known, and appear in the work of Landin, Reynolds, and others. The models for
+escape expressions, fluid variables, and call by need with side effects are
+new. This paper is partly tutorial in intent, gathering all the models
+together for purposes of context.
+This report describes research done at the Artificial Intelligence Laboratory
+of the Massachusetts Institute of Teehnology. Support for the laboratory's
+artificial intelligence research is provided in part by the Advanced Research
+Projects Agency of the Department of Defense under Office of Naval Research
+contract N000l4-75-C-0643.
+* Introduction
+We catalogue a number of common programming constructs. For each
+construct we examine "typical" usage in well-known programming languages, and
+then capture the essence of the semantics of the construct in terms of a
+common meta-language.
+The lambda calculus {Note Alonzowins} is often used as such a meta-
+language. Lambda calculus offers clean semantics, but it is clumsy because it
+was designed to be a minimal language rather than a convenient one. All
+lambda calculus "functions" must take exactly one "argument"; the only "data
+type" is lambda expressions; and the only "primitive operation‘ is variable‘
+substitution. While its utter simplicity makes lambda calculus ideal for
+logicians, it is too primitive for use by programmers. The meta-language we
+use is a programming language called SCHEME {Note Schemepaper) which is based
+on lambda calculus.
+SCHEME is a dialect of LISP. [McCarthy 62] It is an expression-
+oriented, applicative order, interpreter-based language which allows one to
+manipulate programs as data. It differs from most current dialects of LISP in
+that it closes all lambda expressions in the environment of their definition
+or declaration, rather than in the execution environment. {Note Closures}
+This preserves the substitution semantics of lambda calculus, and has the
+consequence that all variables are lexically scoped, as in ALGOL. [Naur 63]
+Another difference is that SCHEME is implemented in such a way that tail-
+recursions execute without net growth of the interpreter stack. {Note
+Schemenote} We have chosen to use LISP syntax rather than, say, ALGOL syntax
+because we want to treat programs as data for the purpose of describing
+transformations on the code. LISP supplies names for the parts of an
+executable expression and standard operators for constructing expressions and
+extracting their components. The use of LISP syntax makes the structure of
+such expressions manifest. We use ALGOL as an expository language, because it
+is familiar to many people, but ALGOL is not sufficiently powerful to express
+the necessary concepts; in particular, it does not allow functions to return
+functions as values. we are thus forced to use a dialect of LISP in many
+cases.
+We will consider various complex programming language constructs and
+show how to model them in terms of only a few simple ones. As far as possible
+we will use only three control constructs from SCHEME: LAMBDA expressions, as
+in LISP, which are Just functions with lexically scoped free variables;
+LABELS, which allows declaration of mutually recursive procedures (Note
+Labelsdef}; and IF, a primitive conditional expression. For more complex
+modelling we will introduce an assignment primitive (ASET).i We will freely
+assume the existence of other comon primitives, such as arithmetic functions.
+The constructs we will examine are divided into four broad classes.
+The first is sﬁnph?Lo0pl; this contains simple recursions and iterations, and
+an introduction to the notion of continuations. The second is hmponﬂivo
+Connrucls; this includes compound statements, G0 T0, and simple variable
+assignments. The third is continuations, which encompasses the distinction between statements and expressions, escape operators (such as Landin's J-
+operator [Landin 65] and Reynold's escape expression [Reynolds 72]). and fluid
+(dynamically bound) variables. The fourth is Parameter Passing Mechanisms, such
+as ALGOL call—by-name and FORTRAN call-by-location.
+Some of the models presented here are already well-known, particularly
+those for G0 T0 and assignment. [McCarthy 60] [Landin 65] [Reynolds 72]
+Those for escape operators, fluid variables, and call-by-need with side
+effects are new.
+** Simple Loops
+By /simple loops/ we mean constructs which enable programs to execute the
+same piece of code repeatedly in a controlled manner. Variables may be made
+to take on different values during each repetition, and the number of
+repetitions may depend on data given to the program.
+*** Simple Recursion
+One of the easiest ways to produce a looping control structure is to
+use a recursive function, one which calls itself to perform a subcomputation.
+For example, the familiar factorial function may be written recursively in
+ALGOL: '
+#+begin_src algol
+integer procedure fact(n) value n: integer n:
+fact := if n=0 then 1 else n*fact(n-1);
+#+end_src
+The invocation =fact(n)= computes the product of the integers from 1 to n using
+the identity n!=n(n-1)! (n>0). If $n$ is zero, 1 is returned; otherwise =fact=:
+calls itself recursively to compute $(n-1)!$ , then multiplies the result by $n$
+and returns it.
+This same function may be written in Clojure as follows:
+#+begin_src clojure
+(ns categorical.imperative)
+(defn fact[n]
+(if (= n 0) 1 (* n (fact (dec n))))
+)
+#+end_src
+#+results:
+: #'categorical.imperative/fact
+Clojure does not require an assignment to the ``variable'' fan: to return a value
+as ALGOL does. The IF primitive is the ALGOL if-then-else rendered in LISP
+syntax. Note that the arithmetic primitives are prefix operators in SCHEME.
+*** Iteration
+There are many other ways to compute factorial. One important way is
+through the use of /iteration/.
+A comon iterative construct is the DO loop. The most general form we
+have seen in any programming language is the MacLISP DO [Moon 74]. It permits
+the simultaneous initialization of any number of control variables and the
+simultaneous stepping of these variables by arbitrary functions at each
+iteration step. The loop is terminated by an arbitrary predicate, and an
+arbitrary value may be returned. The DO loop may have a body, a series of
+expressions executed for effect on each iteration. A version of the MacLISP
+DO construct has been adopted in SCHEME.
+The general form of a SCHEME DO is:
+#+begin_src nothing
+(DO ((<var1> (init1> <stepl>)
+((var2> <init2> <step2>)
+(<varn> <intn> (stepn>))
+(<pred> (value>)
+(optional body>)
+#+end_src
+The semantics of this are that the variables are bound and initialized to the
+values of the <initi> expressions, which must all be evaluated in the
+environment outside the D0; then the predicate <pred> is evaluated in the new
+environment, and if TRUE, the (value) is evaluated and returned. Otherwise
+the (optional body) is evaluated, then each of the steppers <stepi> is
+evaluated in the current environment, all the variables made to have the
+results as their values, the predicate evaluated again, and so on.
+Using D0 loops in both ALGOL and SCHEME, we may express FACT by means
+of iteration.
+#+begin_src algol
+integer procedure fact(n); value n; integer n:
+begin
+integer m, ans;
+ans := 1;
+for m := n step -l until 0 do ans := m*ans;
+fact := ans;
+end;
+#+end_src
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn fact-do[n]
+)
+#+end_src
+Note that the SCHEME D0 loop in FACT has no body -- the stepping functions do
+all the work. The ALGOL DO loop has an assignment in its body; because an
+ALGOL DO loop can step only one variable, we need the assignment to step the
+the variable "manually'.
+In reality the SCHEME DO construct is not a primitive; it is a macro
+which expands into a function which performs the iteration by tail—recursion.
+Consider the following definition of FACT in SCHEME. Although it appears to
+be recursive, since it "calls itself", it is entirely equivalent to the DO
+loop given above, for it is the code that the DO macro expands into! It
+captures the essence of our intuitive notion of iteration, because execution
+of this program will not produce internal structures (e.g. stacks or variable
+bindings) which increase in size with the number of iteration steps.
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn fact-do-expand[n]
+(let [fact1
+	(fn[m ans]
+	  (if (zero? m) ans
+	      (recur (dec m) (* m ans))))]
+(fact1 n 1)))
+#+end_src
+From this we can infer a general way to express iterations in SCHEME in
+a manner isomorphic to the HacLISP D0. The expansion of the general D0 loop
+#+begin_src nothing
+(DO ((<varl> <init1> <step1>)
+(<var2> (init2) <step2>)
+...
+(<varn> <initn> <stepn>))
+(<pred> <va1ue>)
+<body>)
+#+end_src
+is this:
+#+begin_src nothing
+(let [doloop
+(fn [dummy <var1> <var2> ... <varn>)
+(if <pred> <value>
+(recur <body> <step1> <step2> ... <stepn>)))]
+(doloop nil <init1> <init2> ... <initn>))
+#+end_src
+The identifiers =doloop= and =dummy= are chosen so as not to conflict with any
+other identifiers in the program.
+Note that, unlike most implementations of D0, there are no side effects
+in the steppings of the iteration variables. D0 loops are usually modelled
+using assignment statements. For example:
+#+begin_src nothing
+for r :1 0 step b until c do <statement>;
+#+end_src
+can be modelled as follows: [Naur 63]
+#+begin_src nothing
+begin
+x := a;
+L: if (x-c)*sign(n) > 0 then go to Endloop;
+<statement>;
+x := x+b;
+go to L:
+Endloop:
+end;
+#+end_src
+Later we will see how such assignment statements can in general be
+modelled without using side effects.
+* Imperative Programming
+Lambda calculus (and related languages, such as ``pure LISP'') is often
+used for modelling the applicative constructs of programming languages.
+However, they are generally thought of as inappropriate for modelling
+imperative constructs. In this section we show how imperative constructs may
+be modelled by applicative SCHEME constructs.
+** Compound Statements
+The simplest kind of imperative construct is the statement sequencer,
+for example the compound statement in ALGOL:
+#+begin_src algol
+begin
+S1;
+S2;
+end
+#+end_src
+This construct has two interesting properties:
+- (1) It performs statement S1 before S2, and so may be used for
+sequencing.
+- (2) S1 is useful only for its side effects. (In ALGOL, S2 must also
+be a statement, and so is also useful only for side effects, but
+other languages have compound expressions containing a statement
+followed by an expression.)
+The ALGOL compound statement may actually contain any number of statements,
+but such statements can be expressed as a series of nested two-statement
+compounds. That is:
+#+begin_src algol
+begin
+S1;
+S2;
+...
+Sn-1;
+Sn;
+end
+#+end_src
+is equivalent to:
+#+begin_src algol
+begin
+S1;
+begin
+S2;
+begin
+...
+begin
+Sn-1;
+Sn;
+end;
+end;
+end:
+end
+#+end_src
+It is not immediately apparent that this sequencing can be expressed in a
+purely applicative language. We can, however, take advantage of the implicit
+sequencing of applicative order evaluation. Thus, for example, we may write a
+two-statement sequence as follows:
+#+begin_src clojure
+((fn[dummy] S2) S1)
+#+end_src
+where =dummy= is an identifier not used in S2. From this it is
+manifest that the value of S1 is ignored, and so is useful only for
+side effects. (Note that we did not claim that S1 is expressed in a
+purely applicative language, but only that the sequencing can be so
+expressed.) From now on we will use the form =(BLOCK S1 S2)= as an
+abbreviation for this expression, and =(BLOCK S1 S2...Sn-1 Sn)= as an
+abbreviation for
+#+begin_src algol
+(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...)))
+#+end_src
+** 2.2. The G0 TO Statement
+A more general imperative structure is the compound statement with
+labels and G0 T0s. Consider the following code fragment due to
+Jacopini, taken from Knuth: [Knuth 74]
+#+begin_src algol
+begin
+L1: if B1 then go to L2; S1;
+if B2 then go to L2; S2;
+go to L1;
+L2: S3;
+#+end_src
+It is perhaps surprising that this piece of code can be /syntactically/
+transformed into a purely applicative style. For example, in SCHEME we
+could write:
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(let
+[L1 (fn[]
+	  (if B1 (L2) (do S1
+			  (if B2 (L2) (do S2 (L1))))))
+L2 (fn[] S3)]
+(L1))
+#+end_src
+As with the D0 loop, this transformation depends critically on SCHEME's
+treatment of tail-recursion and on lexical scoping of variables. The labels
+are names of functions of no arguments. In order to ‘go to" the labeled code,
+we merely call the function named by that label.
+** 2.3. Simple Assignment
+Of course, all this sequencing of statements is useless unless the
+statements have side effects. An important side effect is assignment. For
+example, one often uses assignment to place intermediate results in a named
+location (i.e. a variable) so that they may be used more than once later
+without recomputing them:
+#+begin_src algol
+begin
+real a2, sqrtdisc;
+a2 := 2*a;
+sqrtdisc := sqrt(b^2 - 4*a*c);
+root1 := (- b + sqrtdisc) / a2;
+root2 := (- b - sqrtdisc) / a2;
+print(root1);
+print(root2);
+print(root1 + root2);
+end
+#+end_src
+It is well known that such naming of intermediate results may be accomplished
+by calling a function and binding the formal parameter variables to the
+results:
+#+begin_src clojure
+(fn [a2 sqrtdisc]
+((fn[root1 root2]
+(do (println root1)
+	(println root2)
+	(println (+ root1 root2))))
+(/ (+ (- b) sqrtdisc) a2)
+(/ (- (- b) sqrtdisc) a2))
+(* 2 a)
+(sqrt (- (* b b) (* 4 a c))))
+#+end_src
+This technique can be extended to handle all simple variable assignments which
+appear as statements in blocks, even if arbitrary G0 T0 statements also appear
+in such blocks. {Note Mccarthywins}
+For example, here is a program which uses G0 TO statements in the form
+presented before; it determines the parity of a non-negative integer by
+counting it down until it reaches zero.
+#+begin_src algol
+begin
+L1: if a = 0 then begin parity := 0; go to L2; end;
+a := a - 1;
+if a = 0 then begin parity := 1; go to L2; end;
+a := a - 1;
+go to L1;
+L2: print(parity);
+#+end_src
+This can be expressed in SCHEME:
+#+begin_src clojure
+(let
+[L1 (fn [a parity]
+	  (if (zero? a) (L2 a 0)
+	      (L3 (dec a) parity)))
+L3 (fn [a parity]
+	  (if (zero? a) (L2 a 1)
+	      (L1 (dec a) parity)))
+L2 (fn [a parity]
+	  (println parity))]
+(L1 a parity))
+#+end_src
+The trick is to pass the set of variables which may be altered as arguments to
+the label functions. {Note Flowgraph} It may be necessary to introduce new
+labels (such as L3) so that an assignment may be transformed into the binding
+for a function call. At worst, one may need as many labels as there are
+statements (not counting the eliminated assignment and GO TO statements).
+** Compound Expressions '
+At this point we are almost in a position to model the most general
+form of compound statement. In LISP, this is called the 'PROG feature". In
+addition to statement sequencing and G0 T0 statements, one can return a /value/
+from a PROG by using the RETURN statement.
+Let us first consider the simplest compound statement, which in SCHEME
+we call BLOCK. Recall that
+=(BLOCK s1 sz)= is defined to be =((lambda (dummy) s2) s1)=
+Notice that this not only performs Sl before S2, but also returns the value of
+S2. Furthermore, we defined =(BLOCK S1 S2 ... Sn)= so that it returns the value
+of =Sn=. Thus BLOCK may be used as a compound expression, and models a LISP
+PROGN, which is a PROG with no G0 T0 statements and an implicit RETURN of the
+last ``statement'' (really an expression).
+Host LISP compilers compile D0 expressions by macro-expansion. We have
+already seen one way to do this in SCHEME using only variable binding. A more
+common technique is to expand the D0 into a PROG, using variable assignments
+instead of bindings. Thus the iterative factorial program:
+#+begin_src clojure
+(oarxnz FACT .
+(LAMaoA (n) .
+(D0 ((M N (- H 1))
+(Ans 1 (* M Ans)))
+((- H 0) A"$))))
+#+end_src
+would expand into:
+#+begin_src clojure
+(DEFINE FACT
+. (LAMeoA (M)
+(PRO6 (M Ans)
+(sszro M n
+Ans 1) ~
+LP (tr (- M 0) (RETURN Ans))
+(ssero M (- n 1)
+Ans (' M Ans))
+(60 LP))))
+#+end_src
+where SSETQ is a simultaneous multiple assignment operator. (SSETQ is not a
+SCHEME (or LISP) primitive. It can be defined in terms of a single assignment
+operator, but we are more interested here in RETURN than in simultaneous
+assignment. The SSETQ's will all be removed anyway and modelled by lambda
+binding.) We can apply the same technique we used before to eliminate G0 T0
+statements and assignments from compound statements:
+#+begin_src clojure
+(DEFINE FACT
+(LAHBOA (I)
+(LABELS ((L1 (LAManA (M Ans)
+(LP n 1)))
+(LP (LAMaoA (M Ans)
+(IF (- M o) (nztunn Ans)
+(£2 H An$))))
+(L2 (LAMaoA (M An )
+(LP (- " 1) (' H ﬂN$)))))
+(L1 NIL NlL))))
+#+end_src clojure
+We still haven't done anything about RETURN. Let's see...
+- ==> the value of (FACT 0) is the value of (Ll NIL NIL)
+- ==> which is the value of (LP 0 1)
+- ==> which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1))
+- ==> which is the value of (RETURN 1)
+Notice that if RETURN were the /identity
+function/ (LAMBDA (X) X), we would get the right answer. This is in fact a
+general truth: if we Just replace a call to RETURN with its argument, then
+our old transformation on compound statements extends to general compound
+expressions, i.e. PROG.
+* Continuations
+Up to now we have thought of SCHEME's LAMBDA expressions as functions,
+and of a combination such as =(G (F X Y))= as meaning ``apply the function F to
+the values of X and Y, and return a value so that the function G can be
+applied and return a value ...'' But notice that we have seldom used LAMBDA
+expressions as functions. Rather, we have used them as control structures and
+environment modifiers. For example, consider the expression:
+=(BLOCK (PRINT 3) (PRINT 4))=
+This is defined to be an abbreviation for:
+=((LAMBDA  (DUMMY) (PRINT 4)) (PRINT 3))=
+We do not care about the value of this BLOCK expression; it follows that we
+do not care about the value of the =(LAMBDA (DUMMY) ...)=. We are not using
+LAMBDA as a function at all.
+It is possible to write useful programs in terms of LAHBDA expressions
+in which we never care about the value of /any/ lambda expression. We have
+already demonstrated how one could represent any "FORTRAN" program in these
+terms: all one needs is PROG (with G0 and SETQ), and PRINT to get the answers
+out. The ultimate generalization of this imperative programing style is
+/continuation-passing/. (Note Churchwins} .
+** Continuation-Passing Recursion
+Consider the following alternative definition of FACT. It has an extra
+argument, the continuation, which is a function to call with the answer, when
+we have it, rather than return a value
+#+begin_src algol.
+procedure Inc!(n, c); value n, c;
+integer n: procedure c(integer value);
+if n-=0 then c(l) else
+begin
+procedure l(!mp(d) value a: integer a;
+c(mm);
+Iacl(n-1, romp):
+end;
+#+end_src
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn fact-cps[n k]
+(if (zero? n) (k 1)
+(recur (dec n) (fn[a] (k (* n a))))))
+#+end_src clojure
+It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to
+do something like this:
+#+begin_src algol
+begin
+integer ann
+procedure :emp(x); value 2:; integer x;
+ans :1 x;
+]'act(3. temp);
+comment Now the variable "am" has 6;
+end;
+#+end_src
+Procedure =fact= does not return a value, nor does =temp=; we must use a side
+effect to get the answer out.
+=FACT= is somewhat easier to use in SCHEME. We can call it like an
+ordinary function in SCHEME if we supply an identity function as the second
+argument. For example, =(FACT 3 (LAMBDA (X) X))= returns 6. Alternatively, we
+could write =(FACT 3 (LAHBDA (X) (PRINT X)))=; we do not care about the value
+of this, but about what gets printed. A third way to use the value is to
+write
+=(FACT 3 (LAMBDA (x) (SQRT x)))=
+instead of
+=(SQRT (FACT 3 (LAMBDA (x) x)))=
+In either of these cases we care about the value of the continuation given to
+FACT. Thus we care about the value of FACT if and only if we care about the
+value of its continuation!
+We can redefine other functions to take continuations in the same way.
+For example, suppose we had arithmetic primitives which took continuations; to
+prevent confusion, call the version of "+" which takes a continuation '++",
+etc. Instead of writing
+=(- (+ B Z)(* 4 A C))=
+we can write
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn enable-continuation "Makes f take a continuation as an additional argument."[f]
+(fn[& args] ((fn[k] (k (apply f (reverse (rest (reverse args)))))) (last args)) ))
+(def +& (enable-continuation +))
+(def *& (enable-continuation *))
+(def -& (enable-continuation -))
+(defn quadratic[a b c k]
+(*& b b
+(fn[x] (*& 4 a c
+	       (fn[y]
+		 (-& x y k))))))
+#+end_src
+where =k= is the continuation for the entire expression.
+This is an obscure way to write an algebraic expression, and we would
+not advise writing code this way in general, but continuation-passing brings
+out certain important features of the computation:
+- [1] The operations to be performed appear in the order in which they are
+performed. In fact, they /must/ be performed in this
+order. Continuation- passing removes the need for the rule about
+left-to-right argument evaluation{Note Evalorder)
+- [2] In the usual applicative expression there are two implicit
+temporary values: those of =(* B B)= and =(* 4 A C)=. The first of
+these values must be preserved over the computation of the second,
+whereas the second is used as soon as it is produced. These facts
+are /manifest/ in the appearance and use of the variable X and Y in
+the continuation-passing version.
+In short, the continuation-passing version specifies /exactly/ and
+explicitly what steps are necessary to compute the value of the
+expression.  One can think of conventional functional application
+for value as being an abbreviation for the more explicit
+continuation-passing style. Alternatively, one can think of the
+interpreter as supplying to each function an implicit default
+continuation of one argument. This continuation will receive the
+value of the function as its argument, and then carry on the
+computation. In an interpreter this implicit continuation is
+represented by the control stack mechanism for function returns.
+Now consider what computational steps are implied by:
+=(LAMBDA (A B C ...) (F X Y Z ...))= when we "apply" the LAMBDA
+expression we have some values to apply it to; we let the names A,
+B, C ... refer to these values. We then determine the values of X,
+Y, Z ... and pass these values (along with "the buck",
+i.e. control!) to the lambda expression F (F is either a lambda
+expression or a name for one).  Passing control to F is an
+unconditional transfer. (Note Jrsthack) {Note Hewitthack) Note that
+we want values from X, Y, Z, ... If these are simple expressions,
+such as variables, constants, or LAMBDA expressions, the evaluation
+process is trivial, in that no temporary storage is required. In
+pure continuation-passing style, all evaluations are trivial: no
+combination is nested within another, and therefore no ‘hidden
+temporaries" are required.  But if X is a combination, say (G P Q),
+then we want to think of G as a function, because we want a value
+from it, and we will need an implicit temporary place to keep the
+result while evaluating Y and Z. (An interpreter usually keeps these
+temporary places in the control stack!) On the other hand, we do not
+necessarily need a value from F. This is what we mean by tail-
+recursion: F is called tail-recursively, whereas G is not. A better
+name for tail-recursion would be "tail-transfer", since no real
+recursion is implied.  This is why we have made such a fuss about
+tail-recursion: it can be used for transfer of control without
+making any commitment about whether the expression expected to
+return a value. Thus it can be used to model statement-like control
+structures. Put another way, tail—recursion does not require a
+control stack as nested recursion does. In our models of iteration
+and imperative style all the LAMBDA expressions used for control (to
+simulate GO statements, for example) are called in tail-recursive
+fashion.
+** Escape Expressions
+Reynolds [Reynolds 72] defines the construction
+= escape x in r =
+to evaluate the expression $r$ in an environment such that the variable $x$ is
+bound to an escape function. If the escape function is never applied, then
+the value of the escape expression is the value of $r$. If the escape function
+is applied to an argument $a$, however, then evaluation of $r$ is aborted and the
+escape expression returns $a$. {Note J-operator} (Reynolds points out that
+this definition is not quite accurate, since the escape function may be called
+even after the escape expression has returned a value; if this happens, it
+“returns again"!)
+As an example of the use of an escape expression, consider this
+procedure to compute the harmonic mean of an array of numbers. If any of the
+numbers is zero, we want the answer to be zero. We have a function hannaunl
+which will sum the reciprocals of numbers in an array, or call an escape
+function with zero if any of the numbers is zero. (The implementation shown
+here is awkward because ALGOL requires that a function return its value by
+assignment.)
+#+begin_src algol
+begin
+real procedure Imrmsum(a, n. escfun)§ p
+real array at integer n; real procedure esciun(real);
+begin
+real sum;
+sum := 0;
+for i :1 0 until n-l do
+begin
+if a[i]=0 then cscfun(0);
+sum :1 sum ¢ I/a[i];
+enm
+harmsum SI sum;
+end: .
+real array b[0:99]:
+print(escape x in I00/hm-m.mm(b, 100, x));
+end
+#+end_src
+If harmsum exits normally, the number of elements is divided by the sum and
+printed. Otherwise, zero is returned from the escape expression and printed
+without the division ever occurring.
+This program can be written in SCHEME using the built-in escape
+operator =CATCH=:
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn harmonic-sum[coll escape]
+((fn [i sum]
+(cond (= i (count coll) ) sum
+	   (zero? (nth coll i)) (escape 0)
+	   :else (recur (inc i) (+ sum (/ 1 (nth coll i))))))
+0 0))
+#+end_src
+This actually works, but elucidates very little about the nature of ESCAPE.
+We can eliminate the use of CATCH by using continuation-passing. Let us do
+for HARMSUM what we did earlier for FACT. Let it take an extra argument C,
+which is called as a function on the result.
+#+begin_src clojure
+(in-ns 'categorical.imperative)
+(defn harmonic-sum-escape[coll escape k]
+((fn[i sum]
+(cond (= i (count coll)) (k sum)
+	  (zero? (nth coll i)) (escape 0)
+	  (recur (inc i) (+ sum (/ 1 (nth coll i))))))
+0 0))
+(let [B (range 0 100)
+after-the-catch println]
+(harmonic-sum-escape B after-the-catch (fn[y] (after-the-catch (/ 100 y)))))
+#+end_src
+Notice that if we use ESCFUN, then C does not get called. In this way the
+division is avoided. This example shows how ESCFUN may be considered to be an
+"alternate continuation".
+** Dynamic Variable Scoping
+In this section we will consider the problem of dynamically scoped, or
+"fluid", variables. These do not exist in ALGOL, but are typical of many LISP
+implementations, ECL, and APL. He will see that fluid variables may be
+modelled in more than one way, and that one of these is closely related to
+continuation—pass1ng.
+*** Free (Global) Variables
+Consider the following program to compute square roots:
+#+begin_src clojure
+(defn sqrt[x tolerance]
+(
+(DEFINE soar
+(LAHBDA (x EPSILON)
+(Pace (ANS)
+(stro ANS 1.0)
+A (coup ((< (ADS (-s x (~s ANS ANS))) EPSILON)
+(nzruau ANS))) '
+(sero ANS (//s (+5 x (//s x ANS)) 2.0))
+(60 A)))) .
+This function takes two arguments: the radicand and the numerical tolerance
+for the approximation. Now suppose we want to write a program QUAD to compute
+solutions to a quadratic equation; p
+(perms QUAD
+(LAHDDA (A a c)
+((LAHBDA (A2 sonmsc) '
+(LIST (/ (+ (- a) SQRTDISC) AZ)
+(/ (- (- B) SORTOISC) AZ)))
+(' 2 A)
+- (SORT (- (9 D 2) (' 4 A C)) (tolerance>))))
+#+end_src
+It is not clear what to write for (tolerance). One alternative is to pick
+some tolerance for use by QUAD and write it as a constant in the code. This
+is undesirable because it makes QUAD inflexible and hard to change. _Another
+is to make QUAD take an extra argument and pass it to SQRT:
+(DEFINE QUAD
+(LANODA (A 8 C EPSILON)
+(soar ... EPSILON) ...))
+This is undesirable because EPSILDN is not really part of the problem QUAD is
+supposed to solve, and we don't want the user to have to provide it.
+Furthermore, if QUAD were built into some larger function, and that into
+another, all these functions would have to pass EPSILON down as an extra
+argument. A third.possibi1ity would be to pass the SQRT function as an
+argument to QUAD (don't laugh!), the theory being to bind EPSILON at the
+appropriate level like this: A U‘ A
+(QUAD 3 A 5 (LAMBDA (X) (SORT X <toIerance>)))
+where we define QUAD as:
+(DEFINE QUAD
+(LAMBDA (A a c soar) ...))

Mercurial > dylan

comparison categorical/imperative.org @ 2:b4de894a1e2e