Abstract
We present a set of primitive program schemes, which together with just two basic combining forms provide a suprisingly expressive parallel programming language. The primitive program schemes (called tropes) take the form of parameterised conditional rewrite rules, and the computational model is a variant of the Gamma style, in which computation proceeds by nondeterministic local rewriting of a global multiset.
We consider a number of examples which illustrate the use of tropes and we study the algebraic properties of the sequential and parallel combining forms. Using the examples we illustrate the application of these properties in the verification of some simple program transformations.
Partially funded by ESPRIT WGs 6345 (SemaGraph) and 6809 (Semantique).
Partially funded by SERC Visiting Fellowship GRH 19330.
Partially funded by ESPRIT WG 6809 (Semantique) and the Danish Natural Sciences Research Council
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Backus. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Communications of the ACM, 21(8):613–641, August 1978.
J.-P. Banâtre and D. Le Métayer. The Gamma model and its discipline of programming. Science of Computer Programming, 15:55–77, 1990.
J.-P. Banâtre and D. Le Métayer, editors. Research Directions in High-level Parallel Programming Languages. Springer-Verlag, LNCS 574, 1992.
J.-P. Banâtre and D. Le Métayer. Programming by multiset transformation. CACM, January 1993.
K. M. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison-Wesley, 1988.
N. Dershowitz and Z. Manna. Proving termination with multiset orderings. Comm. ACM, 22:465–476, 1979.
C. Hankin, D. Le Métayer, and D. Sands. A calculus of Gamma programs. Research Report DOC 92/22, Department of Computing, Imperial College, 1992.
J. Hughes. Why functional programming matters. The Computer Journal, 2(32):98–107, April 1989.
J.W. Klop. Term rewriting systems. Technical Report CS-R9073, CWI, 1990.
A. Maasen. Parallel programming with data structures and higher-order functions. Science of Computer Programming, 18:1–38, 1992.
J. Meseguer and T. Winkler. Parallel programming in Maude. In [BM92], 1991.
P. Roe. Parallel Programming using Functional Languages. PhD thesis, Glasgow University, 1991.
R. Sedgewick. Algorithms. Addison-Wesley, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hankin, C., Le Métayer, D., Sands, D. (1993). A Parallel programming style and its algebra of programs. In: Bode, A., Reeve, M., Wolf, G. (eds) PARLE '93 Parallel Architectures and Languages Europe. PARLE 1993. Lecture Notes in Computer Science, vol 694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56891-3_29
Download citation
DOI: https://doi.org/10.1007/3-540-56891-3_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56891-9
Online ISBN: 978-3-540-47779-2
eBook Packages: Springer Book Archive