The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Dependent types in practical programming
Open accessAbstract
We present an approach to enriching the type system of ML with a restricted form of dependent types, where type index objects are drawn from a constraint domain C, leading to the DML(C) language schema. This allows specification and inference of significantly more precise type information, facilitating program error detection and compiler optimization. A major complication resulting from introducing dependent types is that pure type inference for the enriched system is no longer possible, but we show that type-checking a sufficiently annotated program in DML(C) can be reduced to constraint satisfaction in the constraint domain C. We exhibit the unobtrusiveness of our approach through practical examples and prove that DML(C) is conservative over ML. The main contribution of the paper lies in our language design, including the formulation of type-checking rules which makes the approach practical. To our knowledge, no previous type system for a general purpose programming language such as ML has combined dependent types with features including datatype declarations, higher-order functions, general recursions, let-polymorphism, mutable references, and exceptions. In addition, we have finished a prototype implementation of DML(C) for an integer constraint domain C, where constraints are linear inequalities (Xi and Pfenning 1998).
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
Dijkstra, E. W. (1976) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,733
The Java Language Specification
Gosling, J., Joy, B., & Steele, G. L. (1996) · Cited by 3,924
Milner, R., Harper, R., MacQueen, D., & Tofte, M. (1997) · The MIT Press eBooks · doi:10.7551/mitpress/2319.001.0001 · Cited by 2,419
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
Guarded commands, nondeterminacy and formal derivation of programs
Dijkstra, E. W. (1975) · Communications of the ACM · doi:10.1145/360933.360975 · Cited by 1,941
Necula, G. C. (1997) · Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '97 · doi:10.1145/263699.263712 · Cited by 1,843
An axiomatic basis for computer programming
Hoare, C. A. R. (1983) · Communications of the ACM · doi:10.1145/357980.358001 · Cited by 1,521
Constraint logic programming: a survey
Jaffar, J., & Maher, M. J. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90033-7 · Cited by 1,312
A Transformation System for Developing Recursive Programs
Burstall, R. M., & Darlington, J. (1977) · Journal of the ACM · doi:10.1145/321992.321996 · Cited by 1,300
Martin-Löf, P. (1984) · Bibliopolis eBooks · Cited by 1,274
Cited by
Language-based information-flow security
Sabelfeld, A., & Myers, A. C. (2003) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2002.806121 · Cited by 1,907
Extended static checking for Java
Flanagan, C., Leino, K. R. M., Lillibridge, M., Nelson, G., Saxe, J. B., & Stata, R. (2002) · Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation · doi:10.1145/512529.512558 · Cited by 1,340
Dynamically discovering likely program invariants to support program evolution
Ernst, M. D., Cockrell, J., Griswold, W. G., & Notkin, D. (2001) · IEEE Transactions on Software Engineering · doi:10.1109/32.908957 · Cited by 1,050
From system F to typed assembly language
Morrisett, G., Walker, D., Crary, K., & Glew, N. (1999) · ACM Transactions on Programming Languages and Systems · doi:10.1145/319301.319345 · Cited by 584
Jhala, R., & Majumdar, R. (2009) · ACM Computing Surveys · doi:10.1145/1592434.1592438 · Cited by 418
Advanced Topics in Types and Programming Languages
(2004) · The MIT Press eBooks · doi:10.7551/mitpress/1104.001.0001 · Cited by 348
MCBRIDE, C., & MCKINNA, J. (2004) · Journal of Functional Programming · doi:10.1017/s0956796803004829 · Cited by 327
Guarded recursive datatype constructors
Xi, H., Chen, C., & Chen, G. (2003) · Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/604131.604150 · Cited by 325
Self-citationEliminating array bound checking through dependent types
Xi, H., & Pfenning, F. (1998) · Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation · doi:10.1145/277650.277732 · Cited by 284
Self-citationFrom system F to typed assembly language
Morrisett, G., Walker, D., Crary, K., & Glew, N. (1998) · Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98 · doi:10.1145/268946.268954 · Cited by 282
Flanagan, C. (2006) · Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1111037.1111059 · Cited by 265
Combining effects and coeffects via grading
Gaboardi, M., Katsumata, S.-Y., Orchard, D., Breuvart, F., & Uustalu, T. (2016) · Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming · doi:10.1145/2951913.2951939 · Cited by 63
Really Natural Linear Indexed Type Checking
de Amorim, A. A., Gaboardi, M., Gallego Arias, E. J., & Hsu, J. (2014) · Proceedings of the 26nd 2014 International Symposium on Implementation and Application of Functional Languages · doi:10.1145/2746325.2746335 · Cited by 25
Metadata
- Authors
- Xi, H., & Pfenning, F.
- Venue
- Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
- Publisher
- ACM
- Published
- 1999-01
- Pages
- 214-227
- OpenAlex
- W2005192022
- Cited by
- 575
- References
- 42
- FWCI
- 18.68
- Type
- conference paper
- 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.