A Special Case of Second-Order Strictness Analysis

Abstract

A function declaration is called strict in one of its formal parameters if, in all calls to the function, either the actual corresponding parameter is evaluated, or the call does not terminate. Approximating strictness analysis with abstract interpretation reduces to the evaluation of recursive monotone Boolean functions. This evaluation problem is complete in deterministic exponential time when the functions are declared with only base type formal parameters, and is deterministic super-exponential time hard when functions are formal parameters. However, by coarsening the strictness analysis approximation to be conjunctive, the first-order case can be completed in linear time. This paper will show that the second-order case is NP-hard. Keywords: Programming languages, Semantics.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1989
Accession Number
ADA210829

Entities

People

  • Paul P. Wang

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algebraic Functions
  • Algorithms
  • Calculus
  • Classification
  • Computational Science
  • Computer Languages
  • Computer Science
  • Computers
  • Environment
  • Language
  • Monotone Functions
  • Notation
  • Polynomials
  • Programming Languages
  • Security
  • Standards

Readers

  • Computational Linguistics
  • Operations Research