Abstract rewriting machine

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:

Continuation
f(\vec{x},\vec{y},\vec{z})\rightarrow g(\vec{x},h(\vec{y}),\vec{z})
Return
f(x)\rightarrow x
Match
f(\vec{x},g(\vec{y}),\vec{z})\rightarrow h(\vec{x},\vec{y},\vec{z})
Add
f(\vec{x},\vec{z})\rightarrow g(\vec{x},y,\vec{z}) -
{\rm for }~y\in\vec{x}\cup\vec{z}
Delete
f(\vec{x},\vec{y},\vec{z})\rightarrow g(\vec{x},\vec{z})
Ident
f(\vec{x})\rightarrow g(\vec{x})

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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Abstract Rewriting Machine — The Abstract Rewriting Machine (ARM) is a virtual machinewhich implements term rewriting for minimal term rewriting systems. Minimal term rewriting systems are left linear termrewriting systems in which each rule takes on one of six… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

  • List of functional programming topics — This is a list of functional programming topics. Contents 1 Foundational concepts 2 Lambda calculus 3 Combinatory logic 4 Intuitionistic logic …   Wikipedia

  • ARM — An arm is an upper limb of the body.Arm (or arms) may also refer to:* Armaments, weapons; as in Small arms, Right to arms * Eta Capricorni, a star, traditional name Arm * Arm (geography), a narrow stretch of a larger body of water ** Distributary …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • Algebraic Logic Functional programming language — also known as ALF is a programming language which combines functional and logic programming techniques. Its foundation is Horn clause logic with equality which consists of predicates and Horn clauses for logic programming, and functions and… …   Wikipedia

  • Modernism — For other uses of the word, see Modernism (disambiguation). For the period in sociology beginning with the industrialization, see Modernity. Hans Hofmann, The Gate , 1959–1960, collection: Solomon R. Guggenheim Museum. Hofmann was renowned not… …   Wikipedia

  • Europe, history of — Introduction       history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”