Syntactic Accidents in Program Analysis: On the Impact of the CPS Transformation

We show that a non-duplicating CPS transformation has no effect on control-flow analysis and that it has a positive effect on binding-time analysis: a monovariant control-flow analysis yields strictly comparable results on a direct-style program and on its CPS counterpart; and a monovariant binding-time analysis yields more precise results on a CPS program than on its direct-style counterpart. Our proof technique amounts to constructing the continuation-passing style (CPS) counterpart of flow information and of binding times.

Our results confirm a common intuition about control-flow analysis, namely that it is orthogonal to the CPS transformation. They also prove a folklore theorem about binding-time analysis, namely that CPS has a positive impact on binding times. What may be more surprising is that this beneficial effect holds even if contexts or continuations are not duplicated.

The present study is symptomatic of an unsettling property of program analyses: their quality is unpredictably vulnerable to syntactic accidents in source programs, i.e., to the way these programs are written. More reliable program analyses require a better understanding of the effects of syntactic change.

Abstract: