article

Free access

The incremental garbage collection of processes

Authors:

Henry C. Baker, Jr.,

Carl HewittAuthors Info & Claims

ACM SIGPLAN Notices, Volume 12, Issue 8

Pages 55 - 59

https://doi.org/10.1145/872734.806932

Published: 01 August 1977 Publication History

Abstract

This paper investigates some problems associated with an argument evaluation order that we call “future” order, which is different from both call-by-name and call-by-value, In call-by-future, each formal parameter of a function is bound to a separate process (called a “future”) dedicated to the evaluation of the corresponding argument. This mechanism allows the fully parallel evaluation of arguments to a function, and has been shown to augment the expressive power of a language.

We discuss an approach to a problem that arises in this context: futures which were thought to be relevant when they were created become irrelevant through being ignored in the body of the expression where they were bound. The problem of irrelevant processes also appears in multiprocessing problem-solving systems which start several processors working on the same problem but with different methods, and return with the solution which finishes first. This parallel method strategy has the drawback that the processes which are investigating the losing methods must be identified, stopped, and re-assigned to more useful tasks.

References

[1]

Baker, H. G., Jr. "List Processing in Real Time on a Serial Computer". AI Working Paper 139, MIT AI Lab., Feb. 1977, also to appear in CACM.

Digital Library

[2]

Batcher, K. E. "Sorting Networks and their Applications". 1968 SJCC, April 1968, 307-314.

[3]

Berry, Gerard and Levy, Jean-Jacques. "Minimal and Optimal Computations of Recursive Programs". POPL4, Jan. 1977, 215-226.

Digital Library

[4]

Cheney, C. J. "A Nonrecursive List Compacting Algorithm". CACM 13,11 (Nov. 1970), 677-678.

Digital Library

[5]

Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., Steffens, E. F. M. "On-the-fly Garbage Collection: An Exercise in Cooperation". Dijkstra note EWD496, June 1975.

[6]

Dijkstra, E. W. "After Many a Sobering Experience". Dijkstra note EWD500.

[7]

Erman, L. D. and Lesser, V. R. "A Multi-level Organization for Problem Solving using Many, Diverse, Cooperating Sources of Knowledge". IJCAI-75, Sept. 1975, 483-490.

[8]

Fenichel, R. R., and Yochelson, J. C. "A LISP Garbage-Collector for Virtual-Memory Computer Systems". CACM 12,11 (Nov. 1969), 611-612.

Digital Library

[9]

Friedman, D. P. and Wise, D. S. "Why CONS should not evaluate its arguments". In S. Michaelson and R. Milner (eds.), Automata, Languages and Programming, Edinburgh University Press, Edinburgh (1976), 257-284.

[10]

Friedman, D. P. and Wise, D. S. "The Impact of Applicative Programming on Multiprocessing". 1976 International Conference on Parallel Processing, 263-272.

[11]

Hewitt, C. and Patterson, M. "Comparative Schematology". Record of Project MAC Conference on Concurrent Systems and Parallel Computation, June 1970.

[12]

Hewitt, C. and Atkinson, R. "Parallelism and Synchronization in Actor Systems". POPL4, Jan. 17-19, 1977, L.A., Cal., 267-280.

Digital Library

[13]

Hibbard, P. "Parallel Processing Facilities". in New Directions in Algorithmic Languages, (ed.) Stephen A. Schuman, IRIA, 1976, 1-7.

[14]

Lamport, L. "Garbage Collection with Multiple Processes: An Exercise in Parallelism". Mass. Comp. Associates, CA-7602-2511, Feb. 1976.

[15]

Lamport, L. "On-the-fly Garbage Collection: Once More with Rigor". Mass. Comp. Associates, CA-7508-1611, Aug. 1975.

[16]

Moravec, H. P. "The Role of Raw Power in Intelligence". Unpublished ms., Stanford, Cal., May 1976.

[17]

Vuillemin, Jean. "Correct and Optimal Implementations of Recursion in a Simple Programming Language". JCSS 9 (1974), 332-354.

Digital Library

[18]

Ward, S. A. "Functional Domains of Applicative Languages". MAC TR-136, Project MAC, MIT, Sept. 1974.

Digital Library

[19]

Wulf, W., et al. "HYDRA: The Kernel of a Multiprocessor Operating System". CACM 17,6 (June 1974), 337-345.

Digital Library

Cited By

