Lambda-Kalkül: Unterschied zwischen Kontexten und Bewertungskontexten

Erstens möchte ich darauf hinweisen, dass mein nachstehender Text Fehler enthalten kann. Sie können also jederzeit auf Fehler bei der Formulierung der Frage hinweisen.

Betrachten Sie einen nicht typisierten Lambda-Kalkül mit Booleschen Werten und if-Anweisungen, deren Terme durch diese Syntax gegeben sind:

 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

Die Kontexte C würden in diesem Fall gemäß der folgenden Syntax angegeben:

C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C 

Zusätzlich könnte man Bewertungskontexte E nach dieser anderen Syntax definieren:

E ::= [-] | \x. E | v E | E t | if E t t 

Ich habe meine Frage in drei Unterpunkte aufgeteilt, auf die ich eingehen möchte.

1. Wann werden die beiden Begriffe verwendet? Ich weiß zum Beispiel, dass Bewertungskontexte verwendet werden, um die Semantik des Kalküls zu definieren, aber die Verwendung von Kontexten entgeht mir immer noch etwas. Auch ich möchte hier eine Bestätigung meines Wissens.
2. Wann ist das eine dem anderen vorzuziehen und warum?
3. Könnten Sie auf relevante Artikel verweisen, die mir helfen könnten, diese Angelegenheit zu klären?

Kontext wird für viele Zwecke verwendet, normalerweise jedoch zum Definieren von Programmkongruenzen. Bewertungskontexte sind eine Teilmenge von Kontexten. Sie werden typischerweise zur Definition von Reduktionsrelationen verwendet. Lassen Sie mich jeweils ein Beispiel geben.

Eine formale Art und Weise Programm Gleichheit zu definieren , ist zu sagen , zwei Programme und N ist kontextuell gleich sie sich in jedem Kontext , ohne eine Änderung des Verhaltens ersetzen. Wir können dies wie folgt definieren: M und N sind für alle schließenden Kontexte C [ ⋅ ] für M und N kontextuell gleich : C [ M ] ⇓ t genau dann, wenn C [ N ] ⇓ t . Wir sagen, ein Kontext schließt sich für M , N$M$$N$$M$$N$$C[\cdot]$$M$$N$$C[M] \Downarrow t$$C[N] \Downarrow t$$M, N$wenn weder noch C [ N ] freie Variablen haben. Der Ausdruck M ⇓ t bedeutet, dass sich das Programm M in einer endlichen Anzahl von Schritten auf den Wert t reduziert . (Im Übrigen ist zu beachten, dass die Definition der kontextuellen Äquivalenz für umfangreiche Begriffe der Berechnung, z. B. gleichzeitige Prozesse, eine größere Rolle spielt.)$C[M]$$C[N]$$M \Downarrow t$$M$$t$

Im Gegensatz dazu sind Bewertungskontexte Kontexte, die die Bewertung nicht blockieren. Genauer gesagt ist ein Bewertungskontext ein Begriff mit einem Loch an dem Punkt, an dem der nächste atomare Reduktionsschritt stattfinden muss (oder für eine nicht deterministische Berechnung stattfinden kann). Für Bewertungskontexte sollte also folgende Regel gelten: Als Beispiel für die Verwendung von Bewertungskontexten betrachtenwirdie Reduktionsregeln für Call-by-Value-λ-Kalkül, bei denen wir nicht unterλreduzieren. Selbst wenn alsoM→N ist, haben wir keine Reduktionλx. M→λx. N. Dies kann leicht mit der obigen allgemeinen Kontextregel zusammen mit einer Grammatik für Bewertungskontexte ausgedrückt werden, dieλ-Ausdrückeweglässt. Evaluationskontexte wurden erstmals in verwendet

$$\frac{M \rightarrow N}{E[M] \rightarrow E[N]}$$ $\lambda$$\lambda$$M \rightarrow N$$\lambda x.M \rightarrow \lambda x.N$$\lambda$Der überarbeitete Bericht über die syntaktischen Theorien der Ablaufsteuerung und des Zustands von Felleisen und Hieb.

Ein Kontext ist ein syntaktischer Begriff. Ein Kontext ist ein Begriff mit einem Loch. (Gelegentlich gibt es Kontexte mit mehreren Löchern. In diesem Fall wird die Definition klar angegeben.) Die Syntax von Kontexten wird definiert, indem die Syntax von Begriffen verwendet wird und ein Subterm ein Loch anstelle eines Begriffs sein darf . In BNF (Ich benutze die Lambda-Kalkül als Beispiel, ohne booleans und wenn Aussagen , die sich auf das Beispiel nichts bringen.): C : : = [ ] | x | $[]$

$$C ::= [] \mid x \mid t \, C \mid C \, t \mid \lambda x.C$$

