Normalizace hodnocením - Normalisation by evaluation - Wikipedia

v programovací jazyk sémantika, normalizace hodnocením (NBE) je styl získávání normální forma podmínek v λ počet odvoláním na jejich denotační sémantika. Termín je první interpretován do denotačního modelu λ-termínové struktury a poté je kanonický (β-normální a η-dlouhý) zástupce extrahován reiting označení. Takový v zásadě sémantický přístup se liší od tradičnějšího syntaktického popisu normalizace jako redukce v a systém přepisování termínů kde β-redukce jsou povoleny hluboko uvnitř λ-podmínek.

NBE byl poprvé popsán pro jednoduše zadaný lambda kalkul.^[1] Od té doby byla rozšířena jak na slabší systémy typu tak jako netypový lambda kalkul^[2] používat teoretická doména a systémy bohatšího typu, jako je několik variant systému Teorie typu Martin-Löf.^[3]^[4]

Obrys

Zvažte jednoduše zadaný lambda kalkul, kde typy τ mohou být základní typy (α), typy funkcí (→) nebo produkty (×), dané následujícími Backus – Naurova forma gramatika (→ přidružení vpravo, jako obvykle):

(Typy) τ :: = α | τ₁ → τ₂ | τ₁ × τ₂

Mohou být implementovány jako datový typ v metajazyku; například pro Standardní ML, můžeme použít:

 datový typ ty = Základní z tětiva             | Šíp z ty * ty             | Prod z ty * ty

Pojmy jsou definovány na dvou úrovních.^[5] Nižší syntaktický úroveň (někdy nazývaná dynamický úroveň) je reprezentace, kterou má člověk v úmyslu normalizovat.

Tady lam/aplikace (resp. pár/první,snd) jsou intro /elimin formuláře pro → (resp. ×) a X jsou proměnné. Tyto podmínky mají být implementovány jako první objednávka v metajazyku:

 datový typ tm = var z tětiva             | lam z tětiva * tm | aplikace z tm * tm             | pár z tm * tm | první z tm | snd z tm

The denotační sémantika of (closed) terms in the meta-language interpretuje konstrukty syntaxe, pokud jde o vlastnosti metajazyka; tím pádem, lam je interpretován jako abstrakce, aplikace jako aplikace atd. Konstruované sémantické objekty jsou následující:

(Sémantické podmínky) S,T,… ::= LAM (λX. S X) | PÁR (S, T) | SYN t

Všimněte si, že v sémantice nejsou žádné proměnné ani formy eliminace; jsou reprezentovány jednoduše jako syntaxe. Tyto sémantické objekty jsou reprezentovány následujícím datovým typem:

 datový typ sem = LAM z (sem -> sem)              | PÁR z sem * sem              | SYN z tm

Existuje dvojice funkcí indexovaných podle typu, které se pohybují tam a zpět mezi syntaktickou a sémantickou vrstvou. První funkce, obvykle psaná ↑_τ, odráží termín syntax do sémantiky, zatímco druhý reifikuje sémantika jako syntaktický termín (psaný jako ↓^τ). Jejich definice jsou vzájemně rekurzivní následovně:

${ displaystyle { begin {aligned} uparrow _ { alpha} t & = mathbf {SYN} t uparrow _ { tau _ {1} to tau _ {2}} v & = mathbf {LAM} ( lambda S. uparrow _ { tau _ {2}} ( mathbf {app} (v, downarrow ^ { tau _ {1}} S))) uparrow _ { tau _ {1} times tau _ {2}} v & = mathbf {PAIR} ( uparrow _ { tau _ {1}} ( mathbf {fst} v), uparrow _ { tau _ {2}} ( mathbf {snd} v)) [1ex] downarrow ^ { alpha} ( mathbf {SYN} t) & = t downarrow ^ { tau _ { 1} to tau _ {2}} ( mathbf {LAM} S) & = mathbf {lam} (x, downarrow ^ { tau _ {2}} (S ( uparrow _ { tau _ {1}} ( mathbf {var} x)))) { text {kde}} x { text {je čerstvý}} downarrow ^ { tau _ {1} times tau _ {2}} ( mathbf {PAIR} (S, T)) & = mathbf {pair} ( downarrow ^ { tau _ {1}} S, downarrow ^ { tau _ {2 }} T) end {zarovnáno}}}$

Tyto definice lze snadno implementovat v metajazyku:

 (* reflect: ty -> tm -> sem *) zábava odrážet (Šíp (A, b)) t =       LAM (fn S => odrážet b (aplikace t (reify A S)))   | odrážet (Prod (A, b)) t =       PÁR (odrážet A (první t)) (odrážet b (snd t))   | odrážet (Základní _) t =       SYN t (* reify: ty -> sem -> tm *) a reify (Šíp (A, b)) (LAM S) =       nechat X = fresh_var () v         Lam (X, reify b (S (odrážet A (var X))))       konec   | reify (Prod (A, b)) (PÁR S T) =       Pár (reify A S, reify b T)   | reify (Základní _) (SYN t) = t

