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:
- 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
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!
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