Unbounded Allocation in Bounded Heaps

Abstract : In this paper we introduce a new symbolic semantics for a class of recursive programs which feature dynamic creation and unbounded allocation of objects. We use a symbolic representation of the program state in terms of equations to model the semantics of a program as a pushdown system with a finite set of control states and a finite stack alphabet. Our main technical result is a rigorous proof of the equivalence between the concrete and the symbolic semantics.Adding pointer fields gives rise to a Turing complete language. However, assuming the number of reachable objects in the visible heap is bounded in all the computations of a program with pointers, we show how to construct a program without pointers that simulates it. Consequently, in the context of bounded visible heaps, programs with pointers are no more expressive than programs without them.
Type de document :
Communication dans un congrès
Farhad Arbab; Marjan Sirjani. 5th International Conference on Fundamentals of Software Engineering (FSEN), Apr 2013, Tehran, Iran. Springer Berlin Heidelberg, Lecture Notes in Computer Science, LNCS-8161, pp.1-16, 2013, Fundamentals of Software Engineering. 〈10.1007/978-3-642-40213-5_1〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01514664
Contributeur : Hal Ifip <>
Soumis le : mercredi 26 avril 2017 - 15:22:06
Dernière modification le : mercredi 20 décembre 2017 - 17:42:07
Document(s) archivé(s) le : jeudi 27 juillet 2017 - 12:59:52

Fichier

978-3-642-40213-5_1_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jurriaan Rot, Frank Boer, Marcello Bonsangue. Unbounded Allocation in Bounded Heaps. Farhad Arbab; Marjan Sirjani. 5th International Conference on Fundamentals of Software Engineering (FSEN), Apr 2013, Tehran, Iran. Springer Berlin Heidelberg, Lecture Notes in Computer Science, LNCS-8161, pp.1-16, 2013, Fundamentals of Software Engineering. 〈10.1007/978-3-642-40213-5_1〉. 〈hal-01514664〉

Partager

Métriques

Consultations de la notice

59

Téléchargements de fichiers

14