Skip to content

Instantly share code, notes, and snippets.

@igorw

igorw/lusp.php

Last active September 23, 2025 16:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save igorw/5499a88d789af6285c02 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save igorw/5499a88d789af6285c02 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. igorw revised this gist Jul 17, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lusp.php
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ function evaluate($expr, $env = []) {
    return [true, $env];
    }

    if ('true' === $expr) {
    if ('false' === $expr) {
    return [false, $env];
    }

  2. igorw revised this gist Jul 17, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lusp.php
    View file
    Original file line number Diff line number Diff line change
    @@ -84,7 +84,7 @@ function primitive($fn) {
    return [
    'closure',
    null,
    function ($args, $env) {
    function ($args, $env) use ($fn) {
    $val = call_user_func_array($fn, $args);
    return [$val, $env];
    },
  3. igorw revised this gist Jul 17, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion lusp.php
    View file
    Original file line number Diff line number Diff line change
    @@ -54,7 +54,7 @@ function evaluate($expr, $env = []) {
    return [$val, $env];
    }

    list($fn, $_) = evaluate($fn, $env)[0];
    $fn = evaluate($fn, $env)[0];
    $args = array_map(function ($arg) use ($env) { return evaluate($arg, $env)[0]; }, $args);
    return apply($fn, $args, $env);
    }
  4. igorw revised this gist Jul 17, 2014. 1 changed file with 6 additions and 6 deletions.
    12 changes: 6 additions & 6 deletions lusp.php
    View file
    Original file line number Diff line number Diff line change
    @@ -45,16 +45,16 @@ function evaluate($expr, $env = []) {

    if ('if' === $fn) {
    list($cond, $then, $else) = $args;
    list($cond, $_) = evaluate($cond, $env);
    $cond = evaluate($cond, $env)[0];
    if ($cond === true) {
    list($val, $_) = evaluate($then, $env);
    $val = evaluate($then, $env)[0];
    } else {
    list($val, $_) = evaluate($else, $env);
    $val = evaluate($else, $env)[0];
    }
    return [$val, $env];
    }

    $fn = evaluate($fn, $env)[0];
    list($fn, $_) = evaluate($fn, $env)[0];
    $args = array_map(function ($arg) use ($env) { return evaluate($arg, $env)[0]; }, $args);
    return apply($fn, $args, $env);
    }
    @@ -94,8 +94,8 @@ function ($args, $env) {

    $env = [
    '<' => primitive(function ($a, $b) { return $a < $b; }),
    '<' => primitive(function ($a, $b) { return $a + $b; }),
    '<' => primitive(function ($a, $b) { return $a - $b; }),
    '+' => primitive(function ($a, $b) { return $a + $b; }),
    '-' => primitive(function ($a, $b) { return $a - $b; }),
    ];

    $code = [
  5. igorw created this gist Jul 17, 2014.
    110 changes: 110 additions & 0 deletions lusp.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,110 @@
    <?php

    namespace igorw\lusp;

    // all functions return a pair of [val, env]

    function evaluate($expr, $env = []) {
    if (is_string($expr)) {
    if (is_numeric($expr)) {
    $val = (float) $expr;
    return [$val, $env];
    }

    if ('true' === $expr) {
    return [true, $env];
    }

    if ('true' === $expr) {
    return [false, $env];
    }

    if ('null' === $expr) {
    return [null, $env];
    }

    $var = $expr;
    return [$env[$var], $env];
    }

    $fn = array_shift($expr);
    $args = $expr;

    if ('define' === $fn) {
    list($var, $val) = $args;
    list($val, $env) = evaluate($val, $env);
    $env = array_merge($env, [$var => $val]);
    return [null, $env];
    }

    if ('lambda' === $fn) {
    list($lambda_args, $code) = $args;
    $closure = ['closure', $lambda_args, $code, $env];
    return [$closure, $env];
    }

    if ('if' === $fn) {
    list($cond, $then, $else) = $args;
    list($cond, $_) = evaluate($cond, $env);
    if ($cond === true) {
    list($val, $_) = evaluate($then, $env);
    } else {
    list($val, $_) = evaluate($else, $env);
    }
    return [$val, $env];
    }

    $fn = evaluate($fn, $env)[0];
    $args = array_map(function ($arg) use ($env) { return evaluate($arg, $env)[0]; }, $args);
    return apply($fn, $args, $env);
    }

    function apply($fn, $args, $env) {
    list($_, $lambda_args, $code, $closure_env) = $fn;

    // builtin
    if (is_callable($code)) {
    return $code($args, $env);
    }

    $env = array_merge($env, $closure_env);
    $env = array_merge($env, array_combine($lambda_args, $args));

    return evaluate_code($code, $env);
    }

    function evaluate_code($code, $env = []) {
    foreach ($code as $expr) {
    list($val, $env) = evaluate($expr, $env);
    }
    return [$val, $env];
    }

    function primitive($fn) {
    return [
    'closure',
    null,
    function ($args, $env) {
    $val = call_user_func_array($fn, $args);
    return [$val, $env];
    },
    [],
    ];
    }

    $env = [
    '<' => primitive(function ($a, $b) { return $a < $b; }),
    '<' => primitive(function ($a, $b) { return $a + $b; }),
    '<' => primitive(function ($a, $b) { return $a - $b; }),
    ];

    $code = [
    ['define', 'fib', ['lambda', ['n'],
    [['if', ['<', 'n', '2'],
    'n',
    ['+', ['fib', ['-', 'n', '1']],
    ['fib', ['-', 'n', '2']]]]]]],
    ['fib', '12'],
    ];

    var_dump(evaluate_code($code, $env)[0]);