WORKING LISP WITH RECURSION written in 1:01:54.32 :D

quicklisp.php

<?php

class cons {
    private $head;
    private $tail;
    public function __construct($head, cons $tail = NULL) {
        $this->head = $head;
        $this->tail = $tail;
    }
    static public function car(cons $cons) {
        return $cons->head;
    }
    static public function cdr(cons $cons) {
        return $cons->tail;
    }
    public function __toString() {
        $list = $this;
        $out =  "(";
        do {
            if ($list !== $this) {
                $out .= " ";
            }
            $out .= self::car($list);
            $list = self::cdr($list);
        } while ($list !== NULL);
        $out .= ")";
        return $out;
    }
    public function __debugInfo() {
        return [$this->__toString()];
    }
}

function l(...$items) {
    $tail = NULL;
    foreach (array_reverse($items) as $item) {
         $tail = new cons($item, $tail);
    }
    return $tail;
}

function evalList(cons $list = NULL, array &$env) {
    if ($list === NULL) {
        return NULL;
    } else {
        return new cons(evalLisp(cons::car($list), $env), evalList(cons::cdr($list), $env));
    }
}

function evalLisp($thing, array &$env = []) {
    if (is_string($thing)) {
        if (isset($env[$thing])) {
            return $env[$thing];
        } else {
            throw new RuntimeException("No \"$thing\" in environment");
        }
    }
    // self-quoting values
    if (!($thing instanceof cons)) {
        return $thing;
    } else {
        $list = $thing;
    }
    
    $type = cons::car($list);
    $tail = cons::cdr($list);
    switch ($type) {
        case 'quote':
            return cons::car($tail);
        case 'let':
            $pairs = cons::car($tail);
            $body = cons::car(cons::cdr($tail));
            $newenv = $env;
            do {
                $pair = cons::car($pairs);
                $newenv[cons::car($pair)] = evalLisp(cons::car(cons::cdr($pair)), $newenv);
                $pairs = cons::cdr($pairs);
            } while ($pairs !== NULL);
            return evalLisp($body, $newenv);
        case 'lambda':
            $params = cons::car($tail);
            $body = cons::car(cons::cdr($tail));
            return function(cons $args = NULL) use ($params, $body, &$env) {
                $newenv = $env;
                do {
                    $param = cons::car($params);
                    $arg = cons::car($args);
                    $newenv[$param] = $arg;
                    $params = cons::cdr($params);
                    $args = cons::cdr($args);
                } while ($params !== NULL);
                return evalLisp($body, $newenv);
            };
            break;
        default:
            $tail = evalList($tail, $env);
            break;
    }
    switch ($type) {
        case 'cons':
            return new cons(cons::car($tail), cons::car(cons::cdr($tail)));
        case 'car':
            return cons::car(cons::car($tail));
        case 'cdr':
            return cons::cdr(cons::car($tail));
        case 'list':
            return $tail;
        case 'eq':
            return cons::car($tail) === cons::car(cons::cdr($tail));
        case 'atom':
            return !(cons::car($tail) instanceof cons);
        default:
            if (isset($env[$type])) {
                return $env[$type]($tail);
            } else {
                throw new \RuntimeException("No function \"$x\" in environment?");
            }
    }
}

//$x = new cons('quote', new cons(new cons('a', new cons('b', NULL))));

//$x = new cons('eq', new cons(new cons('quote', new cons('a')), new cons(new cons('quote', new cons('b', NULL)), NULL)));
//$x = l('eq', l('quote', 'a'), l('quote', 'b'));
//var_dump(evalLisp(l('cdr', l('list', l('quote', 'a'), l('quote', 'b')))));

//$x = l('let', l(l('a', 2)), 'a');
//var_dump(evalLisp($x));

//$x = l('let', l(l('foobar', l('lambda', l('a'), 'a'))), l('foobar', 2));
//var_dump(evalLisp($x));
$x = l('let', l(l('foobar', l('lambda', l('a'), l('foobar', 'a')))), l('foobar', 2));
var_dump(evalLisp($x));