Paper: The semantics of reflected proof (at LICS 1990)

Authors: Stuart F. Allen Robert L. Constable Douglas J. Howe William E. Aitken

Abstract

The authors lay the foundations for reasoning about proofs whose steps include both invocations of programs to build subproofs (tactics) and references to representations of proofs themselves (reflected proofs). The main result is the definition of a single type of proof which can mention itself, using a novel technique which finds a fixed point of a mapping between metalanguage and object language. This single type contrasts with hierarchies of types used in other approaches to accomplish the same classification. It is shown that these proofs are valid, and that every proof can be reduced to a proof involving only primitive inference rules. The extension of the results to proofs from which programs (such as tactics) can be derive and to proofs that can refer to a library of definitions and previously proven theorems is shown. It is believed that the mechanism of reflection is fundamental in building proof development systems, and its power is illustrated with applications to automating reasoning and describing modes of computation

BibTeX

  @InProceedings{AllenConstableHoweA-Thesemanticsofrefle,
    author = 	 {Stuart F. Allen and Robert L. Constable and Douglas J. Howe and William E. Aitken},
    title = 	 {The semantics of reflected proof},
    booktitle =  {Proceedings of the Fifth Annual IEEE Symposium on Logic in Computer Science (LICS 1990)},
    year =	 {1990},
    month =	 {June}, 
    pages =      {95--105},
    location =   {Philadelphia, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }