Information about Abstract Rewriting Machine
The Abstract Rewriting Machine (ARM) is a virtual machine
which implements term rewriting for minimal term rewriting systems.
Minimal term rewriting systems are left-linear term rewriting systems in which each rule takes on one of six forms:
Each of these six forms is mapped (in ARM) to one or a few processor instructions on most contemporary micro processors. Accordingly, minimal term rewriting is achieved at tens to hundreds of clock cycles per reduction step -- milions of reduction steps per second.
ARM implements general term rewriting, in that every single-sorted unconditional left-linear term rewriting system can be transformed (compiled) into a minimal term rewriting system that gives rise to the same normal form relation.
An overview with references to this compilation process for innermost rewriting, as well as a detailed overview of ARM, can be found in "Within ARM's reach: compilation of left-linear rewrite systems via minimal rewrite systems". A description for lazy (non-innermost) rewriting can be found in "Lazy rewriting on eager machinery".
A documented implementation of ARM (with the term rewriting language Epic) is available here. Note that site and software are no longer being actively maintained.
..... Click the link for more information.
..... Click the link for more information.
Minimal term rewriting systems are left-linear term rewriting systems in which each rule takes on one of six forms:
- Continuation:
- Return:
- Match:
- Add:
- Delete:
- Ident:
Each of these six forms is mapped (in ARM) to one or a few processor instructions on most contemporary micro processors. Accordingly, minimal term rewriting is achieved at tens to hundreds of clock cycles per reduction step -- milions of reduction steps per second.
ARM implements general term rewriting, in that every single-sorted unconditional left-linear term rewriting system can be transformed (compiled) into a minimal term rewriting system that gives rise to the same normal form relation.
An overview with references to this compilation process for innermost rewriting, as well as a detailed overview of ARM, can be found in "Within ARM's reach: compilation of left-linear rewrite systems via minimal rewrite systems". A description for lazy (non-innermost) rewriting can be found in "Lazy rewriting on eager machinery".
A documented implementation of ARM (with the term rewriting language Epic) is available here. Note that site and software are no longer being actively maintained.
- ''Virtual Machine Manager redirects here. For the virtual machine monitoring application from Microsoft, see System Center Virtual Machine Manager
..... Click the link for more information.
In mathematics, computer science and logic, rewriting covers a wide range of potentially non-deterministic methods of replacing subterms of a formula with other terms. What is considered are rewrite systems (also rewriting systems, or term rewriting systems
..... Click the link for more information.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
