Revisiting coroutines

ABSTRACT

This article advocates the revival of coroutines as a convenient general control abstraction. After proposing a new classification of coroutines, we introduce the concept of full asymmetric coroutines and provide a precise definition for it through an operational semantics. We then demonstrate that full coroutines have an expressive power equivalent to one-shot continuations and one-shot delimited continuations. We also show that full asymmetric coroutines and one-shot delimited continuations have many similarities, and therefore present comparable benefits. Nevertheless, coroutines are easier implemented and understood, especially in the realm of procedural languages.

REFERENCES

• 1: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 2: Rob von Behren , Jeremy Condit , Eric Brewer, Why events are a bad idea (for high-concurrency servers), Proceedings of the 9th conference on Hot Topics in Operating Systems, p.4-4, May 18-21, 2003, Lihue, Hawaii
• 3: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 4: Carl Bruggeman , Oscar Waddell , R. Kent Dybvig, Representing control in the presence of one-shot continuations, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.99-107, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 5: W. F. Clocksin , C. S. Mellish, Programming in Prolog, Springer-Verlag New York, Inc., New York, NY, 1987
• 6: Conway, D. 2000. Rfc 31: Subroutines: Co-routines. http://dev.perl.org/perl6/rfc/31.html.
• 7: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 8: Ole-Johan Dahl , C. A. R. Hoare, Chapter III: Hierarchical program structures, Structured programming, Academic Press Ltd., London, UK, 1972
• 9: Olivier Danvy , Andrzej Filinski, Abstracting control, Proceedings of the 1990 ACM conference on LISP and functional programming, p.151-160, June 27-29, 1990, Nice, France [doi>10.1145/91556.91622]
• 10: R. K. Dybvig , R. Hieb, Engines from continuations, Computer Languages, v.14 n.2, p.109-123, Aug. 1989 [doi>10.1016/0096-0551(89)90018-0]
• 11: Felleisen, M. 1985. Transliterating Prolog into Scheme. Tech. rep. 182, Indiana University.
• 12: Mattias Felleisen, The theory and practice of first-class prompts, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.180-190, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73576]
• 13: Matthias Felleisen, On the Expressive Power of Programming Languages, Proceedings of the 3rd European Symposium on Programming, p.134-151, May 15-18, 1990
• 14: Felleisen, M. and Friedman, D. 1986. Control operators, the SECD-machine, and the λ-calculus. In Formal Description of Programming Concepts-III, M. Wirsing, Ed. North-Holland, 193--217.
• 15: Ralph E. Griswold , Madge T. Griswold, ICON Programmng Language, Prentice Hall Professional Technical Reference, 1983
• 16: Bruce Duba , Robert Harper , David MacQueen, Typing first-class continuations in ML, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99608]
• 17: Christopher T. Haynes, Logic continuations, Journal of Logic Programming, v.4 n.2, p.157-176, June 1, 19876 [doi>10.1016/0743-1066(87)90016-1]
• 18: Christopher T. Haynes , Daniel P. Friedman, Abstracting timed preemption with engines, Computer Languages, v.12 n.2, p.109-121, Aug. 1987 [doi>10.1016/0096-0551(87)90003-8]
• 19: Christopher T Haynes , Daniel P Friedman , Mitchell Wand, Obtaining coroutines with continuations, Computer Languages, v.11 n.3-4, p.143-153, 1986 [doi>10.1016/0096-0551(86)90007-X]
• 20: Christopher T. Haynes , Daniel P. Friedman, Embedding continuations in procedural objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.582-598, Oct. 1987 [doi>10.1145/29873.30392]
• 21: R. Hieb , R. Kent Dybvig, Continuations and concurrency, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.128-136, March 14-16, 1990, Seattle, Washington, United States
• 22: Robert Hieb , R. Kent Dybvig , Claude W. Anderson, III, Subcontinuations, Lisp and Symbolic Computation, v.7 n.1, p.83-110, Jan. 1994 [doi>10.1007/BF01019946]
• 23: Roberto Ierusalimschy, Programming in Lua, Second Edition, Lua.Org, 2006
• 24: Ierusalimschy, R. and de Moura, A. L. 2008. Some proofs about coroutines. Monografias em Ciẽncia da Computação 04/08, PUC-Rio, Rio de Janeiro, Brazil.
• 25: Roberto Ierusalimschy , Luiz Henrique de Figueiredo , Waldemar Celes Filho, Lua—an extensible extension language, Software—Practice & Experience, v.26 n.6, p.635-652, June 1996 [doi>10.1002/(SICI)1097-024X(199606)26:6<635::AID-SPE26>3.0.CO;2-P]
• 26: G. F. Johnson , D. Duggan, Stores and partial continuations as first-class objects in a language and its environment, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.158-168, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73574]
• 27: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 28: Knuth, D. E. 1968. The Art of Computer Programming, Volume 1, Fundamental Algorithms. Addison-Wesley, Reading, MA.
• 29: Sanjeev Kumar , Carl Bruggeman , R. Kent Dybvig, Threads Yield Continuations, Lisp and Symbolic Computation, v.10 n.3, p.223-236, May 1998 [doi>10.1023/A:1007782300874]
• 30: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 31: Christopher D. Marlin, Coroutines, Springer-Verlag New York, Inc., Secaucus, NJ, 1980
• 32: Moody, K. and Richards, M. 1980. A coroutine mechanism for BCPL. Softw. Pract. & Exper. 10, 10, 765--771.
• 33: Moura, A., Rodriguez, N., and Ierusalimschy, R. 2004. Coroutines in Lua. J. Universal Comput. Sci. 10, 7, 910--925.
• 34: Stephan Murer , Stephen Omohundro , David Stoutamire , Clemens Szyperski, Iteration abstraction in Sather, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.1, p.1-15, Jan. 1996 [doi>10.1145/225540.225541]
• 35: Pauli, W. and Soffa, M. L. 1980. Coroutine behaviour and implementation. Softw, Pract. & Exper. 10, 3, 189--204.
• 36: Christian Queinnec , Bernard Serpette, A dynamic extent control operator for partial continuations, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.174-184, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99610]
• 37: Jeffrey Richter, Advanced Windows (3rd ed.), Microsoft Press, Redmond, WA, 1996
• 38: Schemenauer, N., Peters, T., and Hetland, M. 2001. PEP 255: Simple generators. http://www.python.org/peps/pep-0255.html.
• 39: Manuel Serrano , Frédéric Boussinot , Bernard Serpette, Scheme fair threads, Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.203-214, August 24-26, 2004, Verona, Italy [doi>10.1145/1013963.1013986]
• 40: Dorai Sitaram, Handling control, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.147-155, June 21-25, 1993, Albuquerque, New Mexico, United States
• 41: Dorai Sitaram, Models of control and their implications for programming language design, Rice University, Houston, TX, 1994
• 42: George Springer , Daniel P. Friedman, Scheme and the art of programming, MIT Press, Cambridge, MA, 1989
• 43: Tismer, C. 2000. Continuations and stackless Python. In Proceedings of the 8th International Python Conference. Arlington, VA. http://www.python.org/workshops/2000-01/proceedings.html.
• 44: Mitchell Wand, Continuation-Based Multiprocessing, Higher-Order and Symbolic Computation, v.12 n.3, p.285-299, October 1999 [doi>10.1023/A:1010093700911]
• 45: Mitchell Wand , Dale Vaillancourt, Relating models of backtracking, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 46: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Coroutines

General Terms:
Design, Languages

Keywords:
Continuations, generators, multitasking