Abstract
A new model of computation, concurrent term rewriting, is proposed as a bridge between a class of easily programmed ultra high level languages and advanced massively concurrent architectures. At the highest level of abstraction, this model views computation as replacing selected subterms by others, at multiple sites concurrently. In this view, concurrent term rewriting provides a standard of correctness, and the choice between using trees or graphs to represent terms is a matter of convenience and efficiency. After introducing the basic concepts and properties of concurrent term rewriting, we discuss some basic implementation issues. A second, more concrete model of computation, called partitioned concurrent term rewriting, takes account of the fact that a (possibly very large) term may be partitioned into fragments that reside on different processors, with each processor concurrently rewriting its own fragment. A number of implementation and optimization issues are also discussed, including overlapping rewrites, rule ordering, compilation, and flow analysis. Concurrent E-strategies are introduced as a flexible control mechanism to optimize performance and facilitate systems programming tasks. All mathematical definitions are gathered in one appendix, while another describes the OBJ language used in examples.
Supported by Office of Naval Research Contracts N00014-85-C-0417 and N00014-86-C-0450.
CNRS (Centre de Recherche en Informatique de Nancy) France; research performed while on leave at SRI International.
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
Lennart Augustsson. Compiling Pattern-Matching. Technical Report 25, University of Göteborg, Programming Methodology Group, September 1986.
John Backus. Can programming be liberated from the von neumann style? Communications of the Association for Computing Machinery, 21(8):613–641, 1978.
M. Bauderon and Bruno Courcelle. Graph expressions and graph rewritings. Technical Report, Université de Bordeaux 1, 1985.
Gérard Boudol. Computational semantics of term rewriting systems. In Maurice Nivat and John Reynolds, editors, Algebraic Methods in Semantics, pages 169–236, Cambridge University Press, 1985.
Cynthia Dwork, Paris Kanellakis, and Larry Stockmeyer. Parallel Algorithms for Term Matching. Technical Report, MIT, 1986.
Kokichi Futatsugi, Joseph Goguen, Jean-Pierre Jouannaud, and José Meseguer. Principles of OBJ2. In Brian K. Reid, editor, Proceedings of 12th ACM Symposium on Principles of Programming Languages, pages 52–66, Association for Computing Machinery, 1985.
Joseph Goguen. How to prove algebraic inductive hypotheses without induction: with applications to the correctness of data type representations. In W. Bibel and Robert Kowalski, editors, Proceedings, Fifth Conference on Automated Deduction, pages 356–373, Springer-Verlag, 1980. Lecture Notes in Computer Science, Volume 87.
Joseph Goguen. Parameterized programming. Transactions on Software Engineering, SE-10(5):528–543, September 1984.
Joseph Goguen, Jean-Pierre Jouannaud, and José Meseguer. Operational semantics of ordersorted algebra. In W. Brauer, editor, Proceedings, 1985 International Conference on Automata, Languages and Programming, Springer-Verlag, 1985. Lecture Notes in Computer Science, Volume 194.
Joseph Goguen, Claude Kirchner, Sany Leinwand, José Meseguer, and Timothy Winkler. Progress report on the rewrite rule machine. IEEE Computer Architecture Technical Committee Newsletter, 7–21, March 1986.
Joseph Goguen and José Meseguer. Eqlog: equality, types, and generic modules for logic programming. In Douglas DeGroot and Gary Lindstrom, editors, Functional and Logic Programming, pages 295–363, Prentice-Hall, 1986. An earlier version appears in Journal of Logic Programming, Volume 1, Number 2, pages 179–210, September 1984.
Joseph Goguen and José Meseguer. Extensions and foundations for object-oriented programming. In Bruce Shriver and Peter Wegner, editors, Research Directions in Object-Oriented Programming, MIT Press, to appear 1987. Preliminary version in SIGPLAN Notices, Volume 21, Number 10, pages 153–162, October 1986.
Joseph Goguen and José Meseguer. Order-Sorted Algebra I: Partial and Overloaded Operations, Errors and Inheritance. Technical Report To appear, SRI International, Computer Science Lab, 1987. Given as lecture at Seminar on Types, Carnegie-Mellon University, June 1983.
Christoph M. Hoffman and Michael O'Donnell. Programming with equations. Transactions on Programming Languages and Systems, 1(4):83–112, 1982.
Gérard Huet and Jean-Jacques Levy. Computations in Non-ambiguous Linear Term Rewriting Systems. Technical Report, INRIA Laboria, 1979.
Gérard Huet and Derek Oppen. Equations and rewrite rules: a survey. In Ron Book, editor, Formal Language Theory: Perspectives and Open Problems, Academic Press, 1980.
John Hughes. Lazy Memo-Functions. Technical Report 21, University of Göteborg, Programming Methodology Group, September 1985.
Bharadwaj Jayaraman and Robert Keller. Resource control in a demand-driven data-flow model. IEEE Conference on Parallel Processing, 118–127, August 1980.
Robert Keller, F. C. H. Lin, and J. Tanaka. Rediflow multiprocessing. IEEE Compcon, 410–417, February 1984.
Robert Keller, Gary Lindstrom, and S. Patil. A loosely-coupled applicative multi-processing system. AFIPS Conference Proceedings, 613–622, June 1979.
Sany Leinwand and Joseph Goguen. Architectural options for the rewrite rule machine. In Steven and Svetlana Kartashev, editors, Proceedings, Second International Supercomputing Conference, Van Nostrand, 1987. To appear.
José Meseguer and Joseph Goguen. Deduction with Many-Sorted Rewrite Rules. Technical Report CSLI-85-42, Center for the Study of Language and Information, Stanford University, December 1985. To appear in Theoretical Computer Science.
José Meseguer and Joseph Goguen. Initiality, induction and computability. In Maurice Nivat and John Reynolds, editors, Algebraic Methods in Semantics, pages 459–541, Cambridge University Press, 1985.
Timothy Winkler, Sany Leinwand, and Joseph Goguen. Simulation of concurrent term rewriting. In Steven and Svetlana Kartashev, editors, Proceedings, Second International Supercomputing Conference, Van Nostrand, 1987. To appear.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goguen, J., Kirchner, C., Meseguer, J. (1987). Concurrent term rewriting as a model of computation. In: Fasel, J.H., Keller, R.M. (eds) Graph Reduction. GR 1986. Lecture Notes in Computer Science, vol 279. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18420-1_50
Download citation
DOI: https://doi.org/10.1007/3-540-18420-1_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18420-1
Online ISBN: 978-3-540-47963-5
eBook Packages: Springer Book Archive