Compiling concurrent rewriting onto the Rewrite Rule Machine | SpringerLink
Skip to main content
Springer Nature Link
Log in

Compiling concurrent rewriting onto the Rewrite Rule Machine

  • Chapter 5 Architecture, Compilers And Parallel Computation
  • Conference paper
  • First Online:
Conditional and Typed Rewriting Systems (CTRS 1990)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 516))

Included in the following conference series:

  • 160 Accesses

Abstract

Following a brief review of the of the Rewrite Rule Machine's concurrent rewriting model of computation, this paper describes a technique for transforming rule sets which eliminates non-left linear and conditional rules. By Theorem 1, this transformation preserves termination and result; it is used as a first phase of compilation. After a brief review of RRM architecture, the second phase of compilation is described, which transforms unconditional left linear rule sets into ensemble micro code. By Theorem 2, this transformation preserves the time complexity of a set of rewrite rules executed in parallel. The paper concludes with a discussion of the ensemble controller's role.

Supported by Office of Naval Research Contracts N00014-86-C-0450 and N00014-90-C-0210, and NSF Grants CCR-8707155 and CCR-9007010.

work done at SRI International.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Hitoshi Aida, Sany Leinwand, and José Meseguer. Architectural design of the rewrite rule machine ensemble. To appear in Proc. Workshop on VLSI for Artificial Intelligence and Neural Networks, Oxford, September 1990.

    Google Scholar 

  2. Hitoshi Aida and José Meseguer. Transforming conditional rewrite rules into unconditional ones. In preparation.

    Google Scholar 

  3. Arvind and D.E. Culler. Dataflow architectures, 1986. Annual Reviews in Computer Science.

    Google Scholar 

  4. Arvind, Rishiyur Nikhil, and Keshav Pingali. I-structures: Data structures for parallel computing. In Joseph Fasel and Robert Keller, editors, Graph Reduction, pages 337–369. Springer-Verlag, 1987. Lecture Notes in Computer Science, Volume 279.

    Google Scholar 

  5. H.P. Barendregt, M.C.J.D. van Eekelen, J.R.W. Glauert, J.R. Kennaway, M.J. Plasmeijer, and M.R. Sleep. Towards an intermediate language based on graph rewriting. In Proceedings, PARLE Conference. Springer-Verlag, 1987. Lecture Notes in Computer Science, Volume 259.

    Google Scholar 

  6. J. Darlington and M.J. Reeve. Alice: A multiprocessor reduction machine for the parallel evaluation of applicative languages. In ACM Conference on Functional Programming Languages and Computer Architecture. ACM, 1981.

    Google Scholar 

  7. Nachum Dershowitz and David A. Plaisted. Equational programming. In J. Richards, editor, Machine Intelligence 11: The logic and acquisition of knowledge, pages 21–56. Oxford University Press, 1988.

    Google Scholar 

  8. Kokichi Futatsugi, Joseph Goguen, Jean-Pierre Jouannaud, and José Meseguer. Principles of OBJ2. In Brian Reid, editor, Proceedings of 12th ACM Symposium on Principles of Programming Languages, pages 52–66. ACM, 1985.

    Google Scholar 

  9. E. Giovannetti and C. Moiso. Notes on the elimination of conditions. In Jean-Pierre Jouannaud and Stephane Kaplan, editors, Proceedings, Conference on Conditional Term Rewriting, Orsay, France, July 8–10, 1987, pages 91–97. Springer-Verlag, Lecture Notes in Computer Science No. 308, 1988.

    Google Scholar 

  10. J.R.W. Glauert and J.R. Kennaway. A categorical construction for generalised graph rewriting. Submitted to PARLE 89 conference.

    Google Scholar 

  11. J.R.W. Glauert, J.R. Kennaway, and M.R. Sleep. Specification of Dactl. Technical report, School of Information Systems, University of East Anglia, 1987.

    Google Scholar 

  12. J.A. Goguen. Semantic specifications for the rewrite rule machine. In A. Yonezawa, W. McColl, and T. Ito, editors, Concurrency: Theory, Language and Architecture. Springer LNCS, 1990.

    Google Scholar 

  13. Joseph Goguen, Claude Kirchner, Hélène Kirchner, Aristide Mégrelis, José Meseguer, and Timothy Winkler. An introduction to OBJ3. In Jean-Pierre Jouannaud and Stephane Kaplan, editors, Proceedings, Conference on Conditional Term Rewriting, Orsay, France, July 8–10, 1987, pages 258–263. Springer-Verlag, Lecture Notes in Computer Science No. 308, 1988.

    Google Scholar 

  14. Joseph Goguen, Claude Kirchner, and José Meseguer. Concurrent term rewriting as a model of computation. In R. Keller and J. Fasel, editors, Proc. Workshop on Graph Reduction, Santa Fe, New Mexico, pages 53–93. Springer LNCS 279, 1987.

    Google Scholar 

  15. Joseph Goguen and José Meseguer. Eqlog: Equality, types, and generic modules for logic programming. In Douglas DeGroot and Gary Lindstrom, editors, Logic Programming: Functions, Relations and Equations, pages 295–363. Prentice-Hall, 1986. An earlier version appears in Journal of Logic Programming, Volume 1, Number 2, pages 179–210, September 1984.

    Google Scholar 

  16. Joseph Goguen and José Meseguer. Models and equality for logical programming. In Hartmut Ehrig, Giorgio Levi, Robert Kowalski, and Ugo Montanari, editors, Proceedings, 1987 TAPSOFT, pages 1–22. Springer-Verlag, 1987. Lecture Notes in Computer Science, Volume 250; extended version to appear in J. Logic Programming.

    Google Scholar 

  17. Joseph Goguen and José Meseguer. Unifying functional, object-oriented and relational programming with logical semantics. In Bruce Shriver and Peter Wegner, editors, Research Directions in Object-Oriented Programming, pages 417–477. MIT Press, 1987. Preliminary version in SIGPLAN Notices, Volume 21, Number 10, pages 153–162, October 1986; also, Technical Report CSLI-87-93, Center for the Study of Language and Information, Stanford University, March 1987.

    Google Scholar 

  18. Joseph Goguen and José Meseguer. Software for the rewrite rule machine. In Proceedings, International Conference on Fifth Generation Computer Systems 1988, pages 628–637. Institute for New Generation Computer Technology (ICOT), 1988.

    Google Scholar 

  19. Joseph Goguen, José Meseguer, Sany Leinwand, Timothy Winkler, and Hitoshi Aida. The rewrite rule machine. Technical Report SRI-CSL-89-6, SRI International, Computer Science Lab, March 1989.

    Google Scholar 

  20. P.G. Harrison and M.J. Reeve. The parallel graph reduction machine, alice. In R. Keller and J. Fasel, editors, Proc. Workshop on graph reduction, Santa Fe, New Mexico, pages 181–202. Springer LNCS 279, 1987.

    Google Scholar 

  21. Simon L Peyton Jones, Chris Clack, Jon Salkild, and Mark Hardie. GRIP — a high-performance architecture for parallel graph reduction. In Kahn, editor, Proceedings, IFIP Conference on Functional Programming Languages and Computer Architecture, pages 98–112. Springer-Verlag, Portland, September 1987. Lecture Notes in Computer Science, Volume 274.

    Google Scholar 

  22. Simon Peyton Jones. The Implementation of Functional Programming Languages. Prentice-Hall, 1987.

    Google Scholar 

  23. Robert Keller and Joseph Fasel, editors. Proceedings, Graph Reduction Workshop. Springer-Verlag, 1987. Lecture Notes in Computer Science, Volume 279.

    Google Scholar 

  24. R.M. Lea. ASP modules: Cost-effective building blocks for real-time dsp systems. J. of VLSI Signal Processing, 1:69–84, 1989.

    Google Scholar 

  25. S. Leinwand, J.A. Goguen, and T. Winkler. Cell and ensemble architecture for the rewrite rule machine. In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, pages 869–878. ICOT, 1988.

    Google Scholar 

  26. José Meseguer. Conditional rewriting logic: deduction, models and concurrency. This volume.

    Google Scholar 

  27. José Meseguer. A logical theory of concurrent objects. In ECOOP-OOPSLA'90 Conference on Object-Oriented Programming, Ottawa, Canada, October 1990, pages 101–115. ACM, 1990.

    Google Scholar 

  28. José Meseguer. Rewriting as a unified model of concurrency. In Proceedings of the Concur'90 Conference, Amsterdam, August 1990, pages 384–400. Springer LNCS Vol. 458, 1990.

    Google Scholar 

  29. Ugo Montanari and Joseph Goguen. An abstract machine for fast parallel matching of linear patterns. Technical Report SRI-CSL-87-3, Computer Science Lab, SRI International, May 1987.

    Google Scholar 

  30. P.M. Sewell. Cell machine correctness via parallel jungle rewriting. MSc Thesis, Programming Research Group, University of Oxford, 1990.

    Google Scholar 

  31. D.B. Shu, J.G. Nash, and C.C. Weems. A multiple-level heterogeneous architecture for image understanding. In Parallel Architectures and Algorithms for Image Understanding. Academic Press, 1990. To appear.

    Google Scholar 

  32. G. Sivakumar. Proofs and Computations in Conditional Equational Theories. PhD thesis, CS Dept., U. Illinois at Urbana, 1989.

    Google Scholar 

  33. Timothy Winkler. Numerical computation on the RRM. Technical report, SRI International, Computer Science Lab, November 1988. Technical Note SRI-CSL-TN88-3.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. SRI International, 94025, Menlo Park, CA

    Hitoshi Aida, Joseph Goguen & José Meseguer

  2. Department of Electrical Engineering, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, 113, Tokyo, Japan

    Hitoshi Aida

  3. Programming Research Group, Oxford University, OX1 3QD, Oxford, United Kingdom

    Joseph Goguen

Authors
  1. Hitoshi Aida
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joseph Goguen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José Meseguer
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

S. Kaplan M. Okada

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aida, H., Goguen, J., Meseguer, J. (1991). Compiling concurrent rewriting onto the Rewrite Rule Machine. In: Kaplan, S., Okada, M. (eds) Conditional and Typed Rewriting Systems. CTRS 1990. Lecture Notes in Computer Science, vol 516. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54317-1_101

Download citation

  • DOI: https://doi.org/10.1007/3-540-54317-1_101

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-54317-6

  • Online ISBN: 978-3-540-47558-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics