Show simple item record

dc.contributor.authorMurawski, ASen_US
dc.contributor.authorTzevelekos, Nen_US
dc.date.accessioned2016-07-28T14:04:49Z
dc.date.available2016-04-30en_US
dc.date.issued2016-08-17en_US
dc.date.submitted2016-07-28T14:53:07.490Z
dc.identifier.issn1860-5974en_US
dc.identifier.urihttp://qmro.qmul.ac.uk/xmlui/handle/123456789/13737
dc.identifier.urihttp://arxiv.org/abs/1605.02311v1
dc.description.abstractWe 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.en_US
dc.description.sponsorshipSupported by the Engineering and Physical Sciences Research Council (EP/C539753/1, EP/F067607/1) and the Royal Academy of Engineering (RF:Tzevelekos).
dc.format.extent33 - 47 (13)en_US
dc.languageEnglishen_US
dc.publisherIfCoLog (International Federation of Computational Logic)en_US
dc.relation.ispartofLogical Methods in Computer Scienceen_US
dc.rightsCreative Commons
dc.subjectGame semanticsen_US
dc.subjectReferencesen_US
dc.subjectContextual equivalenceen_US
dc.titleBlock Structure vs. Scope Extrusion: Between Innocence and Omniscienceen_US
dc.typeArticle
dc.rights.holder(c) Andrzej S. Murawski and Nikos Tzevelekos
dc.identifier.doi10.1007/978-3-642-12032-9_4en_US
pubs.issue3en_US
pubs.notesNot knownen_US
pubs.publication-statusPublisheden_US
pubs.publisher-urlhttps://link.springer.com/chapter/10.1007/978-3-642-12032-9_4en_US
pubs.volume12en_US
dcterms.dateAccepted2016-04-30en_US
qmul.funderGame Semantics for Program Analysis::Royal Academy of Engineeringen_US


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record