Hostname: page-component-7b9c58cd5d-dlb68 Total loading time: 0 Render date: 2025-03-15T01:46:17.422Z Has data issue: false hasContentIssue false
  • English
  • Français

A semantic basis for Quest

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Luca Cardelli  and
Giuseppe Longo
Luca Cardelli
Affiliation:
Digital Equipment Corporation Systems Research Center, 130 Lytton Ave, Palo Alto Ca 94301 (USA)
Giuseppe Longo
Affiliation:
LIENS (CNRS), Dept. de Mathématique et Informatique, Ecole Normale Supérieure, 45, Rue d'Ulm 75005 Paris (France)
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.

Quest is a programming language based on impredicative type quantifiers and subtyping within a three-level structure of kinds, types and type operators, and values.

The semantics of Quest is rather challenging. In particular, difficulties arise when we try to model simultaneously features such as contravariant function spaces, record types, subtyping, recursive types and fixpoints.

In this paper we describe in detail the type inference rules for Quest, and give them meaning using a partial equivalence relation model of types. Subtyping is interpreted as in previous work by Bruce and Longo (1989), but the interpretation of some aspects – namely subsumption, power kinds, and record subtyping – is novel. The latter is based on a new encoding of record types.

We concentrate on modelling quantifiers and subtyping; recursion is the subject of current work.

Type
Articles
Information
Journal of Functional Programming , Volume 1 , Issue 4 , October 1991 , pp. 417 - 458
Copyright
Copyright © Cambridge University Press 1991

References

