Create a Lambda Interpreter in PHP

le 21 mars 2025

Présentation associée à cet article

La programmation fonctionnelle a gagné en popularité grâce à sa nature déclarative, son immuabilité et sa composabilité. Un de ses atouts majeurs réside dans sa capacité à transformer des données par l'application de fonctions. Son concept fondateur, le lambda-calcul, introduit par Alonzo Church (1903-1995), sert de base théorique au calcul, équivalent à la machine de Turing. Church, mathématicien à Princeton, était fasciné par la compréhension de la notion de fonctions en logique computationnelle. Il est intéressant de noter qu'il a supervisé Alan Turing, connu pour avoir inventé la machine de Turing, pierre angulaire de l'informatique moderne. La thèse de Church-Turing affirme que le lambda-calcul et les machines de Turing sont des modèles de calcul équivalents. Le lambda-calcul sert de modèle conceptuel, tandis que la machine de Turing incarne son implémentation au niveau machine.

Dans cet article, nous explorerons :

  • Le contexte théorique du lambda-calcul ;
  • Comment les principes de la programmation fonctionnelle peuvent être appliqués en PHP ;
  • Comment créer un interpréteur lambda simple en PHP à l'aide d'outils existants.
  • Comment l'intégrer au langage d'expression Symfony.

Pourquoi un interpréteur Lambda ?

L'objectif est de définir un langage permettant de traiter des flux de données selon les principes de la programmation fonctionnelle. La programmation fonctionnelle gagne en popularité grâce à sa nature déclarative, son immuabilité et sa composabilité. Contrairement à la programmation impérative, où chaque étape modifie un état partagé, la programmation fonctionnelle traite le calcul comme l'évaluation de fonctions mathématiques, évitant ainsi les données mutables et les effets de bord. L'une de ses applications les plus fascinantes réside dans la création de compilateurs, qui transforment le code d'une représentation à une autre à l'aide de fonctions pures. Dans cet article, nous explorerons la création d'un compilateur de programmation fonctionnelle minimal en PHP, inspiré de https://github.com/loophp/combinator, https://github.com/igorw/lambda-php et https://github.com/jamiebuilds/the-super-tiny-compiler.

Qu'est-ce que le Lambda Calcul ?

Avant de nous plonger dans le compilateur, revenons sur quelques concepts de la programmation fonctionnelle. Le lambda-calcul est un système formel de logique mathématique permettant d'exprimer des calculs basés sur l'abstraction et l'application de fonctions. Il a été inventé par Alonzo Church comme fondement de la programmation fonctionnelle.

Caractéristiques clés du lambda-calcul :

  • Les fonctions sont des éléments de premier ordre : elles peuvent être passées en arguments et renvoyées sous forme de valeurs.
  • Tout est fonction : le calcul consiste en l'application de fonctions, vues comme des fonctions appliquant des transformations.
  • Fonctions pures : fonctions sans effets de bord.
  • Immutabilité : les données ne changent pas une fois définies.
  • Pas d'état, pas d'affectation : il n'y a pas de variables comme en programmation impérative.

En lambda-calcul, une fonction est traitée comme une boîte noire : elle prend des entrées et produit des sorties. Par exemple, étant donné l'entrée « X », la boîte noire pourrait produire « X + 1 ». Ce comportement est représenté par la notation lambda : λx.x + 1, ce qui signifie que « pour une entrée X, renvoie X + 1 ».

Exemples simples :

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

Avec plusieurs paramètres :

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

Points clés :

  • Il existe des variables.
  • Nous pouvons construire des fonctions.
  • Nous pouvons appliquer des fonctions entre elles en passant des éléments du langage lui-même.

Le lambda-calcul introduit également le concept de fonctions pures, qui renvoient toujours la même sortie pour les mêmes entrées, sans état interne.

Vrai et faux en lambda-calcul

Le lambda-calcul définit les structures logiques de base comme suit : Fonctions :

Vrai = λx.λy.x
Faux = λx.λy.y

Traduit en PHP :

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

Implémentation de Not en Lambda Calcul

L’opération not peut être exprimée ainsi :

Not = λb.b False True

En PHP :

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

Si on l’applique :

echo $not($true)($x, $y); // Devrait produire $y (false)

Le lambda-calcul définit ainsi des variables, un moyen de construire des fonctions et la capacité d'appliquer des fonctions à d'autres fonctions. Tout ce qui dérive du langage du lambda-calcul est intégré à ce système.

Programmation fonctionnelle

Pour en savoir plus sur les principes de la programmation fonctionnelle, il est recommandé d'explorer Haskell, un langage basé sur ces principes.

Programmation fonctionnelle en PHP

Grégoire Hébert a écrit un article de blog sur la programmation fonctionnelle en PHP, présentant des concepts clés comme le curry : 🔗 PHP et programmation fonctionnelle

Comprendre la logique combinatoire en PHP

La logique combinatoire élimine le besoin de variables explicites grâce à l'utilisation de combinateurs, tels que :

  • Identité (I) : λx.x → fn($x) => $x
  • Crécerelle (K) : λx.λy.x → fn($x) => fn($y) => $x
  • Étourneau (S) : λx.λy.λz.x z (y z) → fn($x) => fn($y) => fn($z) => ($x($z))($y($z))

Un combinateur est une fonction d'ordre supérieur qui applique des transformations sans nécessiter de variables explicites. Pol Dellaiera créé un projet qui répertorie et implémente des combinateurs remarquables en PHP : 🔗 loophp/combinator

Exemple de combinateurs en PHP :

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

Cela permet une programmation sans point, c'est-à-dire l'écriture de fonctions sans mentionner explicitement d'arguments.

Lambda-PHP

Igor Wiedler a développé un interpréteur Lambda en PHP, utilisant la bibliothèque Dissect : 🔗 lambda-php

Fonctionnalités bonus :

  • Krivine Machine : un interpréteur alternatif utilisant les indices de Bruijn. - Lambda-calcul binaire : un moyen d'encoder le lambda-calcul sous une forme binaire compacte.

Langage d'expression Symfony

Le langage d'expression Symfony est un moteur qui permet d'évaluer dynamiquement des expressions en PHP. Damien Alexandre a écrit un article sur sa spécialisation avec des fonctions personnalisées : 🔗 Ajout d'une fonction PHP à Symfony ExpressionLanguage

Exemple de fonction personnalisée :

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")'); // Sortie : edoCiloJ

Pour intégrer un analyseur de lambda-calcul à l'ExpressionLanguage de Symfony, vous pouvez l'étendre en ajoutant des fonctions personnalisées qui analysent et évaluent les expressions lambda. Voici comment procéder :

  • Implémenter un analyseur de lambda-calcul : Développer un analyseur capable d'interpréter les expressions de lambda-calcul. Vous pouvez créer vos propres bibliothèques ou utiliser des bibliothèques existantes.
  • Créer une fonction d'expression personnalisée : Définir une fonction personnalisée dans l'ExpressionLanguage de Symfony qui exploite votre analyseur de lambda-calcul. Cela implique l'enregistrement d'une nouvelle fonction capable d'analyser et d'évaluer les expressions lambda.
use Symfony\Component\ExpressionLanguage\ExpressionLanguage;
use Symfony\Component\ExpressionLanguage\ExpressionFunction;

// En supposant que vous ayez une classe LambdaParser capable d'évaluer les expressions lambda
$lambdaParser = new LambdaParser();

$expressionLanguage = new ExpressionLanguage(); $expressionLanguage->addFunction(new ExpressionFunction(
'lambda',
function ($expression) {
// Ceci est la représentation du compilateur ; ajustez-la si nécessaire
return sprintf('$lambdaParser->evaluate(%s)', $expression);
},
function ($arguments, $expression) use ($lambdaParser) {
// Évaluez l'expression lambda à l'aide de votre analyseur
return $lambdaParser->evaluate($expression);
}
));

