[Pl-seminar] PL seminar schedule

[Aaron Turon]

NEU Programming Languages Seminar presents

Dimitris Vardoulakis

Wednesday, February 3, 2009
11:45-1:30
Room 366 WVH (http://www.ccs.neu.edu/home/wand/directions.html)

Title:  CFA2: a Context-Free Approach to Control-Flow Analysis

Abstract:

In a functional language, the dominant control-flow mechanism is
function call and return. Most higher-order flow analyses, including
k-CFA, do not handle call and return well: they remember only a
bounded number of pending calls because they approximate programs with
control-flow graphs. Call/return mismatch introduces
precision-degrading spurious control-flow paths and increases the
analysis time.

In this talk I will discuss CFA2, the first flow analysis with precise
call/return matching in the presence of higher-order functions and
tail calls. I will show some of the limitations of k-CFA, and how CFA2
overcomes them. Like kCFA, CFA2 is based on abstract interpretation.
However, its abstract state space is infinite and the standard
algorithms for k-CFA won't terminate. I will describe a
dynamic-programming technique called summarization, and how it can be
used to explore the state space of CFA2.

Olin and I have written up these ideas in the paper "CFA2: a
Context-Free Approach to Control-Flow Analysis", which will appear in
ESOP 2010.