{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T12:00:18Z","timestamp":1720612818074},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2012,8,31]],"date-time":"2012-08-31T00:00:00Z","timestamp":1346371200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>Frame and anti-frame rules have been proposed as proof rules for modular reasoning about programs. Frame rules allow the hiding of irrelevant parts of the state during verification, whereas the anti-frame rule allows the hiding of local state from the context.<\/jats:p><jats:p>We discuss the semantic foundations of frame and anti-frame rules, and present the first sound model for Chargu\u00e9raud and Pottier's type and capability system including both of these rules. The model is a possible worlds model based on the operational semantics and step-indexed heap relations, and the worlds are given by a recursively defined metric space. We also extend the model to account for Pottier's generalised frame and anti-frame rules, where invariants are generalised to<jats:italic>families<\/jats:italic>of invariants indexed over preorders. This generalisation enables reasoning about some well-bracketed as well as (locally) monotone uses of local state.<\/jats:p>","DOI":"10.1017\/s0960129512000035","type":"journal-article","created":{"date-parts":[[2012,8,31]],"date-time":"2012-08-31T09:29:25Z","timestamp":1346405365000},"page":"1-54","source":"Crossref","is-referenced-by-count":3,"title":["A step-indexed Kripke model of hidden state"],"prefix":"10.1017","volume":"23","author":[{"given":"JAN","family":"SCHWINGHAMMER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LARS","family":"BIRKEDAL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRAN\u00c7OIS","family":"POTTIER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BERNHARD","family":"REUS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KRISTIAN","family":"ST\u00d8VRING","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HONGSEOK","family":"YANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,8,31]]},"reference":[{"key":"S0960129512000035_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01018828"},{"key":"S0960129512000035_ref32","doi-asserted-by":"crossref","unstructured":"Schwinghammer J. , Yang H. , Birkedal L. , Pottier F. and Reus B. (2010) A semantic foundation for hidden state. In: Proceedings of FOSSACS 2\u201316.","DOI":"10.1007\/978-3-642-12032-9_2"},{"key":"S0960129512000035_ref21","volume-title":"Types and Programming Languages","author":"Pierce","year":"2002"},{"key":"S0960129512000035_ref30","doi-asserted-by":"crossref","unstructured":"Schwinghammer J. , Birkedal L. , Reus B. and Yang H. (2009) Nested Hoare triples and frame rules for higher-order store. In: Proceedings of CSL 440\u2013454.","DOI":"10.1007\/978-3-642-04027-6_32"},{"key":"S0960129512000035_ref29","doi-asserted-by":"crossref","unstructured":"Reynolds J. C. (2002) Separation logic: A logic for shared mutable data structures. In: Proceedings of LICS 55\u201374.","DOI":"10.1109\/LICS.2002.1029817"},{"key":"S0960129512000035_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_24"},{"key":"S0960129512000035_ref25","unstructured":"Pottier F. (2009a) Generalizing the higher-order frame and anti-frame rules. Unpublished note, available at http:\/\/gallium.inria.fr\/~fpottier."},{"key":"S0960129512000035_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.11.020"},{"key":"S0960129512000035_ref26","unstructured":"Pottier F. (2009b) Three comments on the anti-frame rule. Unpublished note, available at http:\/\/gallium.inria.fr\/~fpottier."},{"key":"S0960129512000035_ref23","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0052"},{"key":"S0960129512000035_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/1275497.1275499"},{"key":"S0960129512000035_ref10","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(5:1)2006"},{"key":"S0960129512000035_ref27","doi-asserted-by":"crossref","unstructured":"Pottier F. (2011) Syntactic soundness proof of a type-and-capability system with hidden state (submitted for publication).","DOI":"10.1017\/S0956796812000366"},{"key":"S0960129512000035_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00596-1_32"},{"key":"S0960129512000035_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.07.010"},{"key":"S0960129512000035_ref15","doi-asserted-by":"crossref","unstructured":"Levy P. B. (2002) Possible world semantics for general storage in call-by-value. In: Proceedings of CSL 232\u2013246.","DOI":"10.1007\/3-540-45793-3_16"},{"key":"S0960129512000035_ref20","doi-asserted-by":"crossref","unstructured":"Parkinson M. and Bierman G. (2008) Separation logic, abstraction and inheritance. In: Proceedings of POPL 75\u201386.","DOI":"10.1145\/1328438.1328451"},{"key":"S0960129512000035_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_29"},{"key":"S0960129512000035_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926401"},{"key":"S0960129512000035_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/504709.504712"},{"key":"S0960129512000035_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1929553.1929565"},{"key":"S0960129512000035_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90027-5"},{"key":"S0960129512000035_ref1","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480925"},{"key":"S0960129512000035_ref24","doi-asserted-by":"crossref","unstructured":"Pottier F. (2008) Hiding local state in direct style: a higher-order anti-frame rule. In: Proceedings of LICS 331\u2013340.","DOI":"10.1109\/LICS.2008.16"},{"key":"S0960129512000035_ref12","doi-asserted-by":"crossref","unstructured":"Dreyer D. , Neis G. and Birkedal L. (2010) The impact of higher-order state and control effects on local relational reasoning. In: Proceedings of ICFP.","DOI":"10.1145\/1863543.1863566"},{"key":"S0960129512000035_ref13","doi-asserted-by":"crossref","unstructured":"Gotsman A. , Berdine J. , Cook B. , Rinetzky N. and Sagiv M. (2007) Local reasoning for storable locks and threads. Technical Report MSR-TR-2007-39, Microsoft Research.","DOI":"10.1145\/1273920.1273941"},{"key":"S0960129512000035_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411235"},{"key":"S0960129512000035_ref18","doi-asserted-by":"crossref","unstructured":"O'Hearn P. W. , Yang H. and Reynolds J. C. (2004) Separation and information hiding. In: Proceedings of POPL 268\u2013280.","DOI":"10.1145\/964001.964024"},{"key":"S0960129512000035_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78739-6_27"},{"key":"S0960129512000035_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71316-6_14"},{"key":"S0960129512000035_ref34","volume-title":"Handbook of Logic in Computer Science","author":"Smyth","year":"1992"},{"key":"S0960129512000035_ref19","doi-asserted-by":"crossref","unstructured":"Parkinson M. and Bierman G. (2005) Separation logic and abstraction. In: Proceedings of POPL 247\u2013258.","DOI":"10.1145\/1040305.1040326"},{"key":"S0960129512000035_ref31","doi-asserted-by":"crossref","unstructured":"Schwinghammer J. , Birkedal L. and St\u00f8vring K. (2011) A step-indexed Kripke model of hidden state via recursive properties on recursively defined metric spaces. In: Proceedings of FOSSACS 305\u2013319.","DOI":"10.1007\/978-3-642-19805-2_21"},{"key":"S0960129512000035_ref4","unstructured":"Benton N. , Birkedal L. , Kennedy A. and Varming C. (2010) Formalizing domains, ultrametric spaces and semantics of programming languages (draft)."},{"key":"S0960129512000035_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.035"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129512000035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T14:03:36Z","timestamp":1687701816000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129512000035\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,31]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["S0960129512000035"],"URL":"https:\/\/doi.org\/10.1017\/s0960129512000035","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,31]]}}}