Gibt es Zwischen-Eta-Theorien für die Lambda-Rechnung?

Es gibt zwei Haupttheorien des Lambda-Kalküls, die Beta-Theorie und die Post-Complete-Erweiterung, die Beta-Eta-Theorie.

Haben diese beiden Theorien eine Zwischenregel, eine Art Zwischenregel, die eine konfluente Neuschreibungstheorie liefert? Gibt es eine interessante Vorstellung von partieller Extensionalität, der sie entspricht?

Dies ist die zweite Frage , die ich auf der Suche nach Zwischen eta gefragt habe, die bisherigen Wesen Erweiterungen von Beta-Theorie des Lambda - Kalkül , die sich um einen orthogonalen Begriff der Erweiterung Frage geführt, unsichtbar Äquivalenzen Charakterisieren von konfluenten Rewrite - Regeln , die eine Klärung gesucht Antwort auf diese frühere Frage.

Wenn Sie für typisierte Kalküle die negativen Typen ( , × , → ) berücksichtigen , können Sie die eta-Regeln grundsätzlich nach Belieben aktivieren oder deaktivieren, ohne die Konfluenz zu beeinträchtigen.$1$$\times$$\to$

Bei positiven Typen (Summen und Paaren mit der Beseitigung der Musterübereinstimmung) ist die Situation viel unübersichtlicher. Grundsätzlich stellt sich die Frage, ob der Begriff eine geschlossene Eliminierungsform hat, die es ermöglicht, dass Kontexte auf komplizierte Weise mit Eta-Erweiterungen interagieren. Wenn zum Beispiel den Typ A × B hat , dann ist seine eta-Expansion l e $e$$A \times B$ . Um die Gleichungstheorie zu erhalten, die ein Kategorietheoretiker erwarten würde, müssen Sie die Kontexte C [ - ] betrachten und die Gleichung zu C [ e ] ≡ l e t verallgemeinern$\mathsf{let}\;(a,b) = e \;\mathsf{in}\; (a,b)$$\mathbb{C}[-]$ (mit den erwarteten Gültigkeitsbeschränkungen).$\mathbb{C}[e] \equiv \mathsf{let}\;(a,b) = e\;\mathsf{in}\;\mathbb{C}[(a,b)]$

Ich denke, dass Sie immer noch ein Konfluenzergebnis nachweisen können, wenn Sie die Pendelkonvertierungen nicht zulassen. Aber das ist Hörensagen - ich habe es nie selbst ausprobiert oder mir Papiere angeschaut, die es dokumentieren.

Ich weiß allerdings nichts über untypisierte Lambda-Rechnung.

EDIT: Charles fragt nach Eta-Reduktionen. Dies ist vielversprechend für die Art von Beispiel, die er sucht, da sie meiner Meinung nach im Allgemeinen nicht stark genug sind, um die vollständige Gleichheitstheorie zu modellieren, die ich anhand eines einfachen Beispiels mit Booleschen veranschaulichen werde. Die eta-Expansion für Boolesche Werte ist . (Die Eta-Reduktion ist natürlich die andere Richtung.)$\mathbb{C}[e] \mapsto \mathsf{if}(e, \mathbb{C}[\mathsf{true}], \mathbb{C}[\mathsf{false}])$

Betrachte nun den Term . Zeigen, dass dieser Ausdruck äquivalent ist zu i f ( e , $\mathsf{if}(e, f, g)\;\mathsf{if}(e, x, y)$ muss durch eine eta-Expansion gehen, weil wir die haben ersetzen e in einem der if-then-elses mit t r u $\mathsf{if}(e, f\;x, g\;y)$$e$$\mathsf{true}$ und , um eine zum Antrieb β -Reduktion. $\mathsf{false}$$\beta$

Laut John C. Mitchell in Grundlagen der Programmiersprachen, sowohl in der STLC als auch in der nicht typisierten Lambda-Rechnung, pair (proj₁ P, proj₂ P) → Pbricht die Reduktionsregel die Konfluenz, wenn sie mit der fixReduktion kombiniert wird (oder, ich nehme an, wenn ich den Beweis betrachte), ohne solche Bedingungen für den nicht typisierten Fall. Dies ist der Satz 4.4.19 (Seite 289).