Termination is an important but undecidable program property, which has led to a large body of work on static methods for conservatively predicting or enforcing termination. One such method is the size-change termination approach of Lee, Jones, and Ben-Amram, which operates in two phases: (1) abstract programs into “size-change graphs,” and (2) check these graphs for the size-change property: the existence of paths that lead to infinite decreasing sequences. We transpose these two phases with an operational semantics that accounts for the run-time enforcement of the size-change property, postponing (or entirely avoiding) program abstraction. This choice has two key consequences: (1) size-change termination can be checked at run-time and (2) termination can be rephrased as a safety property analyzed using existing methods for systematic abstraction. We formulate run-time size-change checks as contracts in the style of Findler and Felleisen. The result compliments existing contracts that enforce partial correctness specifications to obtain contracts for total correctness. Our approach combines the robustness of the size-change principle for termination with the precise information available at run-time. It has tunable overhead and can check for nontermination without the conservativeness necessary in static checking. To obtain a sound and computable termination analysis, we apply existing abstract interpretation techniques directly to the operational semantics, avoiding the need for custom abstractions for termination. The resulting analyzer is competitive with with existing, purpose-built analyzers.
Tue 25 JunDisplayed time zone: Tijuana, Baja California change
14:00 - 15:30 | Static AnalysisPLDI Research Papers at 229AB Chair(s): Martin C. Rinard Massachusetts Institute of Technology | ||
14:00 20mTalk | Abstract Interpretation under Speculative Execution PLDI Research Papers Media Attached | ||
14:20 20mTalk | A Fast Analytical Model of Fully Associative Caches PLDI Research Papers Tobias Gysi ETH Zurich, Switzerland, Tobias Grosser ETH Zurich, Laurin Brandner ETH Zurich, Switzerland, Torsten Hoefler ETH Zurich Media Attached | ||
14:40 20mTalk | Sound, Fine-Grained Traversal Fusion for Heterogeneous Trees PLDI Research Papers Laith Sakka Purdue University, Kirshanthan Sundararajah Purdue University, Ryan R. Newton Indiana University, Milind Kulkarni Purdue University Media Attached | ||
15:00 20mTalk | Size-Change Termination as a Contract PLDI Research Papers Phúc C. Nguyễn University of Maryland, Thomas Gilray University of Maryland, Sam Tobin-Hochstadt Indiana University, David Van Horn University of Maryland, USA Media Attached |