A Semantic Model of Reference Counting and its Abstraction

Authors:

Paul Hudak

Abstract:

In this paper we present a precise semantic model of reference counting for an applicative-order interpreter of a first-order functional language.  Although a reference count is an operational concept, its semantics is expressed in a conventional denotational style.  We also present an abstraction of (or approximation to) the model over finite domains, with a decideable inferencing algorithm.  We demonstrate the usefulness of the abstraction by applying it to some non-trivial programs that can be optimized based on the inferred reference counts.

Bibtex:

 @inproceedings{huda86f
    ,key="hudak"
    ,author="Hudak, P."
    ,title="A semantic model of reference counting and its abstraction"
    ,booktitle="Abstract Interpretation of Declarative Languages"
    ,editors="Abramsky, S. and Hankin, C."
    ,pages="45-62"
    ,year=1987
    ,publisher="Ellis Horwood"
    ,note="(Preliminary version appeared in Proceedings 1986 ACM Conference on
           LISP and Functional Programming, August 1986, pp. 351-363)"
    } 

Links:

AbstractRC.pdf