Skip to content

Instantly share code, notes, and snippets.

@igorw
Last active January 30, 2017 01:25
Show Gist options
  • Save igorw/7944408 to your computer and use it in GitHub Desktop.
Save igorw/7944408 to your computer and use it in GitHub Desktop.
<?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)])));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment