Coroutines ( & continuations ... ) 
Author Message
 Coroutines ( & continuations ... )

[ Long for a post, short for an essay. Sorry, the language critiques pages
  on minsky.med are down -- it's disk is hosed  - and I have some notes
  from when I originally researches this question while doing the ceval.c
  hacking referred to, but I don't have time to dig them out at the
  moment, so I can't fill in all of the references as I would like to. ]

        "The continuation for some computation is whatever comes after it,
        expressed as a function of the result for that compututaion."
                  R.D.Tennet, Principles of Programming Languages, 1981

More intuitively, you can think of a continuation as the abstraction
of a "place" in a program -- not just a label or address, but more
like a de{*filter*} breakpoint -- there is a machine state that goes
along with that location which captures the state of the computation.

Along with expressions, definitions, commands, state, etc. its one
of the abstractions that all programming languages are built upon.
I state this up-front because, like subroutines or identifiers, there
is the abstract idea and then how their implementation in various
languages. A language that doesn't provide explicit continuations
still has continuations ( just as a program written in a functional
language that doesn't provide explicit commands to handle state, still
HAS a state. ) and a language that provides something called continuations
may provide something that isn't quite what that definition at the top
would lead you to expect.  ( The difference is how global is the state that
is saved. Except for complete transaction rollback, you don't usually WANT
to consider the entire global effect of the computation. )

Sequencer are the things that control program flow.
The most basic sequencer is often represented as ";" in books on
programming language semantics. It means, basically: do the next
thing. You can think of it as the null sequencer.

JUMP or GOTO is the sequencer that changes the program location
without saving any continuation.

CALL saves the current continuation somewhere ( typically, on a stack ),
  and jumps to a new location, also possibly creating a new temporary
  local state or context for execution to begin.
RETURN jumps back to the saved continuation, without saveing the
  current continuation.

RESUME and SUSPEND are the pair that implements what I believe Knuth
calls semi-couroutines ( I can't find the reference at the moment, but
I have some notes around somewhere. )

RESUME is really the same as CALL ( except... )
SUSPEND is like return except that it saves the current continuation
somewhere. Where that somewhere is and how it's expressed varies in
different program languages, but it has to be somehow returned or linked
to the target or label or the RESUME command. That target expression is
really a variable that jumps to the previously saved continuation.

[ This is what Icon calls co-expressions or generators. ]

CALL/RETURN & RESUME/SUSPEND are both asymetrical  -- the callee always
eventually returns to the caller site, and two different types of syntax
elements are usually required to distinguish the pair  of sequencers.

Full coroutines are completely symetrical: save the current continuation
state and jump to a new or restored context. If you add a couroutine to
manage a list of ready-to-run continuations, then you have cooperative
multitasking. If you add an way to externally trigger the saving of a
continuation and the suspension of a thread without requiring it to
explicitly suspend execution, then you have preemptive multitasking.

If you have a way to explicitly handle continuations in a programming
language, then you can build coroutines, threads, objects, generators, and all of
the various flavors of exception handlers. Very powerful. Just like
goto's.  And just as with goto's, it may be much less confusing to avoid
"raw" continuations and use threads, coroutines,  objects,  and exception
handlers. Part of the very idea of structured programming, is after all, to
restrict your choices.  Just as trying to structure words into the sonnet
form, or writing to a particular musical form helps with the flow of
creativity onto the empty page,  the doctrine of structured programming
says that 80% of the things you could possibly ever want to do can easily
fit into a handful of control structures ( and those that don't fit easily
can be splooged without too much {*filter*} ). Add exception handling
and threads and your probably at 95%.

[ I wanted to get back to the 'goto' thread somehow!
  BTW: Knuth wrote the definitive reply to"GOTO Considered Harmful" ,
  describing why and when goto's are necessary, however, when you add
 'break', exception handling,  and some sort of finalization
 ( unwind-protect in Lisp or Python's  try/finally ), I believe you
  cover 99 % of the cases.

  Also: someone ( in that, or some other past thread ) mentioned "the
  mythical 'COME FROM' statement".   INTERCAL actually does have a
  'COME FROM'.  INTERCAL's implementation of COME-FROM, like everything
  else in INTERCAL, is a joke, of course. But when I first heard of the
  feature, I thought it was serious and I tried to think of a reasonable
  implementation. What I came up with was to require matching GOTO's
  and COME-FROM's as a way to impose some discipline on "spagetti code".
  INTERCAL's version is better. If you're intent on writing
  incomprehensible code, what is better than a feature that allows the flow
  of control to suddenly drop through a trapdoor and magically appear pages
  later when the magical incantation is used. Must have been written by
  the same guy that wrote 'Adventure' !  ]

 Anyway, saving all of these continuation states to go back to later imply
 something more than a single stack - either heap allocated frames of
 multiple stacks. The python virtual machine happens to have heap allocated
 frames, which are almost sufficient to implement continuations. I hacked
 up an experimental version of ceval.c, and had to add only one field to
 frameobject,  and a couple of lines of code to implement 'suspend' and
 to make sure that all of the fields were properly updated before suspend.
 Frameobject's are regular python objects ( although they aren't usually
 visible at the Python level except in exception stack traces. ) so they are
 reference counted and aren't disposed of while there is a dangling
 reference to the suspended continuation.  This did manage to implement
 a form of generator/semi-coroutine, however, the problem with implementing
 threads or coroutines in that Python and C can and do call each other, and
 the recursive implementation of ceval.c made stack cleanup impossible if
 you didn't always eventually return to the calling site.

 [ This is when the idea of a 'flatter' implementation of the virtual
 machine, due to be in Python 2.0, was discussed -- although Guido
 had already been considering it for effeciency reasons. ]

 As to the question about what can you do with coroutines that you can't
 do with objects ?  Not much, really. But that's not the right question. (
 I can't disprove the assertion that anything worth saying can be stated in
 the form of a limerick, either. )  You only NEED a single type of loop
 mechanism, but we actually use several.

   Objects in Simula were actually implemented as coroutines. One of the
   history of Lisp papers makes it clear that the Scheme group and Alan
   Kay's Smalltalk group were in communication and agreement about the
   complementarity of Smalltalk objects and Scheme continuations. They had
   discussions about how they were both different ways of looking at the
   same thing. Sometimes one is a more natural notation that the other.
   Icon's coexpressions for example, do in a single line what takes a
   dozen or more lines of Python code. I don't, however, think that
   conciseness is the main virtue, so much as that it's often a convenient
   and simple way to think of a problem. The typical unix command line
   pipeline is just a series of a generator, a buch or filters and a sink
   for the final data, all linked together as coroutines. ( Well, really
   processes, but processes, threads and coroutines are all variations on
   the same thing. )


---|  Computer Systems Engineer          University of {*filter*}ia  |---
---|  Department of Molecular Physiology and Biological Physics  |---
---|  Box 449 Health Science Center    C{*filter*}tesville,VA 22908  |---
 [ "The grass is always greener, except at t=0" - Stan Kelly-Bootle ]



Tue, 22 Dec 1998 03:00:00 GMT  
 Coroutines ( & continuations ... )

  I forgot to mention that the other common use of the idea of
continuations is in CPS - Continuation Passing Style - which
is a compiling technique that, rather than depending on a
stack to pop a return address, passes  the return address or
continuation explicitly, implicilty adding the continuation
as an extra parameter, just as Python and a few other OO languages
add a "self" parameter to method calls. [ Note also that some
RISC microprocessers have an explicit link register used for
subroutine calls, so that leaf calls can often avoid any stack
overhead at all. ]

  CPS makes the implementation of programmer visible continuations
in a language simpler, but it can be a useful compiling technique
even without explicit continuations, as it also makes some optimizations
and program transformation easier. Eliminating tail recursion, for
example, becomes fairly trivial.

 If you add an exceptional return parameter to CPS, you end up with
a very SNOBOL-ish virtual machine instruction:

 CALL func, On-Success-return cont1, On-exception-return cont2, [with args...]

which can also avoid a lot of stack popping and hunting for the
correct exception handler.

[ The standard reference for CPS is Andrew Appel's "Compiling with
  Continuations" ]


---|  Computer Systems Engineer          University of {*filter*}ia  |---
---|  Department of Molecular Physiology and Biological Physics  |---
---|  Box 449 Health Science Center    C{*filter*}tesville,VA 22908  |---
 [ "The grass is always greener, except at t=0" - Stan Kelly-Bootle ]



Tue, 22 Dec 1998 03:00:00 GMT  
 Coroutines ( & continuations ... )

Oops:
 I don't have the history of Lisp papers on-line to check, but I
believe I made a misstatement. It may have been the complementary
nature of Objects  and *Closures* that were discussed by Alan Kay's
smalltalk group and the scheme developers.
 Continuations are a special type of closure, so that term is obviously
the important one missing from my post.

Also: I strongly agree with tmb that, if you don't NEED preemption,
then coroutines are much simpler that threads. If you know that a
computation can only be suspended at a few, well defined points, then
you don't need locking mechanism or semaphores, and, especially
for ease of use, you *don't* need a lot of expertise to know whether
or not you DO require such things.
  Processes ( like unix pipelines ) are easy to use because, since
they are protected in a separate address space, they don't have as
many interactions and side effects to worry about.
  Coroutines execute in the same address space, but since they must
explicitly yield control, their side effects and unexpected interaction
is also rather circumscribed.
  Threads, like global variables, give you comparatively lots of
opportunities to shoot yourself in the foot, when interactions that
seem so unlikely that you don't give them much thought, actually DO occur.


---|  Computer Systems Engineer          University of {*filter*}ia  |---
---|  Department of Molecular Physiology and Biological Physics  |---
---|  Box 449 Health Science Center    C{*filter*}tesville,VA 22908  |---
 [ "The grass is always greener, except at t=0" - Stan Kelly-Bootle ]



Tue, 22 Dec 1998 03:00:00 GMT  
 Coroutines ( & continuations ... )

Quote:

>         "The continuation for some computation is whatever comes after it,
>         expressed as a function of the result for that compututaion."
>                   R.D.Tennet, Principles of Programming Languages, 1981

Excellent discussion.  After my ``huh?'' post and Daniel's and Steve's reply, I realized
that coroutines have a perfect application in internet servers for example, where
a ``handler'' for a session can suspend itself in the middle of some computation
awaiting some data from the network and a separate ``selector'' process can resume
execution, awaking whatever handler may have data, or accepting a new connection
or whatever... when the suspended handler gets new data it starts up again, where
it left off...

Implementing this without some notion of coroutines or something similar is a
pain in the anatomy (and threads are overkill and make things too complicated).

Now I understand why Guido has support for coroutines in mind for 2.0...
It's just too hard to keep up with you folks sometimes. That's what I like about this
group.   --- Aaron Watters
====
La Pi~nata: Period of time just before the Sandinista's left power, where state
   assets (guns, grenades, bazookas, cars, houses...) were distributed to right thinking
   Sandinista party members.  Named after the children's game....



Wed, 23 Dec 1998 03:00:00 GMT  
 Coroutines ( & continuations ... )

Quote:

> ... I realized
> that coroutines have a perfect application in internet servers for example, where
> a ``handler'' for a session can suspend itself in the middle of some computation
> awaiting some data from the network and a separate ``selector'' process can resume
> execution, awaking whatever handler may have data, or accepting a new connection
> or whatever... when the suspended handler gets new data it starts up again, where
> it left off...

When I was at university, we used coroutines for precisely this, in the file handler
of the operating system we were developing. The disadvantage is that you may not want
to allocate stack space for every open file/connection. In those days, we just didn't
have enough memory.




Thu, 24 Dec 1998 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. INTERCAL & COME FROM (was: Coroutines ( & continuations ... ))

2. INTERCAL & COME FROM (was: Coroutines ( & continuations ... ))

3. Coroutines ( & continuations ... )

4. Continuations, Coroutines, Iterators, Threads oh my!

5. Coroutines and continuations

6. coroutines and continuations ( in Python? - long discussion )

7. JPI Topspeed & MS-Windows / CoRoutines

8. Monad & Continuation

9. Continuations and threads (was Re: Iterators & generators)

10. Ports & continuations & UNWIND-PROTECT & GC

11. VAST 4.5 - ODBC Calls Hang Using Abt Coroutine Calls

12. Coroutines Package for Eiffel???

 

 
Powered by phpBB® Forum Software