Lambda-Kalkül durch JavaScript, Teil 5

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

Willkommen zum letzten Teil unserer Tour zum Lambda-Kalkül in JavaScript. Wir haben gesehen, wie Zahlen, Rekursion, Datentypen, alles innerhalb der drei restriktiven Regeln, die wir in Teil 1 beschrieben haben, kodiert werden kann. In diesem Beitrag werden wir einen Schritt zurücktreten und unseren eigenen Evaluator für Lambda-Terme schreiben.

Lambda-Terme als Werte

Warten Sie einen Moment! Hatten wir nicht bereits Lambda-Terme als JavaScript-Funktionen dargestellt? Genau das haben wir in den vorangegangenen Teilen der Serie getan: Wir haben die Tatsache genutzt, dass JavaScript eine Obermenge der Lambda-Kalkulation ist, um einen Interpreter zu verwenden, der unsere Lambda-Terme ausführt. Am Ende dieses Beitrags werden Sie also einen Interpreter für Lambda-Kalküle haben, der auf einem Interpreter für JavaScript läuft! Sie wissen schon, es ist eine Schildkröte auf dem Weg nach unten.

Der erste Schritt besteht darin, keine JavaScript-Ausdrücke mehr zu verwenden, um unsere Lambda-Terme darzustellen. Stattdessen werden wir eine Datenstruktur einführen, die unsere Lambda-Terme explizit darstellt. Der technische Name dafür ist Verdinglichung: Wir verwandeln etwas, das nur implizit existiert und das wir nicht überprüfen können, in etwas, das wir in unserer Sprache manipulieren können. Die Anwendung der Identitätsfunktion auf die Zahl 3 sieht zum Beispiel wie folgt aus:

{
  kind: 'app',
  fun: identity,
  arg: { kind: 'number', n: 3 }
}

Konkreter gesagt, hat jeder Lambda-Term ein kind Feld, das angibt, ob Sie vor einer Variablen ('var'), einer Anwendung ('app') oder einer Funktion ('fun') stehen. Der Einfachheit halber werden wir auch Zahlen einführen, auch wenn wir wissen, dass Church-Zahlen ihre Rolle übernehmen können. Um es einfacher zu machen, diese Ausdrücke zu schreiben, werden wir Konstruktorfunktionen einführen.

const vr = index => ({ kind: 'var', index })
const ap = (fun, arg) => ({ kind: 'app', fun, arg })
const nb = n => ({ kind: 'number', n })

Wenn Sie sich fragen, warum Klammern und geschweifte Klammern, dann liegt das daran, dass JavaScript sonst die geschweiften Klammern als Beginn eines Codeblocks und kind als Bezeichnung interpretiert, anstatt ein Objektliteral und einen Schlüssel.

Die Anwendung der Identität auf die Zahl 3 kann dann wie folgt ausgedrückt werden:

ap(identity, nb(3))

Frage an den Leser: Könnten Sie eine Funktion schreiben, die nicht nur ein, sondern mehrere Argumente auf eine Funktion anwendet? Auf diese Weise müssten wir nicht ap(ap(f), x), y) schreiben, sondern aps(f, x, y).

Lösung: Wir können die Argumentliste iterativ durchgehen und bei jedem Schritt eine größere Anwendung erstellen.

const aps = (fun, ...args) => args.reduce((acc, arg) => ap(acc, arg), fun)

Die Idee, eine Host-Programmiersprache - in diesem Fall JavaScript - zu verwenden, um eine andere Programmiersprache - in diesem Fall Lambda-Kalkül-Terme - zu manipulieren, ist der Ausgangspunkt der Metaprogrammierung. Das bekannteste Beispiel für Metaprogrammierung sind die Makros aus der Lisp-Sprachfamilie. Elixir macht ebenfalls regen Gebrauch von Makros, und Template Haskell ist seine Umsetzung im Kontext von Haskell.

Treffen Sie Meneer de Bruijn

Ich habe bewusst "vergessen", ein Beispiel dafür zu beschreiben, wie eine Funktion aussieht (identity oben wurde nicht definiert); der Grund dafür ist, dass es alles andere als trivial ist, dies auf eine schöne Weise zu tun. Die naheliegendste Lösung, die dem entspricht, was wir in JavaScript tun würden, ist die Einführung eines Argumentnamens und eines Körpers.

const fn = (arg, body) => ({ kind: 'fun', arg, body })
// this is the identity function
const identity = fn('x', vr('x'))

Leider ist dies eine sehr problematische Wahl. Mit den richtigen Namen für die Argumente kommt die Beschattung. Stellen Sie sich vor, wir würden den folgenden Begriff schreiben:

const f = fn('x', fn('x', vr('x')))

Worauf bezieht sich die innere 'x'? Die meisten Sprachen haben Regeln, um mit solchen Fällen umzugehen. Im Fall des Lambda-Kalküls sprechen wir von α-Umwandlung , die angibt, dass der Begriff äquivalent zu fn('x', fn('y', vr('y'))), aber nicht zu fn('x', fn('y', vr('x'))) ist.

Anstatt ein schweres Problem zu lösen, können wir eine andere Darstellung wählen, die dieses Problem trivial macht. In den 1970er Jahren entwickelte der niederländische Mathematiker Nicolaas Govert de Bruijn (die Aussprache des Nachnamens kommt dem englischen Wort "brown" nahe, was auch seine wörtliche Bedeutung ist) das, was wir heute de Bruijn-Indizes nennen. Die Idee ist, dass Variablen statt Eigennamen Indizes angeben, die beschreiben, wie viele "Ebenen" wir durchlaufen müssen, um zu der gewünschten Ebene zu gelangen. Hier sind zwei Beispiele, die diese Idee verdeutlichen:

