ITP on Tuesday, July 13th

09:00‑10:00 FLoC Plenary Talk: Georg Gottlob
Chair: Martin Grohe
Location: George Square Lecture Theatre
09:00 Georg Gottlob (University of Oxford)
Datalog+-: A Family of Logical Query Languages for New Applications.

I will report on a recently introduced family of Datalog-based languages, called Datalog+-, which is a new framework for tractable ontology querying, and for a variety of other applications. Datalog+-extends plain Datalog by features such as existentially quantified rule heads, and, at the same time, restricts the rule bodies so to achieve decidability and tractability. I will review a number of theoretical results and show how Datalog+- relates to both Database Dependency Theory and the Guarded Fragment of first order logic. I will show that popular tractable description logics translate into Datalog+- and illustrate how this formalism can be used in the context of web data extraction, data exchange, and other applications.

10:30‑12:30 Session 7
Chair: Michael Norrish
Location: AT LT5
10:30 Amy Felty and Brigitte Pientka
Reasoning with Higher-Order Abstract Syntax and Contexts: A Comparison

A variety of logical frameworks support the use of higher-order abstract syntax (HOAS) in representing formal systems given via axioms and inference rules and reasoning about them. In such frameworks, object-level binding is encoded directly using meta-level binding. Although these systems seem superficially the same, they differ in a variety of ways; for example, in how hypothetical and parametric reasoning is supported, in how we handle a context of assumptions, in what theorems about a given formal system can be expressed and proven. In this paper, we present several case studies involving properties designed to highlight a variety of different aspects of reasoning using HOAS, with the intention of providing a basis for comparison of different systems. We then carry out such a comparison among three systems: Twelf, Beluga, and Hybrid. We also develop a general set of criteria for comparing such systems. We hope that others will implement these challenge problems, apply these criteria, and further our understanding of the trade-offs involved in choosing one system over another for this kind of reasoning.

11:00 Serge Autexier and Dominik Dietrich
A tactic language for declarative proofs

Influenced by the success of the Mizar system many declarative proof languages have been developed in the theorem prover community, as declarative proofs are more readable, easier to modify and to maintain than their procedural counterparts. However, despite their advantages many users still prefer the procedural style of proof, because procedural proofs are faster to write. In this paper we show how to define a declarative tactic language on top of a declarative proof language. The language comes along with a rich facility to declaratively specify proof states (and conditions on them) in the form of sequent patterns, as well as ellipses (dot notation) to provide a limited form of iteration. As declarative tactics are specified using the declarative proof language, they offer the same advantages as declarative proof languages. At the same time they also produce declarative justifications in form of a declarative proof script and can thus be seen as an attempt to reduce the gap between procedural and declarative proofs.

11:30 Daria Walukiewicz-Chrząszcz and Jacek Chrząszcz
Inductive Consequences in the Calculus of Constructions

Extending the calculus of constructions with rewriting would greatly improve the efficiency of proof assistants such as Coq. In this paper we address the issue of the logical power of such an extension. In our previous work we proposed a procedure to check completeness of user-defined rewrite systems. In many cases this procedure demonstrates that only a basic subset of the rules is sufficient for completeness. Now we investigate the question whether the remaining rules are inductive consequences of the basic subset. We show that the answer is positive for most practical rewrite systems. It is negative for some systems whose critical pair diagrams require rewriting under a lambda. However the positive answer can be recovered when the notion of inductive consequences is modified by allowing a certain form of functional extensionality.

12:00 Magnus O. Myreen
Separation logic adapted for proofs by rewriting

We present a formalisation of separation logic which, by avoiding the use of existential quantifiers, allows proofs that only use standard equational rewriting methods as found in off-the-shelf theorem provers. This proof automation is sufficiently strong to free the user from dealing with low-level details in proofs of functional correctness. The work presented here has been implemented in HOL4 and ACL2. It is illustrated on a standard example (reversal of a linked-list).

12:10 Douglas Howe
Higher-Order Abstract Syntax in Isabelle/HOL

Higher Order Abstract Syntax, or HOAS, is a technique for using a higher-order logic as a metalanguage for an object language with binding operators. It avoids formalizing syntactic details related to variable binding by identifying variables of the object logic with variables of the metalogic. In another paper we extended the usual set-theoretic semantics of HOL with a notion of *parametric* function, and showed how to use this extension to give solutions to the recursive type equations characteristic of HOAS, for example T = T x T + T -> T for a HOAS representation of the untyped lambda-calculus. This paper describes an effort to apply these semantic ideas in a proof assistant.

12:20 Bas Spitters and Eelis van der Weegen
Developing the algebraic hierarchy with type classes in Coq

We propose generic design patterns to organize algebraic structures using type classes inside the Coq system. We support multiple inheritance, sharing of notations and theories, and automated structure inference. A library for many-sorted universal algebra abstracts from the specific algebraic structures and aids the organization of the library. Finally, we provide abstract interfaces for $\N$, $\Z$, $\Q$ as the initial semiring, the initial ring and a field of fractions.

14:00‑15:00 FLoC Keynote Talk: J Strother Moore
Chair: Jean-Pierre Jouannaud
Location: George Square Lecture Theatre
14:00 J Strother Moore (University of Texas)
Theorem Proving for Verification: The Early Days.

Since Turing, computer scientists have understood that the question "does this program satisfy its specifications?" could be reduced to the question "are these formulas theorems?" But the theorem proving technology of the 50s and 60s was inadequate for the task. In 1971, here in Edinburgh, Boyer and I started building the first general-purpose theorem prover designed for a computational logic. This project continues today, with Matt Kaufmann as a partner; the current version of the theorem prover is ACL2 (A Computational Logic for Applicative Common Lisp).

In this talk I'll give a highly personal view of the four decade long "Boyer-Moore Project", including our mechanization of inductive proof, support for recursive definitions, rewriting with previously proved lemmas, integration of decision procedures, efficient representation of logical constants, fast execution, and other proof techniques. Along the way we'll see several interesting side roads: the founding of the Edinburgh school of logic programming, a structure-shared text editor that played a role in the creation of Word, and perhaps most surprisingly, the use of our "Lisp theorem prover" to formalize and prove theorems about commercial microprocessors and virtual machines via deep embeddings, including parts of processors by AMD, Centaur, IBM, Motorola, Rockwell-Collins, Sun, and others. The entire project helps shed light on the dichotomy between general-purpose theorem provers and special-purpose analysis tools.