Lambda-Kalkül: Wie funktionieren Bewertungskontexte?

8

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

e::=xλx.ee1e2

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:

e1e1e1e2e1e2
und
e2e2ve2ve2.

Dies ist sinnvoll, da, wenn wir eine Instanz eines Ausdrucks , klar ist, dass dies der ist der Form und damitt=(λf.λx.fx)((λy.y)λz.z)λw.we1e2e1e2

(λf.λx.fx)((λy.y)λz.z)λw.w(λf.λx.fx)(λz.z)λw.w

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

E::=[]EevE
eeE[e]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 schreibentt

Et=(λf.λx.fx)[]λ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=Et[((λy.y)λz.z)]tEt

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
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:

8

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

Ceci n'est pas une Pipe.

(λf.λx.fx)((λy.y)(λz.z))(λ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.tM(λf.λx.fx)((λy.y)(λz.z))t=M(λw.w)M(λ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,

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

Wenn wir die Regel schreiben

eeE[e]vE[e]
E[]eeE[]eeE[e]E[e]

(λf.λx.fx)[](λw.w)Ett=Et[(λy.y)(λz.z)](λf.λx.fx)((λy.y)(λz.z))(λ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
2
In Verbindung mit Ihrem letzten Absatz: Alle Logiker und alle, die jemals Syntax studieren, sollten dazu gebracht werden, die Substitution zu implementieren.
Andrej Bauer