Sequenzierung oder Continuation-Passing in der reinen Lambda-Kalküle

Question

Ich versuche die folgende Aufgabe zu lösen Hier.

Betrachten Sie die folgende Zahlendarstellung.Wie definiere ich den Zusatz?

|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

Die Nachfolger- und Vorgängeroperatoren sind einfach zu definieren:

Succ n = λx.n
Pred n = n (λx.x)

Eine „naheliegende“ Lösung zum Definieren der Addition besteht darin, die Folgeoperation plus den Test auf Null zusammen mit dem Festkommakombinator zu verwenden, so etwas wie (Y F) für F unten angegeben (der Operator Wenn und boolesche Werte werden wie üblich definiert):

F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

Aber definierend Ist0 scheint nicht trivial.Das Problem ist, dass es sich um eine Zahl handelt |N| verbraucht N+1 Argumente und N Argumente werden dadurch einfach gelöscht.Wenn ich also eine solche Funktion anwende, erscheint es sinnvoll, ihre Anwendung zu beenden, wenn klar wird, dass die Zahl, z. B.ist keine Identität.Ich denke, es ist eine Art Fortsetzung, aber ich kann mir nicht vorstellen, wie man es in der reinen Lambda-Rechnung modellieren kann.Vielleicht weiß jemand Tipps, die helfen könnten?

Ein Sequenzierungsoperator kann auch dabei helfen, die Addition zu definieren.Wenn eine Anwendung einer Ziffer |m| wird verzögert, bis eine Ziffer erscheint |n| wird angewendet auf alle seine Argumente, das Ergebnis wird genau eine Zahl sein |n+m|.Gibt es vielleicht eine Variante eines solchen Sequenzierungskombinators im reinen Lambda-Kalkül?

Die vom Autor der Übung bereitgestellte Antwort verwendet eine nicht reine Operation (nämlich IstProzedur die prüft, ob ihr Argument eine Funktion ist).

UPD: Es ist nicht schwer, ein CPS in der Lambda-Rechnung durchzuführen (Einzelheiten zum CBV finden Sie hier). Hier).Das scheint zur Lösung des Problems nicht auszureichen.

UPD:Wenn wir eine Version davon haben Zitat-Bewertung Funktionen für den reinen Lambda-Kalkül, dann muss es eine Funktion geben $eq$, der erkennt, ob die zitierten Lambda-Ausdrücke vorhanden sind syntaktisch gleich, und wir können konstruieren Ist0 verwenden $eq$.Aber das bezweifle ich $eq$ ist definierbar.Der Grund ist das „Generizitäts-Lemma“ (Barendregt-Buch, Lemma 14.3.24).Wenn wir die Gleichheit der zitierten Lambda-Terme testen könnten, dann ($eq$ (Zitat $\Omega$) (Zitat $\lambda x.x$)) würde zurückkehren $Falsch$, und die Generizität impliziert, dass ($eq$ (Zitat $\lambda x.x$) (Zitat $\lambda x.x$)) würde auch zurückkehren $Falsch$.Widerspricht das einer Konstruktionsmöglichkeit? Zitat in der reinen Lambda-Rechnung?

Answer 1

Ich glaube nicht, dass Sie in der reinen Lambda-Rechnung fündig werden.Der Schlüssel ist diese Aussage, die Sie gemacht haben:

Ein Sequenzierungsoperator kann auch dabei helfen, die Addition zu definieren.Wenn eine Anwendung einer Ziffer | m | wird verzögert, bis eine Ziffer | n | wird auf alle Argumente angewendet, ...

Nun, Modelle der Lambda-Kalküle sollen wie folgt aussehen:

$$U \cong U^U$$

Und der Sinn von Das ist das jeder semantische Wert $u \in U$ kann auf etwas angewendet werden.Es macht also keinen Sinn, über etwas zu sprechen, das "auf all seine Argumente angewendet wird". Es gibt keinen Wert, der nicht auf mehr Argumente im reinen Lambda -Kalkül angewendet werden kann.

Ich kenne auf Anhieb kein Modell/Argument, dass diese Darstellung natürlicher Werte eine Umsetzung unmöglich macht IsZero, obwohl es bei manchen Überlegungen unwahrscheinlich erscheint.Wenn dies jedoch im reinen Lambda-Kalkül möglich sein soll, muss es semantisch sinnvoll sein und darf nicht auf Begriffen basieren, die nur syntaktischer Natur sind.

Bearbeiten:Hier ist eine Skizze eines Arguments.Eine Definition von $\mathsf{IsZero}$ muss irgendwann reduzieren wie:

$$\mathsf{IsZero}\ n ightsquigarrow^* n \overrightarrow v$$

Der Grund dafür ist, dass die Anwendung auf eine bestimmte Anzahl von Werten der einzige Mechanismus in der Lambda-Kalküle ist, der tatsächlich zwischen Zahlen unterscheidet.Es muss Folgendes gelten: $$0 \overrightarrow v = \mathsf{true} \\ \mathsf{s}n \overrightarrow v = \mathsf{false}$$ Allerdings für jeden $\overrightarrow v$ es gilt: $$ || OverRightarrow V | + k | Overrightarrow v = | k | $$ (Wo $|\overrightarrow v|$ ist die Länge von $\overrightarrow v$).Aber nur $ | 1 | = mathsf {false} $ (falls dies die gewählte Konvention ist).Im Englischen gibt es keine Begrenzung hinsichtlich der Anzahl der Begriffe, die erforderlich sind, um durch Anwenden einer Zahl einen booleschen Wert zu erhalten.Es kann also keine geben $\overrightarrow v$ das erfüllt die Gleichungen für alle Ziffern und somit $\mathsf{IsZero}$ kann nicht definiert werden.

Answer 2

Der unkomplizierte Weg, um die Zugabe in Lambda-Calculus zu definieren, besteht darin, die Nummern zu behandeln, als ob sie verknüpfte Listen wären und die Listen kratzen.Um dies richtig zu machen, müssen zusätzliche Variablen verwendet werden, um die äußeren Variablen jeder Zahl auszutauschen, so dass der resultierende Expression für die zweite Zahl für die innere Variable des resultierenden Ausdrucks für die erste Zahl ersetzt werden kann.Dies ergibt den folgenden Ausdruck für die Zugabe:

generasacodicetagpre.