A Type-Based Complexity Analysis of Object Oriented Programs

Emmanuel Hainry 1 Romain Péchoux 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : A type system is introduced for a generic Object Oriented programming language in order to infer resource upper bounds. A sound andcomplete characterization of the set of polynomial time computable functions is obtained. As a consequence, the heap-space and thestack-space requirements of typed programs are also bounded polynomially. This type system is inspired by previous works on ImplicitComputational Complexity, using tiering and non-interference techniques. The presented methodology has several advantages. First, itprovides explicit big $O$ polynomial upper bounds to the programmer, hence its use could allow the programmer to avoid memory errors.Second, type checking is decidable in polynomial time. Last, it has a good expressivity since it analyzes most object oriented featureslike inheritance, overload, override and recursion. Moreover it can deal with loops guarded by objects and can also be extended tostatements that alter the control flow like break or return.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [34 references]  Display  Hide  Download

Contributor : Emmanuel Hainry <>
Submitted on : Monday, February 19, 2018 - 3:42:49 PM
Last modification on : Thursday, February 7, 2019 - 4:21:31 PM
Document(s) archivé(s) le : Saturday, May 5, 2018 - 4:49:09 PM


Files produced by the author(s)




Emmanuel Hainry, Romain Péchoux. A Type-Based Complexity Analysis of Object Oriented Programs. Information and Computation, Elsevier, 2018, Information and Computation, 261 (1), pp.78-115. ⟨https://www.sciencedirect.com/science/article/pii/S0890540118300786⟩. ⟨10.1016/j.ic.2018.05.006⟩. ⟨hal-01712506⟩



Record views


Files downloads