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

Displayed time zone: Osaka, Sapporo, Tokyo change

13:30 - 14:45
Session 10Research Papers at Noh Theater
Chair(s): John Reppy University of Chicago
13:30
25m
Talk
Hierarchical Memory Management for Parallel Programs
Research Papers
Ram Raghunathan Carnegie Mellon University, USA, Stefan K. Muller Carnegie Mellon University, USA, Umut A. Acar Carnegie Mellon University, Guy Blelloch Carnegie Mellon University, USA
DOI
13:55
25m
Talk
Allocation Characterizes Polyvariance: A Unified Methodology for Polyvariant Control-Flow Analysis
Research Papers
Thomas Gilray University of Utah, USA, Michael D. Adams University of Utah, USA, Matthew Might University of Utah, USA
DOI
14:20
25m
Talk
A Fully Concurrent Garbage Collector for Functional Programs on Multicore Processors
Research Papers
Katsuhiro Ueno Tohoku University, Japan, Atsushi Ohori Tohoku University, Japan
DOI