// Exemple d'utilisation
$result = $expressionLanguage->evaluate('lambda("(\u03bbx.x)(5)")');
echo $result; // Sorties : 5

Utiliser la fonction personnalisée dans les expressions

Une fois la fonction personnalisée lambda enregistrée, vous pouvez l'utiliser dans vos expressions :

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

En suivant ces étapes, vous pouvez étendre ExpressionLanguage de Symfony pour analyser et évaluer les expressions de lambda-calcul, intégrant ainsi les principes de la programmation fonctionnelle à vos applications Symfony.

Qu'est-ce que le langage lambda ?

Pour définir un langage d'analyse du lambda-calcul, consultez : 🔗 Introduction au lambda-calcul

<expression> := <name> | <fonction> | <application>
<fonction> := λ <nom>.<expression>
<application> := <expression><expression>

Qu'est-ce qu'un compilateur ?

Les compilateurs transforment le code source en un autre format, qu'il s'agisse de code machine, d'une représentation intermédiaire ou d'un autre langage de programmation. Fondamentalement, les compilateurs suivent les étapes suivantes :

  • Lexique : Conversion du code brut en jetons.
  • Analyse : Construction d'un arbre syntaxique abstrait (AST).
  • Transformation : Modification de l'AST pour optimiser ou modifier sa structure.
  • Génération de code : Production du résultat final.

Dans cet article, nous allons implémenter un compilateur fonctionnel qui prend des expressions de lambda-calcul et les compile en fermetures PHP exécutables.

Implémentation d'un compilateur fonctionnel minimal

Pour créer un compilateur minimaliste, nous pouvons nous inspirer du Super Tiny Compiler : Le compilateur ultra-compilateur

Un compilateur se compose de trois composants principaux. Nous implémentons un interpréteur Lambda en PHP en construisant :

  1. Un tokeniseur : convertit les expressions en tokens.
  2. Un analyseur syntaxique : construit un arbre syntaxique abstrait (AST).
  3. Un évaluateur : interprète l'AST et génère une sortie.

Lexique (Tokenisation)

L'analyseur lexical décompose l'entrée en tokens. Par exemple, pour l'expression « λx.x », nous la tokenisons en :

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

Analyse syntaxique en arbre syntaxique abstrait (AST)

L'analyseur convertit les jetons en un AST :

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

Grâce à la récursivité, nous évaluons l'AST en code exécutable.

Évaluation à l'aide du combinateur Y

Grâce au combinateur Y, nous pouvons implémenter la récursivité :

$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

Cas d'utilisation pratiques

Ce compilateur fonctionnel permet :

  • d'interpréter des expressions de Lambda Calcul en PHP ;
  • de créer des DSL (langages spécifiques à un domaine) avec une logique combinatoire ;
  • de créer des composants fonctionnels extensibles et réutilisables.

Nous pouvons étendre ce compilateur pour compiler des expressions plus complexes, optimiser des calculs ou générer du code PHP dynamiquement.

Programmation sans rien

Tom Stuart a écrit sur la façon de réaliser des transformations complexes avec un minimum de règles : 🔗 Programmation sans rien

Conclusion

En exploitant la programmation fonctionnelle et la logique combinatoire, nous avons créé un compilateur fonctionnel simple en PHP. Il illustre comment le calcul lambda, le combinateur Y et les fonctions pures fonctionnent ensemble pour créer une méthode d'écriture de code concise, expressive et mathématiquement élégante. Ce concept peut être appliqué à une implémentation PHP concrète.

D'autres pistes pourraient inclure l'optimisation de l'AST, la prise en charge de plus de combinateurs ou l'intégration avec Flow pour améliorer l'automatisation et l'orchestration.

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