Set-Based Analysis of ML Programs (Extended Abstract)

Reasoning about program variables as sets of "values" leads to a simple, accurate and intuitively appealing notion of program approximation. This paper presents approach for the compile-time analysis of ML programs. To develop the core ideas of the analysis, we consider a simple untyped callby -value functional language. Starting with an operational semantics for the language, we develop an approximate "setbased" operational semantics, which formalizes the intuition of treating program variables as sets. The key result of the paper is an O(n³) algorithm for computing the set based approximation of a program. We then extend this analysis in a natural way to deal with arrays, arithmetic, exceptions and continuations. We briefly describe our experience with an implementation of this analysis for ML programs