Normalisierung durch Auswertung – Wikipedia

Posted on by
before-content-x4

In der Programmiersprachen-Semantik Normalisierung durch Bewertung (NBE) ist ein Stil, um die normale Form von Begriffen in der λ-Rechnung zu erhalten, indem man sich auf ihre Denotationssemantik beruft. Ein Begriff steht an erster Stelle interpretiert in ein Denotationsmodell der λ-Termstruktur, und dann wird ein kanonischer (β-normaler und η-langer) Vertreter durch extrahiert reifizieren die Bezeichnung. Ein solcher im Wesentlichen semantischer Ansatz unterscheidet sich von der traditionelleren syntaktischen Beschreibung der Normalisierung als Reduktion in einem Term-Rewrite-System, bei dem β-Reduktionen tief in λ-Termen zulässig sind.

NBE wurde zuerst für den einfach typisierten Lambda-Kalkül beschrieben.[1] Es wurde seitdem sowohl auf schwächere Systeme wie den untypisierten Lambda-Kalkül ausgedehnt[2] unter Verwendung eines domänentheoretischen Ansatzes und zu reicheren Typsystemen wie mehreren Varianten der Martin-Löf-Typentheorie.[3][4]

Gliederung[edit]

Betrachten Sie den einfach typisierten Lambda-Kalkül, bei dem die Typen τ Grundtypen (α), Funktionstypen (→) oder Produkte (×) sein können, die durch die folgende Backus-Naur-Formgrammatik gegeben werden (→ wie üblich rechts assoziieren):

(Typen) τ :: = α | τ1 → τ2 | τ1 × τ2

Diese können als Datentyp in der Metasprache implementiert werden. Für Standard ML könnten wir beispielsweise Folgendes verwenden: 

 datatype ty = Basic of string
             | Arrow of ty * ty
             | Prod of ty * ty

Begriffe werden auf zwei Ebenen definiert.[5] Je niedriger syntaktisch Ebene (manchmal die genannt dynamisch level) ist die Darstellung, die man normalisieren will.

