Static analysis of dynamic and functional programming languages requires a precise accounting of various interpenetrating concerns. For example, in functional languages like Racket, a precise analysis of data flow (for closures) is required for a precise analysis of control flow, and in dynamic scripting languages like JavaScript, a precise modeling of hashmaps and their keys is required for every use of an object's fields and methods. For each of these concerns, a careful compromise must be struck between precision and complexity for an analysis to provide useful information at a reasonable computational cost.

 

In this talk, I will review abstracting abstract machines (AAM), a general methodology for deriving a static analysis from a language's concrete (exact) semantics, and show how this approach may be extended to the notion of polyvariance. Specific polyvariant techniques such as call sensitivity, object sensitivity, and argument sensitivity, represent strategies for managing the trade-off between precision and complexity in an analysis and may be well suited for one program, while being both expensive and ineffective on another. I will show how a single function in AAM-style analyses, an allocator, can be used to both unify and generalize this class of techniques. I will then apply this new perspective to developing an introspective polyvariant technique which guarantees perfect stack precision (i.e., no conflation of return flows) for free---that is, at no asymptotic complexity overhead and requiring only the replacement of an allocation function, a trivial change in AAM-style analyses.