Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I found this section confusing on first reading too, and only started to get it after I'd read up elsewhere about continuations and continuation-passing style (which is what this is).</p> <p>At the risk of explaining something that you already get, one way of looking at it that helped me is to think of the "collector" or "continuation" as replacing the normal way for the function to return values. In the normal style of programming, you call a function, receive a value, and do something with it in the caller. For example, the standard recursive <code>length</code> function includes the expression <code>(+ 1 (length (cdr list)))</code> for the non-empty case. That means that once <code>(length (cdr list))</code> returns a value, there's a computation waiting to happen with whatever value it produces, which we could think of as <code>(+ 1 [returned value])</code>. In normal programming, the interpreter keeps track of these pending computations, which tend to "stack up", as you can see in the first couple of chapters of the book. For example, in calculating the length of a list recursively we have a nest of "waiting computations" as many levels deep as the list is long.</p> <p>In continuation-passing style, instead of calling a function and using the <em>returned</em> result in the calling function, we tell the function what to do when it produces its value by providing it with a "continuation" to call. (This is similar to what you have to do with callbacks in asynchronous Javascript programming, for example: instead of writing <code>result = someFunction();</code> you write <code>someFunction(function (result) { ... })</code>, and all of the code that uses <code>result</code> goes inside the callback function).</p> <p>Here's <code>length</code> in continuation-passing style, just for comparison. I've called the continuation parameter <code>return</code>, which should suggest how it functions here, but remember that it's just a normal Scheme variable like any other. (Often the continuation parameter is called <code>k</code> in this style).</p> <pre><code>(define (length/k lis return) (cond ((null? lis) (return 0)) (else (length/k (cdr lis) (lambda (cdr-len) (return (+ cdr-len 1))))))) </code></pre> <p>There is a helpful tip for reading this kind of code in <a href="http://www.cs.indiana.edu/~dfried/appcont.pdf" rel="nofollow noreferrer">an article on continuations by <em>Little Schemer</em> co-author Dan Friedman</a>. (See section II-5 beginning on page 8). Paraphrasing, here's what the <code>else</code> clause above says:</p> <blockquote> <p>imagine you have the result of calling <code>length/k</code> on <code>(cdr lis)</code>, and call it <code>cdr-len</code>, then add one and pass the result of this addition to your continuation (<code>return</code>).</p> </blockquote> <p>Note that this is almost exactly what the interpreter has to do in evaluating <code>(+ 1 (length (cdr lis)))</code> in the normal version of the function (except that it doesn't have to give a name to the intermediate result <code>(length (cdr lis))</code>. By passing around the continuations or callbacks we've made the control flow (and the names of intermediate values) explicit, instead of having the interpreter keep track of it.</p> <p>Let's apply this method to each clause in <code>evens-only*&amp;co</code>. It's slightly complicated here by the fact that this function produces <em>three</em> values rather than one: the nested list with odd numbers removed; the product of the even numbers; and the sum of the odd numbers. Here's the first clause, where <code>(car l)</code> is known to be an even number:</p> <pre><code>(evens-only*&amp;co (cdr l) (lambda (newl product sum) (col (cons (car l) newl) (opx (car l) product) sum))) </code></pre> <blockquote> <p>Imagine that you have the results of removing odd numbers, multiplying evens, and adding odd numbers from the <code>cdr</code> of the list, and call them <code>newl</code>, <code>product</code>, and <code>sum</code> respectively. <code>cons</code> the head of the list onto <code>newl</code> (since it's an even number, it should go in the result); multiply <code>product</code> by the head of the list (since we're calculating product of evens); leave <code>sum</code> alone; and pass these three values to your waiting continuation <code>col</code>.</p> </blockquote> <p>Here's the case where the head of the list is an odd number:</p> <pre><code>(evens-only*&amp;co (cdr l) (lambda (newl product sum) (col newl product (op+ (car l) sum)))) </code></pre> <p>As before, but pass the same values of <code>newl</code> and <code>product</code> to the continuation (i.e. "return" them), along with the sum of <code>sum</code> and the head of the list, since we're summing up odd numbers.</p> <p>And here's the last one, where <code>(car l)</code> is a nested list, and which is slightly complicated by the double recursion:</p> <pre><code>(evens-only*&amp;co (car l) (lambda (newl product sum) (evens-only*&amp;co (cdr l) (lambda (dnewl dproduct dsum) (col (cons newl dnewl) (opx product dproduct) (op+ sum dsum)))))) </code></pre> <blockquote> <p>Imagine you have the results from removing, summing and adding the numbers in <code>(car l)</code> and call these <code>newl</code>, <code>product</code>, and <code>sum</code>; then imagine you have the results from doing the same thing to <code>(cdr l)</code>, and call them <code>dnewl</code>, <code>dproduct</code> and <code>dsum</code>. To your waiting continuation, give the values produced by <code>cons</code>ing <code>newl</code> and <code>dnewl</code> (since we're producing a list of lists); multiplying together <code>product</code> and <code>dproduct</code>; and adding <code>sum</code> and <code>dsum</code>.</p> </blockquote> <p>Notice: each time we make a recursive call, we construct a new continuation for the recursive call, which "closes over" the current values of the argument, <code>l</code>, and the return continuation - <code>col</code>, in other words, you can think of the chain of continuations which we build up during the recursion as modelling the "call stack" of a more conventionally written function!</p> <p>Hope that gives part of an answer to your question. If I've gone a little overboard, it's only because I thought that, after recursion itself, continuations are the second really neat, mind-expanding idea in <em>The Little Schemer</em> and programming in general.</p>
    singulars
    1. This table or related slice is empty.
    1. POThe Little Schemer evens-only*&co
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USJon O.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you Jon O. I'm still fuzzy on what happens in the 3rd case, where it's a nested list and not an atom. Let's say input list l is ((2)), which means on the first time through it hits case 3 with: (2) for (car l), and () for (cdr l) and my evens-results for the col -- which then goes first down the recurs. Re-entering evens-only*&co, it is true for the first cond, (null? l), and picks up '(), 1, 0 for dnewl, dproduct, dsum. But this is the very first time where, presumably, newl, product, sum would not have been initialized or even exist. But obviously I'm seeing this wrong. . . .
      singulars
      1. PO
      1. USmelwasul
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload