Strategia de reducere - Reduction strategy

În rescriere , o strategie de reducere sau strategie de rescriere este o relație care specifică o rescriere pentru fiecare obiect sau termen, compatibilă cu o relație de reducere dată. Unii autori folosesc termenul pentru a se referi la o strategie de evaluare .

Definiții

Formal, pentru un sistem de rescriere abstract , o strategie de reducere este o relație binară pe cu , în cazul în care este închiderea tranzitivă a (dar nu și închiderea reflexiv). ${\ displaystyle (A, \ to)}$ ${\ displaystyle \ to _ {S}}$ ${\ displaystyle A}$ ${\ displaystyle \ to _ {S} \ subseteq {\ overset {+} {\ to}}}$ ${\ displaystyle {\ overset {+} {\ to}}}$ ${\ displaystyle \ to}$

O strategie de reducere cu un singur pas este cea în care . În caz contrar, este o strategie în mai mulți pași . ${\ displaystyle \ to _ {S} \ subseteq \ to}$

O strategie deterministă este una în care este o funcție parțială , adică pentru fiecare există cel mult una astfel încât . Altfel este o strategie nedeterministă . ${\ displaystyle \ to _ {S}}$ ${\ displaystyle a \ în A}$ ${\ displaystyle b}$ ${\ displaystyle a \ to _ {S} b}$

Termen rescriere

Într-un sistem de rescriere a termenului, o strategie de rescriere specifică, din toate subtermele reductibile ( redexes ), care ar trebui redusă ( contractată ) într-un termen.

Strategiile într-un singur pas pentru rescrierea termenului includ:

cel mai stâng-cel mai interior: în fiecare etapă se contractă cel mai stâng dintre cele mai interioare redex-uri, unde un redex-ul interior este un redex care nu conține nici un redex
stânga-extremă: în fiecare etapă se contractă cea mai stângă a celei mai exterioare redexe, unde un redex exterior este un redex care nu conține nicio redexă
cel mai drept-cel mai interior, cel mai dreapta-exterior: în mod similar

Strategiile în mai mulți pași includ:

paralel-interior: reduce toate redexele cele mai interioare simultan. Acest lucru este bine definit, deoarece redexele sunt disjuncte în perechi.
paralel-exterior: în mod similar
Reducerea Gross-Knuth, numită și substituție completă sau reducere Kleene: toate redexurile din termen sunt simultan reduse

Reducerea paralelă exterioară și Gross-Knuth sunt hipernormalizante pentru toate sistemele de rescriere a termenului aproape ortogonale, ceea ce înseamnă că aceste strategii vor ajunge în cele din urmă la o formă normală dacă există, chiar și atunci când se efectuează (finit multe) reduceri arbitrare între aplicațiile succesive ale strategiei.

Stratego este un limbaj specific domeniului, conceput special pentru programarea strategiilor de rescriere a termenilor.

Calcul Lambda

În contextul calculului lambda , reducerea ordinii normale se referă la reducerea cea mai stângă-exterioară în sensul dat mai sus . Reducerea cea mai la stânga este uneori folosită pentru a se referi la reducerea normală a ordinii, întrucât cu o traversare în arbore de precomandă noțiunile coincid, dar cu traversarea în ordine mai tipică noțiunile sunt distincte. De exemplu, pe termen cu definit aici , Redex este textual din stânga , în timp ce Redex-exterior este cel mai din stânga întreaga expresie. Reducerea de ordin normal se normalizează, în sensul că dacă un termen are o formă normală, atunci reducerea de ordin normal va ajunge în cele din urmă, de unde și denumirea de normal. Aceasta este cunoscută sub numele de teorema standardizării. ${\ displaystyle (\ lambda xx \ Omega) (\ lambda yI)}$ ${\ displaystyle \ Omega, I}$ ${\ displaystyle \ Omega}$

