Skip to main content

Abstract Interpretation of Constructive Type Theory

Telford, Alastair J. and Thompson, Simon (1996) Abstract Interpretation of Constructive Type Theory. Technical report. UKC, University of Kent, Canterbury, UK (KAR id:21326)

Abstract

Constructive type theories, such as that of Martin-Lof, allow program construction and verification to take place within a single system: proofs may be read as programs and propositions as types. However, parts of proofs may be seen to be irrelevant from a computational viewpoint. We show how a form of abstract interpretation may be used to detect computational redundancy in a functional language based upon Martin-Lof's type theory. Thus, without making any alteration to the system of type theory itself, we present an automatic way of discovering and removing such redundancy. We also note that the strong normalisation property of type theory means that proofs of correctness of the abstract interpretation are simpler, being based upon a set-theoretic rather than a domain-theoretic semantics. Keywords: Type theory, functional programming, computational redundancy, abstract interpretation.

Item Type: Reports and Papers (Technical report)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 25 Aug 2009 20:58 UTC
Last Modified: 16 Nov 2021 09:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21326 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.