Selectors make set-based analysis too hard

Philippe Meunier*, Robert Bruce Findler, Paul Steckler, Mitchell Wand

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)245-269
Number of pages25
JournalHigher-Order and Symbolic Computation
Volume18
Issue number3-4
DOIs
StatePublished - Dec 2005

Keywords

  • Program analysis
  • Scheme
  • Set-based analysis
  • Static debugging

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Selectors make set-based analysis too hard'. Together they form a unique fingerprint.

Cite this