Eliminating array bound checking through dependent types
Hongwei Xi, Frank Pfenning · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1998
We present a type-based approach to eliminating array bound checking and list tag checking by conservatively extending Standard ML with a restricted form of dependent types. This enables the programmer to capture more invariants through types while type-checking remains decidable in theory and can still be performed efficiently in practice. We illustrate our approach through concrete examples and present the result of our preliminary experiments which support support the feasibility and effectiveness of our approach.
Cited by 284 works. doi:10.1145/277650.277732
Authors
References
- Introduction to Algorithms
- The Java Language Specification
- Proof-carrying code
- Optimization of range checking
- Implementing Mathematics with The Nuprl Proof Development System
- Introduction to algorithms
- On the SUP-INF Method for Proving Presburger Formulas
- A portable machine-independent global optimizer--design and measurements
- Constructive mathematics and computer programming
- The design and implementation of a certifying compiler