Abstract rewriting machine

The Abstract Rewriting Machine (ARM) is a virtual machine which implements term rewriting for minimal term rewriting systems.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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—millions 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376831530 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.