Reducerea ordinii aplicative se referă la reducerea cea mai interioară la stânga. Spre deosebire de ordinea normală, reducerea aplicativă a ordinii nu se poate termina, chiar și atunci când termenul are o formă normală. De exemplu, folosind reducerea aplicativă a ordinii, este posibilă următoarea secvență de reduceri:

{\ displaystyle {\ begin {align} & (\ mathbf {\ lambda} xz) ((\ lambda w.www) (\ lambda w.www)) \\\ rightarrow & (\ lambda xz) ((\ lambda w .www) (\ lambda w.www) (\ lambda w.www)) \\\ rightarrow & (\ lambda xz) ((\ lambda w.www) (\ lambda w.www) (\ lambda w.www) (\ lambda w.www)) \\\ rightarrow & (\ lambda xz) ((\ lambda w.www) (\ lambda w.www) (\ lambda w.www) (\ lambda w.www) (\ lambda w.www)) \\ & \ ldots \ end {align}}}

Dar folosind reducerea ordinii normale, același punct de plecare se reduce rapid la forma normală:

{\ displaystyle (\ mathbf {\ lambda} xz) ((\ lambda w.www) (\ lambda w.www))}

{\ displaystyle \ rightarrow z}

Reducerea β completă se referă la strategia nedeterministă cu un singur pas care permite reducerea oricărui redex la fiecare pas. Β-reducerea paralelă a lui Takahashi este strategia care reduce simultan toate redexurile din termen.

Reducere slabă

Reducerea ordinii normale și aplicative sunt puternice prin faptul că permit reducerea în cazul abstractizărilor lambda. În schimb, reducerea slabă nu se reduce în cazul unei abstractizări lambda. Reducerea apel-după-nume este strategia de reducere slabă care reduce cel mai stâng redex exterior în interiorul unei extracții lambda, în timp ce reducerea apel-după-valoare este strategia de reducere slabă care reduce cel mai stâng interior redex nu în interiorul unei extracții lambda. Aceste strategii au fost concepute pentru a reflecta strategiile de evaluare apel-după-nume și apel-după-valoare . De fapt, reducerea aplicativă a comenzii a fost introdusă inițial pentru a modela tehnica de trecere a parametrilor apel-după-valoare găsită în Algol 60 și în limbajele de programare moderne. Atunci când este combinată cu ideea reducerii slabe, reducerea rezultată apel-după-valoare este într-adevăr o aproximare fidelă.

Din păcate, reducerea slabă nu este confluentă, iar ecuațiile tradiționale de reducere ale calculului lambda sunt inutile, deoarece sugerează relații care încalcă regimul de evaluare slab. Cu toate acestea, este posibil să se extindă confluența sistemului, permițând o formă restrânsă de reducere sub o abstractizare, în special atunci când redexul nu implică variabila legată de abstractizare. De exemplu, λ x . (Λ y . X ) z este în formă normală pentru o strategie de reducere slabă, deoarece redex (λ y . X ) z este conținut într-o abstractizare lambda. Dar termenul λ x . (Λ y . Y ) z poate fi totuși redus în cadrul strategiei extinse de reducere slabă, deoarece redex (λ y . Y ) z nu se referă la x .

Reducere optimă

Reducerea optimă este motivată de existența termenilor lambda în care nu există o secvență de reduceri care să le reducă fără a dubla munca. De exemplu, ia în considerare

((λg. (g (g (λx.x)))) (λh. ((λf. (f (f (λz.z)))) (λw. (h (w (λy.y))))) )))

Este compus din trei termeni similari, x = ((λg. ...) (λh.y)) și y = ((λf. ...) (λw.z)) , și în final z = λw. (H (w (λy.y))) . Există doar două posibile β-reduceri de făcut aici, pe x și pe y. Reducerea termenului x exterior are ca rezultat mai întâi duplicarea termenului y interior și fiecare copie va trebui redusă, dar reducerea termenului y interior va dubla mai întâi argumentul său z, ceea ce va duce la duplicarea lucrului atunci când valorile lui h și w sunt făcute cunoscute.

