Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T04:48:55.890Z Has data issue: false hasContentIssue false
  • English
  • Français

An application of PER models to program extraction

Published online by Cambridge University Press:  04 March 2009

Stefano Berardi
Stefano Berardi
Affiliation:
Dipartimento di Informatica dell’ Universitá di Torino, Corso Sνizzera 185, Torino, Italy e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Type theory allows us to extract from a constructive proof that a specification is satisfiable a program that satisfies the specification. Algorithms for optimization of such programs are currently the object of research.

In this paper we consider one such algorithm, which was described in Beeson (1985) and which we will call ‘Harrop’. This algorithm greatly simplifies programs extracted from proofs in the Pure Construction Calculus. We use a Partial Equivalence Relation model for higher order lambda calculus, to check that t and Harrop(t) return the same outputs from the same inputs, i.e. that they are extensionally equal.

As a corollary, we show that it is correct (and, of course, useful) to replace a program t with Harrop(t). Such a correctness result has already been proved by Möhring (Möhring 1989a, 1989b) using realizability semantics, but we obtain it as a corollary of a new result, the extensional equality between t and Harrop(t). Also the semantic method we use is interesting in its own right.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 3 , September 1993 , pp. 309 - 331
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barendregt, H. P. (1984) The lambda calculus, its Syntax and Semantics, Studies in logic and the foundation of Mathematics, North-Holland.Google Scholar
Barendregt, H. P. (1989) Introduction to Generalized Type System. In: Proceedings of the 3rd Italian Conference on Theoretical Computer Science, Mantova 2–4 November 1989, Word Scientific Publishing Co., Singapore.Google Scholar
Barendregt, H. P. (1990) Lambda Calculi with types. In: Abramsky, S., Gabbai, D. M. and Maibaum, T. S. E. (eds.), Handbook of Logic in Computer Science, Oxford University Press.Google Scholar
Beeson, M. (1980) Foundation of Constructive Mathematics, Springer-Verlag.Google Scholar
Beeson, M. (1985) Foundation of Constructive Mathematics, Metamathematical studies, Springer-Verlag.CrossRefGoogle Scholar
Berardi, S. (1989) Type Dependency and Constructive Mathematics, Ph.D. thesis.Google Scholar
Berarducci, A. and Böhm, C. (1985) Automatic synthesis of λ-programs on term algebras. Theoretical Computer Science 39 135–154.Google Scholar
Cardelli, L. and Longo, G. (1990) A Semantic Basis for Quest. In: Proceedings of the 1990 ACM Conference on Lisp and Functional Programming.CrossRefGoogle Scholar
Constable, R.et al. (1986) Implementing mathematics with Nuprl Proof Development system, Prentice Hall.Google Scholar
Coquand, T. (1989) Metamathematical investigations of a Calculus of Constructions, INRIA Rapport technique 110.Google Scholar
Coquand, T. and Huet, G. (1985) Constructions: a higher order proof system for mechanizing mathematics, Report 401 INRIA (also in Proceeding's of EUROCAL 1985).CrossRefGoogle Scholar
Coquand, T. and Huet, G. (1988) The Calculus of Constructions. Information and Computation 76.CrossRefGoogle Scholar
Girard, J-Y (1971) Une extension de l'interpretation de Gödel á l’Analyse, et son application á l'élimination des coupures dans l’Analyse et dans la theories des types. In: Proceedings of the Second Scandinavian Symposium, North-Holland.Google Scholar
Hayashi, S. (1987) PX, a Computational Logic, Technical Report, Research Institute for Mathematical Sciences, Kyoto University.Google Scholar
Longo, G. (1987) From numbered sets to type theories, Rendiconti del Seminario Matematico dell’Universitá e del Politecnico di Torino, fascicolo speciale.Google Scholar
Longo, G. and Moggi, E. (1987) Constructive Natural Deduction and its ‘Modest’ interpretation. Draft C.M.U. report.Google Scholar
Longo, G. and Moggi, E. (1990) Constructive Natural Deduction and its ‘ω-Set’ Interpretation.MSCS 1 215–254.Google Scholar
Luo, Z. (1989) ECC, an Extended Calculus of Construction. In: Proceedings of the Fourth IEEE Symposium on Logic in Computer Science.Google Scholar
Martin-Löf, P. (1973) An Intuitionistic Theory of types: predicative part. Logic Colloquium ‘73, North-Holland, 73–118.Google Scholar
Martin-Löf, P. (1980) Intuitionistic Type Theory, Bibliopolis.Google Scholar
Möhring, C. (1989) Extraction des programmes dans le Calcul des Constructions, Université Paris VII.Google Scholar
Möhring, C. (1989) Extracting Fω programs from proofs in the Calculus of Constructions. In:Proceedings of POPL 89.Google Scholar
Möhring, C. (1989) Inductive Definitions in the Calculus of Constructions, INRIA Rapport Technique 110.Google Scholar
Möhring, C. (1989) Inductive defined types in the Calculus of Constructions. LNCS 442Google Scholar
Streicher, T. (1990) Ph.D. thesis (to appear).Google Scholar
Takayama, Y. (to appear) Extraction of Redundancy-free Programs from Constructive Natural Deduction Proofs. Journal of Symbolic Computation (to appear).Google Scholar