Henry C. Baker
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.
- 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. Google Scholar
Digital Library
- 2 Batcher, K. E. "Sorting Networks and their Applications". 1968 SJCC, April 1968, 307-314.Google Scholar
- 3 Berry, Gerard and Levy, Jean-Jacques. "Minimal and Optimal Computations of Recursive Programs". POPL4, Jan. 1977, 215-226. Google ScholarDigital Library
- 4 Cheney, C. J. "A Nonrecursive List Compacting Algorithm". CACM 13,11 (Nov. 1970), 677-678. Google ScholarDigital 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.Google Scholar
- 6 Dijkstra, E. W. "After Many a Sobering Experience". Dijkstra note EWD500.Google Scholar
- 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.Google Scholar
- 8 Fenichel, R. R., and Yochelson, J. C. "A LISP Garbage-Collector for Virtual-Memory Computer Systems". CACM 12,11 (Nov. 1969), 611-612. Google ScholarDigital 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.Google Scholar
- 10 Friedman, D. P. and Wise, D. S. "The Impact of Applicative Programming on Multiprocessing". 1976 International Conference on Parallel Processing, 263-272.Google Scholar
- 11 Hewitt, C. and Patterson, M. "Comparative Schematology". Record of Project MAC Conference on Concurrent Systems and Parallel Computation, June 1970.Google Scholar
- 12 Hewitt, C. and Atkinson, R. "Parallelism and Synchronization in Actor Systems". POPL4, Jan. 17-19, 1977, L.A., Cal., 267-280. Google ScholarDigital Library
- 13 Hibbard, P. "Parallel Processing Facilities". in New Directions in Algorithmic Languages, (ed.) Stephen A. Schuman, IRIA, 1976, 1-7.Google Scholar
- 14 Lamport, L. "Garbage Collection with Multiple Processes: An Exercise in Parallelism". Mass. Comp. Associates, CA-7602-2511, Feb. 1976.Google Scholar
- 15 Lamport, L. "On-the-fly Garbage Collection: Once More with Rigor". Mass. Comp. Associates, CA-7508-1611, Aug. 1975.Google Scholar
- 16 Moravec, H. P. "The Role of Raw Power in Intelligence". Unpublished ms., Stanford, Cal., May 1976.Google Scholar
- 17 Vuillemin, Jean. "Correct and Optimal Implementations of Recursion in a Simple Programming Language". JCSS 9 (1974), 332-354.Google ScholarDigital Library
- 18 Ward, S. A. "Functional Domains of Applicative Languages". MAC TR-136, Project MAC, MIT, Sept. 1974. Google ScholarDigital Library
- 19 Wulf, W., et al. "HYDRA: The Kernel of a Multiprocessor Operating System". CACM 17,6 (June 1974), 337-345. Google ScholarDigital Library
Index Terms
- The incremental garbage collection of processes
Recommendations
Garbage-first garbage collection
ISMM '04: Proceedings of the 4th international symposium on Memory management<i>Garbage-First</i> is a server-style garbage collector, targeted for multi-processors with large memories, that meets a soft real-time goal with high probability, while achieving high throughput. Whole-heap operations, such as global marking, are ...
The incremental garbage collection of processes
Proceedings of the 1977 symposium on Artificial intelligence and programming languagesThis 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 languagesThis 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 ...
Comments