Reducerea optimă nu este o strategie de reducere pentru calculul lambda într-un sens strict, deoarece efectuarea β-reducerii pierde informațiile despre redexele substituite care sunt partajate. În schimb, este definit pentru calculul lambda etichetat , un calcul lambda adnotat care surprinde o noțiune precisă a lucrării care ar trebui partajată.

Etichetele constau dintr-un set infinit de etichete atomice și concatenări , linii și sublinieri ale etichetelor. Un termen etichetat este un termen lambda de calcul în care fiecare subterm are o etichetă. Etichetarea inițială standard a unui termen lambda oferă fiecărui subterm o etichetă atomică unică. Reducerea β etichetată este dată de: ${\ displaystyle ab}$ ${\ displaystyle {\ overline {a}}}$ ${\ displaystyle {\ underline {a}}}$

{\ displaystyle ((\ lambda .xM) ^ {\ alpha} N) ^ {\ beta} \ to \ beta {\ overline {\ alpha}} \ cdot M [x \ mapsto {\ underline {\ alpha}} \ cdot N]}

unde concatenează etichete, și substituția este definită după cum urmează (folosind convenția Barendregt ): ${\ displaystyle \ cdot}$ ${\ displaystyle \ beta \ cdot T ^ {\ alpha} = T ^ {\ beta \ alpha}}$ ${\ displaystyle M [x \ mapsto N]}$

{\ displaystyle {\ begin {align} x ^ {\ alpha} [x \ mapsto N] & = \ alpha \ cdot N & \ quad (\ lambda yM) ^ {\ alpha} [x \ mapsto N] & = (\ lambda yM [x \ mapsto N]) ^ {\ alpha} \\ y ^ {\ alpha} [x \ mapsto N] & = y ^ {\ alpha} & \ quad (MN) ^ {\ alpha} [x \ mapsto P] & = (M [x \ mapsto P] N [x \ mapsto P]) ^ {\ alpha} \ end {align}}}

Se poate dovedi că sistemul este confluent. Reducerea optimă este apoi definită a fi o ordine normală sau o reducere extremă la stânga utilizând reducerea de către familii, adică reducerea paralelă a tuturor redexelor cu aceeași etichetă a piesei funcționale.

Un algoritm practic pentru reducerea optimă a fost descris pentru prima dată în 1989, la mai mult de un deceniu după ce reducerea optimă a fost definită pentru prima dată în 1974. Mașina Bologna de ordin superior superior (BOHM) este o implementare prototip a unei extensii a tehnicii la rețelele de interacțiune . Lambdascope este o implementare mai recentă a reducerii optime, folosind și rețele de interacțiune.

Apelați prin reducerea nevoii

Reducerea apelului prin necesitate poate fi definită în mod similar cu reducerea optimă ca reducere slabă extremă la stânga-extremă utilizând reducerea paralelă a redexelor cu aceeași etichetă, pentru un calcul lambda ușor diferit. O definiție alternativă modifică regula beta pentru a găsi calculul „cerut”. Acest lucru necesită extinderea regulii beta pentru a permite reducerea termenilor care nu sunt sintactic adiacenți, astfel încât această definiție este similară definiției etichetate prin faptul că ambele sunt strategii de reducere pentru variațiile calculului lambda. La fel ca în cazul apelului după nume și apelului după valoare, reducerea apelului după nevoie a fost concepută pentru a imita comportamentul strategiei de evaluare cunoscută sub numele de „apel la nevoie” sau evaluare leneșă .

Languages

In other projects

Strategia de reducere - Reduction strategy

Cuprins

Definiții

Termen rescriere

Calcul Lambda

Reducere slabă

Reducere optimă

Apelați prin reducerea nevoii

Vezi si

Note

Referințe

linkuri externe