Variables as Resource in Separation Logic
Author(s) -
Richard Bornat,
Cristiano Calcagno,
Hongseok Yang
Publication year - 2006
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2005.11.059
Subject(s) - separation logic , computer science , concurrency , correctness , heap (data structure) , programming language , variable (mathematics) , theoretical computer science , mathematics , mathematical analysis
eparation logic [Reynolds, J. C., Intuitionistic reasoning about shared mutable data structure, in: J. Davies, B. Roscoe and J. Woodcock, editors, Millennial Perspectives in Computer Science, Palgrave, 2000 pp. 303–321; Reynolds, J. C., Separation logic: A logic for shared mutable data structures, in: LICS '02: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science (2002), pp. 55–74; O'Hearn, P., J. Reynolds and H. Yang, Local reasoning about programs that alter data structures, in: L. Fribourg, editor, CSL 2001 (2001), pp. 1–19, LNCS 2142] began life as an extended formalisation of Burstall's treatment of list-mutating programs [Burstall, R., Some techniques for proving correctness of programs which alter data structures, Machine Intelligence 7 (1972), pp. 23–50]. It rapidly became clear that there was more that it could say: O'Hearn's discovery [O'Hearn, P., Notes on separation logic for shared-variable concurrency (2002), unpublished] of ownership transfer of buffers between threads and Boyland's suggestion [Boyland, J., Checking interference with fractional permissions, in: R. Cousot, editor, Static Analysis: 10th International Symposium, Lecture Notes in Computer Science 2694 (2003), pp. 55–72] of permissions to deal with variable and heap sharing pointed the way to a treatment of safe resource management in concurrent programs. That treatment has so far been incomplete because it deals only with heap cells and not with with (stack) variables as resource. Adding variable contexts' — in the simplest case, lists of owned variables — to assertions in Hoare logic allows a resource treatment of variables. It seems that a formal treatment of aliasing is possible too. It gives a complete formal treatment of critical sections (for the first time, so far as I am aware)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom