Abfrage nach Booleschen Werten in Lambda-Kalkül

Um zu verstehen, wie Boolesche Ausdrücke im Lambda-Kalkül dargestellt werden, hilft es, über einen IF-Ausdruck nachzudenken, "wenn ein dann b else c". Dies ist ein Ausdruck, der den ersten Zweig wählt, b, wenn er wahr ist, und den zweiten, c, falls er falsch ist. Lambda-Ausdrücke können das sehr leicht tun:

gibt Ihnen das erste Argument und

gibt dir die zweite. Wenn also einer dieser Ausdrücke ist, dann

gibt entweder b oder c , was genau das ist, was die IF tun soll. Also definiere

und a b c verhalten sich wie if a then b else c .

Wenn Sie in Ihren Ausdruck bei (n a b) schauen, bedeutet das if n then a else b . Dann bedeutet m (n a b) b

Dieser Ausdruck wird als a ausgewertet, wenn sowohl m als auch n true und andernfalls b sind. Da a das erste Argument Ihrer Funktion ist und b das zweite ist, und true wurde als eine Funktion definiert, die das erste der beiden Argumente angibt. Wenn m und n beide% sind co_de%, so ist der ganze Ausdruck. Sonst ist es true . Und das ist nur die Definition von false !

All dies wurde von Alonzo Church erfunden, der den Lambda-Kalkül erfunden hat.

Im lambda-Kalkül wird ein Boolescher Wert durch eine Funktion dargestellt, die zwei Argumente benötigt, eins für Erfolg und eins für Fehler. Die Argumente heißen Fortsetzungen , weil sie mit dem Rest der Berechnung fortfahren; Der boolesche Wert True ruft die Erfolgsfortsetzung auf und der Boolean False ruft die Fehlerfortsetzung auf. Diese Kodierung wird als Church-Kodierung bezeichnet, und die Idee ist, dass ein Boolescher Wert sehr viel wie eine "Wenn-dann-sonst-Funktion" ist.

So können wir sagen

Dabei steht s für Erfolg, f steht für Fehler und der Backslash ist ein ASCII-Lambda.

Jetzt hoffe ich, dass Sie sehen können, wohin das geht. Wie codieren wir and ? Nun, in C könnten wir es zu

Nur diese sind Funktionen, also

ABER, das ternäre Konstrukt, wenn es im Lambda-Kalkül kodiert wird, ist nur eine Funktion, also haben wir

Endlich erreichen wir

Und wenn wir die Erfolgs- und Fehlerfortsetzungen in a und b umbenennen, kehren wir zu Ihrem ursprünglichen

Wie bei anderen Berechnungen im Lambda-Kalkül, besonders bei der Verwendung von Church-Codierungen, ist es oft einfacher, die Dinge mit algebraischen Gesetzen und dem rationalen Denken zu bearbeiten und dann am Ende in lambdas umzuwandeln.

Eigentlich ist es ein bisschen mehr als nur der AND-Operator. Es ist die Version des Lambda-Kalküls von if m and n then a else b . Hier ist die Erklärung:

Im Lambda-Kalkül wird true als eine Funktion dargestellt, die zwei Argumente * nimmt und die erste zurückgibt. Falsch wird als Funktion dargestellt, indem zwei Argumente * und die zweite zurückgegeben werden.

Die oben gezeigte Funktion benötigt vier Argumente *. Aus der Sicht von ihm sollen m und n boolesche Werte sein und a und b einige andere Werte. Wenn m wahr ist, wird es zu seinem ersten Argument ausgewertet, das n a b ist. Dies wiederum wird zu a ausgewertet, wenn n wahr ist und b wenn n falsch ist. Wenn m falsch ist, wird es zu seinem zweiten Argument b ausgewertet.

Im Grunde gibt die Funktion a zurück, wenn sowohl m als auch n wahr sind und b andernfalls.

(*) Wenn "zwei Argumente übernehmen" bedeutet "ein Argument zu nehmen und eine Funktion zurückzugeben, die ein anderes Argument annimmt".

Bearbeiten Sie als Antwort auf Ihren Kommentar:

and true false , wie auf der Wiki-Seite zu sehen, funktioniert folgendermaßen:

Der erste Schritt besteht einfach darin, jeden Bezeichner durch seine Definition zu ersetzen, d. h. (λm.λn. m n m) (λa.λb. a) (λa.λb. b) . Jetzt wird die Funktion (λm.λn. m n m) angewendet. Das bedeutet, dass jedes Auftreten von m in m n m durch das erste Argument ( (λa.λb. a) ) ersetzt wird und jedes Vorkommen von n durch das zweite Argument ( (λa.λb. b) ) ersetzt wird. Also bekommen wir (λa.λb. a) (λa.λb. b) (λa.λb. a) . Jetzt wenden wir einfach die Funktion (λa.λb. a) an. Da der Rumpf dieser Funktion einfach ein, d.h. das erste Argument ist, wird dies als (λa.λb. b) , d. H.% Co_de% (als false bedeutet λx.λy. y ) ausgewertet.