s c h e m a t i c s : c o o k b o o k

/ Cookbook.CoRoutines

This Web


WebHome 
WebChanges 
TOC (with recipes)
NewRecipe 
WebTopicList 
WebStatistics 

Other Webs


Chicken
Cookbook
Erlang
Know
Main
Plugins
Sandbox
Scm
TWiki  

Schematics


Schematics Home
Sourceforge Page
SchemeWiki.org
Original Cookbook
RSS

Scheme Links


Schemers.org
Scheme FAQ
R5RS
SRFIs
Scheme Cross Reference
PLT Scheme SISC
Scheme48 SCM
MIT Scheme scsh
JScheme Kawa
Chicken Guile
Bigloo Tiny
Gambit LispMe
GaucheChez

Lambda the Ultimate
TWiki.org

Coroutines

Problem

In some cases it is desirable to transform a procedure that returns a table (a list, vector or list of lists and so on) into a procedure that returns one element each time it is called. The reason may be that it is not beforehand known how many of the elements actually will be needed. Another reason may be that the table potentially is infinite. A trivial example is:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Notice that (define inf-counter (make-counter +inf.0)) produces an endless counter, although there are more elegant methods to construct such a counter.

In non trivial cases the problem of converting a list-producer into an element-by-element-producer is located in capturing the internal state of the list-producer in order to make known what has already been done and particularly what is still left to be done. In some cases one or more local variables may be sufficient (as in the case of the above counter), but in other cases, a more sophisticated method is required, particularly if the elements to be produced are interconnected by one or more levels of recursive relations. The most general method of capturing the internal state of a procedure is by capturing the continuation of the current stage of the computation. The procedure should 'replace itself' by this continuation right before returning each next element. Such a procedure is called a coroutine. Another approach is the use of streams. This approach is not treated in this recipe.

Rationale

Section 9.4 of EOPL provides an excellent introduction into the concept of coroutines. This recipe is meant to be a simpler introduction by using a slightly different approach. Moreover the examples in this recipe are in PLT Scheme (#lang scheme) whereas those of EOPL are in EOPL's own language.

Solution

A coroutine needs four things:

We start with a very simple example: a coroutine that returns the numbers 0, 1 and 2 and refuses to be called more than three times.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

The procedures return and coroutine resemble each other very much. In fact when we give procedure coroutine an argument, say resume-value, we have a perfect symmetry:

variables procedures arguments
entry coroutine resume-value
exit return return-value

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

The arguments first-resume-value and resume-value are not used, but will appear to be useful in one of the examples to follow. Notice that always at least one of the variables entry and exit is outdated. When the coroutine is called, variable exit is updated, but the content of variable entry becomes obsolete as soon as the continuation it contains has been called. When the coroutine returns, variable entry is updated and the exit becomes obsolete immediately after being called. Hence we can use one shared variable for the entry and the exit. We shall call it local-state.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Now the two procedures return and coroutine have become alpha-congruent. Hence we need only one of them. We shall call it toggle, because it toggles control between the caller of the coroutine and the coroutine itself.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

It is important that the procedure proper does not return normally. It must always return using procedure toggle. If the procedure proper would be allowed to return normally, control would be passed to the continuation of the first coroutine call probably leading to another call of the coroutine and possibly causing an infite loop. But there is a nicer way to finish. In most cases it is desirable that the procedure proper returns a special value indicating that it must no longer be called. Yet the coroutine must disable itself after finishing in order to prevent problems if by mistake the coroutine would be called after having expired. This will be done by procedure finish:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Now it is time to prepare a procedure that given a proc-maker, id est a procedure that returns the procedure-proper, constructs a procedure that returns a coroutine-constr, i.e. a procedure that produces specimens of a certain species of coroutines.

Procedure call Returned value(s) Remarks
(make-coroutine-constr proc-maker finisher) -> coroutine-constr  
(proc-maker return finish constr-arg ...) -> procedure-proper the constr-args are those given to the coroutine-constr
(finisher last-return-value ...) -> adapted-last-return-value ... the last-return-values are those given to proceure finish
(procedure-proper first-resume-value ...) -> any ...  
(coroutine-constr constr-arg ...) -> coroutine constructor-call
(return return-value ...) -> resume-value ... return-call
(finish last-return-value ...) never returns finish-call
(coroutine resume-value ...) -> return-value ... coroutine-call

The proc-maker may require data to be processed, but it also requires the procedures toggle and finish. Therefore the proc-maker shall have the arguments toggle and finish possibly followed by more arguments for data that are provided during the construction of the coroutine. Procedure make-coroutine-constr, shown below, has been generalized for multiple resume and return values. A call to procedure finish is implied after normal return from the procedure proper, receiving the value(s) returned by the procedure proper. Procedure make-coroutine-constr takes two arguments, the procedure proper and a terminator. The latter is a procedure that is called by procedure finish with the last return values. Whatever is returned by the terminator is returned to the caller of the coroutine after the coroutine has disabled itself.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

A coroutine is too heavy a tool for a counter, but, for its simplicity, let's take a coroutine that conses a count to its resume-value. After a predetermined number of calls the coroutine expires while returning #f.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Coroutines are not necessarily mortal, e.g. as produced by replacing (>= i limit) by #f in the sixth line of the definition of make-consing-counter.

A more realistic example: coroutines for permutations of lists.

This example also shows that coroutines may employ other coroutines, even those of their own species. We start from a list-producing version:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

The accumulated number of cycles of the loop of procedure find-rotation made during one cycle of the loop of procedure list-permutations usually is greater than the length of the list to be permuted. This is not optimal, of course. There are several ways to prevent unnecessary cycles, but they are not shown here, because this problem is not the subject of this recipe and because conversion of procedure find-rotation into a coroutine automatically prevents the rotator from making unnecessary cycles. Conversion into a coroutine:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

Procedure list-permutations (the list-producer) necessarily allocates separate storage for each permutation. So does the element by element producer permute-aabc. Procedures make-permuter and make-rotator can easily be adapted such as to do the permutations in situ (destructively) requiring less memory, less garbage collection and less processor time. However, only one permutation will be available at any given moment. Below procedure make-rotator is replaced by procedure make-exchanger, whose coroutines exchange the first element of the list to be permuted with one of the other elements (the first time with itself). Therefore the permutations may appear in another order. The list given to make-permuter must be mutable.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

The procedures made by make-permuter and make-exchanger do not return lists, because the list is always in variable list-to-be-permuted. They return #t as long as a new permutation cq. new exchange has been found and #f while expiring. As a test:

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)

