A relational model of types-and-effects in higher-order concurrent separation logic
Authors:
Open Access
- 1 January 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 218-231
Abstract
Recently we have seen a renewed interest in programming languages that tame the complexity of state and concurrency through refined type systems with more fine-grained control over effects. In addition to simplifying reasoning and eliminating whole classes of bugs, statically tracking effects opens the door to advanced compiler optimizations. In this paper we present a relational model of a type-and-effect system for a higher-order, concurrent program- ming language. The model precisely captures the semantic invariants expressed by the effect annotations. We demonstrate that these invariants are strong enough to prove advanced program transformations, including automatic parallelization of expressions with suitably disjoint effects. The model also supports refinement proofs between abstract data types implementations with different internal data representations, including proofs that fine-grained concurrent algorithms refine their coarse-grained counterparts. This is the first model for such an expressive language that supports both effect-based optimizations and data abstraction. The logical relation is defined in Iris, a state-of-the-art higher-order concurrent separation logic. This greatly simplifies proving well-definedness of the logical relation and also provides us with a powerful logic for reasoning in the model.Keywords
This publication has 28 references indexed in Scilit:
- Proof-Directed Parallelization Synthesis by Separation LogicACM Transactions on Programming Languages and Systems, 2013
- A kripke logical relation for effect-based program transformations2011
- Logical Step-Indexed Logical RelationsLogical Methods in Computer Science, 2011
- State-dependent representation independenceACM SIGPLAN Notices, 2009
- Automatic Parallelization with Separation Logic2009
- Relational semantics for effect-based program transformations with dynamic allocation2007
- A logic for parametric polymorphism2006
- Reading, Writing and RelationsLecture Notes in Computer Science, 2006
- L3: A Linear Language with Locations2005
- Alias Types2000