Open AccessSyntactic Accidents in Program Analysis: On the Impact of the CPS Transformation
Author(s) -
Daniel Damian,
Olivier Danvy
Publication year - 2000
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v7i15.20142
Subject(s) - transformation (genetics) , style (visual arts) , computer science , control (management) , control flow , continuation , property (philosophy) , flow (mathematics) , mathematics , history , programming language , chemistry , artificial intelligence , philosophy , biochemistry , geometry , archaeology , epistemology , gene
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 equivalent 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 folklore theorem about binding-time analysis, namely that CPS has a positive effect on binding times. What may be more surprising is that this benefit 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 effect of syntactic change.