Monte-Alto HMorveli-Espinoza MTacla C(2024)Argumentation-based multi-agent distributed reasoning in dynamic and open environmentsKnowledge and Information Systems10.1007/s10115-024-02101-x66:8(4631-4666)Online publication date: 15-Apr-2024
https://doi.org/10.1007/s10115-024-02101-x
Kamburjan EWasser N(2022)The Right Kind of Non-Determinism: Using Concurrency to Verify C Programs with Underspecified SemanticsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.365.1365(1-16)Online publication date: 9-Aug-2022
https://doi.org/10.4204/EPTCS.365.1
Lopez TYamasaki N(2022)Prioritized Asynchronous Calls for Parallel Processing on Responsive MultiThreaded Processor2022 Tenth International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR57322.2022.00014(46-55)Online publication date: Nov-2022
https://doi.org/10.1109/CANDAR57322.2022.00014
Show More Cited By

Index Terms

The incremental garbage collection of processes
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Procedures, functions and subroutines
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

The incremental garbage collection of processes
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

This paper investigates some problems associated with an argument evaluation order that we call “future” order, which is different from both call-by-name and call-by-value, In call-by-future, each formal parameter of a function is bound to a separate ...
The incremental garbage collection of processes
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

This paper investigates some problems associated with an argument evaluation order that we call “future” order, which is different from both call-by-name and call-by-value, In call-by-future, each formal parameter of a function is bound to a separate ...
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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 12, Issue 8

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

August 1977

179 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/872734

Issue’s Table of Contents

Proceedings of the 1977 symposium on Artificial intelligence and programming languages
August 1977
185 pages
ISBN:9781450378741
DOI:10.1145/800228
Chairman:
James Low

Copyright © 1977 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1977

Published in SIGPLAN Volume 12, Issue 8

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

220
Total Citations
View Citations
1,368
Total Downloads

Downloads (Last 12 months)210
Downloads (Last 6 weeks)26

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Monte-Alto HMorveli-Espinoza MTacla C(2024)Argumentation-based multi-agent distributed reasoning in dynamic and open environmentsKnowledge and Information Systems10.1007/s10115-024-02101-x66:8(4631-4666)Online publication date: 15-Apr-2024
https://doi.org/10.1007/s10115-024-02101-x
Kamburjan EWasser N(2022)The Right Kind of Non-Determinism: Using Concurrency to Verify C Programs with Underspecified SemanticsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.365.1365(1-16)Online publication date: 9-Aug-2022
https://doi.org/10.4204/EPTCS.365.1
Lopez TYamasaki N(2022)Prioritized Asynchronous Calls for Parallel Processing on Responsive MultiThreaded Processor2022 Tenth International Symposium on Computing and Networking (CANDAR)10.1109/CANDAR57322.2022.00014(46-55)Online publication date: Nov-2022
https://doi.org/10.1109/CANDAR57322.2022.00014
Owe OFazeldehkordi E(2022)A lightweight approach to smart contracts supporting safety, security, and privacyJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2022.100772127(100772)Online publication date: Jun-2022
https://doi.org/10.1016/j.jlamp.2022.100772
Lohstroh MMenard CBateni SLee E(2021)Toward a Lingua Franca for Deterministic Concurrent SystemsACM Transactions on Embedded Computing Systems10.1145/344812820:4(1-27)Online publication date: 18-May-2021
https://dl.acm.org/doi/10.1145/3448128
Karami FOwe OSchneider G(2021)Information-Flow Control by Means of Security Wrappers for Active Object Languages with FuturesSecure IT Systems10.1007/978-3-030-70852-8_5(74-91)Online publication date: 3-Mar-2021
https://doi.org/10.1007/978-3-030-70852-8_5
Glück RKöppl D(2020)Computational Aspects of Ordered Integer Partitions with BoundsAlgorithmica10.1007/s00453-020-00713-782:10(2955-2984)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s00453-020-00713-7
Olyanitch AAkhidzhakova MKhachmafova ZGashimov EAkhidzhak B(2020)Artificial Intelligence: Semiolinguistic and Communicative CompetenciesScientific and Technical Revolution: Yesterday, Today and Tomorrow10.1007/978-3-030-47945-9_1(3-11)Online publication date: 6-Jun-2020
https://doi.org/10.1007/978-3-030-47945-9_1
Dauth TSulzmann MHermenegildo MIgarashi A(2019)Futures and promises in Haskell and ScalaProceedings of the 2019 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation10.1145/3294032.3294080(68-74)Online publication date: 14-Jan-2019
https://dl.acm.org/doi/10.1145/3294032.3294080
Singer KXu YLee IHollingsworth JKeidar I(2019)Proactive work stealing for futuresProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295735(257-271)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295735
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents