Introspective pushdown analysis of higher-order programs
Authors:
Open Access
- 9 September 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 47 (9) , 177-188
Abstract
In the static analysis of functional programs, pushdown flow analysis and abstract garbage collection skirt just inside the boundaries of soundness and decidability. Alone, each method reduces analysis times and boosts precision by orders of magnitude. This work illuminates and conquers the theoretical challenges that stand in the way of combining the power of these techniques. The challenge in marrying these techniques is not subtle: computing the reachable control states of a pushdown system relies on limiting access during transition to the top of the stack; abstract garbage collection, on the other hand, needs full access to the entire stack to compute a root set, just as concrete collection does. Introspective pushdown systems resolve this conflict. Introspective pushdown systems provide enough access to the stack to allow abstract garbage collection, but they remain restricted enough to compute control-state reachability, thereby enabling the sound and precise product of pushdown analysis and abstract garbage collection. Experiments reveal synergistic interplay between the techniques, and the fusion demonstrates "better-than-both-worlds" precision.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- CFA2: A Context-Free Approach to Control-Flow AnalysisLecture Notes in Computer Science, 2010
- Control-flow analysis of function calls and returns by abstract interpretation2009
- Model Checking Via ΓCFA2007
- Weighted pushdown systems and their application to interprocedural dataflow analysisScience of Computer Programming, 2005
- The set constraint/CFL reachability connection in practiceACM SIGPLAN Notices, 2004
- Interconvertibility of a class of set constraints and context-free-language reachabilityTheoretical Computer Science, 2000
- Program analysis via graph reachabilityInformation and Software Technology, 1998
- Polymorphic splittingACM Transactions on Programming Languages and Systems, 1998
- A calculus for assignments in higher-order languages1987
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints1977