A calculus of coroutines

Laird, James (2006) A calculus of coroutines. Theoretical Computer Science, 350 (2-3). pp. 275-291. ISSN 03043975

Full text not available from this repository.

Abstract

We describe a simple but expressive calculus of sequential processes, represented as coroutines. We show that this calculus can be used to express a variety of programming language features including 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 latter into our calculus of coroutines.

Item Type: Article
Schools and Departments: School of Engineering and Informatics > Informatics
Depositing User: James David Laird
Date Deposited: 06 Feb 2012 19:39
Last Modified: 07 Jun 2012 11:39
URI: http://sro.sussex.ac.uk/id/eprint/21695
📧 Request an update