  Low-level program analysis is a fundamental problem, taking the shape of
"flow analysis" in functional languages and "points-to" analysis in imperative
and object-oriented languages. Despite the similarities, the vocabulary and
results in the two communities remain largely distinct, with limited
cross-understanding. One of the few links is Shivers's $k$-CFA work, which has
advanced the concept of "context-sensitive analysis" and is widely known in
both communities.
  Recent results indicate that the relationship between the functional and
object-oriented incarnations of $k$-CFA is not as well understood as thought.
Van Horn and Mairson proved $k$-CFA for $k \geq 1$ to be EXPTIME-complete;
hence, no polynomial-time algorithm can exist. Yet, there are several
polynomial-time formulations of context-sensitive points-to analyses in
object-oriented languages. Thus, it seems that functional $k$-CFA may actually
be a profoundly different analysis from object-oriented $k$-CFA. We resolve
this paradox by showing that the exact same specification of $k$-CFA is
polynomial-time for object-oriented languages yet exponential- time for
functional ones: objects and closures are subtly different, in a way that
interacts crucially with context-sensitivity and complexity. This illumination
leads to an immediate payoff: by projecting the object-oriented treatment of
objects onto closures, we derive a polynomial-time hierarchy of
context-sensitive CFAs for functional programs.
