lambda-calculus.php

<?php

// lambda calculus interpreter
//
// too bad PHP has no tail recursion, meaning it will run out of stack space
// and/or memory rather quickly.
//
// loosely based on Matt Might's:
//
//   7 lines of code, 3 minutes: Implement a programming language from scratch
//
// http://matt.might.net/articles/implementing-a-programming-language/
//
// if you like this, you'll probably also like Tom Stuart's:
//
//   Programming with Nothing
//
// http://codon.com/programming-with-nothing

namespace lambda;

function first(array $list)
{
    return $list[0];
}

function second(array $list)
{
    return $list[1];
}

function evaluate($exp, array $env = [])
{
    // actual PHP numbers and callables
    // needed for hooking into the engine
    // inside of a lambda calculus program you would
    // just use church numerals
    //
    // note: only object callables are supported, which
    // includes closures
    if (is_int($exp) || is_float($exp) || is_bool($exp) || is_object($exp) && is_callable($exp)) {
        return $exp;
    }

    // exp is a symbol, lookup in env
    if (is_string($exp)) {
        return $env[$exp];
    }

    // procedure 'object'
    // encoded as a 4-tuple of [λ, arg, body, env]
    // this is what is passed to apply
    if ('λ' === first($exp)) {
        list($_, $arg, $body) = $exp;
        return ['λ', $arg, $body, $env];
    }

    // function application
    // evaluate sub-expressions, then apply
    $f = evaluate(first($exp), $env);
    $arg = evaluate(second($exp), $env);
    return apply($f, $arg);
}

function apply($f, $x)
{
    // f can be a PHP callable, but this is
    // only used for engine calls
    if (is_callable($f)) {
        return $f($x);
    }

    // evaluate the body of the function
    // by substituting the argument via
    // the environment
    list($_, $arg, $body, $env) = $f;
    return evaluate($body, array_merge($env, [$arg => $x]));
}

function call(/* $f, $args... */)
{
    $args = func_get_args();
    $f = array_shift($args);

    $call = $f;
    foreach ($args as $arg) {
        $call = [$call, $arg];
    }
    return $call;
}

function lazy($exp, $x = 'x')
{
    return ['λ', $x, [$exp, $x]];
}

function to_int($exp)
{
    $inc = function ($n) {
        return $n + 1;
    };

    return [[$exp, $inc], 0];
}

function to_bool($exp)
{
    return [[$exp, true], false];
}

// identity: returns its argument
// λx.x
$identity = ['λ', 'x', 'x'];
$identity_a = ['λ', 'a', 'a'];

// omega: loops forever
// (λf.f f) (λf.f f)
$omega = [['λ', 'f', ['f', 'f']], ['λ', 'f', ['f', 'f']]];

// church numerals, represent numbers as functions
// λf.λx.x
// λf.λx.f x
// λf.λx.f (f x)
$zero = ['λ', 'f', ['λ', 'x', 'x']];
$one  = ['λ', 'f', ['λ', 'x', ['f', 'x']]];
$two  = ['λ', 'f', ['λ', 'x', ['f', ['f', 'x']]]];

// increment a church numeral by one
// λn.λf.λx.f (n f x)
$succ = ['λ', 'n', ['λ', 'f', ['λ', 'x', ['f', [['n', 'f'], 'x']]]]];

// addition
// λm.λn.m SUCC n
$plus = ['λ', 'm', ['λ', 'n', [['m', $succ], 'n']]];

// decrement
// λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
$pred = ['λ', 'n', ['λ', 'f', ['λ', 'x',
            [[['n', ['λ', 'g', ['λ', 'h', ['h', ['g', 'f']]]]],
                ['λ', 'u', 'x']],
                ['λ', 'u', 'u']]]]];

// subtraction
// λm.λn.n PRED m
$sub = ['λ', 'm', ['λ', 'n', [['n', $pred], 'm']]];

// multiplication
// λm.λn.λf.m (n f)
$mult = ['λ', 'm', ['λ', 'n', ['λ', 'f', ['m', ['n', 'f']]]]];

