dylan: categorical/imperative.html comparison

comparison categorical/imperative.html @ 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
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml"
+lang="en" xml:lang="en">
+<head>
+<title>LAMBDA: The Ultimate Imperative</title>
+<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
+<meta name="generator" content="Org-mode"/>
+<meta name="generated" content="2011-07-15 02:49:04 EDT"/>
+<meta name="author" content="Guy Lewis Steele Jr. and Gerald Jay Sussman"/>
+<meta name="description" content=""/>
+<meta name="keywords" content=""/>
+<style type="text/css">
+<!--/*--><![CDATA[/*><!--*/
+html { font-family: Times, serif; font-size: 12pt; }
+.title  { text-align: center; }
+.todo   { color: red; }
+.done   { color: green; }
+.tag    { background-color: #add8e6; font-weight:normal }
+.target { }
+.timestamp { color: #bebebe; }
+.timestamp-kwd { color: #5f9ea0; }
+.right  {margin-left:auto; margin-right:0px;  text-align:right;}
+.left   {margin-left:0px;  margin-right:auto; text-align:left;}
+.center {margin-left:auto; margin-right:auto; text-align:center;}
+p.verse { margin-left: 3% }
+pre {
+	border: 1pt solid #AEBDCC;
+	background-color: #F3F5F7;
+	padding: 5pt;
+	font-family: courier, monospace;
+font-size: 90%;
+overflow:auto;
+}
+table { border-collapse: collapse; }
+td, th { vertical-align: top;  }
+th.right  { text-align:center;  }
+th.left   { text-align:center;   }
+th.center { text-align:center; }
+td.right  { text-align:right;  }
+td.left   { text-align:left;   }
+td.center { text-align:center; }
+dt { font-weight: bold; }
+div.figure { padding: 0.5em; }
+div.figure p { text-align: center; }
+textarea { overflow-x: auto; }
+.linenr { font-size:smaller }
+.code-highlighted {background-color:#ffff00;}
+.org-info-js_info-navigation { border-style:none; }
+#org-info-js_console-label { font-size:10px; font-weight:bold;
+white-space:nowrap; }
+.org-info-js_search-highlight {background-color:#ffff00; color:#000000;
+font-weight:bold; }
+/*]]>*/-->
+</style>
+<script type="text/javascript">
+<!--/*--><![CDATA[/*><!--*/
+function CodeHighlightOn(elem, id)
+{
+var target = document.getElementById(id);
+if(null != target) {
+elem.cacheClassElem = elem.className;
+elem.cacheClassTarget = target.className;
+target.className = "code-highlighted";
+elem.className   = "code-highlighted";
+}
+}
+function CodeHighlightOff(elem, id)
+{
+var target = document.getElementById(id);
+if(elem.cacheClassElem)
+elem.className = elem.cacheClassElem;
+if(elem.cacheClassTarget)
+target.className = elem.cacheClassTarget;
+}
+/*]]>*///-->
+</script>
+<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js">
+<!--/*--><![CDATA[/*><!--*/
+MathJax.Hub.Config({
+// Only one of the two following lines, depending on user settings
+// First allows browser-native MathML display, second forces HTML/CSS
+//  config: ["MMLorHTML.js"], jax: ["input/TeX"],
+jax: ["input/TeX", "output/HTML-CSS"],
+extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",
+"TeX/noUndefined.js"],
+tex2jax: {
+inlineMath: [ ["\\(","\\)"] ],
+displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],
+skipTags: ["script","noscript","style","textarea","pre","code"],
+ignoreClass: "tex2jax_ignore",
+processEscapes: false,
+processEnvironments: true,
+preview: "TeX"
+},
+showProcessingMessages: true,
+displayAlign: "center",
+displayIndent: "2em",
+"HTML-CSS": {
+scale: 100,
+availableFonts: ["STIX","TeX"],
+preferredFont: "TeX",
+webFont: "TeX",
+imageFont: "TeX",
+showMathMenu: true,
+},
+MMLorHTML: {
+prefer: {
+MSIE:    "MML",
+Firefox: "MML",
+Opera:   "HTML",
+other:   "HTML"
+}
+}
+});
+/*]]>*///-->
+</script>
+</head>
+<body>
+<div id="content">
+<div id="table-of-contents">
+<h2>Table of Contents</h2>
+<div id="text-table-of-contents">
+<ul>
+<li><a href="#sec-1">1 Abstract </a></li>
+<li><a href="#sec-2">2 Introduction </a>
+<ul>
+<li><a href="#sec-2-1">2.1 Simple Loops </a>
+<ul>
+<li><a href="#sec-2-1-1">2.1.1 Simple Recursion </a></li>
+<li><a href="#sec-2-1-2">2.1.2 Iteration </a></li>
+</ul></li>
+</ul>
+</li>
+<li><a href="#sec-3">3 Imperative Programming </a>
+<ul>
+<li><a href="#sec-3-1">3.1 Compound Statements </a></li>
+<li><a href="#sec-3-2">3.2 2.2. The G0 TO Statement </a></li>
+<li><a href="#sec-3-3">3.3 2.3. Simple Assignment </a></li>
+<li><a href="#sec-3-4">3.4 Compound Expressions ' </a></li>
+</ul>
+</li>
+<li><a href="#sec-4">4 Continuations </a>
+<ul>
+<li><a href="#sec-4-1">4.1 Continuation-Passing Recursion </a></li>
+<li><a href="#sec-4-2">4.2 Escape Expressions </a></li>
+</ul>
+</li>
+</ul>
+</div>
+</div>
+<div id="outline-container-1" class="outline-2">
+<h2 id="sec-1"><span class="section-number-2">1</span> Abstract </h2>
+<div class="outline-text-2" id="text-1">
+<p>
+We demonstrate how to model the following common programming constructs in
+terms of an applicative order language similar to LISP:
+</p><ul>
+<li>Simple Recursion
+</li>
+<li>Iteration
+</li>
+<li>Compound Statements and Expressions
+</li>
+<li>GO TO and Assignment
+</li>
+<li>Continuation—Passing
+</li>
+<li>Escape Expressions
+</li>
+<li>Fluid Variables
+</li>
+<li>Call by Name, Call by Need, and Call by Reference
+</li>
+</ul>
+<p>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.
+</p>
+</div>
+</div>
+<div id="outline-container-2" class="outline-2">
+<h2 id="sec-2"><span class="section-number-2">2</span> Introduction </h2>
+<div class="outline-text-2" id="text-2">
+<p>
+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.
+</p>
+</div>
+<div id="outline-container-2-1" class="outline-3">
+<h3 id="sec-2-1"><span class="section-number-3">2.1</span> Simple Loops </h3>
+<div class="outline-text-3" id="text-2-1">
+<p>By <i>simple loops</i> 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.
+</p>
+</div>
+<div id="outline-container-2-1-1" class="outline-4">
+<h4 id="sec-2-1-1"><span class="section-number-4">2.1.1</span> Simple Recursion </h4>
+<div class="outline-text-4" id="text-2-1-1">
+<p>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: '
+</p>
+<pre class="src src-algol">integer procedure fact(n) value n: integer n:
+fact := if n=0 then 1 else n*fact(n-1);
+</pre>
+<p>
+The invocation <code>fact(n)</code> computes the product of the integers from 1 to n using
+the identity n!=n(n-1)! (n&gt;0). If \(n\) is zero, 1 is returned; otherwise <code>fact</code>:
+calls itself recursively to compute \((n-1)!\) , then multiplies the result by \(n\)
+and returns it.
+</p>
+<p>
+This same function may be written in Clojure as follows:
+</p>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.imperative)
+(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact</span>[n]
+(<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))))
+)
+</pre>
+<p>
+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.
+</p>
+</div>
+</div>
+<div id="outline-container-2-1-2" class="outline-4">
+<h4 id="sec-2-1-2"><span class="section-number-4">2.1.2</span> Iteration </h4>
+<div class="outline-text-4" id="text-2-1-2">
+<p>There are many other ways to compute factorial. One important way is
+through the use of <i>iteration</i>.
+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.
+</p>
+<p>
+The general form of a SCHEME DO is:
+</p>
+<pre class="src src-nothing">(DO ((&lt;var1&gt; (init1&gt; &lt;stepl&gt;)
+((var2&gt; &lt;init2&gt; &lt;step2&gt;)
+(&lt;varn&gt; &lt;intn&gt; (stepn&gt;))
+(&lt;pred&gt; (value&gt;)
+(optional body&gt;)
+</pre>
+<p>
+The semantics of this are that the variables are bound and initialized to the
+values of the &lt;initi&gt; expressions, which must all be evaluated in the
+environment outside the D0; then the predicate &lt;pred&gt; 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 &lt;stepi&gt; 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.
+</p>
+<pre class="src 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;
+</pre>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
+(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do</span>[n]
+)
+</pre>
+<p>
+Note that the SCHEME D0 loop in FACT has no body &ndash; 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.
+</p>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
+(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-do-expand</span>[n]
+(<span style="color: #f0dfaf; font-weight: bold;">let</span> [fact1
+(<span style="color: #8cd0d3;">fn</span>[m ans]
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? m) ans
+(<span style="color: #f0dfaf; font-weight: bold;">recur</span> (<span style="color: #8cd0d3;">dec</span> m) (<span style="color: #8cd0d3;">*</span> m ans))))]
+(fact1 n 1)))
+</pre>
+<p>
+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
+</p>
+<pre class="src src-nothing">(DO ((&lt;varl&gt; &lt;init1&gt; &lt;step1&gt;)
+(&lt;var2&gt; (init2) &lt;step2&gt;)
+...
+(&lt;varn&gt; &lt;initn&gt; &lt;stepn&gt;))
+(&lt;pred&gt; &lt;va1ue&gt;)
+&lt;body&gt;)
+</pre>
+<p>
+is this:
+</p>
+<pre class="src src-nothing">(let [doloop
+(fn [dummy &lt;var1&gt; &lt;var2&gt; ... &lt;varn&gt;)
+(if &lt;pred&gt; &lt;value&gt;
+(recur &lt;body&gt; &lt;step1&gt; &lt;step2&gt; ... &lt;stepn&gt;)))]
+(doloop nil &lt;init1&gt; &lt;init2&gt; ... &lt;initn&gt;))
+</pre>
+<p>
+The identifiers <code>doloop</code> and <code>dummy</code> 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:
+</p>
+<pre class="src src-nothing">for r :1 0 step b until c do &lt;statement&gt;;
+</pre>
+<p>
+can be modelled as follows: [Naur 63]
+</p>
+<pre class="src src-nothing">begin
+x := a;
+L: if (x-c)*sign(n) &gt; 0 then go to Endloop;
+&lt;statement&gt;;
+x := x+b;
+go to L:
+Endloop:
+end;
+</pre>
+<p>
+Later we will see how such assignment statements can in general be
+modelled without using side effects.
+</p>
+</div>
+</div>
+</div>
+</div>
+<div id="outline-container-3" class="outline-2">
+<h2 id="sec-3"><span class="section-number-2">3</span> Imperative Programming </h2>
+<div class="outline-text-2" id="text-3">
+<p>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.
+</p>
+</div>
+<div id="outline-container-3-1" class="outline-3">
+<h3 id="sec-3-1"><span class="section-number-3">3.1</span> Compound Statements </h3>
+<div class="outline-text-3" id="text-3-1">
+<p>The simplest kind of imperative construct is the statement sequencer,
+for example the compound statement in ALGOL:
+</p>
+<pre class="src src-algol">begin
+S1;
+S2;
+end
+</pre>
+<p>
+This construct has two interesting properties:
+</p><ul>
+<li>(1) It performs statement S1 before S2, and so may be used for
+sequencing.
+</li>
+<li>(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.)
+</li>
+</ul>
+<p>
+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:
+</p>
+<pre class="src src-algol">begin
+S1;
+S2;
+...
+Sn-1;
+Sn;
+end
+</pre>
+<p>
+is equivalent to:
+</p>
+<pre class="src src-algol">begin
+S1;
+begin
+S2;
+begin
+...
+begin
+Sn-1;
+Sn;
+end;
+end;
+end:
+end
+</pre>
+<p>
+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:
+</p>
+<pre class="src src-clojure">((<span style="color: #8cd0d3;">fn</span>[dummy] S2) S1)
+</pre>
+<p>
+where <code>dummy</code> 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 <code>(BLOCK S1 S2)</code> as an
+abbreviation for this expression, and <code>(BLOCK S1 S2...Sn-1 Sn)</code> as an
+abbreviation for
+</p>
+<pre class="src src-algol">(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...)))
+</pre>
+</div>
+</div>
+<div id="outline-container-3-2" class="outline-3">
+<h3 id="sec-3-2"><span class="section-number-3">3.2</span> 2.2. The G0 TO Statement </h3>
+<div class="outline-text-3" id="text-3-2">
+<p>
+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]
+</p>
+<pre class="src src-algol">begin
+L1: if B1 then go to L2; S1;
+if B2 then go to L2; S2;
+go to L1;
+L2: S3;
+</pre>
+<p>
+It is perhaps surprising that this piece of code can be <i>syntactically</i>
+transformed into a purely applicative style. For example, in SCHEME we
+could write:
+</p>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
+(<span style="color: #f0dfaf; font-weight: bold;">let</span>
+[L1 (<span style="color: #8cd0d3;">fn</span>[]
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> B1 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S1
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> B2 (L2) (<span style="color: #f0dfaf; font-weight: bold;">do</span> S2 (L1))))))
+L2 (<span style="color: #8cd0d3;">fn</span>[] S3)]
+(L1))
+</pre>
+<p>
+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.
+</p>
+</div>
+</div>
+<div id="outline-container-3-3" class="outline-3">
+<h3 id="sec-3-3"><span class="section-number-3">3.3</span> 2.3. Simple Assignment </h3>
+<div class="outline-text-3" id="text-3-3">
+<p>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:
+</p>
+<pre class="src 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
+</pre>
+<p>
+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:
+</p>
+<pre class="src src-clojure">(<span style="color: #8cd0d3;">fn</span> [a2 sqrtdisc]
+((<span style="color: #8cd0d3;">fn</span>[root1 root2]
+(<span style="color: #f0dfaf; font-weight: bold;">do</span> (<span style="color: #8cd0d3;">println</span> root1)
+(<span style="color: #8cd0d3;">println</span> root2)
+(<span style="color: #8cd0d3;">println</span> (<span style="color: #8cd0d3;">+</span> root1 root2))))
+(<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">+</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2)
+(<span style="color: #8cd0d3;">/</span> (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">-</span> b) sqrtdisc) a2))
+(<span style="color: #8cd0d3;">*</span> 2 a)
+(sqrt (<span style="color: #8cd0d3;">-</span> (<span style="color: #8cd0d3;">*</span> b b) (<span style="color: #8cd0d3;">*</span> 4 a c))))
+</pre>
+<p>
+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}
+</p>
+<p>
+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.
+</p>
+<pre class="src 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);
+</pre>
+<p>
+This can be expressed in SCHEME:
+</p>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">let</span>
+[L1 (<span style="color: #8cd0d3;">fn</span> [a parity]
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 0)
+(L3 (<span style="color: #8cd0d3;">dec</span> a) parity)))
+L3 (<span style="color: #8cd0d3;">fn</span> [a parity]
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? a) (L2 a 1)
+(L1 (<span style="color: #8cd0d3;">dec</span> a) parity)))
+L2 (<span style="color: #8cd0d3;">fn</span> [a parity]
+(<span style="color: #8cd0d3;">println</span> parity))]
+(L1 a parity))
+</pre>
+<p>
+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).
+</p>
+</div>
+</div>
+<div id="outline-container-3-4" class="outline-3">
+<h3 id="sec-3-4"><span class="section-number-3">3.4</span> Compound Expressions ' </h3>
+<div class="outline-text-3" id="text-3-4">
+<p>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 <i>value</i>
+from a PROG by using the RETURN statement.
+</p>
+<p>
+Let us first consider the simplest compound statement, which in SCHEME
+we call BLOCK. Recall that
+<code>(BLOCK s1 sz)</code> is defined to be <code>((lambda (dummy) s2) s1)</code>
+</p>
+<p>
+Notice that this not only performs Sl before S2, but also returns the value of
+S2. Furthermore, we defined <code>(BLOCK S1 S2 ... Sn)</code> so that it returns the value
+of <code>Sn</code>. 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).
+</p>
+<p>
+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:
+</p>
+<pre class="src src-clojure">(oarxnz FACT .
+(LAMaoA (n) .
+(D0 ((M N (<span style="color: #8cd0d3;">-</span> H 1))
+(Ans 1 (<span style="color: #8cd0d3;">*</span> M Ans)))
+((<span style="color: #8cd0d3;">-</span> H 0) A<span style="color: #cc9393;">"$))))</span>
+</pre>
+<p>
+would expand into:
+</p>
+<pre class="src src-clojure">(DEFINE FACT
+. (LAMeoA (M)
+(PRO6 (M Ans)
+(sszro M n
+Ans 1) ~
+LP (tr (<span style="color: #8cd0d3;">-</span> M 0) (RETURN Ans))
+(ssero M (<span style="color: #8cd0d3;">-</span> n 1)
+Ans (' M Ans))
+(60 LP))))
+</pre>
+<p>
+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:
+</p>
+<pre class="src src-clojure">(DEFINE FACT
+(LAHBOA (I)
+(LABELS ((L1 (LAManA (M Ans)
+(LP n 1)))
+(LP (LAMaoA (M Ans)
+(IF (<span style="color: #8cd0d3;">-</span> M o) (nztunn Ans)
+(&#163;2 H An$))))
+(L2 (LAMaoA (M An )
+(LP (<span style="color: #8cd0d3;">-</span> <span style="color: #cc9393;">" 1) (' H &#64258;N$)))))</span>
+<span style="color: #e37170; background-color: #332323;">(</span><span style="color: #cc9393;">L1 NIL NlL))))</span>
+</pre>
+<p>
+clojure
+</p>
+<p>
+We still haven't done anything about RETURN. Let's see&hellip;
+</p><ul>
+<li>==&gt; the value of (FACT 0) is the value of (Ll NIL NIL)
+</li>
+<li>==&gt; which is the value of (LP 0 1)
+</li>
+<li>==&gt; which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1))
+</li>
+<li>==&gt; which is the value of (RETURN 1)
+</li>
+</ul>
+<p>
+Notice that if RETURN were the <i>identity function</i> (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.
+</p>
+</div>
+</div>
+</div>
+<div id="outline-container-4" class="outline-2">
+<h2 id="sec-4"><span class="section-number-2">4</span> Continuations </h2>
+<div class="outline-text-2" id="text-4">
+<p>Up to now we have thought of SCHEME's LAMBDA expressions as functions,
+and of a combination such as <code>(G (F X Y))</code> 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 &hellip;'' 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:
+<code>(BLOCK (PRINT 3) (PRINT 4))</code>
+</p>
+<p>
+This is defined to be an abbreviation for:
+<code>((LAMBDA  (DUMMY) (PRINT 4)) (PRINT 3))</code>
+</p>
+<p>
+We do not care about the value of this BLOCK expression; it follows that we
+do not care about the value of the <code>(LAMBDA (DUMMY) ...)</code>. We are not using
+LAMBDA as a function at all.
+</p>
+<p>
+It is possible to write useful programs in terms of LAHBDA expressions
+in which we never care about the value of <i>any</i> 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
+<i>continuation-passing</i>. (Note Churchwins} .
+</p>
+</div>
+<div id="outline-container-4-1" class="outline-3">
+<h3 id="sec-4-1"><span class="section-number-3">4.1</span> Continuation-Passing Recursion </h3>
+<div class="outline-text-3" id="text-4-1">
+<p>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
+</p>
+<pre class="src 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;
+</pre>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
+(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">fact-cps</span>[n k]
+(<span style="color: #f0dfaf; font-weight: bold;">if</span> (zero? n) (k 1)
+(<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))))))
+</pre>
+<p>
+clojure
+It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to
+do something like this:
+</p>
+<pre class="src src-algol">begin
+integer ann
+procedure :emp(x); value 2:; integer x;
+ans :1 x;
+]'act(3. temp);
+comment Now the variable <span style="color: #cc9393;">"am"</span> has 6;
+end;
+</pre>
+<p>
+Procedure <code>fact</code> does not return a value, nor does <code>temp</code>; we must use a side
+effect to get the answer out.
+</p>
+<p>
+<code>FACT</code> 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, <code>(FACT 3 (LAMBDA (X) X))</code> returns 6. Alternatively, we
+could write <code>(FACT 3 (LAHBDA (X) (PRINT X)))</code>; we do not care about the value
+of this, but about what gets printed. A third way to use the value is to
+write
+<code>(FACT 3 (LAMBDA (x) (SQRT x)))</code>
+instead of
+<code>(SQRT (FACT 3 (LAMBDA (x) x)))</code>
+</p>
+<p>
+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!
+</p>
+<p>
+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
+<code>(- (+ B Z)(* 4 A C))</code>
+we can write
+</p>
+<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">in-ns</span> 'categorical.imperative)
+(<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]
+(<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)) ))
+(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">+&amp;</span> (enable-continuation +))
+(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">*&amp;</span> (enable-continuation *))
+(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">-&amp;</span> (enable-continuation -))
+(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">quadratic</span>[a b c k]
+(*&amp; b b
+(<span style="color: #8cd0d3;">fn</span>[x] (*&amp; 4 a c
+(<span style="color: #8cd0d3;">fn</span>[y]
+(-&amp; x y k))))))
+</pre>
+<p>
+where <code>k</code> is the continuation for the entire expression.
+</p>
+<p>
+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:
+</p><ul>
+<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
+</li>
+</ul>
+<p>performed. In fact, they <i>must</i> be performed in this
+order. Continuation- passing removes the need for the rule about
+left-to-right argument evaluation{Note Evalorder)
+</p><ul>
+<li><sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup> In the usual applicative expression there are two implicit
+temporary values: those of <code>(* B B)</code> and <code>(* 4 A C)</code>. 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 <i>manifest</i> in the appearance and use of the variable X and Y in
+the continuation-passing version.
+</li>
+</ul>
+<p>
+In short, the continuation-passing version specifies <i>exactly</i> 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:
+</p>
+<p>
+<code>(LAMBDA (A B C ...) (F X Y Z ...))</code> when we "apply" the LAMBDA
+expression we have some values to apply it to; we let the names A,
+B, C &hellip; refer to these values. We then determine the values of X,
+Y, Z &hellip; 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, &hellip; 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.
+</p>
+</div>
+</div>
+<div id="outline-container-4-2" class="outline-3">
+<h3 id="sec-4-2"><span class="section-number-3">4.2</span> Escape Expressions </h3>
+<div class="outline-text-3" id="text-4-2">
+<p>Reynolds [Reynolds 72] defines the construction
+= escape x in r =
+</p>
+<p>
+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"!)
+</p>
+<p>
+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.)
+</p>
+<pre class="src src-algol">begin
+real procedure Imrmsum(a, n. escfun)&#167; 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 &#162; 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
+</pre>
+<p>
+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 <code>CATCH</code>:
+</p>
+<pre class="src src-clojure">abc
+</pre>
+<div id="footnotes">
+<h2 class="footnotes">Footnotes: </h2>
+<div id="text-footnotes">
+<p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> DEFINITION NOT FOUND: 1
+</p>
+<p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> DEFINITION NOT FOUND: 2
+</p>
+</div>
+</div>
+</div>
+</div>
+</div>
+<div id="postamble">
+<p class="date">Date: 2011-07-15 02:49:04 EDT</p>
+<p class="author">Author: Guy Lewis Steele Jr. and Gerald Jay Sussman</p>
+<p class="creator">Org version 7.6 with Emacs version 23</p>
+<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>
+</div>
+</div>
+</body>
+</html>

Mercurial > dylan

comparison categorical/imperative.html @ 2:b4de894a1e2e