DDP: Demand-Driven Analysis with Goal Pruning


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:

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:

  1. How should exhaustive analysis of entire programs be performed? In particular, How can subsidiary goals be reused between different top-level goals?
  2. What kind of context-sensitivity
  3. 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.
  4. 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!


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

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

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

Lex Spoon