Collecting interpretations of expressions
Authors:
Open Access
- 1 April 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 13 (2) , 269-290
Abstract
A collecting interpretation of expressions is an interpretation of a program that allows one to answer questions of the sort: “What are all possible values to which an expression might evaluate during program execution?” Answering such questions in a denotational framework is akin to traditional data flow analysis and, when used in the context of abstract interpretation, allows one to infer properties that approximate the run-time behavior of expression evaluation. Exact collecting interpretations of expressions are developed for three abstract functional languages: a strict first-order language, a nonstrict first-order language, and a nonstrict higher order language (the full untyped lambda calculus with constants). It is argued that the method is simple (in particular, no powerdomains are needed), Natural (it captures the intuitive operational behavior of a cache), yet more expressive than existing methods (it is the first exact collecting interpretation for either nonstrict higher order languages). Correctness of the interpretations with respect to the standard semantics is shown via a generalization of the notion of strictness. It is further shown how to form abstractions of these exact interpretations, using as an example a collecting strictness analysis which yields compile-time information not previously captured by conventional strictness analyses.Keywords
This publication has 10 references indexed in Scilit:
- Detecting sharing of partial applications in functional programsLecture Notes in Computer Science, 1987
- Projections for strictness analysis1987
- Static evaluation of functional programsACM SIGPLAN Notices, 1986
- Data flow analysis of applicative programs using minimal function graphs1986
- A semantic model of reference counting and its abstraction (detailed summary)1986
- Code generation techniques for functional languages1986
- Higher-order strictness analysis in untyped lambda calculus1986
- The theory and practice of transforming call-by-need into call-by-value1980
- Systematic design of program analysis frameworks1979
- Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints1977