Create a Lambda Interpreter in PHP

der 21. März 2025

Präsentation zu diesem Artikel

Funktionale Programmierung hat aufgrund ihres deklarativen Charakters, ihrer Unveränderlichkeit und ihrer Kompositierbarkeit an Bedeutung gewonnen. Ein wichtiger Aspekt der funktionalen Programmierung ist die Fähigkeit, Daten durch die Anwendung von Funktionen zu transformieren. Das grundlegende Konzept, die Lambda-Kalkül, die von Alonzo Church (1903–1995) eingeführt wurde, dient als theoretische Grundlage für Berechnungen und entspricht der Turingmaschine. Church, Mathematiker in Princeton, war fasziniert vom Funktionsbegriff in der Computerlogik. Interessanterweise betreute er Alan Turing, der für die Erfindung der Turingmaschine bekannt ist – einem Eckpfeiler der modernen Informatik. Die Church-Turing-These besagt, dass Lambda-Kalkül und Turingmaschinen gleichwertige Berechnungsmodelle sind. Die Lambda-Kalkül dient als konzeptionelles Modell, während die Turingmaschine die maschinenbasierte Implementierung verkörpert.

In diesem Artikel untersuchen wir: – den theoretischen Hintergrund der Lambda-Kalkül. – wie sich Prinzipien der funktionalen Programmierung in PHP anwenden lassen. – wie wir mit vorhandenen Tools einen einfachen Lambda-Interpreter in PHP erstellen können. Integration in die Symfony Expression Language.

Warum Lambda Interpreter?

Ziel ist die Entwicklung einer Sprache, die die Verarbeitung von Datenflüssen nach den Prinzipien der funktionalen Programmierung ermöglicht. Funktionale Programmierung gewinnt aufgrund ihres deklarativen Charakters, ihrer Unveränderlichkeit und ihrer Kompostierbarkeit zunehmend an Bedeutung. Im Gegensatz zur imperativen Programmierung, bei der jeder Schritt einen gemeinsamen Zustand verändert, behandelt funktionale Programmierung Berechnungen als Auswertung mathematischer Funktionen und vermeidet so veränderliche Daten und Nebeneffekte. Eine ihrer faszinierendsten Anwendungen ist die Erstellung von Compilern – die Transformation von Code von einer Darstellung in eine andere mithilfe reiner Funktionen. In diesem Artikel untersuchen wir die Entwicklung eines minimalen Compilers für funktionale Programmierung in PHP, inspiriert von https://github.com/loophp/combinator, https://github.com/igorw/lambda-php und https://github.com/jamiebuilds/the-super-tiny-compiler.

Was ist Lambda-Kalkül?

Bevor wir uns mit dem Compiler befassen, wollen wir noch einmal einige Konzepte der funktionalen Programmierung betrachten. Die Lambda-Kalkül ist ein formales System der mathematischen Logik zur Darstellung von Berechnungen basierend auf Funktionsabstraktion und -anwendung. Sie wurde von Alonzo Church als Grundlage für die funktionale Programmierung entwickelt.

Wichtige Eigenschaften der Lambda-Kalkül: – Funktionen sind First-Class-Bürger: Sie können als Argumente übergeben und als Werte zurückgegeben werden. – Alles ist eine Funktion: Berechnungen bestehen aus Funktionsanwendungen, betrachtet als Funktionen, die Transformationen anwenden. – Reine Funktionen: Funktionen ohne Nebeneffekte. – Unveränderlichkeit: Daten ändern sich nach ihrer Definition nicht. – Kein Zustand, keine Zuweisungen: Es gibt keine Variablen wie in der imperativen Programmierung.

In der Lambda-Kalkül wird eine Funktion wie eine Blackbox behandelt: Sie nimmt Eingaben entgegen und erzeugt Ausgaben. Beispielsweise könnte die Blackbox bei der Eingabe „X“ „X + 1“ erzeugen. Dieses Verhalten wird mit der Lambda-Notation dargestellt: λx.x + 1. Das bedeutet: „Gib für eine Eingabe X X + 1 zurück.“

Einfache Beispiele:

λx.x + 1
(λx.x + 1)(5) = 5 + 1 = 6

Mit mehreren Parametern:

λx.λy.x + y
(λx.λy.x + y)(5, 6) = 5 + 6 = 11

Wichtige Punkte:

