Im -calculus, wir können Arithmetik, Zahlen, Boolesche Werte codieren und sogar Fakultäten von Zahlen berechnen, wie hier gezeigt .
Gibt es eine Kodierung von "für" oder "während"?
Im -calculus, wir können Arithmetik, Zahlen, Boolesche Werte codieren und sogar Fakultäten von Zahlen berechnen, wie hier gezeigt .
Gibt es eine Kodierung von "für" oder "während"?
Antworten:
Sicher! Lassen Sie mich anhand eines Beispiels zeigen, wie FOR codiert wird.
Angenommen, wir möchten ein einfaches faktorielles FOR-Programm übersetzen
Wir schreiben es um als
dann setzen wir alle Variablen, die wir verwenden, in ein Tupel (hier genügt ein Paar)
Dies wendet die Funktion effektiv an& lgr; ⟨ x , i ⟩ . ⟨ X * i , i + 1 ⟩ zum ersten Paar ⟨1,1⟩ zum N mal.
Schon seitN kann als Kirchenzahl dargestellt werden, bekommen wir
Die obige Syntax verwendet einige Dinge, die über den einfachen Lambda-Kalkül hinausgehen. Zahlen und Arithmetik können mit Kirchenzahlen präzisiert werden. Paare haben auch eine eigene Kirchencodierung:
Wenn Sie mehr als zwei Variablen haben, können Sie die obige Codierung auf Tupel verallgemeinern oder Tupel einfach als verschachtelte Paare darstellen.
WÄHREND die Rekursion am besten behandelt wird: statt
Wo
p
ein Prädikat undf
eine (Teil-) Funktion ist, können wir so etwas verwendenIn der Lambda-Rechnung wird die Rekursion unter Verwendung eines Festpunktkombinators , z. B. der Kirche, erhaltenY oder Turings Θ . Wir bekommen so etwas wie
woif b then t else e≡bte vorausgesetzt, Boolesche Werte sind kirchenkodiert.
Beachten Sie auch, dass WHILE (streng) leistungsfähiger als FOR ist. Jedes FOR kann als WHILE codiert werden, sodass diese Codierungstechnik auch für FOR verwendet werden kann.
quelle
Es gibt Codierungen von Schleifen, aber sie funktionieren nicht genau wie die Schleifen, die Sie gewohnt sind, da der Lambda-Kalkül keine zwingende Sprache ist. Der Lambda-Kalkül hat keine Nebenwirkungen (es ist eine rein funktionale Sprache), daher wäre das genaue Äquivalent einer Schleife nutzlos.
Expliziter Zustand
Ein imperatives Programm kann in eine rein funktionale Sprache übersetzt werden, indem der gesamte Status explizit als Variable im Programm weitergegeben wird. Ich werde die Python-Syntax für den imperativen Pseudocode verwenden. Es sollte größtenteils transparent sein, mit der Angabe,
(a, b) = f(…)
dass der Aufruf der Funktionf
ein Paar zurückgibta
undb
der ersten bzw. zweiten Komponente des Paares zugewiesen wird. Betrachten Sie eine SchleifeLassen Sie uns den Zustand explizit machen.
Wir können dies in einen rekursiven Aufruf übersetzen.
def loop(state):
definiert eine aufgerufene Funktionloop
.Hierbei werden nur die folgenden Konzepte verwendet, die alle im Lambda-Kalkül leicht ausgedrückt werden können:
Und so können wir eineC ( B (
while
Funktion für eine Bedingung definierentest_condition
) und ein Körperdo_stuff
):For-Schleifen variieren je nach Programmiersprache, sind jedoch immer ein Sonderfall von while-Schleifen, sodass sie auf die gleiche Weise codiert werden können. Wenn die Ausgangssprache die Ausdruckskraft von for-Schleifen einschränkt, kann es zu einfacheren Codierungen kommen. Zum Beispiel „Wiederholenn times ”ist einfach Funktionszusammensetzung n Zeiten, in denen die Funktion die Zustandstransformation ist, die den Körper der Schleife bildet, und wenn n ist eine kirchliche Ziffer, die einfach zutrifft n selbst auf die Schleifenkörperfunktion.
Hinzufügen eines Status zur Sprache
Ein alternativer Ansatz für den Zustand besteht darin, den Lambda-Kalkül mit Grundelementen zur Zustandsmanipulation zu erweitern. Wenn Sie dies tun, wird die Reihenfolge der Bewertung wichtig. In diesem Fall kann eine while-Schleife direkt mit Rekursion ausgedrückt werden.
quelle