Coroutine vs Continuation vs Generator

Coroutine is one of several procedures that take turns doing their job and then pause to give control to the other coroutines in the group.

Continuation is a "pointer to a function" you pass to some procedure, to be executed ("continued with") when that procedure is done.

Generator (in .NET) is a language construct that can spit out a value, "pause" execution of the method and then proceed from the same point when asked for the next value.

In newer version of Python, you can send values to Generators with generator.send(), which makes python Generators effectively coroutines.

The main difference between python Generator, and other generator, say greenlet, is that in python, your yield value can only return back to the caller. While in greenlet, target.switch(value) can take you to a specific target coroutine and yield a value where the target would continue to run.

I appreciate Keith Gaughan's answer. In addition, I'd like to provide an explanation from a different perspective.

Everything begins with the concept of continuation, which is a data type whose value conceptually contains the current stack, including all frames, and the program counter (PC), which holds the address from where the CPU fetches the next instruction to execute.

Generators, coroutines, and exceptions are applications of continuations. These programming paradigms are built upon and enabled by continuation.

Continuation is a foundational type

The excellent book Teach Yourself Scheme in Fixnum Days explains continuation in Scheme. We can use the function call/cc to capture the current stack and PC into a continuation, wrapping it into a callable function. When invoked, this function restores the captured stack and PC, resuming execution. This is the origin of the term "continuation."

The book also illustrates how continuations can be used to implement generators and coroutine. These paradigms and continuation initially conceived in the Lisp/Scheme community before being implemented in Python.

Generators is a syntactical application of continuation

When a Python program calls a generator, such as in the following example, the Python interpreter captures a continuation, which we can refer to as caller_continuation.

for x in gen(): print(x) 

When the generator gen executes a yield statement, the interpreter captures the continuation in_generator and restores caller_continuation. This causes execution to "jump" back to the avoe loop. After executing print(x), the program calls gen() again, triggering the interpreter to capture a new caller_continuation, and restoring in_generator. This resumes execution within gen. This process continues until gen completes and returns.

Coroutines is another syntactical application of continuation

Teach Yourself Scheme in Fixnum Days shows that using the highly flexible define-macro syntax in Scheme, we can create the syntax coroutine.

In Python, analogous constructs include async and await. When encountering a statement like await foo(), the Python interpreter captures a continuation. Later, after foo() completes, the captured continuation is restored, resuming execution at the appropriate point.

Exception Handling is yet another application

In the following example, the try statement causes the Python interpreter to capture a continuation.

try: bar() except: print("Ouch") 

If bar() or a function it calls raises an exception using raise, the interpreter restores the captured continuation, resuming execution at the except block.

Keith Gaughan's answer is great which says the relation between generator and coroutine in its 2nd paragraph. Actually, cc(max(x, y)) in biggest = callcc(foo, [23, 42]) can be thought as doing biggest = max(23, 42). This is what "return with the value you're calling the current continuation with" means.

Here I give example programs which can be run to show how them work as one supplementary resource for Keith Gaughan's answer. For the former 2 I is mainly based on Reuven's blog. For callcc, I followed lispy2 doc.

I also give their relations with codes or implementation ideas. If we can understand relations, then differences may probably be implicitly got.

generator

definition extracted from wikipedia

a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately

Here yield means generate.

implementation

Simple demo from the above blog.

# creation def myfunc(): yield 1 yield 2 yield 3 # usage for one_item in myfunc(): print(one_item) # 1 # 2 # 3 

coroutine

definition

This is from one wikipedia reference

Under these conditions each module may be made into a coroutine; that is, it may be coded as an autonomous program which communicates with adjacent modules as if they were input or output subroutines. Thus, coroutines are subroutines all at the same level, each acting as if it were the master program when in fact there is no master program. ... When coroutines A and B are connected so that A sends items to B, B runs for a while until it encounters a read command, which means it needs something from A. Then control is transferred to A until it wants to "write," whereupon control is returned to B at the point where it left off.

