Robert J. Simmons

Substructural Logical Specifications Degree Type: Ph.D. in Computer Science
Advisor(s): Frank Pfenning
Graduated: December 2012

Abstract:

A logical framework and its implementation should serve as a flexible tool for specifying, simulating, and reasoning about formal systems. When the formal systems we are interested in exhibit state and concurrency, however, existing logical frameworks fall short of this goal. Logical frameworks based on a rewriting interpretation of substructural logics, ordered and linear logic in particular, can help. To this end, this dissertation introduces and demonstrates four methodologies for developing and using substructural logical frameworks for specifying and reasoning about stateful and concurrent systems.

Structural focalization is a synthesis of ideas from Andreoli's focused sequent calculi and Watkins's hereditary substitution. We can use structural focalization to take a logic and define a restricted form of derivations, the focused derivations, that form the basis of a logical framework. We apply this methodology to define SLS, a logical framework for substructural logical specifications, as a fragment of ordered linear lax logic.

Logical correspondence is a methodology for relating and inter-deriving different styles of programming language specification in SLS. The styles we connect range from very high-level specification styles like natural semantics, which do not fully specify the control structure of programs, to low-level specification styles like destination-passing, which provide detailed control over concurrency and control flow. We apply this methodology to systematically synthesize a low-level destination-passing semantics for a Mini-ML language extended with stateful and concurrent primitives. The specification is mostly high-level except for the relatively few rules that actually deal with concurrency.

Linear logical approximation is a methodology for deriving program analyses by performing abstract analysis on the SLS encoding of the language's operational semantics. We demonstrate this methodology by deriving a control flow analysis and an alias analysis from suitable programming language specifications.

Generative invariants are a powerful generalization of both context-free grammars and LF's regular worlds that allow us to express invariants of SLS specifications in SLS.We show that generative invariants can form the basis of progress-andpreservation- style reasoning about programming languages encoded in SLS.

Thesis Committee:
Frank Pfenning (Chair)
Robert Harper
Andre ́ Platzer
Iliano Cervesato (Carnegie Mellon Qatar)
Dale Miller (INRIA-Saclay & LIX/Ecole Polytechnique)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Logical frameworks, linear logic, ordered logic, operational semantics