Archive for the 'Logics' Category

Higher-order representations of substructural logics

Now I’ve settled in to Italy (and my new job), it’s time to resurrect the blog.

By Karl Crary, from ICFP 2010, available from Karl Crary’s website:

We present a technique for higher-order representation of substructural logics such as linear or modal logic. We show that such logics can be encoded in the (ordinary) Logical Framework, without any linear or modal extensions. Using this encoding, metatheoretic proofs about such logics can easily be developed in the Twelf proof assistant.

Associated Twelf code can be found here.


A logic for reasoning with higher-order abstract syntax

By Raymond McDowell and Dale Miller, from LICS 1997, available from Dale Miller’s website:

Logical frameworks based on intuitionistic or linear logics with higher-type quantification have been successfully used to give high-level, modular, and formal specifications of many important judgments in the area of programming languages and inference systems. Given such specifications, it is natural to consider proving properties about the specified systems in the framework: for example, given the specification of evaluation for a functional programming language, prove that the language is deterministic or that the subject-reduction theorem holds. One challenge in developing a framework for such reasoning is that higher-order abstract syntax (HOAS), an elegant and declarative treatment of object-level abstraction and substitution, is difficult to treat in proofs involving induction. In this paper, we present a meta-logic that can be used to reason about judgments coded using HOAS; this meta-logic is an extension of a simple intuitionistic logic that admits higher-order quantification over simply typed lambda-terms (key ingredients for HOAS) as well as induction and a notion of definition. The latter concept of a definition is a proof-theoretic device that allows certain theories to be treated as “closed” or as defining fixed points. The resulting meta-logic can specify various logical frameworks and a large range of judgments regarding programming languages and inference systems. We illustrate this point through examples, including the admissibility of cut for a simple logic and subject reduction, determinacy of evaluation, and the equivalence of SOS and natural semantics presentations of evaluation for a simple functional programming language.

Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables

By Murdoch J. Gabbay and Dominic P. Mulligan, from LFMTP 2009, available from Murdoch J. Gabbay’s website:

This paper develops the correspondence between equality reasoning with axioms using λ-terms syntax, and reasoning using nominal terms syntax. Both syntaxes involve name-abstraction: λ-terms represent functional abstraction; nominal terms represent atomsabstraction in nominal sets.

It is not evident how to relate the two syntaxes because their intended denotations are so different. We use universal algebra, the logic of equational reasoning, a logical foundation based on an equality judgement form which is spartan but which is sufficiently expressive to encode mathematics in theory and practice.

We investigate how syntax, algebraic theories, and derivability relate across λ-theories (algebra over λ-terms) and nominal algebra theories.

Nominal logic, a first-order theory of names and binding

Andrew Pitts, from the Journal of Information and Computation, available from Andrew Pitts’s website:

This paper formalises within first-order logic some common practices in computer science to do with representing and reasoning about syntactical structures involving lexically scoped binding constructs. It introduces Nominal Logic, a version of first-order many-sorted logic with equality containing primitives for renaming via name-swapping, for freshness of names, and for name-binding. Its axioms express properties of these constructs satisfied by the FM-sets model of syntax involving binding, which was recently introduced by the author and M.J. Gabbay and makes use of the Fraenkel-Mostowski permutation model of set theory. Nominal Logic serves as a vehicle for making two general points. First, name-swapping has much nicer logical properties than more general, non-bijective forms of renaming while at the same time providing a sufficient foundation for a theory of structural induction/recursion for syntax modulo α-equivalence. Secondly, it is useful for the practice of operational semantics to make explicit the equivariance property of assertions about syntax – namely that their validity is invariant under name-swapping.

On the role of names in reasoning about lambda-tree syntax specifications

Alwen Tiu, from LFMTP 2008, available from Alwen Tiu’s website.

Lambda tree syntax (a variant of HOAS) and nominal techniques are two approaches to representing and reasoning about languages containing bindings. Although they are based on separate foundations, recent advances in the proof theory of generic judgments have shown that one may be able to incorporate some aspects of nominal techniques (i.e., the equivariant principle) to simplify reasoning about λ-tree syntax specifications, while still maintaining the crucial aspects of λ-tree syntax. In this paper, we present a logic, called LGnω , which incorporates a notion of generic judgments and equivariant reasoning. The logic LGnω is a simple extension of a logic called LGω by Tiu, and can be seen as a special case of the logic G by Gacek, Miller and Nadathur. A central idea of LGnω is the representation of a data type for names (represented by a predicate). Although the data type is inhabited by infinitely many elements, the judgments of the logic only ever use finitely many of them, and more importantly, validity of these judgments are preserved under arbitrary permutation of names, i.e., they are equivariant judgments. This finite support of judgments allows for tractable introduction rules of the name predicate. We illustrate with two examples how this simple extension can be used for reasoning about specifications involving bindings. In the first example, we show how one can represent the data type for λ-terms, and derive a structural induction principle for inductive reasoning over λ-terms. In the second example, we re-examine previous known encodings of open and late bisimulations for the π-calculus. We show that the difference between open and late bisimulation can be characterized by the choice of the encodings of names: the “untyped” version (for the former) versus the “typed” one (for the latter).

Binding logic

Gilles Dowek, Thérèse Hardin and Claude Kirchner, from LPAIR 2002, long version available at Gilles Dowek’s website:

We define an extension of predicate logic, called Binding Logic, where variables can be bound in terms and in propositions. We introduce a notion of model for this logic and prove a soundness and completeness theorem for it. This theorem is obtained by encoding this logic back into predicate logic and using the classical soundness and
completeness theorem there.