Abadi, M. and Plotkin, G. D. 1990. A Per model of polymorphism and recursive types. Proc. Fifth Annual Symposium on Logic in Computer Science.Google Scholar
Amadio, R. 1989 a. Recursion over realizability structures. Information and Computation, 1991.Google Scholar
Amadio, R. 1989 b. Formal theories of inheritance for typed functional languages. Note interne TR 28/89, Dipartimento di Informatica, Università di Pisa, Italy.Google Scholar
Asperti, A. and Longo, G. 1991. Categories, Types and Structures: an introduction to category theory for the working computer scientist, MIT Press.Google Scholar
Asperti, A. and Martini, S. 1989. Categorical models of polymorphism. Information and Computation (to appear).Google Scholar
Bainbridge, E. S., Freyd, P. J., Scedrov, A. and Scott, P. J. 1987. Functional polymorphism, preliminary report. Proc. Programming Institute on Logical Foundations of Functional Programming, Austin, Texas.Google Scholar
Barendregt, H. 1984. The lambda calculus; its syntax and semantics, (revised and expanded edition), North-Holland.Google Scholar
Breazu-Tannen, V., Coquand, T., Gunter, C. and Scedrov, A. 1989. Inheritance and explicit coercion. Proc. Fourth Annual Symposium on Logic in Computer Science.Google Scholar
Bruce, K. and Longo, G. 1989. Modest models of records, inheritance and bounded quantification. Information and Computation, 87 (1/2).Google Scholar
Carboni, A., Freyd, P. J. and Scedrov, A. 1987. A categorical approach to realizability and polymorphic types. Proc. Third Symposium on Mathematical Foundations of Programming Language Semantics,New Orleans, USA (to appear).CrossRefGoogle Scholar
Cardelli, L. 1988. A semantics of multiple inheritance. Information and Computation, 76: 138–164.CrossRefGoogle Scholar
Cardelli, L. 1989. Typeful programming. Lecture Notes for the IFIP Advanced Seminar on Formal Methods in Programming Language Semantics, Rio de Janeiro, Brazil. (SRC Report #45, Digital Equipment Corporation, 1989.)Google Scholar
Cardelli, L., Donahue, J., Glassman, L., Jordan, M., Kalsow, B. and Nelson, G. 1988. Modula-3 report. Research Report n.31, DEC Systems Research Center (September 1988).Google Scholar
Cardelli, L. and Mitchell, J. C. 1989. Operations on records. Proc. Fifth Conference on Mathematical Foundations of Programming Language Semantics,New Orleans, USA (to appear in Mathematical Structures in Computer Science, 1.)Google Scholar
Cardelli, L. and Wegner, P. 1985. On understanding types, data abstraction and polymorphism. Computing Surveys, 17 (4): 471–522.CrossRefGoogle Scholar
Cook, W., Hill, W. and Canning, P. 1990. Inheritance is not subtyping. Proc. POPL'90, San Francisco, USA.Google Scholar
Curien, P. L. and Ghelli, G. 1990. Coherence of subsumption, Mathematical Structures in Computer Science, 1 no. 3.Google Scholar
Ehrhard, T. 1988. A categorical semantics of constructions. Proc. 3rd Annual Symposium on Logic in Computer Science,Edinburgh, UK.Google Scholar
Fairbairn, J. 1989. Some types with inclusion properties in ∀, →, μ. Technical Report No. 171, University of Cambridge Computer Laboratory, UK.Google Scholar
Feferman, S. 1987. Weyl Vindicated: Das Kontinuum, 70 Years Later. Preprint, Stanford University. Proc. Cesena Conf. on Logic and Philosophy of Science (to appear).Google Scholar
Feferman, S. 1988. Polymorphic typed lambda-calculi in a type-free axiomatic framework. J. ACM, 151, 185, 30, 1 January.Google Scholar
Freyd, P. J., Mulry, P., Rosolini, G. and Scott, D. 1990. Domains in Per. Proc. 5th Annual Symposium on Logic in Computer Science.Google Scholar
Girard, J.-Y. 1972. Interpretation Fonctionelle et Élimination des Coupures dans l'Arithmétique d'Ordre Supérieur. Thèse de doctorat d'état, Université Paris VII, France.Google Scholar
Hindley, R. and Longo, G. 1980. Lambda-calculus models and extensionality. Zeit. Math. Logik Grund. Math. 26: 289–310.CrossRefGoogle Scholar
Hyland, J. M. E. 1987. A small complete category. Annals of Pure and Applied Logic, 40.Google Scholar
Hyland, J. M. E. and Pitts, A. M. 1987. The theory of constructions: categorical semantics and topos-theoretic models, Categories in Computer Science and Logic (Proc. Boulder '87), Providence, USA.Google Scholar
Hyland, M. 1982. The effective topos. In Troelstra, A. and Van Dalen, (editors), The Brower Symposium,North-Holland.Google Scholar
Longo, G. 1988. Some aspects of impredicativity: notes on Weyl's philosophy of mathematics and today's Type Theory. CMU Report CS-88-135. In Ebbinghaus, et al. (editors), North-Holland.Google Scholar
Longo, G. and Moggi, E. 1988. Constructive Natural Deduction and its “ω-Set” interpretation. CMU report CS-88-131, Mathematical Structures in C.S., 1 no. 2, 1991.Google Scholar
Luo, Z. 1988. ECC, an Extended Calculus of Constructions. Report, LFCS, Department of Computer Science University of Edinburgh, UK.Google Scholar
Martini, S. 1988. Bounded quantifiers have interval models. ACM Conf. Lisp and Functional Programming Languages,Snowbird, USA.CrossRefGoogle Scholar
Meseguer, J. 1988. Relating Models of Polymorphism. SRI-CSL-88-13, October, SRI Projects 2316, 4415 and 6729, SRI International.Google Scholar
Mitchell, J. C. 1984. Coercion and type inference. Proc. POPL '84.CrossRefGoogle Scholar
Mitchell, J. C. 1986. A type-inference approach to reduction properties and semantics of polymorphic expressions. ACM Conf. LISP and Functional Programming,Boston, USA,308–319.Google Scholar
Mitchell, J. C. 1988. Polymorphic type inference and containment. Information and Computation, 76(2/3): 211–249.Google Scholar
Mitchell, J. C. and Plotkin, G. D. 1985. Abstract types have existential type. Proc. POPL '85.Google Scholar
Ohori, A. 1987. Orderings and types in databases. Proc. Workshop on Database Programming Languages, Roscoff, France (September 1987).Google Scholar
Pitts, A. 1987. Polymorphism is Set theoretic, constructively. Symposium on Category Theory and Computer Science, SLNCS 283,Edinburgh, UK.Google Scholar
Reynolds, J. C. 1984. Polymorphism is not set-theoretic. Symposium on Semantics of Data Types, Volume 173 of Lecture Notes in Computer Science,Springer-Verlag.Google Scholar
Rosolini, G. 1986. Continuity and effectiveness in Topoi. DPhil. Thesis, Oxford University, UK.Google Scholar
Scedrov, A.A Guide to Polymorphic Types. CIME Lectures Montecatini Terme, June, (revised version).Google Scholar
Troelstra, A. 1973. Metamathematical investigation of Intuitionistic Arithmetic and Analysis. Volume 344 of Lecture Notes in Mathematics, Springer-Verlag.Google Scholar
Wand, M.Type inference for record concatenation and multiple inheritance. Proc. Fourth Annual Symposium on Logic in Computer Science.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.