Logical Step-Indexed Logical Relations
Authors:
- Derek DreyerDDDerek Dreyer
- Amal AhmedAAAmal Ahmed
- Lars BirkedalLBLars Birkedal
Open Access
- 7 June 2011
- journal article
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 7, Iss
Abstract
Appel and McAllester's "step-indexed" logical relations have proven to be a simple and effective technique for reasoning about programs in languages with semantically interesting types, such as general recursive types and general reference types. However, proofs using step-indexed models typically involve tedious, error-prone, and proof-obscuring step-index arithmetic, so it is important to develop clean, high-level, equational proof principles that avoid mention of step indices. In this paper, we show how to reason about binary step-indexed logical relations in an abstract and elegant way. Specifically, we define a logic LSLR, which is inspired by Plotkin and Abadi's logic for parametricity, but also supports recursively defined relations by means of the modal "later" operator from Appel, Melli\`es, Richards, and Vouillon's "very modal model" paper. We encode in LSLR a logical relation for reasoning relationally about programs in call-by-value System F extended with general recursive types. Using this logical relation, we derive a set of useful rules with which we can prove contextual equivalence and approximation results without counting steps.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Biorthogonality, step-indexing and compiler correctness2009
- State-dependent representation independenceACM SIGPLAN Notices, 2009
- Imperative self-adjusting computation2008
- A very modal model of a modern, major, general type system2007
- Step-Indexed Syntactic Logical Relations for Recursive and Quantified Types2006
- Syntactic considerations on recursive types2002
- Operational Properties of Lily, a Polymorphic Linear Lambda Calculus with RecursionElectronic Notes in Theoretical Computer Science, 2001
- An indexed model of recursive types for foundational proof-carrying codeACM Transactions on Programming Languages and Systems, 2001
- Relational Interpretations of Recursive Types in an Operational SettingInformation and Computation, 1999
- Formal parametric polymorphismTheoretical Computer Science, 1993