Write a Blog >>
ICFP 2016
Sun 18 - Sat 24 September 2016 Nara, Japan
Wed 21 Sep 2016 13:55 - 14:20 at Noh Theater - Session 10 Chair(s): John Reppy

The polyvariance of a static analysis is the degree to which it structurally differentiates approximations of program values. Polyvariant techniques come in a number of different flavors that represent alternative heuristics for managing the trade-off an analysis strikes between precision and complexity. For example, call sensitivity supposes that values will tend to correlate with recent call sites, object sensitivity supposes that values will correlate with the allocation points of related objects, the Cartesian product algorithm supposes correlations between the values of arguments to the same function, and so forth.

In this paper, we describe a unified methodology for implementing and understanding polyvariance in a higher-order setting (i.e., for control-flow analyses). We do this by extending the method of abstracting abstract machines (AAM), a systematic approach to producing an abstract interpretation of abstract-machine semantics. AAM eliminates recursion within a languageā€™s semantics by passing around an explicit store, and thus places importance on the strategy an analysis uses for allocating abstract addresses within the abstract heap or store. We build on AAM by showing that the design space of possible abstract allocators exactly and uniquely corresponds to the design space of polyvariant strategies. This allows us to both unify and generalize polyvariance as tunings of a single function. Changes to the behavior of this function easily recapitulate classic styles of analysis and produce novel variations, combinations of techniques, and fundamentally new techniques.

Wed 21 Sep
Times are displayed in time zone: (GMT+09:00) Osaka, Sapporo, Tokyo change

13:30 - 14:45: Research Papers - Session 10 at Noh Theater
Chair(s): John ReppyUniversity of Chicago
icfp-2016-papers13:30 - 13:55
Ram RaghunathanCarnegie Mellon University, USA, Stefan K. MullerCarnegie Mellon University, USA, Umut A. AcarCarnegie Mellon University, Guy BlellochCarnegie Mellon University, USA
icfp-2016-papers13:55 - 14:20
Thomas GilrayUniversity of Utah, USA, Michael D. AdamsUniversity of Utah, USA, Matthew MightUniversity of Utah, USA
icfp-2016-papers14:20 - 14:45
Katsuhiro UenoTohoku University, Japan, Atsushi OhoriTohoku University, Japan