ﻻ يوجد ملخص باللغة العربية
Appel and McAllesters 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 Abadis logic for parametricity, but also supports recursively defined relations by means of the modal later operator from Appel, Melli`es, Richards, and Vouillons 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.
It is well-known that constructing models of higher-order probabilistic programming languages is challenging. We show how to construct step-indexed logical relations for a probabilistic extension of a higher-order programming language with impredicat
The theory of program modules is of interest to language designers not only for its practical importance to programming, but also because it lies at the nexus of three fundamental concerns in language design: the phase distinction, computational effe
Stone-type dualities provide a powerful mathematical framework for studying properties of logical systems. They have recently been fruitfully explored in understanding minimisation of various types of automata. In Bezhanishvili et al. (2012), a dual
While quantum computers are expected to yield considerable advantages over classical devices, the precise features of quantum theory enabling these advantages remain unclear. Contextuality--the denial of a notion of classical physical reality--has em
Logical relations are one of the most powerful techniques in the theory of programming languages, and have been used extensively for proving properties of a variety of higher-order calculi. However, there are properties that cannot be immediately pro