A *contextual effects* system generalizes standard type
and effect systems: where a standard effects system computes the
effect of an expression *e*, a contextual effects system
additionally computes the *prior* and *future* effect of
*e*, which characterize the behavior of computation prior to, and
following, respectively, the evaluation of *e*. This paper
describes the formalization and proof of soundness of contextual
effects, which we mechanized using the Coq proof assistant.
Contextual effect soundness is an unusual property because the prior
and future effect of a term *e* depends not on *e* itself (or its
evaluation), but rather on the evaluation of the context in which
*e* appears. Therefore, to state and prove soundness we must
``match up'' a subterm in the original typing derivation with the
possibly-many evaluations of that subterm during the evaluation of
the program, in a way that is robust under substitution. We do this
using a novel typed operational semantics. We conjecture that our
approach could prove useful for approaching other properties of
derivations that rely on the context in which that derivation
appears.

[ .pdf ]

@INPROCEEDINGS{pratikakis08context, AUTHOR = {Polyvios Pratikakis and Jeffrey S. Foster and Michael Hicks and Iulian Neamtiu}, TITLE = {Formalizing Soundness of Contextual Effects}, BOOKTITLE = {Proceedings of the International Conference on Theorem Proving in Higher Order Logics (TPHOLs)}, EDITOR = {Otmane A\"it Mohamed and C\'esar Mu\={n}oz and Sofi\`ene Tahar}, PAGES = {262--277}, PUBLISHER = {Springer}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {5170}, MONTH = AUG, YEAR = 2008 }