Selector-based versus conditional-constraint-based value-flow analysis of programs

[摘要] MrSpidey, a program debugger for PLT Scheme, infers the flow of values in a program. It uses Flanagan's selector-based analysis framework. Unfortunately, due to limitations of that framework, the debugger often flags potential errors where none exists. In particular, it is too conservative when analyzing n-ary functions, functions with rest arguments, and arity-overloaded functions (case-lambda). Flanagan's analysis can be extended to give more precise results, but at the cost of a high running time. We therefore conclude that this framework is not well suited to analyzing functions in real-world programming languages.To overcome the limitations of Flanagan's framework, we develop an alternative based on Palsberg and Schwartzbach's conditional constraint rules. After scaling the analysis to the full R5RS Scheme language (adding primitives using types, multiples values, imperativeness, and generative structures), experiments show that it infers value sets as precisely as the extended selector-based analysis and runs significantly faster.

[发布机构] Rice University

[效力级别] science