Zusammen mit der Definition eines Kontexts entsteht die Definition, einen Begriff in einen Kontext zu setzen. Wenn ein Kontext und t ein Term ist, dann ist C [ t ] der Term, der erhalten wird, indem t in den Syntaxbaum gesetzt wird, in dem sich das Loch [ ] in C [ t ] befindet . Dies ist im Grunde eine Substitution, bei der die Variable garantiert genau einmal vorkommt (beachten Sie jedoch, dass die „Variable“, die substituiert wird, eine Variable auf Metaebene ist, [ ] und keine Variable im Lambda-Kalkül oder in einer anderen Sprache der Begriffe t ).$C[]$$t$$C[t]$$t$$[]$$C[t]$$[]$$t$

Kontexte werden verwendet, um verschiedene Definitionen in der Semantik zu formulieren. Ein weit verbreitetes Beispiel ist, dass die meisten Evaluierungsbegriffe die Definition von Kontexten beinhalten, in denen eine Evaluierung durchgeführt werden kann. Betrachten Sie zum Beispiel die Lambda-Rechnung. Der Grundbegriff der Bewertung ergibt sich aus der Beta-Reduktionsregel: wobei M { x ← N } dieauf M angewendeteSubstitution x ↦ N ist .

$$(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}$$ $M \{x\leftarrow N\}$$x \mapsto N$$M$

Dies ist nicht die vollständige Definition von Beta-Reduktion: Wenn ein Term , kann er Beta-Reduktion bewirken , wenn es Subtermen M und N und eine Variable x gibt, so dass t = ( λ x . M $t$$M$$N$$x$ ; aber allgemeinerkann t beta-reduzieren,wenn es eine Untermenge t 'gibt, so dass t ' = ( λ x . M )$t = (\lambda x. M) \, N$$t$$t'$$t' = (\lambda x. M) \, N$ . Eine andere Möglichkeit, dies auszudrücken, ist, dass beta-reduzieren kann, wenn es einen Kontext C und einige Terme M und N und eine Variable x gibt, so dass t = C [ ( λ x . M $t$$C$$M$$N$$x$ . Bei einer solchen Reduktion ist die rechte Seite C [ M { x ← N } ] . Um eine formale Notation zu verwenden, wird die Beta-Reduktion durch die folgenden Abzugsregeln definiert: $t = C[(\lambda x. M) \, N]$$C[M \{x\leftarrow N\}]$ Dieselbe Definition kann ausgedrückt werden, indem alle Arten von Kontexten explizit angegeben werden:

$$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \qquad \dfrac{M \to_\beta N}{C[M] \to_\beta C[N]} (\gamma)$$ $$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_\beta N}{\lambda x. M \to_\beta \lambda x. N} (C_\lambda) \qquad \dfrac{M \to_\beta N}{M \, P \to_\beta N \, P} (C_{@\lt}) \qquad \dfrac{M \to_\beta N}{P \, M \to_\beta P \, N} (C_{@\gt})$$

Diese Definition führt zu einer Beta-Reduktion, dh einem Evaluationsbegriff, der die Reduzierung von Subtermen ermöglicht. In Programmiersprachen durchgeführte Berechnungen ermöglichen häufig keine Reduzierung von Untertiteln innerhalb von Funktionen: Die Reduzierungsregel kann nur auf der obersten Ebene oder auf der linken oder rechten Seite einer Anwendung angewendet werden. Das können wir ausdrücken , indem eine neue Art von Kontext zu definieren , die nicht alle syntaktischen Formen erlaubt: Mit dieser Syntax können wir den semantischen Begriff der nicht partiellen Auswertung definieren:

$$D ::= [] \mid x \mid t \, D \mid D \, t$$ Wir könnten diese Definition auch präsentieren, indem wir sie erweitern, wie wir es oben für die vollständige Beta-Reduktion getan haben: $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} \qquad \dfrac{M \to_{np} N}{D[M] \to_{np} D[N]}$$ Dwürde als Bewertungskontext bezeichnet, da es zur Definition eines Bewertungsbegriffs verwendet wird. Ein Bewertungskontext ist keine besondere Art von Kontext. Vielmehrist es eine Frage, wofür der Kontext verwendetwird, ihn als Bewertungskontext zu bezeichnen. $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_{np} N}{M \, P \to_{np} N \, P} (C_{@\lt}) \qquad \dfrac{M \to_{np} N}{P \, M \to_{np} P \, N} (C_{@\gt})$$ $D$

Ich werde ein weiteres Beispiel für den Kontext geben. Definieren sie Werte gemäß der folgenden Syntax: V : : = x V 1 ... V n | & lgr; x . M Nun wollen wir definieren eine andere Art von Zusammenhängen: E : : = [ ] | $V$

$$V ::= x V_1 \ldots V_n \mid \lambda x. M$$ $$E ::= [] \mid M \, E \mid E \, V$$ $D$ $$\dfrac{}{(\lambda x. M) \, V \to_{cbva} M \{x\leftarrow V\}} (\beta_{cbva}) \qquad \dfrac{M \to_\beta N}{E[M] \to_{cbva} E[N]} (\gamma_{cbva})$$