(Syntaxbegriffe) s,t,… :: = var x | lam ((x, t) | App ((s, t) | Paar ((s, t) | fst t | snd t

Hier lam/.App (bzw. Paar/.fst,snd) sind die Intro / Elim-Formen für → (bzw. ×) und x sind Variablen. Diese Begriffe sollen als erste Ordnung in der Metasprache implementiert werden: 

 datatype tm = var of string
             | lam of string * tm | app of tm * tm
             | pair of tm * tm | fst of tm | snd of tm

Die Denotationssemantik von (geschlossenen) Begriffen in der Metasprache interpretiert die Konstrukte der Syntax in Bezug auf Merkmale der Metasprache; so, lam wird als Abstraktion interpretiert, App als Anwendung usw. Die konstruierten semantischen Objekte sind wie folgt:

(Semantische Begriffe) S.,T.,… :: = LAM (λx. S. x) | PAAR ((S., T.) | SYN t

Beachten Sie, dass die Semantik keine Variablen oder Eliminierungsformen enthält. Sie werden einfach als Syntax dargestellt. Diese semantischen Objekte werden durch den folgenden Datentyp dargestellt: 

 datatype sem = LAM of (sem -> sem)
              | PAIR of sem * sem
              | SYN of tm

Es gibt zwei typindizierte Funktionen, die sich zwischen der syntaktischen und der semantischen Ebene hin und her bewegen. Die erste Funktion, normalerweise geschrieben ↑τ, spiegelt der Begriff Syntax in die Semantik, während der zweite reifiziert die Semantik als syntaktischer Begriff (geschrieben als ↓τ). Ihre Definitionen rekursiv wie folgt:

↑αt=S.Y.N. t↑τ1→τ2v=L.EINM.((λS.. ↑τ2((einpp ((v,↓τ1S.)))↑τ1×τ2v=P.EINichR.((↑τ1((fst v),↑τ2((snd v))↓α((S.Y.N. t)=t↓τ1→τ2((L.EINM. S.)=leinm ((x,↓τ2((S. ((↑τ1((veinr x)))) wo x ist frisch↓τ1×τ2((P.EINichR. ((S.,T.))=peinichr ((↓τ1S.,↓τ2T.){ displaystyle { begin {align} 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 {where}} x { text {is fresh}} \ downarrow ^ { tau _ {1} times tau _ {2}} ( mathbf {PAIR} (S, T)) & = mathbf {pair} ( downarrow ^ { tau _ {1}} S, downarrow ^ { tau _ {2}} T) end {align}}}

Diese Definitionen lassen sich leicht in der Metasprache implementieren: 

 (* reflect : ty -> tm -> sem *)
 fun reflect (Arrow (a, b)) t =
       LAM (fn S => reflect b (app t (reify a S)))
   | reflect (Prod (a, b)) t =
       PAIR (reflect a (fst t)) (reflect b (snd t))
   | reflect (Basic _) t =
       SYN t

 (* reify   : ty -> sem -> tm *)
 and reify (Arrow (a, b)) (LAM S) =
       let x = fresh_var () in
         Lam (x, reify b (S (reflect a (var x))))
       end
   | reify (Prod (a, b)) (PAIR S T) =
       Pair (reify a S, reify b T)
   | reify (Basic _) (SYN t) = t

Durch Induktion auf die Struktur von Typen folgt, dass wenn das semantische Objekt S. bezeichnet einen gut typisierten Begriff s vom Typ τ, dann das Objekt erneut bestätigen (dh ↓τ S) erzeugt die β-normale η-lange Form von s. Alles, was bleibt, ist daher, die anfängliche semantische Interpretation zu konstruieren S. von einem syntaktischen Begriff s. Diese Operation, geschrieben ∥s∥Γ, wobei Γ ein Kontext von Bindungen ist, erfolgt die Induktion ausschließlich über den Begriff Struktur:

‖veinr x‖Γ=Γ((x)‖leinm ((x,s)‖Γ=L.EINM. ((λS.. ‖s‖Γ,x↦S.)‖einpp ((s,t)‖Γ=S. ((‖t‖Γ) wo ‖s‖Γ=L.EINM. S.‖peinichr ((s,t)‖Γ=P.EINichR. ((‖s‖Γ,‖t‖Γ)‖fst s‖Γ=S. wo ‖s‖Γ=P.EINichR. ((S.,T.)‖snd t‖Γ=T. wo ‖t‖Γ=P.EINichR. ((S.,T.){ displaystyle { begin {align} | mathbf {var} x | _ { Gamma} & = Gamma (x) \ | mathbf {lam} (x, s) | _ { Gamma} & = mathbf {LAM} ( lambda S. | s | _ { Gamma, x mapsto S}) \ | mathbf {app} (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 {where}} | t | _ { Gamma} = mathbf {PAIR} (S, T) end {align}}}

In der Implementierung: 

 (* meaning : ctx -> tm -> sem *)
 fun meaning G t =
       case t of
         var x => lookup G x
       | lam (x, s) => LAM (fn S => meaning (add G (x, S)) s)
       | app (s, t) => (case meaning G s of
                          LAM S => S (meaning G t))
       | pair (s, t) => PAIR (meaning G s, meaning G t)
       | fst s => (case meaning G s of
                     PAIR (S, T) => S)
       | snd t => (case meaning G t of
                     PAIR (S, T) => T)

Beachten Sie, dass es viele nicht erschöpfende Fälle gibt. wenn jedoch auf a angewendet geschlossen Keiner dieser fehlenden Fälle ist jemals aufgetreten. Die NBE-Operation zu geschlossenen Bedingungen lautet dann: 

 (* nbe : ty -> tm -> tm *)
 fun nbe a t = reify a (meaning empty t)

Betrachten Sie als Beispiel für seine Verwendung den syntaktischen Begriff SKK unten definiert: 

 val K = lam ("x", lam ("y", var "x"))
 val S = lam ("x", lam ("y", lam ("z", app (app (var "x", var "z"), app (var "y", var "z")))))
 val SKK = app (app (S, K), K)

Dies ist die bekannte Codierung der Identitätsfunktion in der kombinatorischen Logik. Das Normalisieren auf einen Identitätstyp erzeugt: 

 - nbe (Arrow (Basic "a", Basic "a")) SKK;
 val it = lam ("v0",var "v0") : tm

Das Ergebnis ist tatsächlich in η-langer Form, wie leicht durch Normalisieren auf einen anderen Identitätstyp zu sehen ist: 

 - nbe (Arrow (Arrow (Basic "a", Basic "b"), Arrow (Basic "a", Basic "b"))) SKK;
 val it = lam ("v1",lam ("v2",app (var "v1",var "v2"))) : tm

Siehe auch[edit]

Verweise[edit]

  1. ^ Berger, Ulrich; Schwichtenberg, Helmut (1991). “Eine Umkehrung der Bewertungsfunktion für typisierten λ-Kalkül”. LICS.
  2. ^ Filinski, Andrzej; Rohde, Henning Korsholm (2004). “Ein Bezeichnungsbericht über untypisierte Normalisierung durch Bewertung”. FOSSACS.
  3. ^ Abel, Andreas; Aehlig, Klaus; Dybjer, Peter (2007). “Normalisierung durch Evaluation für die Martin-Löf-Typentheorie mit einem Universum” (PDF). MFPS.
  4. ^ Abel, Andreas; Coquand, Thierry; Dybjer, Peter (2007). “Normalisierung durch Bewertung für die Martin-Löf-Typentheorie mit typisierten Gleichheitsurteilen” (PDF). LICS.
  5. ^ Danvy, Olivier (1996). “Typgerichtete Teilbewertung” (PostScript gzippt). POPL: 242–257.


after-content-x4