– Es gibt Variablen. – Wir haben eine Möglichkeit, Funktionen zu erstellen. – Wir können Funktionen aufeinander anwenden, indem wir Elemente der Sprache selbst übergeben.

Die Lambda-Kalkül führt außerdem das Konzept reiner Funktionen ein, die für dieselben Eingaben immer die gleiche Ausgabe ohne internen Zustand zurückgeben.

Wahr und Falsch in der Lambda-Kalkül

Die Lambda-Kalkül definiert grundlegende logische Strukturen als Funktionen:

Wahr = λx.λy.x
Falsch = λx.λy.y

Übersetzt in PHP:

$true = fn($x) => fn($y) => $x;
$false = fn($x) => fn($y) => $y;

Implementierung von „Not“ im Lambda-Kalkül

Die „Not“-Operation kann wie folgt ausgedrückt werden:

Not = λb.b Falsch Wahr

In PHP:

$not = fn($b) => $b($false)($true);

Anwendung:

echo $not($true)($x, $y); // Sollte $y (false) erzeugen

Die Lambda-Kalkül definiert somit Variablen, eine Möglichkeit zum Erstellen von Funktionen und die Möglichkeit, Funktionen auf andere Funktionen anzuwenden. Alle aus der Lambda-Kalkül-Sprache abgeleiteten Elemente sind in diesem System in sich geschlossen.

Funktionale Programmierung

Um mehr über die Prinzipien der funktionalen Programmierung zu erfahren, empfiehlt sich Haskell, eine Sprache, die auf diesen Prinzipien aufbaut.

Funktionale Programmierung in PHP

Grégoire Hébert hat einen Blogbeitrag über funktionale Programmierung in PHP geschrieben und darin Schlüsselkonzepte wie Currying vorgestellt: ? PHP und funktionale Programmierung

Kombinatorische Logik in PHP verstehen

Kombinatorische Logik macht explizite Variablen überflüssig, indem sie Kombinatoren verwendet, wie zum Beispiel:

• Identität (I): λx.x → fn($x) => $x
• Turmfalke (K): λx.λy.x → fn($x) => fn($y) => $x
• Starling (S): λx.λy.λz.x z (y z) → fn($x) => fn($y) => fn($z) => ($x($z))($y($z))

Ein Kombinator ist eine Funktion höherer Ordnung, die Transformationen ohne explizite Variablen anwendet. Pol DellaierIch habe ein Projekt erstellt, das bemerkenswerte Kombinatoren in PHP auflistet und implementiert: 🔗 loophp/combinator

Beispiel für Kombinatoren in PHP:

use loophp\Combinator\Combinators;
$I = Combinators::I();
$K = Combinators::K();
$S = Combinators::S();

Dies ermöglicht punktfreie Programmierung – das Schreiben von Funktionen ohne explizite Angabe von Argumenten.

Lambda-PHP

Igor Wiedler entwickelte einen Lambda-Interpreter in PHP mithilfe der Dissect-Bibliothek: 🔗 lambda-php

Zu den zusätzlichen Funktionen gehören:

• Krivine Machine: Ein alternativer Interpreter mit de-Bruijn-Indizes. Binäre Lambda-Kalküle: Eine Möglichkeit, Lambda-Kalküle in kompakter Binärform zu kodieren.

Symfony Expression Language

Symfony Expression Language ist eine Engine, mit der Sie Ausdrücke dynamisch in PHP auswerten können. Damien Alexandre beschreibt die Spezialisierung mit benutzerdefinierten Funktionen: 🔗 PHP-Funktion zu Symfony ExpressionLanguage hinzufügen

Beispiel für eine benutzerdefinierte Funktion:

use Symfony\Component\ExpressionLanguage\ExpressionLanguage;
use Symfony\Component\ExpressionLanguage\ExpressionFunction;

$language = new ExpressionLanguage();
$language->addFunction(new ExpressionFunction(
'reverse',
function ($str) {
return sprintf('strrev(%s)', $str);
},
function ($arguments, $str) {
return strrev($str);
}
));

echo $language->evaluate('reverse("JoliCode")'); // Ausgabe: edoCiloJ

Um einen Lambda-Kalkül-Parser in Symfonys ExpressionLanguage zu integrieren, können Sie ihn um benutzerdefinierte Funktionen erweitern, die Lambda-Ausdrücke analysieren und auswerten. So erreichen Sie dies:

• Implementieren Sie einen Lambda-Kalkül-Parser: Entwickeln Sie einen Parser, der Lambda-Kalkül-Ausdrücke interpretieren kann. Sie können einen eigenen Parser erstellen oder vorhandene Bibliotheken nutzen.
• Erstellen Sie eine benutzerdefinierte Expression-Funktion: Definieren Sie eine benutzerdefinierte Funktion in Symfonys ExpressionLanguage, die Ihren Lambda-Kalkül-Parser nutzt. Dazu muss eine neue Funktion registriert werden, die Lambda-Ausdrücke analysieren und auswerten kann.

use Symfony\Component\ExpressionLanguage\ExpressionLanguage;
use Symfony\Component\ExpressionLanguage\ExpressionFunction;

// Vorausgesetzt, Sie haben eine LambdaParser-Klasse, die Lambda-Ausdrücke auswerten kann.
$lambdaParser = new LambdaParser();

$expressionLanguage = new ExpressionLanguage();
$expressionLanguage->addFunction(new ExpressionFunction(
'lambda',
function ($expression) {
// Dies ist die Compiler-Darstellung; ggf. anpassen.
return sprintf('$lambdaParser->evaluate(%s)', $expression);
},
function ($arguments, $expression) use ($lambdaParser) {
// Lambda-Ausdruck mit Ihrem Parser auswerten.
return $lambdaParser->evaluate($expression);
}
));

// Anwendungsbeispiel
$result = $expressionLanguage->evaluate('lambda("(\u03bbx.x)(5)")');
echo $result; // Ausgaben: 5

Benutzerdefinierte Funktion in Ausdrücken verwenden

Nachdem die benutzerdefinierte lambda-Funktion registriert ist, können Sie sie nun in Ihren Ausdrücken verwenden:

$expression = 'lambda("(\u03bbx.x + 1)(5)")';
$result = $expressionLanguage->evaluate($expression);
echo $result; // Ausgaben: 6

Mit diesen Schritten können Sie Symfonys ExpressionLanguage erweitern, um Lambda-Kalkül-Ausdrücke zu analysieren und auszuwerten und so Prinzipien der funktionalen Programmierung in Ihre Symfony-Anwendungen zu integrieren.

Was ist die Lambda-Sprache?

Um eine Sprache zum Parsen von Lambda-Kalkülen zu definieren, können Sie Folgendes verwenden: 🔗 Einführung in die Lambda-Kalkül

<Ausdruck> := <Name> | <Funktion> | <Anwendung>
<Funktion> := λ <Name>.<Ausdruck>
<Anwendung> := <Ausdruck><Ausdruck>

Was ist ein Compiler?

Compiler wandeln Quellcode in eine andere Form um, sei es Maschinencode, eine Zwischendarstellung oder eine andere Programmiersprache. Im Kern durchlaufen Compiler folgende Schritte:

• Lexing: Konvertieren von Rohcode in Token.
• Parsing: Erstellen eines abstrakten Syntaxbaums (AST).
• Transformation: Modifizieren des AST zur Optimierung oder Änderung seiner Struktur.
• Codegenerierung: Erstellen der endgültigen Ausgabe.

In diesem Artikel implementieren wir einen funktionalen Compiler, der Lambda-Ausdrücke verarbeitet und in ausführbare PHP-Closures kompiliert.

Implementierung eines minimalen funktionalen Compilers

Um einen minimalistischen Compiler zu erstellen, können wir uns vom Super Tiny Compiler inspirieren lassen: 🔗 Der Super Tiny Compiler

Ein Compiler besteht aus drei Hauptkomponenten. Wir implementieren einen Lambda-Interpreter in PHP, indem wir Folgendes erstellen:

1. Tokenizer: Konvertiert Ausdrücke in Token.
2. Parser: Erstellt einen AST (Abstract Syntax Tree).
3. Evaluator: Interpretiert den AST und erzeugt die Ausgabe.

Lexing (Tokenisierung)

Der Lexer zerlegt die Eingabe in Token. Beispiel: Der Ausdruck λx.x tokenisieren wir wie folgt:

