Continuations and immutable lists (Was: Re: Handler-Bind question...)

[drichter@owlnet.rice.edu (David Richter)]

What's the connection?  Read on.

In article <36esve$afu@kernighan.cs.umass.edu>, 
schmill@earhart.NOT.SET (Matt Schmill) writes:
|> 
|> Hello all... I'm building an error handling macro that I want to use for a $
|> on top of a portable application. The macro will basically be :
|> 
|> (defmacro with-error-handling (&body body)
|>   (handler-bind ((error (condition) ...)
|>               (warning (condition) ...))
|>      ,@body))
|> 
|> the problem is that I can't differentiate clearly between the two cases;
|> If there is an error, I want to jump out of the body. a throw/catch form will
|>   allow this. But if there's a warn, I want to finish evaluation of BODY 
|>   _without the warning being displayed_ in the listener. I want my GUI to
|> handle
|>   these cases without the listener displaying anything.
|> 
|> handler-case has the opposite problem. I can't seem to find a way to resume the
|>   body if the WARNING is trapped. 
|> 
|> Does anyone out there have a clever solution ? If so, I'd love to hear it..
|> (redefining the warn function is out of the question)
|> 
|> thanks in advance 

What you need is a better paradigm.  Here's one such.  The basic idea
is that control structures (catch/throw, abort-with-value, call/cc,
setlongjmp/longjmp, etc.) have an implicit delimiter at the "top
level" (whether it be the REP loop of an interactive system or the
init/exit code around the main() function, or anything else).

What is needed are two functions, with a relationship similar to that
between catch and throw.  Call them run and jump.  Jump takes one
argument; I'll say what it does momentarily.  Run takes a thunk--the
expression--and a function of two arguments--the handler.  The thunk
is evaluated; if, in the process of evaluating it, jump is not called,
then run returns whatever it returned.  (Alternatively, run could take
a third argument that accepts the output of the thunk in this case.)
Otherwise--when evaluation of the thunk reaches an invocation of
jump--the handler is invoked on 1) the argument to the jump and 2) the
part of the continuation from the run to the jump.

For example: (in Scheme syntax)

(run (lambda () 5) foo) ==> 5  (assuming evaluation of foo 
                                 doesn't diverge)
(run (lambda () (k (jump 5))) foo) ==> (foo 5 k)

It should be obvious that this implements exception handling,
(reentrant) warning handling, catch/throw, call/cc; in fact, it
can macro-express almost any such control paradigm.

(More information on this topic is available in various papers by
Felleisen, Sitaram, Duba, et al.  Many can be found online in
cs.rice.edu:/public/languages.  I suggest starting with
pldi-93.s.dvi.)

Speedy implementation, however, is difficult.  By speedy, I mean
constant time overhead for unrestricted use of run/jump.
(Unrestricted call/cc can be made constant time.)

Here's why O(1) is probably impossible:

Suppose the program is as follows: 
(indented for clarity to non-pro-paren-people)
(run (lambda () 
        (j (run (lambda () (k (jump 0)))
                (lambda (x y) (y x)))
           )
        )
     (lambda (x y) x))
the application of j to something is the first continuation; the
application of k to something is the second; and in the expression (y
x), the continuations must be (logically) appended.

Playing around with this, one comes to the conclusion that
implementing the continuation is equivalent to implenting
cons/car/cdr/append for (non-mutable) lists.  The usual representation
has cons, car, and cdr at O(1), but then append is O(n).  By
representing lists with trees (figuring that if continuations are
composed then they will also sometimes be discarded, so we can delay
flattening the tree until necessary), we can make cons and append O(1)
and car/cdr O(log n).  We could also push car/cdr to be O(1) (with a
bigger constant) by having cons/append be O(n) (with a smaller
constant) by requiring the tree to be never more than x levels deep.

David

PS: And if anyone knows a better way to implement immutable lists, I
(and various others including the authors listed above) would love to
hear from you.