research-article

Contextual effects for version-consistent dynamic software updating and safe concurrent programming

Authors:

Iulian Neamtiu,

Jeffrey S. Foster,

Polyvios PratikakisAuthors Info & Claims

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 37 - 49

https://doi.org/10.1145/1328438.1328447

Published: 07 January 2008 Publication History

Abstract

This paper presents a generalization of standard effect systems that we call contextual effects. A traditional effect system computes the effect of an expression e. Our system additionally computes the effects of the computational context in which e occurs. More specifically, we computethe effect of the computation that has already occurred(the prior effect) and the effect of the computation yet to take place (the future effect).

Contextual effects are useful when the past or future computation of the program is relevant at various program points. We present two substantial examples. First, we show how prior and future effects can be used to enforce transactional version consistency(TVC), a novel correctness property for dynamic software updates. TV Censures that programmer-designated transactional code blocks appear to execute entirely at the same code version, even if a dynamic update occurs in the middle of the block. Second, we show how future effects can be used in the analysis of multi-threaded programs to find thread-shared locations. This is an essential step in applications such as data race detection.

References

[1]

Martin Abadi and Cedric Fournet. Access control based on execution history. In NDSS, 2003.

[2]

Andrew Baumann, Gernot Heiser, Jonathan Appavoo, et al. Providing dynamic update in an operating system. In USENIX, 2005.

Digital Library

[3]

Andrew Baumann, Jonathan Appavoo, Robert W. Wisniewski, et al. Reboots are for hardware: Challenges and solutions to updating an operating system on the fly. In USENIX, 2007.

Digital Library

[4]

Chandrasekhar Boyapati, Barbara Liskov, Liuba Shrira, Chuang-Hue Moh, and Steven Richman. Lazy modular upgrades in persistent object stores. In OOPSLA, 2003.

Digital Library

[5]

Haibo Chen, Rong Chen, Fengzhe Zhang, Binyu Zang, and Pen-Chung Yew. Live updating operating systems using virtualization. In VEE, 2006.

Digital Library

[6]

Haibo Chen, Jie Yu, Rong Chen, Binyu Zang, and Pen-Chung Yew. POLUS: A POwerful Live Updating System. In ICSE, pages 271--281, 2007.

Digital Library

[7]

Dawson Engler and Ken Ashcraft. RacerX: effective, static detection of race conditions and deadlocks. In SOSP, 2003.

Digital Library

[8]

Cormac Flanagan and Stephen N. Freund. Type-based race detection for Java. In PLDI, 2000.

Digital Library

[9]

Jeffrey S. Foster, Robert Johnson, John Kodumal, and Alex Aiken. Flow-Insensitive Type Qualifiers. TOPLAS, 28(6):1035--1087, November 2006.

Digital Library

[10]

Stephen Gilmore, Dilsun Kirli, and Chris Walton. Dynamic ML without dynamic types. Technical Report ECS-LFCS-97-378, LFCS, University of Edinburgh, 1997.

[11]

Tim Harris and Keir Fraser. Language support for lightweight transactions. In OOPSLA, 2003.

Digital Library

[12]

M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, 1993.

Digital Library

[13]

Michael Hicks, Jeffrey S. Foster, and Polyvios Pratikakis. Lock Inference for Atomic Sections. In TRANSACT, 2006.

[14]

Atsushi Igarashi and Naoki Kobayashi. Resource Usage Analysis. In POPL, Portland, Oregon, 2002.

Digital Library

[15]

John Kodumal and Alexander Aiken. Banshee: A scalable constraint-based analysis toolkit. In SAS, 2005.

Digital Library

[16]

Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. CACM, 21(7):558--565, 1978.

Digital Library

[17]

Insup Lee. DYMOS: A Dynamic Modification System. PhD thesis, Dept. of Computer Science, University of Wisconsin, Madison, April 1983.

Digital Library

[18]

John M. Lucassen. Types and Effects: Towards the Integration of Functional and Imperative Programming. PhD thesis, MIT Laboratory for Computer Science, August 1987. MIT/LCS/TR-408.

[19]

Kristis Makris and Kyung Dong Ryu. Dynamic and adaptive updates of non-quiescent subsystems in commodity operating system kernels. In Proc. EuroSys, March 2007.

Digital Library

[20]

Jeremy Manson, William Pugh, and Sarita V. Adve. The Java Memory Model. In POPL, 2005.

Digital Library

[21]

John C. Mitchell. Type inference with simple subtypes. JFP, 1(3):245--285, July 1991.

[22]

Mayur Naik and Alex Aiken. Conditional must not aliasing for static race detection. In POPL, 2007.

Digital Library

[23]

Mayur Naik, Alex Aiken, and John Whaley. Effective static race detection for java. In PLDI, 2006.

Digital Library

[24]

Iulian Neamtiu, Jeffrey S. Foster, and Michael Hicks. Understanding Source Code Evolution Using Abstract Syntax Tree Matching. In MSR'05, 2005. URL http://www.cs.umd.edu/~mwh/papers/evolution.pdf.

Digital Library

[25]

Iulian Neamtiu, Michael Hicks, Gareth Stoyle, and Manuel Oriol. Practical dynamic software updating for C. In PLDI, 2006.

Digital Library

[26]

Iulian Neamtiu, Michael Hicks, Jeffrey S. Foster, and Polyvios Pratikakis. Contextual Effects for Version-Consistent Dynamic Software Updating and Safe Concurrent Programming. Technical Report CS-TR-4920, Dept. of Computer Science, University of Maryland, November 2007.

[27]

George C. Necula, Scott McPeak, Shree P. Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. LNCS, 2304:213--228, 2002.

Digital Library

[28]

Yang Ni, Vijay S. Menon, Ali-Reza Adl-Tabatabai, et al. Open nesting in software transactional memory. In PPoPP, 2007.

Digital Library

[29]

Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer-Verlag, 1999. ISBN 3540654100.

Digital Library

[30]

Polyvios Pratikakis, Jeffrey S. Foster, and Michael Hicks. Context-sensitive correlation analysis for detecting races. In PLDI, 2006.

Digital Library

[31]

Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. Eraser: A Dynamic Data Race Detector for Multi--Threaded Programs. In SOSP, 1997.

Digital Library

[32]

Christian Skalka, Scott Smith, and David Van Horn. Types and trace effects of higher order programs. JFP, July 2007. Forthcoming; available on-line at http://www.journals.cambridge.org.

Digital Library

[33]

Fred Smith, David Walker, and Greg Morrisett. Alias types. In ESOP, 2000.

Digital Library

[34]

Craig AN. Soules, Jonathan Appavoo, Kevin Hui, et al. System support for online reconfiguration. In USENIX, 2003.

[35]

Gareth Stoyle, Michael Hicks, Gavin Bierman, Peter Sewell, and Iulian Neamtiu. Mutatis Mutandis: Safe and flexible dynamic software updating (full version). TOPLAS, 29(4):22, August 2007.

Digital Library

[36]

Christoph von Praun and Thomas R. Gross. Static conflict analysis for multi-threaded object-oriented programs. In PLDI '03, 2003.

Digital Library

[37]

David Walker, Karl Crary, and Greg Morrisett. Typed memory management in a calculus of capabilities. TOPLAS, 24(4):701--771, July 2000.

Digital Library

Cited By

Larisch JMickens JKohler ETilevich EMössenböck H(2018)AltoProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237022(1-7)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237022
Baresi LGhezzi CMa XManna V(2017)Efficient Dynamic Updates of Distributed Components Through Version ConsistencyIEEE Transactions on Software Engineering10.1109/TSE.2016.259291343:4(340-358)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TSE.2016.2592913
Long YLiu YRajan H(2016)First-class effect reflection for effect-guided programmingACM SIGPLAN Notices10.1145/3022671.298403751:10(820-837)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984037
Show More Cited By

Index Terms

Recommendations

Contextual effects for version-consistent dynamic software updating and safe concurrent programming
POPL '08

This paper presents a generalization of standard effect systems that we call contextual effects. A traditional effect system computes the effect of an expression e. Our system additionally computes the effects of the computational context in which e ...
Contextual effects in the visual cortex area 1 (v1) and camouflage perception
PerMIn'12: Proceedings of the First Indo-Japan conference on Perception and Machine Intelligence

The cells in the visual cortex area 1 (V1) and area 2 (V2) show context dependent modulation in their responses. Suppressive as well as modulatory effects from stimuli well outside the classical receptive field are observed. This is attributed to the ...
Dynamic software updating: a systematic mapping study

Dynamic software updating (DSU) is shifting gears to modify software systems without a halt. Even though extensive research has been conducted on DSU, it is necessary to synthesise and map the results of recent studies on DSU for prospective research ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2008

448 pages

ISBN:9781595936899

DOI:10.1145/1328438

General Chair:
George Necula
University of California, Berkeley
,
Program Chair:
Philip Wadler
University of Edinburgh

ACM SIGPLAN Notices Volume 43, Issue 1
POPL '08
January 2008
420 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1328897
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL08

Sponsor:

POPL08: The 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 7 - 12, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
639
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Larisch JMickens JKohler ETilevich EMössenböck H(2018)AltoProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237022(1-7)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237022
Baresi LGhezzi CMa XManna V(2017)Efficient Dynamic Updates of Distributed Components Through Version ConsistencyIEEE Transactions on Software Engineering10.1109/TSE.2016.259291343:4(340-358)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TSE.2016.2592913
Long YLiu YRajan H(2016)First-class effect reflection for effect-guided programmingACM SIGPLAN Notices10.1145/3022671.298403751:10(820-837)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984037
Long YLiu YRajan HVisser ESmaragdakis Y(2016)First-class effect reflection for effect-guided programmingProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984037(820-837)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2984037
Kusum ANeamtiu IGupta RZaks AHermenegildo M(2016)Safe and flexible adaptation via alternate data structure representationsProceedings of the 25th International Conference on Compiler Construction10.1145/2892208.2892220(34-44)Online publication date: 17-Mar-2016
https://dl.acm.org/doi/10.1145/2892208.2892220
Zhao ZGu TMa XXu CLu J(2016)CURE: Automated Patch Generation for Dynamic Software Update2016 23rd Asia-Pacific Software Engineering Conference (APSEC)10.1109/APSEC.2016.043(249-256)Online publication date: 2016
https://doi.org/10.1109/APSEC.2016.043
Hicks MBierman GGuts NLeijen DSwamy N(2014)Polymonadic ProgrammingElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.153.7153(79-99)Online publication date: 5-Jun-2014
https://doi.org/10.4204/EPTCS.153.7
Brasser FBucicoiu MSadeghi AAhn GOprea ASafavi-Naini R(2014)Swap and PlayProceedings of the 6th edition of the ACM Workshop on Cloud Computing Security10.1145/2664168.2664173(33-44)Online publication date: 7-Nov-2014
https://dl.acm.org/doi/10.1145/2664168.2664173
Hayden CSaur KSmith EHicks MFoster J(2014)KitsuneACM Transactions on Programming Languages and Systems10.1145/262946036:4(1-38)Online publication date: 28-Oct-2014
https://dl.acm.org/doi/10.1145/2629460
Giuffrida CKuijsten ATanenbaum A(2013)Safe and automatic live update for operating systemsACM SIGPLAN Notices10.1145/2499368.245114748:4(279-292)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451147
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents