-calculus, gibt es eine Kodierung für oder während?

7

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"?

alim
quelle
6
λ-Kalkül ist vollständig, also können Sie das Gleiche für eine for- oder while-Schleife tun. Ich würde sie nicht als Kodierungen bezeichnen , da sie nur Funktionen sind, wie alles in λ-Kalkül
Euge

Antworten:

11

Sicher! Lassen Sie mich anhand eines Beispiels zeigen, wie FOR codiert wird.

Angenommen, wir möchten ein einfaches faktorielles FOR-Programm übersetzen

x := 1
for i := 1 to N do
   x := x * i

Wir schreiben es um als

x := 1
i := 1
repeat N times
   x := x*i
   i := i+1

dann setzen wir alle Variablen, die wir verwenden, in ein Tupel (hier genügt ein Paar)

(x,i) := (1,1)
repeat N times
   (x,i) := (x*i, i+1)

Dies wendet die Funktion effektiv an λx,i.xi,i+1 zum ersten Paar 1,1 zum N mal.

Schon seit N kann als Kirchenzahl dargestellt werden, bekommen wir

N(λx,i.xi,i+1)1,1

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:

x,yλk.kxyλx,y.Mλz.M{zT/x,zF/y}
wo z ist eine neue Variable, T=λab.a und F=λab.b.

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

while p(x,i) do
   (x,i) := f(x,i)

Wo pein Prädikat und feine (Teil-) Funktion ist, können wir so etwas verwenden

def recFun(x,i):
   if p(x,i):
      return recFun(f(x,i))
   else:
      return (x,i)

In der Lambda-Rechnung wird die Rekursion unter Verwendung eines Festpunktkombinators , z. B. der Kirche, erhaltenY oder Turings Θ. Wir bekommen so etwas wie

Y(λr.λx,i.if pxi then r(fx,i) else x,i)

wo if b then t else ebte 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.

Chi
quelle
9

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 Funktion fein Paar zurückgibt aund bder ersten bzw. zweiten Komponente des Paares zugewiesen wird. Betrachten Sie eine Schleife

while test_condition():
    do_stuff()

Lassen Sie uns den Zustand explizit machen.

state = initial_state
(state, cond) = test_condition(state)
while cond:
    (state, cond) = test_condition(do_stuff(state))

Wir können dies in einen rekursiven Aufruf übersetzen. def loop(state):definiert eine aufgerufene Funktion loop.

def loop(state):
    (state, cond) = test_condition(state)
    if cond: return loop(do_stuff(state))
    else: return state
state = loop(initial_state)

Hierbei werden nur die folgenden Konzepte verwendet, die alle im Lambda-Kalkül leicht ausgedrückt werden können:

Und so können wir eine whileFunktion für eine Bedingung definierenC( test_condition) und ein KörperB( do_stuff):

while:=λC.λB.fix(λf.λs.(λp.BODY(firstp)(secondp))(Cs))where BODY=λs.λc.ifc(f(Bs))s

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.

whileimperative:=λC.λB.fix(λf.ifC(B;f)())
Gilles 'SO - hör auf böse zu sein'
quelle