Trustworthy Systems

On CSP and the algebraic theory of effects

Authors

Rob van Glabbeek and Gordon Plotkin

NICTA

UNSW

University of Edinburgh

Abstract

We consider CSP from the point of view of the algebraic theory of effects, which classifies operations as effect constructors or effect deconstructors; it also provides a link with functional programming, being a refinement of Moggi's seminal monadic point of view. Constructors form the signature of a natural algebraic theory whose free algebra functor is Moggi's monad; we illustrate this by characterising free and initial algebras in terms of two versions of the stable failures model of CSP, one more general than the other. Deconstructors are dealt with as homomorphisms to (possibly non-free) algebras. One can view CSP's action and choice operations as constructors and the rest, such as concealment and concurrency, as deconstructors. Carrying this programme out results in taking deterministic external choice as constructor rather than general external choice. However, binary deconstructors, such as the CSP concurrency operation, provide unresolved difficulties. We conclude by presenting a combination of CSP with Moggi's computational lambda-calculus, in which the operations, including concurrency, are polymorphic. While the paper mainly concerns CSP, it ought to be possible to carry over similar ideas to other process calculi.

BibTeX Entry

  @inbook{vanGlabbeek_Plotkin_10,
    address          = {London Dordrecht Heidelberg New York},
    author           = {van Glabbeek, Robert and Plotkin, Gordon},
    booktitle        = {Reflections on the Work of C.A.R. Hoare},
    editor           = {{Cliff B. Jones, A.W. Roscoe \& Kenneth R. Wood}},
    isbn             = {978-1-84882-911-4},
    keywords         = {concurrency, functional programming, computational lambda-calculus, free algebras, (de)constructors,
                        stable failures model},
    month            = sep,
    pages            = {333--369},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/3656.pdf},
    publisher        = {Springer},
    series           = {History of Computing},
    title            = {On {CSP} and the Algebraic Theory of Effects},
    volume           = { },
    year             = {2010}
  }

Download