Collecting Interpretations of Expressions


Paul Hudak and Jonathan Young


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.

In this paper collecting interpretations of expressions are developed for three abstract functional languages: (1) a first-order language with call-by-value semantics, (2) a first-order language with call-by-name semantics, and (3) a higher-order language with call-by-name semantics (i.e., 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 lazy or higher-order programs).


    ,author={Hudak, P. and Young, J.}
    ,title={Collecting Interpretations of Expressions}
    ,journal={ACM Transactions on Programming Languages and Systems}
    ,note={Preliminary version appeared in the Proceedings of the
           1988 ACM Symposium on Principles of Programming Languages.}