asymmetric coroutine implementation

The following program is just following the structure of Keith Gaughan's. Notice here x is directly passed from my_coroutine_body to x = my_coro.send(x). So it is asymmetric. How "symmetric and asymmetric coroutines" are converted to each other is shown in boost doc "Symmetric and asymmetric coroutine transformation" (reference of this QA answer) which is fine to read without much cpp background.

1. my_coroutine_body is just one doubling program. Here it can still do suspension and resumption at least due to yield as the above shows. But notice here we uses yield-expression bar = yield foo instead of yield-statement yield foo (please see PEP 342 for more infos). It is used here since it can pass data in by send. So it achieves the data communication implied in the definition.

   which is the value that should be sent in to the generator ... the send() method returns the next value yielded by the generator-iterator

2. What make_coroutine does is to Delegate to a Subgenerator as PEP 380 shows. For here it is just to keep the Keith Gaughan's structure to show how the general idea works. We can work well without this here as the blog shows. But as "Delegate" implies, it will be helpful when implementing one dispatcher (see switchboard in the blog).

   One good explanation of yield-from is shown in this QA answer "transparent, bidirectional connection"

3. next(my_coro) usage is said by PEP 342

   Because generator-iterators begin execution at the top of the generator’s function body ... advance its execution to the first yield expression.

how this implementation relates with the above definition

I give number index in the following paragraph to show the relation with the above quote sentence more clearly. In a nutshell, it is just one loop where 2 or more coroutines passes data read/write control to each other.

1- Here my_coro (let it be coroutine A) cooperates with my_coroutine_body (let it be coroutine B) just as make_coroutine expects. 2- Assume the master program (MP) is the program part which is running currently. 3- Coroutine A (CMP, i.e. the current MP) sends one number to coroutine B. 4- coroutine B then immediately reads that by x = yield x where the result of yield x is that coroutine A sends in. Then coroutine B (CMP) does some calculation and then transfer control explicitly by yield x in x = yield x. 5- Then coroutine A (CMP) reads that yielded value which is assigned to the left x in x = my_coro.send(x). Then coroutine A does the next write by send. 6- Then coroutine B continues from the "the point where it left off" implied by yield similar to the generator behavior.

# https://lerner.co.il/2020/05/08/making-sense-of-generators-coroutines-and-yield-from-in-python/ def my_coroutine_body(): x = '' while True: print(f'Yielding x ({x}) and waiting…') # Do some funky stuff x = yield x # Do some more funky stuff if x is None: break print(f'Got x {x}. Doubling.') x = x * 2 def make_coroutine(routine): yield from routine() my_coro = make_coroutine(my_coroutine_body) next(my_coro) x = 1 while True: # The coroutine does some funky stuff to x, and returns a new value. # send to routine which then sends to the left x in `x = yield x` in my_coroutine_body. if x < 2**10: x = my_coro.send(x) else: my_coro.send(None) print(x) ## in coroutine B # Yielding x () and waiting… # Got x 1. Doubling. # Yielding x (2) and waiting… ## back to coroutine A # 2 ## again into coroutine B # Got x 2. Doubling. # ... 

relation with generator

As the above implementation implies, here we still uses suspension and resumption offered by yield. But we added the data passing mechanism by send method. So this implies we can use coroutine to implement generator where we don't send data but just send the command to let the generator continuing to run. One straightforward implementation is shown in c2 CoRoutine wiki with the same Generate123 example which uses wikipedia yield, resume notation.

IMHO the following from c2 CoRoutine wiki is inappropriate since generator actually also saves control state. The difference is Keith Gaughan says, coroutine can pass data while generator can't.

Coroutines are functions or procedures that save control state between calls (as opposed to, but very similar to, Generators, such as Random Number Generators, that save data state between calls).

symmetric coroutine implementation

