Create a Lambda Interpreter in PHP

on March 21, 2025

Presentation associated to this article

Functional programming has gained traction due to its declarative nature, immutability, and composability. A powerful aspect of functional programming is its ability to transform data through the application of functions. The foundational concept behind it, Lambda Calculus, introduced by Alonzo Church (1903 - 1995), serves as the theoretical basis for computation, equivalent to the Turing Machine. Church, a mathematician at Princeton, was fascinated by understanding the notion of functions in computational logic. Interestingly, he supervised Alan Turing, known for inventing the Turing machine—a cornerstone of modern computing. The Church-Turing thesis states that lambda calculus and Turing machines are equivalent models of computation. Lambda calculus serves as the conceptual model, while the Turing machine embodies its machine-level implementation.

In this article, we will explore:

• The theoretical background of Lambda Calculus.
• How functional programming principles can be applied in PHP.
• How we can build a simple lambda interpreter in PHP using existing tools.
• How to integrate it with Symfony Expression Language.

Why Lambda Interpreter?

The goal is to define a language that allows processing data-flows with functional programming principles. Functional programming is gaining traction due to its declarative nature, immutability, and composability. Instead of imperative programming, where each step modifies a shared state, functional programming treats computation as the evaluation of mathematical functions, avoiding mutable data and side effects. One of its most fascinating applications is in the creation of compilers—transforming code from one representation to another using pure functions. In this article, we will explore building a minimal functional programming compiler in PHP, inspired by https://github.com/loophp/combinator, https://github.com/igorw/lambda-php, and https://github.com/jamiebuilds/the-super-tiny-compiler.

What is Lambda Calculus?

Before diving into the compiler, let's revisit some functional programming concepts. Lambda Calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application. It was invented by Alonzo Church as a foundation for functional programming.

Key properties of Lambda Calculus:

• Functions are first-class citizens: They can be passed as arguments and returned as values.
• Everything is a function: Computation consists of function application viewed as functions that apply transformations.
• Pure functions: Functions without side effects.
• Immutability: Data does not change once defined.
• No state, no assignments: There are no variables as in imperative programming.

In lambda calculus, a function is treated like a black box: it takes inputs and produces outputs. For instance, given the input X, the black box might produce X + 1. This behavior is represented using lambda notation: λx.x + 1, which means "for an input X, return X + 1.

Basic examples:

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

With multiple parameters:

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

Key points:

• There are variables.
• We have a way to build functions.
• We can apply functions to each other by passing elements of the language itself.

Lambda calculus also introduces the concept of pure functions, which always return the same output for the same inputs without any internal state.

True and False in Lambda Calculus

Lambda calculus defines basic logical structures as functions:

True = λx.λy.x
False = λx.λy.y

Translated to PHP:

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

Implementing Not in Lambda Calculus

The not operation can be expressed as:

Not = λb.b False True

In PHP:

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

If we apply it:

echo $not($true)($x, $y); // Should produce $y (false)

Lambda calculus thus defines variables, a way to build functions, and the capacity to apply functions to other functions. Everything derived from the lambda calculus language is self-contained within this system.

Functional Programming

To learn more about functional programming principles, it is recommended to explore Haskell, a language built on these principles.

Functional Programming in PHP

Grégoire Hébert wrote a blog about functional programming in PHP, introducing key concepts like currying: 🔗 PHP et programmation fonctionnelle

Understanding Combinatory Logic in PHP

Combinatory logic eliminates the need for explicit variables by using combinators, such as:

• Identity (I): λx.x → fn($x) => $x
• Kestrel (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))

A combinator is a higher-order function that applies transformations without needing explicit variables. Pol Dellaiera created a project that lists and implements remarkable combinators in PHP: 🔗 loophp/combinator

Example of combinators in PHP:

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

This allows for point-free programming—writing functions without explicitly mentioning arguments.

Lambda-PHP

Igor Wiedler developed a Lambda interpreter in PHP, using the Dissect library: 🔗 lambda-php

Bonus features include:

