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
Martin-Löf, P. (1984) · Bibliopolis eBooks · Cited by 1,590
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
Implementing Mathematics with The Nuprl Proof Development System
Constable, R. L., Allen, S. F., Bromley, H. M., Cleaveland, W. R., Cremer, J. F., Harper, R. W., Howe, D. J., Knoblock, T. B., Mendler, N. P., Panangaden, P., et al. (1986) · Cited by 1,279
Coquand, T., & Huet, G. (1988) · Information and Computation · doi:10.1016/0890-5401(88)90005-3 · Cited by 1,082
Assigning Meanings to Programs
Floyd, R. W. (1993) · Studies in Cognitive Systems · doi:10.1007/978-94-011-1793-7_4 · Cited by 1,079
Barendregt, H. P., Dekkers, W., & Statman, R. (2013) · Cambridge University Press eBooks · doi:10.1017/cbo9781139032636 · Cited by 1,041
A framework for defining logics
Harper, R., Honsell, F., & Plotkin, G. (1993) · Journal of the ACM · doi:10.1145/138027.138060 · Cited by 990
Extensibility safety and performance in the SPIN operating system
Bershad, B. N., Savage, S., Pardyak, P., Sirer, E. G., Fiuczynski, M. E., Becker, D., Chambers, C., & Eggers, S. (1995) · Proceedings of the fifteenth ACM symposium on Operating systems principles - SOSP '95 · doi:10.1145/224056.224077 · Cited by 955
To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism
Curry, H. B., Hindley, J. R., & Seldin, J. P. (1980) · Academic Press eBooks · Cited by 924
Computational lambda-calculus and monads
Moggi, E. (2003) · [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science · doi:10.1109/lics.1989.39155 · Cited by 842
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
Self-citationFourier-Motzkin elimination and its dual
Dantzig, G. B., & Eaves, B. C. (1973) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(73)90004-6 · Cited by 386
The design and implementation of a certifying compiler
Necula, G. C., & Lee, P. (1998) · Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation · doi:10.1145/277650.277752 · Cited by 358
TIL: a type-directed optimizing compiler for ML
Tarditi, D., Morrisett, G., Cheng, P., Stone, C., Harper, R., & Lee, P. (1996) · Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation · doi:10.1145/231379.231414 · Cited by 317
Cayenne—a language with dependent types
Augustsson, L. (1998) · Proceedings of the third ACM SIGPLAN international conference on Functional programming · doi:10.1145/289423.289451 · Cited by 286
Church, A., & Rosser, J. B. (1936) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1936-1501858-0 · Cited by 285
Eliminating 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
Type inference with constrained types
Odersky, M., Sulzmann, M., & Wehr, M. (1999) · Theory and Practice of Object Systems · doi:10.1002/(sici)1096-9942(199901/03)5:1<35::aid-tapo4>3.0.co;2-4 · Cited by 216
ECC, an extended calculus of constructions
Luo, Z. (2003) · [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science · doi:10.1109/lics.1989.39193 · Cited by 214
Haskell 98 — A Non−strict‚ Purely Functional Language
Hinze, R. T. W. (1999) · Cited by 210
Simple imperative polymorphism
Wright, A. K. (1995) · LISP and Symbolic Computation · doi:10.1007/bf01018828 · Cited by 196
Pierce, B. C., & Turner, D. N. (1998) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/268946.268967 · Cited by 174
Higher-order modules and the phase distinction
Harper, R. W., Mitchell, J. C., & Moggi, E. (1990) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/96709.96744 · Cited by 167
A simple applicative language: mini-ML
Clément, D., Despeyroux, T., Kahn, G., & Despeyroux, J. (1986) · ACM Conference on LISP and Functional Programming (LFP) · doi:10.1145/319838.319847 · Cited by 159
Proof of Algorithms by General Snapshots
Naur, P. (1993) · Studies in cognitive systems · doi:10.1007/978-94-011-1793-7_3 · Cited by 144
Elf: a language for logic definition and verified metaprogramming
Pfenning, F. (2003) · doi:10.1109/lics.1989.39186 · Cited by 115
Self-citationFrom ML to Ada: Strongly-typed language interoperability via source translation
Tolmach, A. P., & Oliva, D. P. (1998) · Journal of Functional Programming · doi:10.1017/s0956796898003086 · Cited by 113
Morrisett, G. (1995) · Cited by 94
On the Undecidability of Partial Polymorphic Type Reconstruction
Pfenning, F. (1993) · Fundamenta Informaticae · doi:10.3233/fi-1993-191-208 · Cited by 37
Self-citationA unifying theory of dependent types: the schematic approach
Luo, Z. (2005) · Springer eBooks · doi:10.1007/bfb0023883 · Cited by 31
The Fox Project: Advanced Language Technology for Extensible Systems
Harper, R. W., Lee, P., & Pfenning, F. (1998) · Defense Technical Information Center (DTIC) · doi:10.21236/ada341557 · Cited by 20
Self-citationDesign and implementation of practical constraint logic programming systems
Michaylov, S. (1992) · Defense Technical Information Center (DTIC) · Cited by 11
Automatic program specialization for interactive media
Draves, S., & Lee, P. (1997) · Cited by 8
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
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.