Abstract
Recent developments by Hewitt and others have stimulated interest in message-passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. The present work illuminates the distinction between applicative and message-passing semantics by means of the μ-calculus, a syntactic model of message-passing systems similar in mechanism to the λ-calculus. Algorithms for the translation of expressions from the λ- to the μ-calculus are presented, and differences between the two approaches are discussed.
Message-passing semantics seem particularly applicable to the study of multiprocessing. The μ-calculus, through the mechanism of conduits, provides a simple model for a limited but interesting class of parallel computations. Multiprocessing capabilities of the μ-calculus are illustrated, and multiple-processor implementations are discussed briefly.
- 1 BAKER, H, AND HEWITT, CThe incremental garbage collection of processes Syrup on Artlf. lntell and Programming Languages, Rochester, N Y, Aug 1977, pp 55-59 Google Scholar
- 2 CHURCH, A The calculi of lambda conversion Annals of Mathematics Studies, Princeton Umvers~ty Press, Princeton, N J, 1941 Google Scholar
- 3 CURRY, H B, AND FEYS, R Combmatory Log:c, North Holland, Amsterdam, 1958Google Scholar
- 4 FISCHER, M Lambda calculus schemata ACM Conf on Proving Assertions about Programs, Las Cruces, N M, Jan 1972, pp 104-109 Google Scholar
- 5 GREIF, 1 Semantics of commumcatmg parallel processes MAC TR-154, Project MAC, M.I T, Cambridge, Mass, Sept 1975Google Scholar
- 6 GULA, J Operating system considerations for multiprocessor architectures Proc 7th Texas Conf on Comptg Syst, Oct 1978, pp 7-1-7-6Google Scholar
- 7 HALSTEAD, R Muluple-processor lmplementauons of message-passing systems LCS TR-198, Lab for Comptr Sct, M IT, Cambridge, Mass, April 1978Google Scholar
- 8 H~LSTEAD, R Object management on multiprocessor systems Proc 7th Texas Conf. on Comptg Syst, Oct 1978, pp 7-7-7-14Google Scholar
- 9 HENDERSON, D A The binding model a semantic base for modular programming systems MAC TR-145, Project MAC, M I T, Cambridge, Mass, Nov 1974Google Scholar
- 10 HEWITT, C Protection and synchromzatlon in actor systems A I Working Paper 83, Artif Intell Lab, M I T, ambridge, Mass, Nov 1974Google Scholar
- 11 HEWITT, C Viewing control structures as patterns of passing messages A I Working Paper 92, Artif Intell Lab. M i T, Cambridge, Mass, Apr 1976Google Scholar
- 12 LEARNING RESEARCH GROUP Personal dynamic media Xerox PARC Report SSL76-1, Xerox Palo Alto Research Center, Palo Alto, Cahf, 1976Google Scholar
- 13 REED, D P, AND KANODIA, R K Synchronization with eventcounts and sequencers Comm A CM 22. 2 (Feb 1979), 115-123 Google Scholar
- 14 RITCHIE, D, AND THOMPSON, K The UNIX timesharing system Comm A CM 17, 7 (July 1974), 365-375 Google Scholar
- 15 STEELE, G LAMBDA the ultimate declarative A I Memo 379, Artlf lnteU Lab., M.I.T, Cambridge, Mass, Nov 1976 Google Scholar
- 16 STEELE, G, AND SUSSMAN, G LAMBDA the ultimate imperative A I Memo 353, Araf Intell Lab, M I T, Cambridge, Mass, Mar 1976 Google Scholar
- 17 STEFLE, G, AND SUSSMAN, G The revised report on SCHEME a dialect of LISP A.I Memo 452, Artff Intell Lab, M 1 T, Cambridge, Mass, Jan 1978Google Scholar
- 18 STRACHEY, C, AND WADSWORTH, C P Continuations a mathematical semantics for handhng full jumps Technical Monograph PRG-I 1, Oxford U Comptg Lab, Oxford, England, Jan 1974Google Scholar
- 19 STROVINK, E Compilation strategies for multiprocessor message-passing systems Proc 7th Texas Conf on Comptg Syst, Oct 1978, pp 7-15-7-20Google Scholar
- 20 WARD, S A Functional domains of apphcative languages MAC TR-136, ProJect MAC, M.I T Cambridge, Mass, Sept 1974 Google Scholar
- 21 WARD, S The MuNet a multiprocessor message-passing system architecture Proc 7th Texas Conf on Comptg Syst, Oct 1978, pp 7-21-7-24Google Scholar
Index Terms
- A Syntactic Theory of Message Passing
Recommendations
Performance of hybrid message-passing and shared-memory parallelism for discrete element modeling
SC '00: Proceedings of the 2000 ACM/IEEE conference on SupercomputingThe current trend in HPC hardware is towards clusters of shared-memory (SMP) compute nodes. For applications developers the major question is how best to program these SMP clusters. To address this we study an algorithm from Discrete Element Modeling, ...
Comments