A type-based complexity analysis of object oriented programs
From MaRDI portal
(Redirected from Publication:1640983)
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 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.
Recommendations
- The structured complexity of object-oriented programs
- Analyzing the implicit computational complexity of object-oriented programs
- scientific article; zbMATH DE number 4080882
- A Flexible, (C)LP-Based Approach to the Analysis of Object-Oriented Programs
- Type-based parametric analysis of program families
- scientific article; zbMATH DE number 1953279
- scientific article; zbMATH DE number 1508929
- Complexity of type inference
- Algebraic Methodology and Software Technology
Cites work
- scientific article; zbMATH DE number 445159 (Why is no real title available?)
- A new recursion-theoretic characterization of the polytime functions
- Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
- Cost analysis of object-oriented bytecode programs
- Efficient Type-Checking for Amortised Heap-Space Analysis
- Evolving Graph-Structures and Their Implicit Computational Complexity
- FM 2005: Formal Methods
- Light linear logic
- Logic for Programming, Artificial Intelligence, and Reasoning
- Objects in polynomial time
- On the termination of integer loops
- Programming Languages and Systems
- Pure pointer programs with iteration
- Resource control graphs
- SPEED: Symbolic Complexity Bound Analysis
- SPEED: precise and efficient static estimation of program computational complexity
- Size-change termination, monotonicity constraints and ranking functions
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Static Analysis
- Static determination of quantitative resource usage for higher-order programs
- Static prediction of heap space usage for first-order functional programs
- Transition predicate abstraction and fair termination
- Type-Based Complexity Analysis for Fork Processes
Cited in
(11)- Type-Based Complexity Analysis for Fork Processes
- Complexity information flow in a multi-threaded imperative language
- scientific article; zbMATH DE number 1508929 (Why is no real title available?)
- Analyzing the implicit computational complexity of object-oriented programs
- Refinements of complexity results on type consistency for object-oriented databases
- Objects in polynomial time
- Behavioural types for memory and method safety in a core object-oriented language
- Static Analysis
- An empirical study into COBOL type inferencing
- A computational complexity analysis of tunable type inference for Generic Universe Types
- \textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs
This page was built for publication: A type-based complexity analysis of object oriented programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1640983)
