AD-A270 597 ( Set Based Analysis of ML Programs (Exended Abstract)

Also appears as Fox Memorandum CMU-CS-FOX-93-03 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 0(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