Lambda-Kalkül: Wie funktionieren Bewertungskontexte?

In der reinen Lambda-Rechnung haben wir die induktiv definierte Menge von Begriffen (die Grammatik):

e ::= x ∣ λ x . e ∣ e_{1} e_{2}

$e::= x \mid \lambda x . e \mid e_1 e_2$

Im Rahmen der Call-by-Value-Bewertungsstrategie haben wir die Inferenzregeln für die Beta-Reduktion und Regeln für die Bewertung von Anwendungen (Kongruenzregeln). Ich versuche zu verstehen, wie Bewertungskontexte die Kongruenzregeln ersetzen können, ohne die Syntax der Sprache tatsächlich zu ändern. Ohne Bewertungskontexte haben wir Folgendes:

\frac{e_{1} \to e_{1}^{'}}{e_{1} e_{2} \to e_{1}^{'} e_{2}}

$\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}$ und

\frac{e_{2} \to e_{2}^{'}}{v e_{2} \to v e_{2}^{'}} .

$\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.$

Dies ist sinnvoll, da, wenn wir eine Instanz eines Ausdrucks , klar ist, dass dies der ist der Form und damit $t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$ $e_1e_2 \rightarrow e_1'e_2$

(λ f . λ x . f x) ((λ y . y) λ z . z) λ w . w \to (λ f . λ x . f x) (λ z . z) λ w . w

$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$

Wenn wir die Kongruenzregeln durch Bewertungskontexte ersetzen: , benötigen wir nur eine einzige Regel, um die Kongruenzregeln der Sprache auszudrücken:

E ::= [\cdot] ∣ E e ∣ v E

$E::= [\cdot] \mid Ee \mid vE$

\frac{e \to e^{'}}{E [e] \to E [e^{'}]} .

$\frac{e \rightarrow e'}{E[e] \rightarrow E[e']}.$

Ich bin verwirrt darüber, wie Bewertungskontexte uns sagen können, wie der Ausdruck von oben bewertet werden kann, ohne die Syntax der Sprache zu ändern. Ich verstehe nicht, wie der Evaluierungskontext "funktioniert", ohne as neu zu schreiben $t$ $t$

E_{t} = (λ f . λ x . f x) [\cdot] λ w . w

$E_t = (\lambda f . \lambda x. f x)[\cdot]\lambda w.w$

wobei . Es gibt keinen offensichtlichen a priori Grund, unter Call-by-Value ohne Kenntnis von zu bewerten . Ich habe wirklich keine Ahnung, wo ich falsch liege. Kann jemand helfen, mein Denken zu korrigieren? $t = E_t[((\lambda y .y)\lambda z .z)]$ $t$ $E_t$

programming-languages lambda-calculus semantics verblüfft
quelle

Reduktion ist keine Kongruenz mit Reduktionsstrategien wie Call-by-Value. Siehe auch hier .

Martin Berger

Ich verstehe deine Antwort nicht. Ihre Verwendung von "Kongruenz" als Verb macht für mich keinen Sinn. Ich habe die Antworten in dem von Ihnen angegebenen Link gelesen, verstehe aber immer noch nicht, warum als syntaktische Form dargestellt wird, aber es wird in der Syntax der Sprache, für die es definiert ist, nie verwendet.

E

$E$

Baffld

Ich benutze Kongruenz nicht als Verb. Ich verstehe nicht, was du meinst. E ist eine Metavariable, die sich über Bewertungskontexte erstreckt. Bewertungskontexte sind eine geeignete Teilmenge von Kontexten. Kontexte sind Programme mit einem Loch.

Martin Berger

Antworten:

Die Subtilität liegt darin, wo zwischen Sprache und Metasprache unterschieden wird. Wie René Magritte es ausdrückte:

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$ ist ein Lambda-Term, der in der Syntax für Lambda-Terme geschrieben ist. Nennen wir diesen Lambda-Term . Sei der Lambda-Term . Ich kann schreiben (und das ist eine echte Gleichheit): Alles, was ich getan habe, war, einem Subterm einen Namen zu geben. Wenn Sie die rechte Seite dieser Gleichheit " " betrachten, ist sie nicht in der Syntax von Lambda-Begriffen geschrieben; Es ist in einer mathematischen Notation geschrieben, in der wir einen Buchstaben für einen Lambda-Term stehen lassen. $t$ $M$ $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z))$ $t = M \, (\lambda w.w)$ $M \, (\lambda w.w)$

Wenn wir eine Regel wie schreiben , gibt sie das folgende Axiom an: für alle Lambda-Terme und und jeden Wert , wenn reduziert sich auf dann reduziert sich auf . Hier verwenden wir wieder Meta-Notationen (dh mathematische Notationen, um über eine Sprache zu argumentieren): den Pfeil , um die Reduktionsrelation auszudrücken; Metavariablen, bei denen ein Buchstabe die Sortierung angibt ( für Lambda-Begriffe,

\frac{e_{2} \to e_{2}^{'}}{v e_{2} \to v e_{2}^{'}}

$\frac{e_2 \to e_2'}{v \, e_2 \to v \, e_2'}$

e_{2}

$e_2$

e_{2}^{'}

$e_2'$

v

$v$

e_{2}

$e_2$

e_{2}^{'}

$e_2'$

v e_{2}

$v \, e_2$

v e_{2}^{'}

$v \, e_2'$

\to

$\to$

e

$e$

v

$v$ für Werte) und Indizes und Primzahlen unterscheiden zwischen Metavariablen derselben Art; die Bruchnotation zum Schreiben eines induktiven Axioms.

Wenn wir die Regel schreiben

\frac{e \to e^{'}}{E [e] \to v E [e^{'}]}

$\frac{e \to e'}{E[e] \to v E[e']}$

E [\cdot]

$E[\cdot]$

e

$e$

e^{'}

$e'$

E [\cdot]

$E[\cdot]$

e

$e$

e^{'}

$e'$

E [e]

$E[e]$

E [e^{'}]

$E[e']$

$(\lambda f. \lambda x. f x)[\cdot] (\lambda w.w)$ $E_t$ $t = E_t[(\lambda y.y)(\lambda z.z)]$ $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$

$t$

Bei der Notation mit mehreren Regeln müssen Sie einen Abzugsbaum finden (im Allgemeinen - hier ist die Ableitung linear, sodass Sie lediglich eine Kette finden müssen, die zu einem Axiom führt).
Bei der Notation unter Verwendung von Bewertungskontexten müssen Sie einen geeigneten Bewertungskontext finden.

Die Grammatik des Bewertungskontexts folgt der Struktur der Bewertungsregeln. Es handelt sich also nicht wirklich um zwei Methoden, sondern um zwei verschiedene Arten, dieselbe Definition auszudrücken.

Um dies zu verstehen, empfehle ich dringend die folgende Übung: Implementieren Sie in Ihrer Lieblingssprache die Bewertung des Lambda-Term-Call-by-Value auf einfache Weise, wobei ein Typ Lambda-Terme darstellt und eine Funktion einen Reduktionsschritt ausführt.

Gilles 'SO - hör auf böse zu sein'
quelle

In Verbindung mit Ihrem letzten Absatz: Alle Logiker und alle, die jemals Syntax studieren, sollten dazu gebracht werden, die Substitution zu implementieren.

Andrej Bauer