A calculus of coroutines

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Citations (Scopus)

Abstract

We describe a simple but expressive calculus of sequential processes, which are represented as coroutines. This calculus can be used to express a variety of programming language features; we give simple macros for procedure calls, labelled jumps, integer references and stacks. We describe the operational properties of the calculus using reduction rules and equational axioms. We describe a notion of categorical model for our calculus, and give a simple example of such a model based on a category of games and strategies. We prove full abstraction results showing that equivalence in the categorical model corresponds to observational equivalence in the calculus, and also to equivalence of evaluation trees, which are infinitary normal forms for the calculus. We show that our categorical model can be used to interpret the untyped λ-calculus and use this fact to extract a sound translation of the λ-calculus into our calculus of coroutines.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication Proceedings of 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004.
EditorsJ. Diaz, J. Karhumaki, A. Lepisto, D. Sannella
Place of PublicationBerlin, Germany
PublisherSpringer Verlag
Pages882-893
Number of pages12
ISBN (Print)9783540228493
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3142

Fingerprint Dive into the research topics of 'A calculus of coroutines'. Together they form a unique fingerprint.

  • Cite this

    Laird, J. (2004). A calculus of coroutines. In J. Diaz, J. Karhumaki, A. Lepisto, & D. Sannella (Eds.), Automata, Languages and Programming: Proceedings of 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. (pp. 882-893). (Lecture Notes in Computer Science; Vol. 3142). Springer Verlag. https://doi.org/10.1007/978-3-540-27836-8_74