On bounding space usage of streams using interpretation analysis

Marco Gaboardi, Romain Péchoux (Lead / Corresponding author)

    Research output: Contribution to journalArticle

    1 Citation (Scopus)

    Abstract

    Interpretation methods are important tools in implicit computational complexity. They have been proved particularly useful to statically analyze and to limit the complexity of programs. However, most of these studies have been so far applied in the context of term rewriting systems over finite data.In this paper, we show how interpretations can also be used to study properties of lazy first-order functional programs over streams. In particular, we provide some interpretation criteria useful to ensure two kinds of stream properties: space upper bounds and input/output upper bounds. Our space upper bounds criteria ensure global and local upper bounds on the size of each output stream element expressed in terms of the maximal size of the input stream elements. The input/output upper bounds criteria consider instead the relations between the number of elements read from the input stream and the number of elements produced on the output stream.This contribution can be seen as a first step in the development of a methodology aiming at using interpretation properties to ensure space safety properties of programs working on streams.

    Original languageEnglish
    Pages (from-to)395-425
    Number of pages31
    JournalScience of Computer Programming
    Volume111
    Issue number3
    Early online date1 Jun 2015
    DOIs
    Publication statusPublished - 1 Nov 2015

    Keywords

    • Implicit computational complexity
    • Interpretations
    • Lazy languages
    • Program space usage
    • Stream programs

    Fingerprint Dive into the research topics of 'On bounding space usage of streams using interpretation analysis'. Together they form a unique fingerprint.

  • Projects

    PLATFORM International Outgoing Fellowship

    Gaboardi, M. & Komendantskaya, E.

    COMMISSION OF THE EUROPEAN COMMUNITIES

    1/10/1331/07/14

    Project: Research

    Cite this