Re: continuations

[Mario Latendresse <address@hidden>]

Hello everybody,

Matthias Felleisen wrote:

> You must start with asking the very simple question of why Schemers use 
> 
>  (call/cc (lambda (k) ... ))
> or 
>  (let/cc k ...)
> 
> and not 
> 
>  (the-continuation)

I like this question. (Needless to say, Matthias loves to teach. Even
at his age he shows a lot of enthusiasm in class; at least the one I
attended!) (Thanks to the people who made Dan Friedman's paper
available on the net.)

The spirit of that post was pedagogic; so I would like to add my point
of view in that direction.

Some time ago, in the 70's, I read a beautiful book on group theory
written in French by Georges Papy.  It is simply titled ``Groupe''
(Dunod, 1967). In it, the abstract theory is sprinkled with nice
colorful diagrams, most of them with simplicity: lines, circles and
dots. And the accompanying equations have coordinating colors!  (I
still have it! This is no small feat as it changed home more than 16
times, from Joliette (Canada, Qc) to Pacific Grove (USA, Ca).)

Anyhow, this was probably done and written somewhere else: What would
be a simple diagram to represent continuations and the effect of
call/cc?

The following way appeals to me.

Let say that the current thread of execution is represented by a
vertical line, where computation proceed from top to bottom:
(Sorry Georges, I can't use colors here.)

    ...
     |
     o a
     |
     o b
     |
     o c
     |
     o d
     |
     o e      
     |
     v
     |
    ...

I prefer the vertical line even though it takes more space than an
horizontal one. The three dots emphasize this as a segment of
computations marked a, b, c, d and e.

How can the computation from d, downward, be bound to an id, without
executing d or any of the downward steps? (After all we can't roll a
carpet if we step on it.) In other words, how can the line be broken
right at d; and be put on the side of the diagram?

Not much choice: another line, a redirection or fork, must be provided
and sticks it right after c.

    ...
     |
     o a
     |
     o b
     |
     o c
      \
       o d'
        \
         o e'
          \
          ...
     o d
     |
     o e      
     |
     v
     |
    ...
    

The segment d-e-... (aka ``the rest of the computation'', ``the
continuation'') is detached and a new one d'-e'-... is provided by the
programmer.

Call/cc detaches the segment.  The programmer provides the new
segment as a function; call/cc gives to that function the detached
segment. So the function has one parameter, the segment, aka the
continuation; and it can save away that continuation to call
it later.

Does the continuation has a parameter or none? Since we are in
functional language, and that at point d a value is expected, the
continuation should receive a value. So, the continuation has one
parameter receiving the value it would have received as if no
detachment had occurred. 

>From this diagram it seems easier to visualize the applications of
call/cc: threads, exceptions, breaking out of a loop, chaotic tree
walking, premature returns, debugging, backtracking, etc.

Did I write a line of code? S'cusez!

-- Mario