[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

good pictures vs. good stories (was: Re: CPS in Parrot)

Geoffrey Knauth wrote:

 > We need good pictures that show how continuations work, and good
 > stories.

There are two schools of thought on this subject.  One favors pictures
(geometric thinking), the other symbolic reasoning (algebraic thinking).

Here's a somewhat relevant quote from "ANSI Common Lisp", Section 3.9,
by Paul Graham:

 > Students learning about recursion are sometimes encouraged to trace
 > all the invocations of a recursive function on a piece of paper. ...
 > This exercise could be misleading: a programmer defining a recursive
 > function usually does not think explicitly about the sequence of
 > invocations that results from calling it.
 > If one always had to think of a program in such terms, recursion
 > would be burdensome, not helpful.  The advantage of recursion is
 > precisely that it lets us view algorithms in a more abstract
 > way. ...
 > ... The secret to understanding recursion is a lot the secret for
 > dealing with parentheses.  How do you see which parenthesis matches
 > which?  You don't have to.  How do you visualize all those
 > invocations?  You don't have to.

I find this advice encouraging, as I gave up on trying to visualize
the execution path of the following program:

((call/cc call/cc) (call/cc call/cc))

I sort of understand that the execution path will jump back and forth
-- mostly forth, I guess -- and the program will never terminate.  I
can sort of reason about it symbolically by "viewing algorithms in a
more abstract way":

For ease of reference, I can rewrite the above as follows:

((call/cc1 call/cc2) (call/cc3 call/cc4))

where call/cc1 is just another name for call/cc. Kinda like

(define call/cc1 call-with-current-continuation)

Let k1, k2, k3, and k4 denote the continuations captured by call/cc1,
call/cc2, call/cc3, and call/cc4, respectively.

What's the value of (call/cc1 call/cc2)? Reasoning in purely algebraic
terms, I can say that call/cc1 invokes call/cc2 passing it k1 as the
argument.  So, the value of this term is (call/cc2 k1). The latter
does a similar thing: call/cc2 calls k1 and passes it k2 as the
argument.  So, we get (k2 k1). Now, k2 returns whatever is thrown to
it.  This means, it returns k1.

By the same token, (call/cc3 call/cc4) returns k3.  So, the entire
original thingy evaluates to (k1 k3).  This, of course, returns k3.
Easy as pie.  Now, what on earth is k3?  At this point, I have this
little voice in my head that tells me I would be better off, if I
tried to visualize the tree of activation frames instead of trying to
think about this symbolically, as Paul Graham advises.

I suppose I should really find the time to read The Seasoned Schemer.