// Y combinator, recursion
// does not work due to call-by-value, it loops forever
// λf.(λx.f (x x)) (λx.f (x x))
$Y = ['λ', 'f', [['λ', 'x', ['f', ['x', 'x']]],
                 ['λ', 'x', ['f', ['x', 'x']]]]];

// Z combinator
// applicative order Y combinator, no longer loops
// λf.(λx.f (λv.((x x) v))) (λx.f (λv.((x x) v)))
$Z = ['λ', 'f', [['λ', 'x', ['f', ['λ', 'v', [['x', 'x'], 'v']]]],
                 ['λ', 'x', ['f', ['λ', 'v', [['x', 'x'], 'v']]]]]];

// true
// λx.λy.x
$true = ['λ', 'x', ['λ', 'y', 'x']];

// false
// λx.λy.y
$false = ['λ', 'x', ['λ', 'y', 'y']];

// logical and
// λp.λq.p q p
$and = ['λ', 'p', ['λ', 'q', [['p', 'q'], 'p']]];

// logical or
// λp.λq.p p q
$or = ['λ', 'p', ['λ', 'q', [['p', 'p'], 'q']]];

// logical not
// λp.λa.λb.p b a
$not = ['λ', 'p', ['λ', 'a', ['λ', 'b', [['p', 'b'], 'a']]]];

// if
// λp.λa.λb.p a b
$if = ['λ', 'p', ['λ', 'a', ['λ', 'b', [['p', 'a'], 'b']]]];

// more church numerals
$four  = [[$mult, $two], $two];
$five  = [[$plus, $four], $one];
$ten   = [[$mult, $five], $two];
$forty = [[$mult, $ten], $four];
$fortytwo = [[$plus, $forty], $two];

// is zero
// λn.n (λx.FALSE) TRUE
$is_zero = ['λ', 'n', [['n', ['λ', 'x', $false]], $true]];

// less than or equal
// λm.λn.ISZERO (SUB m n),
$lte = ['λ', 'm', ['λ', 'n', [$is_zero, [[$sub, 'm'], 'n']]]];

$fact = [$Z, ['λ', 'fact',
            ['λ', 'n',
                call($if, [$is_zero, 'n'],
                    $one,
                    lazy([[$mult, 'n'], ['fact', [$pred, 'n']]]))]]];

$fib = [$Z, ['λ', 'fib',
        ['λ', 'n',
            call($if, call($lte, 'n', $one),
                'n',
                lazy(call($plus, ['fib', call($sub, 'n', $two)],
                                 ['fib', call($sub, 'n', $one)])))]]];

// var_dump(evaluate($identity));
// var_dump(evaluate([$identity, $identity_a]));
// var_dump(evaluate([[[$identity, $identity], $identity], $identity_a]));
// var_dump(evaluate($omega));
// var_dump(evaluate(to_int($zero)));
// var_dump(evaluate(to_int($one)));
// var_dump(evaluate(to_int($two)));
// var_dump(evaluate(to_int([$succ, [$succ, $zero]])));
// var_dump(evaluate(to_int([[$plus, $zero], $one])));
// var_dump(evaluate(to_int([$pred, $two])));
// var_dump(evaluate(to_int([[$sub, $fortytwo], $two])));
// var_dump(evaluate(to_int([[$mult, $two], $two])));
// var_dump(evaluate(to_bool([[$and, $true], $true])));
// var_dump(evaluate(to_bool([[$and, $true], $false])));
// var_dump(evaluate(to_bool([$not, $true])));
// var_dump(evaluate(to_int([[[$if, $true], $fortytwo], 0])));
// var_dump(evaluate(to_bool([$is_zero, $zero])));
// var_dump(evaluate(to_bool([$is_zero, $one])));
// var_dump(evaluate(to_bool([[$lte, $one], $one])));
// var_dump(evaluate(to_bool([[$lte, $one], $two])));
// var_dump(evaluate(to_bool([[$lte, $two], $one])));
// var_dump(evaluate(to_int([$fact, $five])));
var_dump(evaluate(to_int([$fib, call($plus, $five, $two)])));