article

Open access

Analysis of functional programs to detect run-time garbage cells

Editor: Susan L. Graham Authors:

Hikaru YagiAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 10, Issue 4

Pages 555 - 578

https://doi.org/10.1145/48022.48025

Published: 01 October 1988 Publication History

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]

ALLEN, J{ Anatomy o{ LISP. McGraw-Hill, New York, 1978.

[2]

BARTH, J. Shifting garbage collection overhead to compile .time. Commun. ACM 20, 7 (July 1977), 513-518.

[3]

CLARK, D. W., AND GREEN, C.C. An empirical study of list structure in LISP. Commun. ACM 20, 2 (Feb. 1977), 78-87.

[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]

COHEN, J. Garbage collection of linked data structure. ACM Comput. Surv. 13, 3 (Sept. 1981), 341-367.

[6]

DEUTSH, L. P., AND BOBROW, D. G. An efficient incremental automatic garbage collector. Commun. ACM 19, 9 (Sept. 1976), 522-526.

[7]

GABRIEL, R.P. Performance and evaluation of LISP Systems. MIT Press, Cambridge, Mass., 1985.

[8]

HOPCROFT, J., AND ULLMAN, J. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979.

[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]

KATAYAMA, T. Type inference and type checking for functional programming languages--a reduced computation approach. In Con{erence Record of the 1984 ACM Symposium on LISP and Functional Programming (Austin, TX., Aug. 6-8). ACM, New York, 1984, pp. 263-272.

[12]

MCCARTHY, J., ABRAHAMS, P. W., EDWARDS, D. J., HART, T. P., AND LEVIN, M.I. LISP 1.5 Programmer's Manual. MIT Press, Cambridge, Mass., 1965.

[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.

Cited By

Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397208
Kumar K. PSanyal AKarkare A(2016)Liveness-based garbage collection for lazy languagesACM SIGPLAN Notices10.1145/3241624.292669851:11(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/3241624.2926698
Kanvar VKhedker U(2016)Heap Abstractions for Static AnalysisACM Computing Surveys10.1145/293109849:2(1-47)Online publication date: 30-Jun-2016
https://dl.acm.org/doi/10.1145/2931098
Show More Cited By

Index Terms

Analysis of functional programs to detect run-time garbage cells
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Linked lists
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies

Recommendations

A fully concurrent garbage collector for functional programs on multicore processors
ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming

This paper presents a concurrent garbage collection method for functional programs running on a multicore processor. It is a concurrent extension of our bitmap-marking non-moving collector with Yuasa's snapshot-at-the-beginning strategy. Our collector ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Garbage collection for strongly-typed languages using run-time type reconstruction

Garbage collectors perform two functions: live-object detection and dead-object reclamation. In this paper, we present a new technique for live-object detection based on run-time type reconstruction for a strongly typed, polymorphic language. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 10, Issue 4

Oct. 1988

128 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/48022

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1988 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1988

Published in TOPLAS Volume 10, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
578
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)14

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
Kumar K. PSanyal AKarkare A(2016)Liveness-based garbage collection for lazy languagesACM SIGPLAN Notices10.1145/3241624.292669851:11(122-133)Online publication date: 14-Jun-2016
Kanvar VKhedker U(2016)Heap Abstractions for Static AnalysisACM Computing Surveys10.1145/293109849:2(1-47)Online publication date: 30-Jun-2016
Kumar K. PSanyal AKarkare AFlood CZhang Z(2016)Liveness-based garbage collection for lazy languagesProceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management10.1145/2926697.2926698(122-133)Online publication date: 14-Jun-2016
Flood CZhang Z(2016)Proceedings of the 2016 ACM SIGPLAN International Symposium on Memory ManagementundefinedOnline publication date: 14-Jun-2016
Asati RSanyal AKarkare AMycroft A(2014)Liveness-Based Garbage CollectionCompiler Construction10.1007/978-3-642-54807-9_5(85-106)Online publication date: 2014
Montenegro MPeña RSegura C(2009)An Inference Algorithm for Guaranteeing Safe DestructionLogic-Based Program Synthesis and Transformation10.1007/978-3-642-00515-2_10(135-151)Online publication date: 4-Mar-2009
Hosoya HYonezawa A(2006)Garbage collection via dynamic type inference - A formal treatment -Types in Compilation10.1007/BFb0055520(215-239)Online publication date: 28-May-2006
Shaham RYahav EKolodner ESagiv M(2005)Establishing local temporal heap safety properties with applications to compile-time memory managementScience of Computer Programming10.1016/j.scico.2005.02.01058:1-2(264-289)Online publication date: 1-Oct-2005
Mohneu M(2005)Efficient compile-time garbage collection for arbitrary data structuresProgramming Languages: Implementations, Logics and Programs10.1007/BFb0026824(241-258)Online publication date: 16-Jun-2005
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents