Set Based Analysis of ML Programs (Extended Abstract)
Nevin Heintze · 1993
) NEVIN HEINTZE School of Computer Science Carnegie Mellon University July 28, 1993 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 O(n 3 ) 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. 5000 Forbes Ave., Pittsburgh, PA 152...