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 |