TY - JOUR
T1 - Selectors make set-based analysis too hard
AU - Meunier, Philippe
AU - Findler, Robert Bruce
AU - Steckler, Paul
AU - Wand, Mitchell
PY - 2005/12
Y1 - 2005/12
N2 - A set-based program analysis establishes constraints between sets of abstract values for all expressions in a program. Solving the system of constraints produces a conservative approximation to the program's runtime flow of values. Some practical set-based analyses use explicit selectors to extract the relevant values from an approximation set. For example, if the analysis needs to determine the possible return values of a procedure, it uses the appropriate selector to extract the relevant component from the abstract representation of the procedure. In this paper, we show that this selector-based approach complicates the constraint solving phase of the analysis too much and thus fails to scale up to realistic programming languages. We demonstrate this claim with a full-fledged value flow analysis for case-lambda, a multi-branched version of lambda. We show how both the theoretical underpinnings and the practical implementation become too complex. In response, we present a variant of set-based closure analysis that computes equivalent results in a much more efficient manner.
AB - A set-based program analysis establishes constraints between sets of abstract values for all expressions in a program. Solving the system of constraints produces a conservative approximation to the program's runtime flow of values. Some practical set-based analyses use explicit selectors to extract the relevant values from an approximation set. For example, if the analysis needs to determine the possible return values of a procedure, it uses the appropriate selector to extract the relevant component from the abstract representation of the procedure. In this paper, we show that this selector-based approach complicates the constraint solving phase of the analysis too much and thus fails to scale up to realistic programming languages. We demonstrate this claim with a full-fledged value flow analysis for case-lambda, a multi-branched version of lambda. We show how both the theoretical underpinnings and the practical implementation become too complex. In response, we present a variant of set-based closure analysis that computes equivalent results in a much more efficient manner.
KW - Program analysis
KW - Scheme
KW - Set-based analysis
KW - Static debugging
UR - http://www.scopus.com/inward/record.url?scp=28244480233&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=28244480233&partnerID=8YFLogxK
U2 - 10.1007/s10990-005-4876-5
DO - 10.1007/s10990-005-4876-5
M3 - Article
AN - SCOPUS:28244480233
SN - 1388-3690
VL - 18
SP - 245
EP - 269
JO - Higher-Order and Symbolic Computation
JF - Higher-Order and Symbolic Computation
IS - 3-4
ER -