Block Structure vs. Scope Extrusion: Between Innocence and Omniscience
Lists
Only you see this
Abstract
We study the semantic meaning of block structure using game semantics and introduce the notion of block-innocent strategies, which turns out to characterise call-by-value computation with block-allocated storage through soundness, finitary definability and universality results. This puts us in a good position to conduct a comparative study of purely functional computation, computation with block storage and dynamic memory allocation respectively. For example, we show that dynamic variable allocation can be replaced with block-allocated variables exactly when the term involved (open or closed) is of base type and that block-allocated storage can be replaced with purely functional computation when types of order two are involved. To illustrate the restrictive nature of block structure further, we prove a decidability result for a finitary fragment of call-by-value Idealized Algol for which it is known that allowing for dynamic memory allocation leads to undecidability.
BibTeX
@inproceedings{murawski2010block,
author = {Andrzej S. Murawski and Nikos Tzevelekos},
title = {{Block Structure vs. Scope Extrusion: Between Innocence and Omniscience}},
booktitle = {FoSSaCS},
year = {2010},
doi = {10.1007/978-3-642-12032-9\_4},
}Loading related content...