It is not that often that you learn something and get a good laugh from a Ph.D. thesis. Hence, Shivers’ Control-flow analysis of higher-order languages has been a pleasant surprise.

He is at the origin of k-CFA, a class of static analyses that tackle the dynamic dispatch problem with context-sensitive data-flow analysis. Even though the analysis is targeted at functional languages, it also applies to object-oriented languages with virtual function calls (see Matt Might for a gentle introduction). From Shivers’ thesis:

So, if we wish to have a control-flow graph for a piece of Scheme code, we need to answer the following question: for every procedure call in the program, what are the possible lambda expressions that call could be a jump to? But this is a flow analysis question! So with regard to flow analysis in a [higher-order language], we are faced with the following unfortunate situation:

• In order to do flow analysis, we need a control-flow graph.
• In order to determine control-flow graphs, we need to do flow analysis.

The problem could be rephrased for Java as: “if we wish to have an [inter-procedural] control flow graph for a Java application, we need to answer the following question: for every instance method call, what classes could the object be an instance of?”