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.

REFERENCES

• 1: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• 2: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 3: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 4: CLARK, D. W., ANO GREEN, C.C. A note on shared list structure in LISP. In{. Process. Lett. 7, 6 (Oct. 1987), 312-315.
• 5: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 6: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 7: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 8: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: INOUE, K., SEKI, H., AND YAGI, H. A method to detect unused list cells at compile time of functional program. In Papers of Technical Group on Automata and Languages (Tokyo, July 1985), The Institute of Electronics and Communications Engineers of Japan, AL85-26, pp. 45-54.
• 10: INOUE, g., SEKI, H., TANIGUCHI, K., AND KASAMI, T. Compiling and optimizing methods for functional language ASL/F. Sci. Comput. Program. 7, 3 (Nov. 1986), 297-312.
• 11: Takuya Katayama, Type inference and type checking for functional programming languages: A reduced computation approach, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.263-272, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802043]
• 12: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 13: MYCROFT, A. Abstract interpretations and optimising transformations for applicative programs. Ph.D. dissertation, University of Edinburgh, Scotland, 1981.
• 14: SEKI, H., INOUE, K., TANIGUCHI, K., AND KASAMI, T. Optimization of functional language ASL/F programs. Trans. o{IECE Japan. J67-D, 10 (Oct. 1984), 1115-1122.
• 15: TAKEUCHI, I. The result of the Lisp contest. Tech. Rep. SYM5-3. Information Processing Society of Japan, Aug. 1978, pp. 1-28.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Optimization

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

General Terms:
Languages, Performance