$tokens = [
['type' => 'lambda', 'value'' => 'λ'],
['type' => 'identifier', 'value' => 'x'],
['type' => 'dot', 'value' => '.'],
['type' => 'identifier', 'value' => 'x']
];

Parsen in einen abstrakten Syntaxbaum (AST)

Der Parser konvertiert Token in einen AST:

$ast = [
'λ', 'x', ['identifier', 'x']
];

Mittels Rekursion evaluieren wir den AST in ausführbaren Code.

Auswertung mit dem Y-Kombinator

Mit dem Y-Kombinator können wir Rekursion implementieren:

$handle = static function (string $expression, array $params) {
    $job = new LambdaJob($expression);
    $result = array_reduce($params, static fn ($carry, $param) => empty($carry) ? $job($param) : $carry($param));
    $encodedParams = array_map(static fn ($param) => $param instanceof Closure ? 'Closure' : (is_object($param) ? get_class($param) : $param), $params);
    echo 'Evaluating ' . $expression . ' with params ' . json_encode($encodedParams) . ' : ' . $result . "\n";
};

// | Y         | Y-Fixed point |                   |         | `λa.(λb(a(bb))(λb(a(bb))))` | `a => (b => b(b))(b => a(c => b(b)(c)))` |                                                      | 1           |
$handle('λf.(λx.f (λy.(x x) y)) (λx.f (λy.(x x) y))', [
    static function ($factorial) {
        return static function (YFlowData $data) use ($factorial): YFlowData {
            return new YFlowData(
                $data->id,
                $data->number,
                ($data->number <= 1) ? 1 : $data->number * $factorial(new YFlowData($data->id, $data->number - 1, $data->result - 1))->result
            );
        };
    },
    new YFlowData(1, 6),
]);
// output Evaluating λf.(λx.f (λy.(x x) y)) (λx.f (λy.(x x) y)) with params ["Closure","Flow\\Examples\\Model\\YFlowData"] : 720

Praktische Anwendungsfälle

Dieser funktionale Compiler ermöglicht:

• Interpretation von Lambda-Kalkül-Ausdrücken in PHP.
• Erstellung von DSLs (Domain-Specific Languages) mit kombinatorischer Logik.
• Erstellung erweiterbarer und wiederverwendbarer Funktionskomponenten.

Wir können dies erweitern, um komplexere Ausdrücke zu kompilieren, Berechnungen zu optimieren oder PHP-Code dynamisch zu generieren.

Programmieren mit Nichts

Tom Stuart schrieb darüber, wie man komplexe Transformationen mit minimalen Regeln durchführt: 🔗 Programmieren mit Nichts

Fazit

Durch die Nutzung funktionaler Programmierung und kombinatorischer Logik haben wir einen einfachen funktionalen Compiler in PHP erstellt. Dies zeigt, wie Lambda-Kalkül, der Y-Kombinator und reine Funktionen zusammenarbeiten, um eine prägnante, ausdrucksstarke und mathematisch elegante Methode zum Schreiben von Code zu ermöglichen. Das Konzept lässt sich in einer realen PHP-Implementierung anwenden.

Weitere Untersuchungen könnten die Optimierung des AST, die Unterstützung weiterer Kombinatoren oder die Integration mit Flow zur Verbesserung der Automatisierung und Orchestrierung umfassen.

Resources

• Wikipedia Lambda calculus : https://en.wikipedia.org/wiki/Lambda_calculus
• Introduction to the Lambda Calculus : https://personal.utdallas.edu/~gupta/courses/apl/lambda.pdf
• Lambda syntax : https://opendsa.cs.vt.edu/ODSA/Books/PL/html/Syntax.html
• Parsing Lambda Calculus in Scala : https://web.archive.org/web/20130802034031/http://zeroturnaround.com/rebellabs/parsing-lambda-calculus-in-scala
• 7 lines of code, 3 minutes: Implement a programming language from scratch : https://matt.might.net/articles/implementing-a-programming-language
• The smallest compiler ever : https://github.com/jamiebuilds/the-super-tiny-compiler
• Expression Langage from symfony : https://github.com/symfony/symfony/tree/7.3/src/Symfony/Component/ExpressionLanguage
• Lambda calculus interpreter in PHP https://github.com/igorw/lambda-php
• A curated list of combinators in PHP https://github.com/loophp/combinator
• Flow that use Asynchrone and functional programming https://github.com/darkwood-com/flow
• Programming with Nothing : https://tomstu.art/programming-with-nothing
• Adding PHP Function to Symfony ExpressionLanguage, The Simple Way ? : https://jolicode.com/blog/adding-php-function-to-symfony-expressionlanguage-the-simple-way
• PHP et programmation fonctionnelle : https://knot.gheb.dev/blog/php-programmation-fonctionnelle

• Send ein Kommentar