• Krivine Machine: An alternate interpreter using de Bruijn indices.
• Binary Lambda Calculus: A way to encode lambda calculus in a compact binary form.

Symfony Expression Language

Symfony Expression Language is an engine that allows you to evaluate expressions dynamically in PHP. Damien Alexandre wrote about specializing it with custom functions: 🔗 Adding PHP Function to Symfony ExpressionLanguage

Example of a custom function:

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

To integrate a lambda calculus parser into Symfony's ExpressionLanguage, you can extend it by adding custom functions that parse and evaluate lambda expressions. Here's how you can achieve this:

• Implement a Lambda Calculus Parser: Develop a parser that can interpret lambda calculus expressions. You can create your own or utilize existing libraries.
• Create a Custom Expression Function: Define a custom function within Symfony's ExpressionLanguage that leverages your lambda calculus parser. This involves registering a new function that can parse and evaluate lambda expressions.

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

// Assuming you have a LambdaParser class that can evaluate lambda expressions
$lambdaParser = new LambdaParser();

$expressionLanguage = new ExpressionLanguage();
$expressionLanguage->addFunction(new ExpressionFunction(
    'lambda',
    function ($expression) {
        // This is the compiler representation; adjust as needed
        return sprintf('$lambdaParser->evaluate(%s)', $expression);
    },
    function ($arguments, $expression) use ($lambdaParser) {
        // Evaluate the lambda expression using your parser
        return $lambdaParser->evaluate($expression);
    }
));

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

Utilize the Custom Function in Expressions

With the custom lambda function registered, you can now use it within your expressions:

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

By following these steps, you can extend Symfony's ExpressionLanguage to parse and evaluate lambda calculus expressions, integrating functional programming principles into your Symfony applications.

What is the lambda language

To define a language for parsing Lambda Calculus, you can refer to: 🔗 Introduction to Lambda Calculus

<expression> := <name> | <function> | <application>
<function> := λ <name>.<expression>
<application> := <expression><expression>

What is a compiler ?

Compilers transform source code into another form, whether it's machine code, an intermediate representation, or another programming language. At their core, compilers follow these steps:

• Lexing: Converting raw code into tokens.
• Parsing: Constructing an abstract syntax tree (AST).
• Transformation: Modifying the AST to optimize or change its structure.
• Code Generation: Producing the final output.

In this article, we'll implement a functional compiler that takes lambda calculus expressions and compiles them into executable PHP closures.

Implementing a Minimal Functional Compiler

To create a minimalist compiler, we can take inspiration from The Super Tiny Compiler: ? The Super Tiny Compiler

A compiler consists of three main components. We implement a Lambda interpreter in PHP by building:

1. Tokenizer: Converts expressions into tokens.
2. Parser: Builds an AST (Abstract Syntax Tree).
3. Evaluator: Interprets the AST and produces output.

Lexing (Tokenization)

The lexer breaks input into tokens. For example, given the expression λx.x, we tokenize it into:

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

Parsing into an Abstract Syntax Tree (AST)

The parser converts tokens into an AST:

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

Using recursion, we evaluate the AST into executable code.

Evaluation using the Y Combinator

Using the Y combinator, we can implement recursion:

$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

Practical Use Cases

This functional compiler allows for:

• Interpreting Lambda Calculus expressions in PHP.
• Creating DSLs (Domain-Specific Languages) with combinatory logic.
• Building extensible and reusable functional components.

We can extend this to compile more complex expressions, optimize computations, or generate PHP code dynamically.

Programming with Nothing

Tom Stuart wrote about how to make complex transformations with minimal rules: 🔗 Programming with Nothing

Conclusion

By leveraging functional programming and combinatory logic, we have built a simple functional compiler in PHP. This showcases how lambda calculus, the Y combinator, and pure functions work together to create a concise, expressive, and mathematically elegant way of writing code. Concept can be applied in a real-world PHP implementation.

Further exploration could include optimizing the AST, supporting more combinators, or integrating with Flow to enhance automation and 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

• Post a comment