When a coroutine calls a continuation of its caller or reversely

When the procedure proper bypasses the toggler and calls a continuation pointing into the caller of the coroutine, contact between the coroutine and its caller is lost because the caller becomes part of the procedure proper. When the caller bypasses the toggler and calls a continuation pointing into the procedure proper, contact between the coroutine and its caller is lost because the procedure proper becomes part of the caller. All continuations always see the most recently stored local state. This state does not make explicit which one is supposed to have control, the caller or the coroutine. Contact can be reestablished though. E.g, if the procedure proper calls a continuation pointing into the caller, contact can be reestablished by making the caller call a continuation pointing into the procedure proper, assuming such a continuation has been made available to the caller.

If a procedure proper tries to call the coroutine it belongs to

If the procedure proper tries to call the coroutine it is part of, the toggler in fact returns control to the caller. Likewise, if the caller tries to call the returner of a coroutine, the toggler in fact returns control to the coroutine. Because this may lead to confusion and to errors that cannot easily be traced, it may be desirable to adapt procedure make-coroutine-constr such as to prohibit the procedure proper from calling the coroutine it belongs to and to prohibit the caller from calling the returner. This can be done in several ways, for instance by maintaining two separate procedures for the coroutine and its returner and adding a variable, say control-state, in which is recorded who is supposed to be in control, the caller or the coroutine. This does not prevent the procedure proper from being recursive.

500 Can't connect to 127.0.0.1:8778 (connect: Connection refused)


Comments about this recipe

Very welcome.

Contributors

-- JosKoot - 27 Aug 2006, last update: April 22, 2009.

Source code

Last tested with : DrScheme, version 4.1.5.4-svn19apr2009 [3m].

All examples included in this recipe can be found in: cookbookcoroutines.scm:

CookbookForm
TopicType: Recipe
ParentTopic: IdiomRecipes
TopicOrder: 999

Attachment: Action: Size: Date: Who: Comment:
cookbookcoroutines.scm action 13120 21 Apr 2009 - 11:40 JosKoot  

 
 
Copyright © 2004 by the contributing authors. All material on the Schematics Cookbook web site is the property of the contributing authors.
The copyright for certain compilations of material taken from this website is held by the SchematicsEditorsGroup - see ContributorAgreement & LGPL.
Other than such compilations, this material can be redistributed and/or modified under the terms of the GNU Lesser General Public License (LGPL), version 2.1, as published by the Free Software Foundation.
Ideas, requests, problems regarding Schematics Cookbook? Send feedback.
/ You are Main.guest