Lambda-Kalkül durch JavaScript, Teil 2

Dieser Artikel wurde ursprünglich auf 47deg.com am 7. Januar 2021 veröffentlicht.

Im vorigen Beitrag dieser Serie wurden die Einschränkungen vorgestellt, die wir beachten müssen, um JavaScript als untypisierte Lambda-Kalkulation zu verwenden. Anschließend haben wir einige dieser Einschränkungen durch Currying (für Funktionen mit mehr als einem Argument) und Translation (um const lokale Variablen in eine Kombination von Funktionen zu verwandeln) gelockert. In diesem Beitrag werden wir unsere Reise fortsetzen, indem wir uns zunächst die Konditionale ansehen. Dann werden wir Church-Zahlen einführen, um Zahlen zu kodieren.

Boolesche Werte

Alles in der Lambda-Berechnung ist letztendlich eine Funktion. Diese Sichtweise unterscheidet sich deutlich von der Betrachtung der Booleschen Logik als winzige Objekte - oder , hohe oder niedrige Spannung. Um beide Sichtweisen miteinander in Einklang zu bringen, werden wir mit der Analogie der Logikgatter arbeiten.

In unserer Kodierung stellen wir uns jeden booleschen Wert als ein "Tor" mit zwei Drähten vor. Der Ausgang dieses Gatters kommt von einem der Drähte; welcher es ist, hängt von dem booleschen Wert ab. Beachten Sie, dass wir die Wahl für true und false auch umkehren können; wir müssen nur konsequent sein.

Diese Funktionen können mit den Blöcken des Lambda-Kalküls definiert werden:

const true_  = x => y => x
const false_ = x => y => y

Die Bedingung, die wir normalerweise als if (cond) a else b darstellen, muss auch als Funktion dargestellt werden. Alles, was wir zu diesem Zeitpunkt wissen, ist die Form, die sie haben sollte:

const if_ = cond => a => b => ???

Hier kommt der Zaubertrick! Wir wissen, dass einer unserer booleschen Werte oder sein wird. Das bedeutet, dass cond eine Funktion ist, die zwei Argumente akzeptiert; genau die Argumente, die wir haben! Die Definition von if_ kann dann verfeinert werden zu:

const if_ = cond => a => b => cond(a)(b)

Funktioniert das? Lassen Sie uns versuchen, mit beiden Varianten von cond zu rechnen:

// cond == true_
if_(true_)(a)(b) = true_(a)(b) = (x => y => x)(a)(b) == a
// cond == false_
if_(false_)(a)(b) = false_(a)(b) = (x => y => y)(a)(b) == b

Erfolgreich! Wir waren in der Lage, die booleschen Werte und ihre wichtigste Operation - die bedingte Auswahl - nur mit Funktionen zu definieren.

Übung für den Leser

Könnten Sie die Funktion not für Boolesche Werte schreiben?

Die Lösung: Wenn wir diese Funktion mit normalem JavaScript schreiben würden, bekämen wir etwas in der Art des folgenden Codeblocks.

const not = (a) => if(a) false else true

Ersetzen wir einfach jede der JavaScript-Komponenten durch die der Lambda-Kalkulation.

// using our definitions for if_, true_, and false_
const not = (a) => if_(a)(false_)(true_)
// expanding the definitions
const not = (a) => a(false_)(true_)
const not = (a) => a(x => y => y)(x => y => x)

Lambda-Zahlen

Das ist ein cooler Name, aber der reguläre Name für die Darstellung von Zahlen im Lambda-Kalkül ist Church-Zahlen, benannt nach seinem Schöpfer Alonzo Church. Wie bei den Booleschen Zahlen werden wir eine Funktion mit zwei Argumenten verwenden, um jede Zahl darzustellen. Der Trick ist, etwas zu finden, das wir irgendwie iterieren können.

In unserem Fall wird diese Iteration durch die wiederholte Anwendung derselben Funktion durchgeführt. Lassen Sie mich Ihnen zeigen, wie die Zahlen 1 bis 3 auf diese Weise dargestellt werden:

