© 1990 by British Computer Society
Reference Counting of Cyclic Graphs for Functional Programs
Computer Science, University of Birmingham, Birmingham B15 2TT, UK
A simple method of reference counting applicable to graphs of functional language programs is described. The graph contains strong and weak pointers, but only the strong pointers are counted in the reference counts and by the graph deletion algorithms.
It is shown that graphs of functional programs can be constructed in such a way that the sub-graphs got by removing all weak pointers is connected and acyclic. The weak pointers are used only for those recursive references which create cycles in an otherwise acyclic graph. Explicit recursive definitions of functions and data structures may be represented in the graph.
The usual graph reduction rules can be implemented so that they do not destroy the required properties of the graph: the sub-graph of strong pointers always remains connected and acyclic. Thus, simple reference counting can be used safely with cyclic graphs of functional programs
This method of storage management has the advantage that is incurs little overhead in either storage space or execution time of beta reduction. Nor is there any excessive increase in the complexity of the algorithm needed for graph reduction. It is less suitable, however, for combinator and supercombinator reduction.
Received January 1988. revised May 1988.
* Computer Science, University of Birmingham, Birmingham B15 2TT