Accession Number:

ADA270597

Title:

Set Based Analysis of ML Programs

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-07-01

Pagination or Media Count:

22.0

Abstract:

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE