Abstraktní přepisovací stroj - Abstract rewriting machine

The Abstraktní přepisovací stroj (ARM) je a virtuální stroj který implementuje přepis termínu pro systémy přepisování minimálních termínů.

Systémy přepisování minimálních termínů jsou levý lineární systémy přepisování termínů ve kterém každé pravidlo má jednu ze šesti forem:

Pokračování

${ displaystyle f ({ vec {x}}, { vec {y}}, { vec {z}}) rightarrow g ({ vec {x}}, h ({ vec {y}} ), { vec {z}})}$

Vrátit se

${ displaystyle f (x) rightarrow x}$

Zápas

${ displaystyle f ({ vec {x}}, g ({ vec {y}}), { vec {z}}) rightarrow h ({ vec {x}}, { vec {y} }, { vec {z}})}$

Přidat

${ displaystyle f ({ vec {x}}, { vec {z}}) rightarrow g ({ vec {x}}, y, { vec {z}}) - { rm {for} } ~ y in { vec {x}} cup { vec {z}}}$

Vymazat

${ displaystyle f ({ vec {x}}, { vec {y}}, { vec {z}}) rightarrow g ({ vec {x}}, { vec {z}})}$

Ident

${ displaystyle f ({ vec {x}}) rightarrow g ({ vec {x}})}$

Každá z těchto šesti forem je mapována (v ARM) na jednu nebo několik instrukcí procesoru na většině současných mikro procesorů. Minimálního přepisu termínu je tedy dosaženo při desítkách až stovkách hodinových cyklů na redukční krok - miliony redukčních kroků za sekundu.

ARM implementuje obecné přepisování termínů tak, že každý jednorázový bezpodmínečný levý lineární systém přepisování termínů lze transformovat (zkompilovat) do systému minimálního přepisování termínů, který vede ke stejnému normálnímu formálnímu vztahu.

Přehled s odkazy na tento proces kompilace pro nejniternější přepisování a také podrobný přehled ARM najdete v „V dosahu ARM: kompilace levotočivých přepisovacích systémů prostřednictvím minimálních přepisovacích systémů“. Popis líného (nejvnitřnějšího) přepisování najdete v „Líné přepisování na nedočkavé mašinérii“.

K dispozici je zdokumentovaná implementace ARM (s termínem přepisovací jazyk Epic) tady. Upozorňujeme, že web a software již nejsou aktivně udržovány.

Reference

• Giesl, J. R .; Middeldorp, A. (červenec 2004). „Transformační techniky pro kontextově citlivé přepisovací systémy“ (PDF). Journal of Functional Programming. 14 (4): 379–427. CiteSeerX  10.1.1.127.2817. doi:10.1017 / S0956796803004945.
• Lucas, Salvador (2002). „Lazy Rewriting and Context-Sensitive Rewriting“ (PDF). Elektronické poznámky v teoretické informatice. 64: 234–254. CiteSeerX  10.1.1.14.3470. doi:10.1016 / S1571-0661 (04) 80353-0. Archivovány od originál (PDF) dne 2006-05-16. Citováno 2015-08-29.
• Nguyen, Quang-Huy (2001). „Kompaktní trasování normalizace pomocí líného přepisování“ (PDF). Elektronické poznámky v teoretické informatice. 57: 87–108. CiteSeerX  10.1.1.24.771. doi:10.1016 / S1571-0661 (04) 00269-5.
• Schernhammer, F .; Gramlich, B. (duben 2008). „Ukončení líného přepisování se znovu objevilo“ (PDF). Elektronické poznámky v teoretické informatice. 204: 35–51. CiteSeerX  10.1.1.142.1957. doi:10.1016 / j.entcs.2008.03.052.