Skip to main content

About the completeness of type systems

Kahrs, Stefan (1996) About the completeness of type systems. In: UNSPECIFIED. (KAR id:21352)

PDF
Language: English
Click to download this file (243kB)
[thumbnail of completeness.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Postscript
Language: English
Click to download this file (204kB) Preview
[thumbnail of completeness.ps]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format

Abstract

The original purpose of type systems for programming languages was to prevent certain forms of run-time errors, like using a number as a function. Some type systems go as far as guaranteeing the absence of run-time errors, e.g. the type system of Standard ML. One can call such a type system ``sound''. This raises the question of the dual notion of completeness, i.e. is everything typable that does not have run-time errors? Or, to put it in another way: does the type system restrict the expressive power of the underlying implementation in an undesirable way? To make this rather vague idea precise we define an abstract notion of ``type system'', together with general notions of soundness and completeness. We examine several type systems for these properties, for instance ?<sup>?</sup> and PCF are both complete, but for very different reasons.

Item Type: Conference or workshop item (UNSPECIFIED)
Uncontrolled keywords: completeness, type systems, definability
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: 27 Aug 2009 19:29 UTC
Last Modified: 16 Nov 2021 09:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21352 (The current URI for this page, for reference purposes)
Kahrs, Stefan: https://orcid.org/0000-0001-5099-9375
  • Depositors only (login required):

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