fn(fn(0))  // corresponds to a => b => b
fn(fn(1))  // corresponds to a => b => a

Beginnend mit 0 als innerstem umschließenden fn, rückt jeder weitere Index um einen fn nach außen. Beachten Sie, dass wir aufgrund dieser Kodierung den Argumenten keine Namen mehr geben. Einige Leute haben andere Darstellungen erfunden, die die guten Seiten der de Bruijn-Indizes beibehalten, aber für die menschliche Lesbarkeit einfacher sind.

Schließlich die Bewertung

Wir sind nun bereit, die Funktion zu schreiben, die einen dieser Lambda-Ausdrücke nimmt und seine ausgewertete Form zurückgibt. Das Skelett ist eine große switch über die kind Eigenschaft, die uns sagt, wie wir jeden Fall behandeln sollen. Im Falle von Zahlen beispielsweise geben wir sie einfach unverändert zurück:

  switch (expression.kind) {
    case 'number':
      return expression
    case 'var':
      ...
    case 'app':
      ...
    case 'fun':
      ...
  }

Der subtile Teil hier ist das Zusammenspiel zwischen Anwendung und Funktionen. Wir werden die gängigste Auswertungsstrategie verwenden, bei der wir, um das Ergebnis eines Funktionsaufrufs zu erhalten, zunächst die Funktion selbst und ihr Argument rekursiv auswerten. Und wenn es sich um eine Funktion der Art handelt, haben wir noch zusätzliche Arbeit zu erledigen. Das entspricht einem JavaScript-Code der Form '(x => body) argument`.

    case 'app':
      const f = // evaluate expression.fun
      const a = // evaluate expression.arg
      switch (f.kind) {
        case 'fun':
          ...  // the important case
        default:
          return { kind: 'app', function: f, argument: a }
      }

Woher kennt der Körper der Funktion den Wert seiner Argumente? Eine Möglichkeit besteht darin, den Wert direkt im Code des Funktionskörpers zu ersetzen, aber auch dies ist ein komplizierter und fehleranfälliger Code. Stattdessen werden wir den Wert dieser Argumente in einer Liste aufbewahren, die normalerweise als Kontext bezeichnet wird. Wenn wir mit der Auswertung des Körpers beginnen, müssen wir daran denken, den Wert des Arguments in dieser Liste hinzuzufügen - das sind die mit ! markierten Zeilen.

const evaluate = (context, expression) => {
  switch (expression.kind) {
    ... // other cases
    case 'app':
      const f = evaluate(context, expression.fun)  // recur
      const a = evaluate(context, expression.arg)  // recur
      switch (f.kind) {
        case 'fun':
          const newContext = [a, ...context]  // !
          return evaluate(newContext, f.body) // !
        default:
          return { kind: 'app', function: f, argument: a }
      }
    case 'fun':
      return expression
  }
}

Die Tatsache, dass a am Anfang des Kontexts eingefügt wurde, ist keine willkürliche Wahl. Auf diese Weise wird die Liste vom innersten zum äußersten Argument geordnet. Folglich können wir den de Bruijn-Index in einer Variablen buchstäblich als Index für diese Liste verwenden!

    case 'var':
      return context[expression.index]

Die übrigen Fälle bleiben unverändert: Wenn Sie eine Funktion haben, schauen wir nicht in den Body. Wenn Ihrer Anwendung keine Funktion vorangestellt ist, brechen wir die Auswertung ebenfalls ab. Dies entspricht dem Begriff der Kopf-Normalform , den man normalerweise im Zusammenhang mit Faulheit in Haskell hört.

Funktioniert das?

Lassen Sie uns eine Node.js REPL öffnen und unsere Datei mit der Definition der Konstruktoren und der Funktion evaluate laden.

> .load lambdaEval.js
// lots of things
undefined

Wir definieren die Funktion identity unter Verwendung unserer Darstellung und bitten dann um die Auswertung ihrer Anwendung auf die Zahl 3. Da wir auf der obersten Ebene beginnen, verwendet die Auswertung einen leeren Kontext.

> const identity = fn(vr(0))
undefined
> evaluate([], ap(identity, nb(3)))
{ kind: 'number', n: 3 }

Sieg! Wir können dem Node.js-Interpreter auch einen Strich durch die Rechnung machen, indem wir ihn bitten, den unendlichen Term Ω auszuwerten, den wir in Teil 3 eingeführt haben.

> const omega = fn(ap(vr(0), vr(0)))
> const Omega = ap(omega, omega)
> evaluate([], Omega)
Uncaught RangeError: Maximum call stack size exceeded

Fazit

Sie sind jetzt der stolze Autor eines Interpreters! Compiler und Interpreter sehen normalerweise wie Fabelwesen aus, aber sie sind einfach Programme, die eine Darstellung eines Programms manipulieren. Und diese Darstellung sieht nicht anders aus als alle anderen Daten, die Sie bei Ihrer täglichen Programmierarbeit manipulieren.

Ich hoffe, dass diese Serie etwas Licht ins Dunkel gebracht hat, was Lambda-Kalkül ist. Oft verbirgt sich hinter der mathematischen Darstellung die Tatsache, dass die meisten Programmierer heutzutage die Lambda-Berechnung bereits kennen, aber nicht wissen, dass sie sie kennen.