More Web Proxy on the site http://driver.im/

Article

Free access

The incremental garbage collection of processes

Authors:

Henry C. Baker, Jr.,

Carl HewittAuthors Info & Claims

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

Pages 55 - 59

https://doi.org/10.1145/800228.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

Andrieux MHenrio LRadanne G(2024)Active Objects Based on Algebraic EffectsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_1(3-36)Online publication date: 29-Jan-2024
https://doi.org/10.1007/978-3-031-51060-1_1
Gonnord LHenrio LMorel LRadanne G(2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3564529
Rogowski MAseeri SKeyes DDalcin L(2023)mpi4py.futures: MPI-Based Asynchronous Task Execution for PythonIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.322548134:2(611-622)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TPDS.2022.3225481
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 Conferences

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

August 1977

185 pages

ISBN:9781450378741

DOI:10.1145/800228

Chairman:
James Low

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
ACM SIGART Bulletin Just Accepted
Proceedings of the 1977 symposium on Artificial intelligence and programming languages
August 1977
179 pages
ISSN:0163-5719
DOI:10.1145/872736
Issue’s Table of Contents

Copyright © 1977 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1977

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

220
Total Citations
View Citations
1,381
Total Downloads

Downloads (Last 12 months)207
Downloads (Last 6 weeks)21

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Andrieux MHenrio LRadanne G(2024)Active Objects Based on Algebraic EffectsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_1(3-36)Online publication date: 29-Jan-2024
https://doi.org/10.1007/978-3-031-51060-1_1
Gonnord LHenrio LMorel LRadanne G(2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3564529
Rogowski MAseeri SKeyes DDalcin L(2023)mpi4py.futures: MPI-Based Asynchronous Task Execution for PythonIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.322548134:2(611-622)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TPDS.2022.3225481
Spenger JCarbone PHaller PScholliers CSinger J(2022)Portals: An Extension of Dataflow Streaming for Stateful ServerlessProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3563835.3567664(153-171)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563835.3567664
Fatourou PKallimanis NKosmas ELee JAgrawal KSpear M(2022)The performance power of software combining in persistenceProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508426(337-352)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508426
Colonnelli IAldinucci MCantalupo BPadovani LRabellino SSpampinato CMorelli RDi Carlo RMagini NCavazzoni C(2022)Distributed workflows with JupyterFuture Generation Computer Systems10.1016/j.future.2021.10.007128:C(282-298)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.future.2021.10.007
Swalens JKoster JMeuter W(2021)ChocolaACM Transactions on Programming Languages and Systems10.1145/342720142:4(1-56)Online publication date: 27-Jan-2021
https://dl.acm.org/doi/10.1145/3427201
Gomez-Zamalloa MIsabel M(2021)Deadlock-Guided TestingIEEE Access10.1109/ACCESS.2021.30654219(46033-46048)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3065421
Kowalski KBair RBauman NBoschen JBylaska EDaily Jde Jong WDunning TGovind NHarrison RKeçeli MKeipert KKrishnamoorthy SKumar SMutlu EPalmer BPanyala APeng BRichard RStraatsma TSushko PValeev EValiev Mvan Dam HWaldrop JWilliams-Young DYang CZalewski MWindus T(2021)From NWChem to NWChemEx: Evolving with the Computational Chemistry LandscapeChemical Reviews10.1021/acs.chemrev.0c00998121:8(4962-4998)Online publication date: 31-Mar-2021
https://doi.org/10.1021/acs.chemrev.0c00998
Bauwens JGonzalez Boix EMarr S(2020)From causality to stability: understanding and reducing meta-data in CRDTsProceedings of the 17th International Conference on Managed Programming Languages and Runtimes10.1145/3426182.3426183(3-14)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.1145/3426182.3426183
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 Table of Contents