See "A simple co-routine scheduler ..." part in PEP 342. Actually it does same as the above boost doc by using one scheduler to allow yield to one given address instead of only to the caller.

relation with generator

Quoted from wikipedia which quotes PEP 342

The only difference is that a generator function cannot control where should the execution continue after it yields; the control is always transferred to the generator's caller.

call/cc or call-with-current-continuation

The naming is borrowed from Scheme.

definition from wikipedia

The "current continuation" or "continuation of the computation step" is the continuation that, from the perspective of running code, would be derived from the current point in a program's execution. The term continuations can also be used to refer to first-class continuations, which are constructs that give a programming language the ability to save the execution state at any point and return to that point at a later point in the program, possibly multiple times.

In a nutshell you can think of it like the calling stack.

implementation in python

There is one implementation based on exception as this question implies in lispy2. This is possible since exception can be implemented based on continuation as wikipedia and mattmight blog shows. In a nutshell, it uses try location as the continuation.

def callcc(proc): "Call proc with current continuation; escape only" ball = RuntimeWarning("Sorry, can't continue this continuation any longer.") def throw(retval): ball.retval = retval; raise ball try: return proc(throw) except RuntimeWarning as w: if w is ball: return ball.retval else: raise w 

Let us check this implementation based on one official lispy2 example lisp program (You can think the syntax here as (function argument1 ... argumentn) where function can be also special operator like lambda here to denote one lambda expression).

(call/cc (lambda (throw) (+ 5 (* 10 (call/cc (lambda (escape) (* 100 (throw 3)))))))) ; 3 

When (call/cc (lambda (throw) ...)) is run, proc(throw) is run. Then (throw 3) will do raise ball which is one exception so that is directly caught by except RuntimeWarning as w: part of the 1st call/cc. This implicitly implements the continuation and uses Exception to pass the value around.

relation with coroutine

In Scheme (probably also for other Lisp dialect with first-class continuation), coroutine can be implemented by call/cc which is also said by wikipedia. c2 wiki has one such implementation but that is wrong because it will fail for some cases where yield doesn't yield back to the call with the same caller's caller.

For example you can use

(= (test-coroutine-1) 2) ;Value: #f (= (test-coroutine-1) 1) ;Value: #t 

where both should return #f since (test-coroutine-1) returns 1 and then 2.

I tried to fix that problem, but when we call (test-coroutine-1) the 2nd time, it will call next book-kept before. I don't know how to change the binding related with continuation (especially yield inside next continuation) at least in MIT/GNU Scheme. The problem is that when coroutine is executed the 2nd time, (current returner) is actually running (next-stored-before new-returner) which won't update the returner at all which then will use the old and maybe wrong return (sometimes this will work if return is not in one nested caller env).

Shawn gives one useful comment here. Its implementation uses one simple idea to solve the above problem, i.e. similar to current above we also make return available to all calls of that coroutine by env. next in c2 wiki functions same as resume here.

;; almost same as https://github.com/scheme-requests-for-implementation/srfi-158/blob/32aed996ecc98680c65848c54f23121adb1ba692/srfi-158-impl.scm#L77-L87 ;; from https://git.savannah.gnu.org/cgit/mit-scheme.git/tree/src/runtime/generator.scm#n135 (define (make-coroutine-generator proc) (let ((return #f) (resume #f)) (define (yield v) (call/cc (lambda (k) (set! resume k) (return v)))) (lambda () (call/cc (lambda (cc) (set! return cc) (if resume (resume unspecific) (begin (proc yield) (set! resume (lambda (v) (declare (ignore v)) (return (eof-object)))) (return (eof-object)) ))))))) 

We need to do (set! resume ...) after (proc yield) to ensure as srfi-158 says:

If proc returns, it is the end of the sequence g returns an end-of-file object from then on

Here the last (return (eof-object)) needs return since in the env after finishing calling (proc yield), return may have been modified.