A Rewrite Rule Machine. Simulation of Concurrent Tree Rewriting.
Abstract
This report presents results of simulated concurrent tree rewriting of programs in the OBJ2 language, as well as descriptive statistics for the rule sets of typical OBJ2 examples. This work explores the use of OBJ2 as a concurrent programming language, explores in detail the implications of the concurrent tree rewriting model for realistic problems, and provides information for design decisions about the Rewrite Rule Machine. We found that it was easy to write good concurrent programs in OBJ2; most rewrite rules from the OBJ2 examples are simple and fall into easy-to-handle categories. The simulations indicate that concurrently executed interpreted programs will often be faster than sequentially executed compiled programs. This report also presents some techniques for controlling tree size in concurrent rewriting. Finally, we present some high-level simulation results for a VLSI rewrite rule engine that we are considering implementing. The results are highly favorable.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 10, 1986
- Accession Number
- ADA171039
Entities
People
- Joseph Goguen
- Sany Leinwand
- Timothy Winkler
Organizations
- SRI International