| Publication type: |
Article |
| Author: |
Till Mossakowski, Lutz Schröder, Sergey Goncharov |
| Title: |
A Generic Complete Dynamic Logic for Reasoning about Purity and Effects |
| Volume: |
22 |
| Page(s): |
363 – 384 |
| Journal: |
Formal Aspects of Computing |
| Number: |
3-4 |
| Year published: |
2010 |
| Abstract: |
For a number of programming languages, among them Eiffel, C, Java, and Ruby, Hoare-style logics
and dynamic logics have been developed. In these logics, pre- and postconditions are typically formulated
using potentially effectful programs. In order to ensure that these pre- and postconditions behave like logical
formulae (that is, enjoy some kind of referential transparency), a notion of purity is needed. Here, we introduce a
generic framework for reasoning about purity and effects. Effects are modelled abstractly and axiomatically, using
Moggi’s idea of encapsulation of effects as monads.We introduce a dynamic logic (from which, as usual, a Hoare
logic can be derived) whose logical formulae are pure programs in a strong sense. We formulate a set of proof
rules for this logic, and prove it to be complete with respect to a categorical semantics. Using dynamic logic, we
then develop a relaxed notion of purity which allows for observationally neutral effects such writing on newly
allocated memory. |
| ISSN: |
0934-5043 |
| Internet: |
http://dx.doi.org/10.1007/s00165-010-0153-4 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~lschrode/papers/mdl-compl.pdf |
| Keywords: |
monad logic purity side-effect soundness completeness |
| Status: |
Reviewed |
| Last updated: |
10. 06. 2010 |
|
 |
