Journal article
Polymorphic Iterable Sequential Effect Systems
ACM transactions on programming languages and systems, v 43(1), pp 1-79
01 Apr 2021
Featured in Collection : UN Sustainable Development Goals @ Drexel
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 structure on effects.
We present an abstract polymorphic effect system parameterized by an effect quantale-an algebraic structure with well-defined properties that can model the effects of 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 an induced notion of iterating a sequential effect; that for systems we consider the derived iteration agrees with the manually designed iteration operators in prior work; and that this induced notion of iteration is as precise as possible when defined. 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 the course of giving a thorough survey of these frameworks. Our derived iteration construct should generalize to these semantic structures, addressing limitations of that work. Finally, we consider the relationship between sequential effects and Kleene Algebras, where the latter may be used as instances of the former.
Metrics
Details
- Title
- Polymorphic Iterable Sequential Effect Systems
- Creators
- Colin S. Gordon - Drexel University
- Publication Details
- ACM transactions on programming languages and systems, v 43(1), pp 1-79
- Publisher
- Assoc Computing Machinery
- Number of pages
- 79
- Grant note
- 2007582 / NSF; National Science Foundation (NSF)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000646399300004
- Scopus ID
- 2-s2.0-85104934923
- Other Identifier
- 991019168327504721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Software Engineering