Re: continuations and linear types

[James Knight <jknight@xxxxxxxx>]

On Wednesday, April 17, 2002, at 02:58  PM, Allen Short wrote:
> i'm very excited about the possibilities goo presents; it's almost
> everything i've wanted from a language.
>
> my primary interest is in distributed and concurrent apps; hence, i've
> been quite interested in the disucssions of continuations and threads so
> far. I propose adding linear types to goo;
> [.....]

After an initial reading of that paper, I'm quite unconvinced that 
linear types as described there are a useful concept. As far as I can 
tell, the main argument for them is to make it impossible for one to be 
accessed by multiple threads. However, this is a _*great*_ cost in 
complexity for single-threaded programs. I can tell you right now I'd 
hate to use a language that makes me go through the hoops described in 
that paper. Even they admit its basically impossible to use without a 
GUI programming UI. What are the chances of that ever getting done in 
the near future? They poo-poo text-programming, but I haven't seen any 
indication that its going to go away any time soon. The rest of the 
arguments seem to me like they're basically premature optimizations 
exposed to the programmer.

However, I do believe that a similar concept, not applied to number of 
references, but rather, to number of *different threads that have 
references* is a great idea. In fact, I'm currently a proponent of the 
concept that objects should *always* be linear-with-respect-to-threads. 
That is, two threads cannot ever hold a reference to the same object 
[[at least, as far as they can tell]]. Make RPC the only method of 
communication, but make it very optimized. In my experience, when 
writing a threaded program, you pretty much need to work that way 
anyways if you're going to stay sane, but its just a lot easier to screw 
up and allow a reference to escape to another thread when you didn't 
intend to.

> Additionally, linear continuations have unique advantages; they allow
> continuations to be stack allocated (since they cannot be captured), and
> avoid the bad interactions shareable continuations have with
> unwind-protect and tail recursion (for a detailed discussion of this
> issue, see http://lists.tunes.org/archives/tunes/1999-August/002235.html
> ) while providing most of the control advantages of shareable
> continuations such as coroutines and microthreading.
>
> Of course, some applications require non-linear continuations;
> Queinnec-style use of continuations for web apps most notably, as well
> as prolog-style backtracking. My own feelings are that only allowing
> linear continuations is a sufficient tradeoff between expressitivity and
> clean semantics/efficient implementation.

Single-shot continuations have a lot going for them, but unless I'm 
missing something, being able to be stack-allocated is not one of them. 
However, every time I think about multi-callable continuations they seem 
like a worse idea. That message reminds me of my biggest objection: that 
functions can get put in normally-impossible states of execution. Even 
for web-applications it seems like a poor idea, as the state of the data 
is not copied, only the state of execution. The That's all well-and-good 
as long as you make sure not to ever modify program state or ever use 
non-functional operations in your app. If anything does, it could end up 
in serious trouble. That seems to me to be quite poor, and it makes me 
think that what you really want to have for web-applications is fork().

Then there's the issues with callbacks from a C library. With one-shot 
continuations, it seems at least *possible* to make the C 
interoperability issues work out, but with multi-shot continuations, 
that gets more complicated. Its not really possible to return to a C 
function more than once.

Banging out a microthread implementation in psudeo-GOO to demonstrate to 
myself impossibility of stack-allocating frames [gonna need it sometime, 
why not write it in an email program with no indenting or parenmatching? 
;P]:


(dv *threads* (tup))

(df yield ()
   (call-cc
     (fun (cont)
       (if (> 0 (len *threads*))
         (seq
           (def next (1st *threads*)
           (set *threads* (add (tail *threads*) cont) ; substitute the 
appropriate generic equivalent of "tail" in GOO
           (next))
         (cont)
       ))))

(df die ()
   (msg out "Thread died")
   (def next (1st *threads*)
   (set *threads* (tail *threads*))
   (next))

(df add-thread (func)
   (msg out "Thread started")
   (set *threads*
     (add *threads*
       (fun ()
         (func)
         (die))))

(df foo ()
   (msg out "Foo frame allocated")
   (add-thread bar)
   (yield)
   (msg out "Foo frame deallocated")
)

(df bar ()
   (msg out "Bar frame allocated")
   (yield)
   (msg out "Bar frame deallocated")
)

=> (foo)
Foo frame allocated
Thread started
Bar frame allocated
Foo frame deallocated

now foo has returned to top-level, but bar's activation frame must still 
exist, so if yield is called again,
=> (yield)
Bar frame deallocated
Thread died