Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-24T12:01:29.738Z Has data issue: false hasContentIssue false

Dependent types ensure partial correctness of theorem provers

Published online by Cambridge University Press:  14 January 2004

ANDREW W. APPEL
Affiliation:
Princeton University, 35 Olden Street, Princeton, NJ 08544, USA (e-mail: appel@princeton.edu)
AMY P. FELTY
Affiliation:
University of Ottawa, 800 King Edward Ave., Ottawa, Ontario K1N 6N5, Canada (e-mail: afelty@site.uottawa.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Static type systems in programming languages allow many errors to be detected at compile time that wouldn't be detected until runtime otherwise. Dependent types are more expressive than the type systems in most programming languages, so languages that have them should allow programmers to detect more errors earlier. In this paper, using the Twelf system, we show that dependent types in the logic programming setting can be used to ensure partial correctness of programs which implement theorem provers, and thus avoid runtime errors in proof search and proof construction. We present two examples: a tactic-style interactive theorem prover and a union-find decision procedure.

Type
Article
Copyright
© 2004 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.