const one   = f => x => f(x)
const two   = f => x => f(f(x))
const three = f => x => f(f(f(x)))

Sie können hier sicherlich das Muster erkennen: Wir haben so viele verschachtelte fwie die Zahl, die wir darstellen wollen. Halten Sie hier einen Moment inne und überlegen Sie, wie die Zahl 0 in dieser Kodierung aussehen würde.

Lösung: Die Kirchenziffer für 0 darf ihr Argument f nicht anwenden. Mit anderen Worten, es sollte die x unverändert zurückgeben.

const zero = f => x => x

Eine einfache Operation, die wir definieren können, ist die Addition einer konstanten Zahl zu einer Church-Zahl. Lassen Sie uns zum Beispiel die Funktion erstellen, die die Operation x => x + 1 darstellt. Die Idee ist, dass die resultierende Church-Zahl ihr f Argument noch einmal anwenden soll.

const addOne = n => (f => x => f(n(f)(x)))
//                   ---------------------

Um diesen Code zu verstehen, müssen wir ihn in seine Einzelteile zerlegen. addOne ist eine Funktion, die eine Church-Zahl - die n - akzeptiert und eine andere Zahl zurückgibt - daher die f => x => im unterstrichenen Abschnitt. Wie gesagt, wir müssen f noch einmal anwenden, aber wir müssen daran denken, f und x an die ursprüngliche Zahl n weiterzugeben!

Falls Sie noch nicht ganz überzeugt sind, können wir ein Beispiel ausarbeiten:

addOne(two) = f => x => f(two(f)(x))
            = f => x => f(f(f(x)))
            = three

Genauso wie Boolesche Zahlen direkt eine bedingte Auswahl kodieren, kodieren Church-Zahlen direkt eine Wiederholung. Sie können eine Boolesche Zahl als Funktion verwenden, um zwischen zwei Alternativen zu wählen, und Sie können eine Zahl als Funktion verwenden, um eine Operation zu wiederholen. Diese Erkenntnis ermöglicht es uns, komplexere Operationen mit Zahlen zu definieren, z.B. Addition.

Denken Sie daran, wie Sie als Kind addiert haben (wenn Sie wie ich sind, tun Sie es vielleicht immer noch!). Sie beginnen mit einer Anzahl von Fingern nach oben und fügen dann einen weiteren Finger so oft hinzu, wie es die zweite Zahl vorgibt. Konkreter ausgedrückt: Um 2 + 3 auszuführen, beginnen Sie mit 2 Fingern nach oben und fügen einen Finger dreimal hinzu. Dieser Algorithmus ist genau das, was wir tun werden: Sie wiederholen die Operation so oft, wie ein Argument, beginnend mit dem anderen. Der coole Trick ist, dass "eine Operation x mal wiederholen" genau dasselbe ist wie "die Operation als erstes Argument auf xanwenden"!

const add = a => b => a(addOne)(b)

Noch einmal: Funktioniert das? Versuchen wir es mit unserem 2 + 3 Beispiel:

add(two)(three) = two(addOne)(three)
                = addOne(addOne(three))
                = addOne(addOne(f => x => f(f(f(x)))))
                = f => x => f(f(f(f(f(x)))))

Jetzt, wo Sie die Addition gemeistert haben, fühlen Sie sich vielleicht mutig genug, die Multiplikation zu definieren!

Genug für heute

Wir kommen einer realistischeren Programmiersprache immer näher: Zumindest haben wir Konditionale und begrenzte Schleifen. Um jedoch allgemeine Funktionen zu definieren, brauchen wir eine Möglichkeit, Schleifen zu bilden, zu iterieren oder eine ungebundene Anzahl von Wiederholungen durchzuführen. Wenn Sie zum Beispiel versuchen, die Fakultät nur mit den Tricks zu definieren, die Sie jetzt kennen, werden Sie sicher scheitern. Bleiben Sie dran für den nächsten Beitrag, in dem wir feste Punkte einführen werden, um dieses Problem zu lösen!