[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki22\/2021\/02\/02\/normalisierung-durch-auswertung-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki22\/2021\/02\/02\/normalisierung-durch-auswertung-wikipedia\/","headline":"Normalisierung durch Auswertung – Wikipedia","name":"Normalisierung durch Auswertung – Wikipedia","description":"before-content-x4 In der Programmiersprachen-Semantik Normalisierung durch Bewertung (NBE) ist ein Stil, um die normale Form von Begriffen in der \u03bb-Rechnung","datePublished":"2021-02-02","dateModified":"2021-02-02","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki22\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki22\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/132f849875b39d6d3308753bd32a89661168f8c7","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/132f849875b39d6d3308753bd32a89661168f8c7","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki22\/2021\/02\/02\/normalisierung-durch-auswertung-wikipedia\/","wordCount":6441,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In der Programmiersprachen-Semantik Normalisierung durch Bewertung (NBE) ist ein Stil, um die normale Form von Begriffen in der \u03bb-Rechnung zu erhalten, indem man sich auf ihre Denotationssemantik beruft.  Ein Begriff steht an erster Stelle interpretiert in ein Denotationsmodell der \u03bb-Termstruktur, und dann wird ein kanonischer (\u03b2-normaler und \u03b7-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 \u03b2-Reduktionen tief in \u03bb-Termen zul\u00e4ssig sind.  NBE wurde zuerst f\u00fcr den einfach typisierten Lambda-Kalk\u00fcl beschrieben.[1]  Es wurde seitdem sowohl auf schw\u00e4chere Systeme wie den untypisierten Lambda-Kalk\u00fcl ausgedehnt[2]  unter Verwendung eines dom\u00e4nentheoretischen Ansatzes und zu reicheren Typsystemen wie mehreren Varianten der Martin-L\u00f6f-Typentheorie.[3][4]Gliederung[edit]Betrachten Sie den einfach typisierten Lambda-Kalk\u00fcl, bei dem die Typen \u03c4 Grundtypen (\u03b1), Funktionstypen (\u2192) oder Produkte (\u00d7) sein k\u00f6nnen, die durch die folgende Backus-Naur-Formgrammatik gegeben werden (\u2192 wie \u00fcblich rechts assoziieren):(Typen) \u03c4 :: = \u03b1 |  \u03c41 \u2192 \u03c42 |  \u03c41 \u00d7 \u03c42Diese k\u00f6nnen als Datentyp in der Metasprache implementiert werden.  F\u00fcr Standard ML k\u00f6nnten wir beispielsweise Folgendes verwenden:   datatype ty = Basic of string             | Arrow of ty * ty             | Prod of ty * tyBegriffe 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,\u2026 :: = var x | lam ((x, t) | App ((s, t) | Paar ((s, t) | fst t | snd tHier lam\/.App (bzw. Paar\/.fst,snd) sind die Intro \/ Elim-Formen f\u00fcr \u2192 (bzw. \u00d7) 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 tmDie 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.,\u2026 :: = LAM (\u03bbx. S. x) | PAAR ((S., T.) | SYN tBeachten Sie, dass die Semantik keine Variablen oder Eliminierungsformen enth\u00e4lt.  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 tmEs gibt zwei typindizierte Funktionen, die sich zwischen der syntaktischen und der semantischen Ebene hin und her bewegen.  Die erste Funktion, normalerweise geschrieben \u2191\u03c4, spiegelt der Begriff Syntax in die Semantik, w\u00e4hrend der zweite reifiziert die Semantik als syntaktischer Begriff (geschrieben als \u2193\u03c4).  Ihre Definitionen rekursiv wie folgt:\u2191\u03b1t=S.Y.N. t\u2191\u03c41\u2192\u03c42v=L.EINM.((\u03bbS.. \u2191\u03c42((einpp ((v,\u2193\u03c41S.)))\u2191\u03c41\u00d7\u03c42v=P.EINichR.((\u2191\u03c41((fst v),\u2191\u03c42((snd v))\u2193\u03b1((S.Y.N. t)=t\u2193\u03c41\u2192\u03c42((L.EINM. S.)=leinm ((x,\u2193\u03c42((S. ((\u2191\u03c41((veinr x)))) wo x ist frisch\u2193\u03c41\u00d7\u03c42((P.EINichR. ((S.,T.))=peinichr ((\u2193\u03c41S.,\u2193\u03c42T.){ 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\u00a0: 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) = tDurch Induktion auf die Struktur von Typen folgt, dass wenn das semantische Objekt S. bezeichnet einen gut typisierten Begriff s vom Typ \u03c4, dann das Objekt erneut best\u00e4tigen (dh \u2193\u03c4 S) erzeugt die \u03b2-normale \u03b7-lange Form von s.  Alles, was bleibt, ist daher, die anf\u00e4ngliche semantische Interpretation zu konstruieren S. von einem syntaktischen Begriff s.  Diese Operation, geschrieben \u2225s\u2225\u0393, wobei \u0393 ein Kontext von Bindungen ist, erfolgt die Induktion ausschlie\u00dflich \u00fcber den Begriff Struktur:\u2016veinr x\u2016\u0393=\u0393((x)\u2016leinm ((x,s)\u2016\u0393=L.EINM. ((\u03bbS.. \u2016s\u2016\u0393,x\u21a6S.)\u2016einpp ((s,t)\u2016\u0393=S. ((\u2016t\u2016\u0393) wo \u2016s\u2016\u0393=L.EINM. S.\u2016peinichr ((s,t)\u2016\u0393=P.EINichR. ((\u2016s\u2016\u0393,\u2016t\u2016\u0393)\u2016fst s\u2016\u0393=S. wo \u2016s\u2016\u0393=P.EINichR. ((S.,T.)\u2016snd t\u2016\u0393=T. wo \u2016t\u2016\u0393=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\u00a0: 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\u00f6pfende F\u00e4lle gibt.  wenn jedoch auf a angewendet geschlossen Keiner dieser fehlenden F\u00e4lle ist jemals aufgetreten.  Die NBE-Operation zu geschlossenen Bedingungen lautet dann: (* nbe\u00a0: ty -> tm -> tm *) fun nbe a t = reify a (meaning empty t)Betrachten Sie als Beispiel f\u00fcr 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\u00e4tsfunktion in der kombinatorischen Logik.  Das Normalisieren auf einen Identit\u00e4tstyp erzeugt: - nbe (Arrow (Basic \"a\", Basic \"a\")) SKK; val it = lam (\"v0\",var \"v0\") : tmDas Ergebnis ist tats\u00e4chlich in \u03b7-langer Form, wie leicht durch Normalisieren auf einen anderen Identit\u00e4tstyp 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\"))) : tmSiehe auch[edit]Verweise[edit]^ Berger, Ulrich;  Schwichtenberg, Helmut (1991).  “Eine Umkehrung der Bewertungsfunktion f\u00fcr typisierten \u03bb-Kalk\u00fcl”. LICS.^ Filinski, Andrzej;  Rohde, Henning Korsholm (2004). “Ein Bezeichnungsbericht \u00fcber untypisierte Normalisierung durch Bewertung”. FOSSACS.^ Abel, Andreas;  Aehlig, Klaus;  Dybjer, Peter (2007). “Normalisierung durch Evaluation f\u00fcr die Martin-L\u00f6f-Typentheorie mit einem Universum” (PDF). MFPS.^ Abel, Andreas;  Coquand, Thierry;  Dybjer, Peter (2007). “Normalisierung durch Bewertung f\u00fcr die Martin-L\u00f6f-Typentheorie mit typisierten Gleichheitsurteilen” (PDF). LICS.^ Danvy, Olivier (1996).  “Typgerichtete Teilbewertung” (PostScript gzippt). POPL: 242\u2013257.     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki22\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki22\/2021\/02\/02\/normalisierung-durch-auswertung-wikipedia\/#breadcrumbitem","name":"Normalisierung durch Auswertung – Wikipedia"}}]}]