The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
On understanding types, data abstraction, and polymorphism
Open accessAbstract
Our objective is to understand the notion of type in programming languages, present a model of typed, polymorphic programming languages that reflects recent research in type theory, and examine the relevance of recent research to the design of practical programming languages. Object-oriented languages provide both a framework and a motivation for exploring the interaction among the concepts of type, data abstraction, and polymorphism, since they extend the notion of type to data abstraction and since type inheritance is an important form of polymorphism. We develop a λ-calculus-based model for type systems that allows us to explore these interactions in a simple setting, unencumbered by complexities of production programming languages. The evolution of languages from untyped universes to monomorphic and then polymorphic type systems is reviewed. Mechanisms for polymorphism such as overloading, coercion, subtyping, and parameterization are examined. A unifying framework for polymorphic type systems is developed in terms of the typed λ-calculus augmented to include binding of types by quantification as well as binding of values by abstraction. The typed λ-calculus is augmented by universal quantification to model generic functions with type parameters, existential quantification and packaging (information hiding) to model abstract data types, and bounded quantification to model subtypes and type inheritance. In this way we obtain a simple and precise characterization of a powerful type system that includes abstract data types, parametric polymorphism, and multiple inheritance in a single consistent framework. The mechanisms for type checking for the augmented λ-calculus are discussed. The augmented typed λ-calculus is used as a programming language for a variety of illustrative examples. We christen this language Fun because fun instead of λ is the functional abstraction keyword and because it is pleasant to deal with. Fun is mathematically simple and can serve as a basis for the design and implementation of real programming languages with type facilities that are more powerful and expressive than those of existing programming languages. In particular, it provides a basis for the design of strongly typed object-oriented languages.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,448
A Machine-Oriented Logic Based on the Resolution Principle
Robinson, J. A. (1965) · Journal of the ACM · doi:10.1145/321250.321253 · Cited by 3,909
Smalltalk-80: The Language and its Implementation
Goldberg, A., & Robson, D. J. (1983) · HAL · Cited by 3,866
A theory of type polymorphism in programming
Milner, R. (1978) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(78)90014-4 · Cited by 2,205
Martin-Löf, P. (1984) · Bibliopolis eBooks · Cited by 1,274
Principal type-schemes for functional programs
Damas, L., & Milner, R. (1982) · Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '82 · doi:10.1145/582153.582176 · Cited by 1,097
Wirth, N. (1988) · Springer eBooks · doi:10.1007/978-3-642-83565-0 · Cited by 896
Towards a theory of type structure
Reynolds, J. C. (1974) · Lecture Notes in Computer Science · doi:10.1007/3-540-06859-7_148 · Cited by 815
Scott, D. (2006) · Springer eBooks · doi:10.1007/bfb0079432 · Cited by 737
A semantics of multiple inheritance
Cardelli, L. (1988) · Information and Computation · doi:10.1016/0890-5401(88)90007-7 · Cited by 624
Self-citationBooch, G. (1983) · CERN Document Server (European Organization for Nuclear Research) · Cited by 577
Girard, J.-Y. (1971) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(08)70843-7 · Cited by 452
The principle type-scheme of an object in combinatory logic
Hindley, R. (1969) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1969-0253905-6 · Cited by 448
The Principal Type-Scheme of an Object in Combinatory Logic
Hindley, R. (1969) · Transactions of the American Mathematical Society · doi:10.2307/1995158 · Cited by 319
(1981) · Lecture Notes in Computer Science · doi:10.1007/bfb0035014 · Cited by 296
MacQueen, D. (1984) · Proceedings of the 1984 ACM Symposium on LISP and functional programming - LFP '84 · doi:10.1145/800055.802036 · Cited by 269
Milner, R. (1984) · doi:10.1145/800055.802035 · Cited by 253
Abstract types have existential types
Mitchell, J. C., & Plotkin, G. D. (1985) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/318593.318606 · Cited by 159
Using dependent types to express modular structure
MacQueen, D. B. (1986) · Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '86 · doi:10.1145/512644.512670 · Cited by 159
Three approaches to type structure
Reynolds, J. C. (1985) · Lecture notes in computer science · doi:10.1007/3-540-15198-2_7 · Cited by 131
Basic polymorphic typechecking
Cardelli, L. (1987) · Science of Computer Programming · doi:10.1016/0167-6423(87)90019-0 · Cited by 130
Self-citationAmbiguities and insecurities in pascal
Welsh, J., Sneeringer, W. J., & Hoare, C. A. R. (1977) · Software Practice and Experience · doi:10.1002/spe.4380070604 · Cited by 118
The typechecking of programs with implicit type structure
McCracken, N. (1984) · Lecture Notes in Computer Science · doi:10.1007/3-540-13346-1_15 · Cited by 53
Cited by
Pustejovsky, J. (2004) · Semantics · doi:10.1093/oso/9780195136975.003.0018 · Cited by 3,963
Service oriented architectures: approaches, technologies and research issues
Papazoglou, M. P., & van den Heuvel, W.-J. (2007) · The VLDB Journal · doi:10.1007/s00778-007-0044-3 · Cited by 1,939
Coquand, T., & Huet, G. (1988) · Information and Computation · doi:10.1016/0890-5401(88)90005-3 · Cited by 1,082
How to make ad-hoc polymorphism less ad hoc
Wadler, P., & Blott, S. (1989) · Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 · doi:10.1145/75277.75283 · Cited by 773
Julia: A Fast Dynamic Language for Technical Computing
Anderson, T. A., Liu, H., Kuper, L., Totoni, E., Vitek, J., & Shpeisman, T. (2012) · arXiv (Cornell University) · doi:10.4230/lipics.ecoop.2017.4 · Cited by 627
Metadata
- Authors
- Cardelli, L., & Wegner, P.
- Venue
- ACM Computing Surveys
- Published
- 1985-12-10
- Volume
- 17
- Issue
- 4
- Pages
- 471-523
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2027657506
- Cited by
- 1,669
- References
- 24
- FWCI
- 34.11
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.