Programming Research Group Technical Monograph PRG-76

Joseph Goguen, Sany Leinwand, Jose Meseguer, Timothy Winkler

August 1989, 43 pages

This monograph consists of two papers which jointly summarize research in the Rewrite Rule Machine (RRM) Project as of about the end of 1988. Research in this period focussed on two topics: the design of very high level multi-paradigm programming languages; and an architecture for executing such languages using graph rewriting. The first paper, "Software for the Rewrite Rule Machine," gives an overview of RRM implementation techniques for functional, relational ("logic"), and object oriented languages, as well as for their combinations. This paper is nearly the same as one that appeared on pages 628-637 of the Proceedings of the International Conference on Fifth Generation Computer Systems, held in Toyko in November 1988. The languages are unusual because their designs are based directly on logic, and nothing has been allowed to compromise their basis in logic. The second paper, "Cell, Tile and Ensemble Architecture of the Rewrite Rule Machine," describes the quite unconventional hierarchical architecture of a custom VLSI chip, called a rewrite ensemble, which processes data directly in memory, in SIMD mode. A complete RRM consists of many independent rewrite ensembles connected over a network. This paper is a very substantial modification of one appearing on pages 869-878 of the same Proceedings.