On Bounding Space Usage of Streams Using Interpretation Analysis

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 this 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 ensures global and local upper bounds on the size of each output stream element expressed in term 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.
Type de document :
Article dans une revue
Science of Computer Programming, Elsevier, 2015, pp.44
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01112161
Contributeur : Romain Péchoux <>
Soumis le : jeudi 2 avril 2015 - 15:56:45
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : jeudi 10 septembre 2015 - 13:25:53

Fichier

main-submitted.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01112161, version 1

Collections

Citation

Marco Gaboardi, Romain Péchoux. On Bounding Space Usage of Streams Using Interpretation Analysis. Science of Computer Programming, Elsevier, 2015, pp.44. 〈hal-01112161〉

Partager

Métriques

Consultations de la notice

318

Téléchargements de fichiers

151