A type-based complexity analysis of object oriented programs

DOI10.1016/J.IC.2018.05.006zbMATH Open1395.68087arXiv1802.06653OpenAlexW2964137868WikidataQ129726623 ScholiaQ129726623MaRDI QIDQ1640983FDOQ1640983

Authors: Emmanuel Hainry, Romain Péchoux 

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1802.06653

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

zbMATH Keywords

complexitypolynomial timetype systemobject-oriented program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• SPEED: Symbolic Complexity Bound Analysis
• Space Lower Bounds for Maze Threadability on Restricted Machines
• SPEED: precise and efficient static estimation of program computational complexity
• Cost analysis of object-oriented bytecode programs
• Title not available (Why is that?)
• Static prediction of heap space usage for first-order functional programs
• Transition predicate abstraction and fair termination
• Logic for Programming, Artificial Intelligence, and Reasoning
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• FM 2005: Formal Methods
• On the termination of integer loops
• Resource control graphs
• Pure pointer programs with iteration
• Objects in polynomial time
• Efficient Type-Checking for Amortised Heap-Space Analysis
• Type-Based Complexity Analysis for Fork Processes
• Static determination of quantitative resource usage for higher-order programs
• Evolving Graph-Structures and Their Implicit Computational Complexity
• Static Analysis
• Programming Languages and Systems
• Size-change termination, monotonicity constraints and ranking functions

Cited In (11)

• Type-Based Complexity Analysis for Fork Processes
• Complexity information flow in a multi-threaded imperative language
• Title not available (Why is that?)
• Refinements of complexity results on type consistency for object-oriented databases
• Analyzing the implicit computational complexity of object-oriented programs
• 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

Uses Software

• COSTA
• Featherweight Java

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)