Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
A Generic Approach to Flow-Sensitive Polymorphic Effects (Extended Version)
arXiv (Cornell University)
05 May 2017
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
lattice 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 a clear 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
order-sensitive 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 effect quantales provide 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 order-sensitive effect systems, which provides
guidance on non-obvious points of designing order-sensitive effect systems.
Effect quantales have clear relationships to the recent category theoretic work
on order-sensitive effect systems, but are explained without recourse to
category theory. In addition, our derived iteration construct should generalize
to these semantic structures, addressing limitations of that work.
Metrics
6 Record Views
Details
- Title
- A Generic Approach to Flow-Sensitive Polymorphic Effects (Extended Version)
- Creators
- Colin S Gordon
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021868093204721