DDP: Demand-Driven Analysis with Goal Pruning

Overview

DDP is an approach to static program analysis. It was developed in the Chuck project. Chuck is a program-editor (analogous to Eclipse, Dr. Scheme, Star Browser, ....) for Squeak Smalltalk. It faces a combination of challenges including large programs (300 kloc), higher-order control flow, a high rate of programmer-driven code changes, and no static types to fall back on.

Technically, the DDP approach has two defining characteristics:

It is demand-driven: it posts goals to itself and then tries to answer those goals. In the course of answering one goal, it can spawn new goals as subgoals.
It prunes goals: just because it has posted a goal does not mean that the analyzer will find the best possible answer for that goal. DDP selectively prunes less-important goals, giving them trivial solutions, so that there is more time to focus on more-important goals and so that the overall number of goals is limited.

Intuitively, this combination means that DDP controls the level of effort it places on different information goals. It puts a lot of effort on finding the answer to a goal specified directly by the user, whereas it puts less effort on increasingly subsidiary goals. Demand-driven normally have trouble in that some initial goals cause most of the entire program to be traversed--i.e., the minimal portion of a program that must be analyzed can be most of the program! DDP uses pruning to prevent this.

I believe the DDP approach is useful beyond the original problem of Smalltalk type inference. I am now exploring DDP analysis for entire Scala codebases. This new problem opens questions like:

How should exhaustive analysis of entire programs be performed? In particular, How can subsidiary goals be reused between different top-level goals?
What kind of context-sensitivity
How does it matter what order goals are updated? For intra-procedural analysis, different orders yield different speeds of convergence. DDP makes the problem more complex because the set of active goals changes as the analysis proceeds.
What analysis questions pay off in this context? Dead-code removal? Inlining? Specialization? Verification tools?

It is not yet clear for sure. I will tell you how it goes!

Documents

The current documentation about DDP comes from the Chuck project. The most comprehensive information to date is in the following documents:

"Demand-Driven Type Inference with Subgoal Pruning", an evolving online report. An evolving document, posted only online, with the best one-stop description of the research project to date. This is the place to start if you want to learn about the DDP analyzer in general.
"Demand-Driven Type Inference with Subgoal Pruning", my dissertation. My dissertation is older than the evolving online report, but it has been rigorously reviewed through the standard Ph.D. process. The raw Squeak experimental results are in chuck-results-f2004.tar.bz2. Load them in Squeak 3.7 using fileInObjectAndCode.

The following peer-reviewed conference papers have been published about DDP and Chuck:

"Demand-Driven Type Inference with Subgoal Pruning: Trading Precision for Scalability" (pdf ps) (ECOOP 2004). This paper describes the DDP algorithm in general. The experimental results described in the paper are in "Classification of Types Inferred in DDP Experiment" (ps.gz pdf). The raw experimental data is in chuck-results-ecoop04.tar.bz2.
"Semantic Navigation of Large Code Bases in Higher-Order, Dynamically Typed Languages" (WCRE 2005). This paper describes the Chuck user interface. This describes DDP being used for its originally intended goal.
"Dynamic Data Polyvariance Using Source-Tagged Classes" (DLS 2005). This paper describes the "class tags" extension to DDP, called DDP/CT. DDP/CT can effectively analyze data-polymorphic code such as collection types.

For full citation information on these documents, see lexspoon.bib.

Lex Spoon