Podle indukce na struktuře typů vyplývá, že pokud je sémantický objekt S označuje dobře napsaný výraz s typu τ, pak reifikování objektu (tj. ↓^τ S) produkuje β-normální η-dlouhou formu s. Zbývá tedy pouze zkonstruovat počáteční sémantickou interpretaci S ze syntaktického výrazu s. Tato operace, napsáno ∥s∥_Γ, kde Γ je kontext vazeb, probíhá indukcí pouze na pojmu struktura:

${ displaystyle { begin {zarovnáno} | mathbf {var} x | _ { Gamma} & = Gamma (x) | mathbf {lam} (x, s) | _ { Gamma} & = mathbf {LAM} ( lambda S. | s | _ { Gamma, x mapsto S}) | mathbf {aplikace} (s, t) | _ { Gamma} & = S ( | t | _ { Gamma}) { text {where}} | s | _ { Gamma} = mathbf {LAM} S | mathbf {pair} (s, t) | _ { Gamma} & = mathbf {PAIR} ( | s | _ { Gamma}, | t | _ { Gamma}) | mathbf {fst} s | _ { Gamma} & = S { text {where}} | s | _ { Gamma} = mathbf {PAIR} (S, T) | mathbf {snd} t | _ { Gamma} & = T { text {kde}} | t | _ { Gamma} = mathbf {PAIR} (S, T) end {zarovnáno}}}$

Při implementaci:

 (* význam: ctx -> tm -> sem *) zábava význam G t =       případ t z         var X => vzhlédnout G X       | lam (X, s) => LAM (fn S => význam (přidat G (X, S)) s)       | aplikace (s, t) => (případ význam G s z                          LAM S => S (význam G t))       | pár (s, t) => PÁR (význam G s, význam G t)       | první s => (případ význam G s z                     PÁR (S, T) => S)       | snd t => (případ význam G t z                     PÁR (S, T) => T)

Všimněte si, že existuje mnoho neúplných případů; pokud se však použije na a Zavřeno dobře napsaný termín, žádný z těchto chybějících případů se nikdy nestretne. Operace NBE za uzavřených podmínek je pak:

 (* nbe: ty -> tm -> tm *) zábava nbe A t = reify A (význam prázdný t)

Jako příklad jeho použití zvažte syntaktický výraz Sk definováno níže:

 val K. = lam ("X", lam ("y", var "X")) val S = lam ("X", lam ("y", lam („z“, aplikace (aplikace (var "X", var „z“), aplikace (var "y", var „z“))))) val Sk = aplikace (aplikace (S, K.), K.)

Toto je dobře známé kódování funkce identity v kombinační logika. Normalizace na typ identity vytvoří:

 - nbe (Šíp (Základní "A", Základní "A")) Sk; val to = lam („v0“,var „v0“) : tm

Výsledek je ve skutečnosti ve formě η-long, což lze snadno zjistit normalizací na jiný typ identity:

 - nbe (Šíp (Šíp (Základní "A", Základní „b“), Šíp (Základní "A", Základní „b“))) Sk; val to = lam („v1“,lam („v2“,aplikace (var „v1“,var „v2“))) : tm

Viz také

MINLOG, a důkaz asistent který používá NBE jako svůj přepisovací modul.

Reference

^ Berger, Ulrich; Schwichtenberg, Helmut (1991). Msgstr "Inverzní funkce vyhodnocení pro typizovaný λ-počet". LICS.
^ Filinski, Andrzej; Rohde, Henning Korsholm (2004). „Denotační popis netypové normalizace hodnocením“. FOSSACS.
^ Abel, Andreas; Aehlig, Klaus; Dybjer, Peter (2007). „Normalizace hodnocením pro Martin-Löfovu teorii typu s jedním vesmírem“ (PDF). MFPS.
^ Abel, Andreas; Coquand, Thierry; Dybjer, Peter (2007). „Normalizace pomocí vyhodnocení pro Martin-Löfovu teorii typu s rozsudky typizované rovnosti“ (PDF). LICS.
^ Danvy, Olivier (1996). „Typově zaměřené dílčí hodnocení“ (gzipovaný PostScript ). POPL: 242–257.

[berger_schwichtenberg_lics-91-1] Berger, Ulrich; Schwichtenberg, Helmut (1991). Msgstr "Inverzní funkce vyhodnocení pro typizovaný λ-počet". LICS.

[filinski_rohde_fossacs-04-2] Filinski, Andrzej; Rohde, Henning Korsholm (2004). „Denotační popis netypové normalizace hodnocením“. FOSSACS.

[abel_aehlig_dybjer_mfps-07-3] Abel, Andreas; Aehlig, Klaus; Dybjer, Peter (2007). „Normalizace hodnocením pro Martin-Löfovu teorii typu s jedním vesmírem“ (PDF). MFPS.

[abel_coquand_dybjer_lics-07-4] Abel, Andreas; Coquand, Thierry; Dybjer, Peter (2007). „Normalizace pomocí vyhodnocení pro Martin-Löfovu teorii typu s rozsudky typizované rovnosti“ (PDF). LICS.

[danvy_popl_96-5] Danvy, Olivier (1996). „Typově zaměřené dílčí hodnocení“ (gzipovaný PostScript ). POPL: 242–257.

[1]

[2]

[3]

[4]

[5]