Backward Analysis for Higher-Order Functions Using Inverse Images

Abstract

We propose a method for performing backward analysis on higher--order functional programming languages based on computing inverse images of functions over abstract domains. This method can be viewed as abstract interpretation done backward. Given an abstract semantics which supports forward analysis, we can transform it into an abstract semantics which performs backward analysis. We show that if the original abstract semantics is correct and computable, then the transformed version of the abstract semantics is also correct and computable. More specifically, given a forward abstract semantics of a higher--order functional language which is expressed in terms of Scott--closed powerdomains, we derive an backward abstraction semantics which is expressed in terms of Scott--open powerdomains. The derivation is shown to be correct and the relationships between forward analysis and backward analysis is established. We apply this method to the classic strictness analysis in functional languages...

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1991
Accession Number
AD1020198

Entities

People

  • Benjamin M. Goldberg
  • Tyng-ruey Chuang

Organizations

  • Columbia University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Computer Languages
  • Computer Programming
  • Formal Languages
  • Language
  • Linguistics
  • Programming Languages
  • Semantics
  • Two Dimensional
  • Words (Language)

Fields of Study

  • Computer science
  • Engineering
  • Geography

Readers

  • Calculus or Mathematical Analysis
  • Computational Linguistics