Analysis of functional programs to detect run-time garbage cells

Abstract

We propose a method for detecting the generation of garbage cells by analyzing a source text written in a functional programming language which uses ordinary linked lists to implement list-type values. For a subexpression such as F ( G ( . . . )) in a program where the function values of F and G are of list type, if a cell c is created during the computation of G and if c does not appear in a list-type value of F , then c becomes a garbage cell at the end of the computation of F . We discuss this problem on the basis of formal languages derived from the functional program text and show some sufficient conditions that predict the generation of garbage cells. Also, we give an efficient algorithm to detect at compile time the generation of garbage cells which are linearly linked. We have implemented these algorithms in an experimental LISP system. By executing several sample programs on the system, we conclude that our method is effective in detecting the generation of garbage cells.