Set Based Analysis of ML Programs
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
Reasoning about a program by treating program variables as sets of values leads to a simple, accurate and intuitively appealing notion of program approximation. This paper presents such an approach for the compile-time analysis of ML programs. To develop the core ideas of the analysis, we consider a simple untyped call-by-value functional language. Starting with an operational semantics for the language, we develop an approximate set based operational semantics which formalizes the intuition of treating program variables as sets. The key result of the paper is an On3 algorithm for computing the set based approximation of a program. We then show how the analysis can be extended in a natural way to deal with arrays, arithmetic, exceptions and continuations. We also briefly describe results from an implementation of this analysis for ML programs.
- Computer Programming and Software