Skip to content

Research at St Andrews

Static Determination of Quantitative Resource Usage for Higher-Order Programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Author(s)

Steffen Jost, Kevin Hammond, Hans-Wolfgang Loidl, Martin Hofmann

School/Research organisations

Abstract

We describe a new automatic static analysis for determining upper-bound functions on the use of quantitative resources for strict, higher-order, polymorphic, recursive programs dealing with possibly-aliased data. Our analysis is a variant of Tarjan's manual amortised cost analysis technique. We use a type-based approach, exploiting linearity to allow inference, and place a new emphasis on the number of references to a data object. The bounds we infer depend on the sizes of the various inputs to a program. They thus expose the impact of specific inputs on the overall cost behaviour.

The key novel aspect of our work is that it deals directly with polymorphic higher-order functions without requiring source-level transformations that could alter resource usage. We thus obtain safe and accurate compile-time bounds. Our work is generic in that it deals with a variety of quantitative resources. We illustrate our approach with reference to dynamic memory allocations/deallocations, stack usage, and worst-case execution time, using metrics taken from a real implementation on a simple micro-controller platform that is used in safety-critical automotive applications.

Close

Details

Original languageEnglish
Title of host publicationPOPL'10 Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
Place of PublicationNew York
PublisherACM
Pages223-236
Number of pages14
ISBN (Print)978-1-60558-479-9
DOIs
StatePublished - 2010
Event37th ACM-SIGPLAN-SIGACT Symposium on Principles of Programming Languages - Madrid, Spain
Duration: 17 Jan 201023 Jan 2010

Conference

Conference37th ACM-SIGPLAN-SIGACT Symposium on Principles of Programming Languages
CountrySpain
CityMadrid
Period17/01/1023/01/10

    Research areas

  • Functional Programming, Resource Analysis, Types, POLYMORPHIC RECURSION, COMPLEXITY

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y. Feb 2018 In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V. Feb 2018 In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  3. Proof-relevant Horn clauses for dependent type inference and term synthesis

    Farka, F., Komendantskya, E. & Hammond, K. 2018 In : Theory and Practice of Logic Programming. 18, 3-4, p. 484-501

    Research output: Contribution to journalArticle

  4. Type-based cost analysis for lazy functional languages

    Jost, S., Vasconcelos, P., Florido, M. & Hammond, K. Jun 2017 In : Journal of Automated Reasoning. 59, 1, p. 87-120 34 p.

    Research output: Contribution to journalArticle

ID: 4509761