Polymorphic Iterable Sequential Effect Systems

Gordon, Colin S.

ACM Transactions on Programming Languages and Systems (TOPLAS), volume 43, number 1, April 2021, doi: 10.1145/3450272

Abstract

Effect systems are lightweight extensions to type systems that can verify a wide range of important properties with modest developer burden. But our general understanding of effect systems is limited primarily to systems where the order of effects is irrelevant. Understanding such systems in terms of a semilattice of effects grounds understanding of the essential issues, and provides guidance when designing new effect systems. By contrast, sequential effect systems --- where the order of effects is important --- lack an established algebraic characterization. We derive an algebraic characterization from the shape of prior concrete sequential effect systems. We present an abstract polymorphic effect system with singleton effects parameterized by an effect quantale --- an algebraic structure with well-defined properties that can model a range of existing sequential effect systems. We define effect quantales, derive useful properties, and show how they cleanly model a variety of known sequential effect systems. We show that for most effect quantales, there is a free, general notion of iterating a sequential effect, and that for systems we consider the derived iteration agrees with the manually designed iteration operators in prior work. Identifying and applying the right algebraic structure led us to subtle insights into the design of sequential effect systems, which provides guidance on non-obvious points of designing sequential effect systems. We also position effect quantales with respect to work on categorical semantics for sequential effect systems, clarifying the distinctions between these systems and our own. In addition, our derived iteration construct should generalize to these semantic structures, addressing limitations of that work.

Bibtex

@article{toplas21,
  abbr = {TOPLAS},
  bibtex_show = {true},
  author = {Gordon, Colin S.},
  title = {{Polymorphic Iterable Sequential Effect Systems}},
  year = 2021,
  institution = {{Computing Research Repository (Corr)}},
  eprint = {1808.02010},
  volume={43},
  month={April},
  number={1},
  articleno={4},
  archivePrefix={arXiv},
  primaryClass={cs.PL},
  url = {https://arxiv.org/abs/1808.02010},
  arxiv = {1808.02010},
  acm = {https://dl.acm.org/doi/abs/10.1145/3450272},
  journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)},
  doi = {10.1145/3450272},
  selected={true},
  pdf = {papers/toplas21.pdf},
  abstract = {Effect systems are lightweight extensions to type systems that can verify a wide range of important properties with modest developer burden. But our general understanding of effect systems is limited primarily to systems where the order of effects is irrelevant. Understanding such systems in terms of a semilattice of effects grounds understanding of the essential issues, and provides guidance when designing new effect systems. By contrast, sequential effect systems --- where the order of effects is important --- lack an established algebraic characterization. 

We derive an algebraic characterization from the shape of prior concrete sequential effect systems. We present an abstract polymorphic effect system with singleton effects parameterized by an effect quantale --- an algebraic structure with well-defined properties that can model a range of existing sequential effect systems. We define effect quantales, derive useful properties, and show how they cleanly model a variety of known sequential effect systems. We show that for most effect quantales, there is a free, general notion of iterating a sequential effect, and that for systems we consider the derived iteration agrees with the manually designed iteration operators in prior work. Identifying and applying the right algebraic structure led us to subtle insights into the design of sequential effect systems, which provides guidance on non-obvious points of designing sequential effect systems. We also position effect quantales with respect to work on categorical semantics for sequential effect systems, clarifying the distinctions between these systems and our own. In addition, our derived iteration construct should generalize to these semantic structures, addressing limitations of that work.}
}