Set Based Analysis of ML Programs

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 O(n3) 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1993
Accession Number
ADA270597

Entities

People

  • Nevin Heintze

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Arithmetic
  • Compilers
  • Computations
  • Computer Science
  • Construction
  • Environment
  • Grammars
  • Language
  • Safety
  • Safety Analysis
  • Semantics
  • Side Effects
  • Standards

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Operations Research