A Modular Hierarchy of Logical Frameworks

Robin Adams

Research output: ThesisDoctoral Thesis

63 Downloads (Pure)

Abstract

Logical frameworks - formal systems for the specification and representation of other formal systems - are now a well-established field of research, and the number and variety of logical frameworks is large and growing continuously. In this thesis, I tie several examples of logical frameworks into a single hierarchy.

I begin by introducing an infinite family of new, weak, lambda-free logical frameworks. These systems do not use lambda-abstraction, local definition, or any similar feature; parameterisation, and the instantiation of parameterisation, is taken as basic. These frameworks form conservative extensions of one another; this structure of extension is what I call the modular hierarchy of logical frameworks.

I show how several examples of existing logical frameworks - specifically, the systems PAL and AUT-68 from the AUTOMATH family, the Edinburgh Logical Framework, Martin-Lof's Logical Framework, and Luo's system PAL+ - can be fitted into this hierarchy, in the sense that one of the weak frameworks can be embedded in each as a conservative subsystem. I give several examples of adequacy theorems for object theories in the weak frameworks; these theorems are easier to prove than is usually the case for a logical framework. Adequacy theorems for the systems higher in the hierarchy follow as immediate corollaries.

In the second part of this thesis, I investigate an approach to the design of logical frameworks suggested by the existence of such a hierarchy: that a framework could be built by specifying a set of features, the result of adding any of which to a framework is a conservative extension of the same. I show how all of the weak frameworks from the first part, as well as two of the systems we gave there as examples, can indeed be built in this manner.
Original languageEnglish
QualificationPhD
Awarding Institution
  • University of Manchester
Supervisors/Advisors
  • Aczel, Peter, Supervisor, External person
Thesis sponsors
Award date10 Nov 2004
Publication statusUnpublished - 2004

Cite this