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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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,590
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
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
Freeman, T., & Pfenning, F. (1991) · Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91 · doi:10.1145/113445.113468 · Cited by 424
The Combinatorial BLAS: design, implementation, and applications
Buluç, A., & Gilbert, J. R. (2011) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342011403516 · Cited by 415
Conception, evolution, and application of functional programming languages
Hudak, P. (1989) · ACM Computing Surveys · doi:10.1145/72551.72554 · Cited by 409
On the representation of roles in object-oriented and conceptual modelling
Steimann, F. (2000) · Data & Knowledge Engineering · doi:10.1016/s0169-023x(00)00023-9 · Cited by 398
Amadio, R. M., & Cardelli, L. (1993) · ACM Transactions on Programming Languages and Systems · doi:10.1145/155183.155231 · Cited by 350
Self-citationStatic analysis of android apps: A systematic literature review
Li, L., Bissyandé, T. F., Papadakis, M., Rasthofer, S., Bartel, A., Octeau, D., Klein, J., & Traon, L. (2017) · Information and Software Technology · doi:10.1016/j.infsof.2017.04.001 · Cited by 350
Types and persistence in database programming languages
Atkinson, M. P., & Buneman, O. P. (1987) · ACM Computing Surveys · doi:10.1145/62070.45066 · Cited by 344
Mechanized Metatheory for the Masses: The PoplMark Challenge
Aydemir, B. E., Bohannon, A., Fairbairn, M., Foster, J. N., Pierce, B. C., Sewell, P., Vytiniotis, D., Washburn, G., Weirich, S., & Zdancewic, S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11541868_4 · Cited by 303
Pierce, B. C., & Turner, D. N. (2000) · ACM Transactions on Programming Languages and Systems · doi:10.1145/345099.345100 · Cited by 287
A type-theoretic approach to higher-order modules with sharing
Harper, R., & Lillibridge, M. (1994) · Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '94 · doi:10.1145/174675.176927 · Cited by 287
Type inclusion constraints and type inference
Aiken, A., & Wimmers, E. L. (1993) · Proceedings of the conference on Functional programming languages and computer architecture · doi:10.1145/165180.165188 · Cited by 262
Manifest types, modules, and separate compilation
Leroy, X. (1994) · Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '94 · doi:10.1145/174675.176926 · Cited by 257
Using parameterized signatures to express modular structure
Jones, M. P. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237731 · Cited by 57
Rounds, W. C. (1997) · Handbook of Logic and Language · doi:10.1016/b978-044481714-3/50012-6 · Cited by 36
Learning higher-order logic programs
Cropper, A., Morel, R., & Muggleton, S. (2020) · Machine Learning · doi:10.1007/s10994-019-05862-7 · Cited by 11
“nstance, suppose you are given examples of the concept f (x, y) where x is a list of integers and y is x but reversed, where each element has had one added to it, and then doubled, such as f ([1,2,3],[8,6,4]). Then Metagolho could learn the following program given the metarules used in Figure 7: f(A,B):-f1(A,C),f5(C,B…”
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.