22
\$\begingroup\$

Had some free time this weekend and I hacked together a small Brainfuck interpreter, with the sole intention of explaining PHP's flavour of OO to a friend. This is a bit over-engineered on purpose, and performance wasn't really considered (or I wouldn't have written this in PHP in the first place).

Thoughts? Criticisms? Cookies?

I'm more interested on comments on the design, but as with any review, everything is fair game. The code is a bit much, so I removed comments, some whitespace and an interface or two. You can check out the full code and tests on github.

Example

$source = "5,2,10,1!!>>,[>>,]<<[[-<+<]>[>[>>]<[.[-]<[[>>+<<-]<]>>]>]<<]";
$bf     = new \Brainfart\Brainfart();
$output = $bf->run($source);

$output will be:

array (size=4)
  0 => int 1
  1 => int 2
  2 => int 5
  3 => int 10


The interpreter

namespace Brainfart;

use Brainfart\VM\Output;
use Brainfart\Parser\Parser;
use Brainfart\VM\VM;

class Brainfart {
    private $optimize = true;
    private $vm;
    private $parser;
    private $output;

    public function __construct($loopLimit = 100, $optimize = true) {
        $this->vm     = new VM(array(), $loopLimit);
        $this->parser = new Parser();

        $this->setOptimize($optimize);
    }

    public function setOptimize($optimize = true) {
        $this->optimize = ($optimize === true);

        return $this;
    }

    public function run($source, $input = "", $fetchMode = Output::FETCH_ARRAY) {
        $this->parser->loadSource($source);
        if ($this->parser->getFlag("string_output") === true) $fetchMode = Output::FETCH_STRING;

        $appLoop  = $this->parser->parse($this->optimize);
        $appInput = $this->parser->getInput();
        if (!empty($appInput)) $input = $appInput;

        $this->vm->init($input);

        $appLoop->execute($this->vm);

        return $this->vm->getOutput()->fetch($fetchMode);
    }
}


The Virtual Machine

VM

namespace Brainfart\VM;

class VM {
    private $input;
    private $output;
    private $memory;
    private $loopLimit = 0;

    public function __construct($input = array(), $loopLimit = 0) {
        $this->init($input, $loopLimit);
    }

    public function init($input = array(), $loopLimit = 0) {
        $this->input  = new Input($input);
        $this->output = new Output();
        $this->memory = new Memory();

        $this->setLoopLimit($loopLimit);

        return $this;
    }

    public function getInput() { return $this->input; }

    public function getOutput() { return $this->output; }

    public function getMemory() { return $this->memory; }

    public function setLoopLimit($loopLimit = 100) {
        $this->loopLimit = is_numeric($loopLimit) && $loopLimit > 0 ? (int) $loopLimit : 0;

        return $this;
    }

    public function getLoopLimit() { return $this->loopLimit; }
}

Memory

namespace Brainfart\VM;

class Memory {
    private $memory = array();
    private $pointer = 0;

    public function move($value) {
        $this->pointer += is_numeric($value) ? (int) $value : 0;

        return $this;
    }

    public function fetch() {
        return isset($this->memory[$this->pointer]) ? $this->memory[$this->pointer] : 0;
    }

    public function store($value) {
        $this->memory[$this->pointer] = $this->fetch() + (is_numeric($value) ? (int) $value : 0);

        return $this;
    }    
}    

Input

namespace Brainfart\VM;

class Input {
    private $input = array();

    public function __construct($input) {
        $this->store($input);
    }

    public function store($input) {
        if (is_scalar($input)) $input = str_split(trim($input));
        if (!is_array($input)) throw new \InvalidArgumentException();

        foreach ($input as $key => $value) $input[$key] = is_numeric($value) ? (int) $value : ord($value);

        $this->input = $input;

        return $this;
    }

    public function fetch() {
        return
            !(empty($this->input))
                ? array_shift($this->input)
                : 0;
    }    
}

Output

namespace Brainfart\VM;

class Output {
    const FETCH_ARRAY  = 0;
    const FETCH_STRING = 1;

    private $output = array();

    public function store($value) {
        $this->output[] = $value;

        return $this;
    }

    public function fetch($fetchMode = self::FETCH_ARRAY) {
        return
            ($fetchMode === self::FETCH_STRING)
                ? implode("", array_map("chr", $this->output))
                : $this->output;
    }    
}


Virtual Machine Operations

ChangeOperation

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class ChangeOperation implements OperationInterface, MutableInterface {
    use MutableTrait;

    public function execute(VM $vm) {
        $vm->getMemory()->store($this->getValue());
    }

}

InputOperation

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class InputOperation implements OperationInterface {

    public function execute(VM $vm) {
        $vm->getMemory()->store($vm->getInput()->fetch());
    }
}

LoopOperation

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class LoopOperation implements OperationInterface {

    private $master = false;
    private $operations = array();

    public function __construct(array $operations, $master = false) {

        $this->setOperations($operations)->setMaster($master);
    }

    public function setOperations(array $operations) {
        $this->operations = $operations;

        return $this;
    }

    public function getOperations() { return $this->operations; }

    public function setMaster($master) {
        $this->master = ($master === true);    
        return $this;
    }

    public function getMaster() { return $this->master; }

    public function execute(VM $vm) {
        $operations = $this->getOperations();
        $limit      = $vm->getLoopLimit();

        $i = 0;
        while (
            $this->getMaster() // master loop is the whole app, runs regardless of memory value
            || ($vm->getMemory()->fetch() != 0)
        ) {
            foreach ($operations as $operation) 
                $operation->execute($vm);

            if ($this->getMaster()) break;

            $i++;
            if ($limit > 0 && $limit < $i) throw new \RuntimeException("Limit of {$limit} operations per loop reached.");
        }
    }

}

MoveOperation

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class MoveOperation implements OperationInterface, MutableInterface {
    use MutableTrait;

    public function execute(VM $vm) {
        $vm->getMemory()->move($this->getValue());
    }    
}

OutputOperation

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class OutputOperation implements OperationInterface {

    public function execute(VM $vm) {
        $vm->getOutput()->store($vm->getMemory()->fetch());
    }    
}

SleepOperation

This is how you turn a good joke into a bad one.

namespace Brainfart\Operations;

use Brainfart\VM\VM;

class SleepOperation implements OperationInterface {    
    public function execute(VM $vm) { sleep($vm->getMemory()->fetch()); }    
}

MutableTrait

namespace Brainfart\Operations;

trait MutableTrait {
    private $value;

    public function __construct($value) { $this->setValue($value); }

    public function setValue($value) {
        $this->value = is_numeric($value) ? (int) $value : 0;

        return $this;
    }

    public function getValue() { return $this->value; }

    public function combine(MutableInterface $operation) {
        $class = get_class($this);
        if ($operation instanceof $class) {
            $this->setValue($this->getValue() + $operation->getValue());

            return $this;
        }    
        return false;
    }
}


The Parser

Loader

namespace Brainfart\Parser;

class Loader {
    private $input;
    private $source = "";
    private $flags = array();

    public function __construct($source = null) {
        if (!is_null($source)) $this->loadSource($source);

        $this->setFlag("no_optimization", false)->setFlag("string_output", false);
    }

    public function loadSource($source) {
        if (is_file($source)) $source = @ file_get_contents($source);
        if (!is_string($source)) throw new \InvalidArgumentException();

        $source = $this->prepare($source);
        $source = $this->skintoad($source);
        $source = $this->cleanup($source);

        return $this->source = $source;
    }

    public function getSource() { return $this->source; }

    public function getInput() { return $this->input; }

    public function getFlag($flag = null) {
        if (is_null($flag) || !is_scalar($flag)) return $this->flags;

        $flag = strtolower(trim($flag));

        return isset($this->flags[$flag]) ? $this->flags[$flag] : null;
    }

    protected function setFlag($flag, $value = null) {
        $flag = (!is_scalar($flag)) ? "unknown" : strtolower(trim($flag));
        if (!is_null($value)) $value = ($value === true);

        $this->flags[$flag] = $value;

        return $this;
    }

    public function setInput($input) {
        if (!is_scalar($input)) throw new \InvalidArgumentException();

        $input = (string) $input;
        $input = trim($input, ", ");
        $input = explode(",", $input);
        $input = array_map("trim", $input);

        $this->input = $input;

        return $this;
    }

    private function prepare($source) {
        $flags = array("@@" => "no_optimization", "$$" => "string_output");

        foreach ($flags as $operator => $flag) {
            if (strpos($source, $operator) !== false) {
                $this->setFlag($flag, true);
                $source = str_replace($operator, "", $source);
            }
        }

        $pos = strpos($source, "!!");
        if ($pos !== false) {
            $input  = substr($source, 0, $pos);
            $source = substr($source, $pos + 2);

            $this->setInput($input);
        }

        return preg_replace('/\s+/', "", strtolower($source));
    }

    private function skintoad($source) {
        if (!preg_match_all('/:(.*?);/', $source, $matches)) return $source;

        foreach ($matches[0] as $match) {
            $source = str_replace($match, "", $source);
            $match  = trim($match, ":;");
            if (preg_match('/^[a-zA-Z0-9_]*/', $match, $identifier)) {
                $identifier = $identifier[0];
                $sequence   = str_replace($identifier, "", $match);
                $source     = str_replace($identifier, $sequence, $source);
            }
        }

        return $source;
    }

    private function cleanup($source) {
        return preg_replace('/[^<|>|\-|\+|\.|\~|\,|\]|\[]/', "", $source);
    }

}

Parser

namespace Brainfart\Parser;

use Brainfart\Operations\LoopOperation;
use Brainfart\Operations\SleepOperation;
use Brainfart\Operations\ChangeOperation;
use Brainfart\Operations\MoveOperation;
use Brainfart\Operations\InputOperation;
use Brainfart\Operations\OutputOperation;
use Brainfart\Operations\MutableInterface;

class Parser extends Loader {
    private $operations;

    public function parse($optimize = true) {
        if ($this->getFlag("no_optimization") === true) $optimize = false;

        $operations = $this->tokenize($this->getSource(), $optimize);

        return $this->operations = new LoopOperation($operations, true);
    }

    public function getOperations() { return $this->operations; }

    private function tokenize($source, $optimize) {
        $result   = array();
        $optimize = $optimize === true;
        $length   = strlen($source);

        for ($i = 0; $i < $length; $i++) {
            $token = isset($source[$i]) ? $source[$i] : false;
            if (!$token) break;

            if ($token == "[") {
                $loopEnd = $this->findLoopEnd(substr($source, $i + 1));
                if (!$loopEnd) throw new \LogicException("Neverending loop.");

                $loopSource = substr($source, $i + 1, $loopEnd);
                $loopTokens = $this->tokenize($loopSource, $optimize);
                $operation  = new LoopOperation($loopTokens);

                $i += $loopEnd + 1;
            } else {
                $operation = $this->getOperation($token);
                if (!$operation) continue;

                if ($optimize && ($operation instanceof MutableInterface)) {
                    $index    = count($result) - 1;
                    $previous = isset($result[$index]) ? $result[$index] : false;
                    $combined = ($previous instanceof MutableInterface) ? $previous->combine($operation) : false;

                    if ($combined) {
                        $result[$index] = $combined;
                        continue;
                    }
                }
            }    
            $result[] = $operation;
        }    
        return $result;
    }

    private function findLoopEnd($source) {
        $posCloseBracket = strpos($source, "]");
        $posOpenBracket  = strpos($source, "[");

        if ($posOpenBracket === false || $posCloseBracket < $posOpenBracket) return $posCloseBracket;
        $source[$posOpenBracket] = $source[$posCloseBracket] = "_";

        return $this->findLoopEnd($source);
    }

    private function getOperation($token) {
        $operation = false;
        switch ($token) {
            case ">":
                $operation = new MoveOperation(1);
                break;
            case "<":
                $operation = new MoveOperation(-1);
                break;
            case "+":
                $operation = new ChangeOperation(1);
                break;
            case "-":
                $operation = new ChangeOperation(-1);
                break;
            case ".":
                $operation = new OutputOperation();
                break;
            case ",":
                $operation = new InputOperation();
                break;
            case "~":
                $operation = new SleepOperation();
        }    
        return $operation;
    }    
}
\$\endgroup\$
5
\$\begingroup\$

So for starters, make the operations lazy-loaded (yeah big surprise, Haskeller says make it lazy)

As such:

class LoopOperation implements OperationInterface {

    private $master = false;
    private $operations = array();

    public function __construct(array $operations, $master = false) {

        $this->setOperations($operations)->setMaster($master);
    }

becomes:

class LoopOperation implements OperationInterface {

    public $master = false;
    public $operations = array();

Then you either add operations to the public array as you interpret them, or create an addOperation method, either way you need to be able to construct the LoopOperation and then as parsing continues add individual operations to it.

Then here's some parser combinators with an error monad for ya (I don't know PHP so bear with me):

abstract class M
{
    abstract public function then($f); // Formally this is 'bind', the f is the function to bind to the action

    abstract public function otherwise($f); // Formally this would be an application of an `alternative` or monoid

    public $a; // The a is for 'action'
}

class Success extends M
{
    public function __construct($a) {
        $this->a = $a;
    }

    public function then($f) {
        return $f($this->a);
    }

    public function otherwise($f) {
        return $this;
    }
}

class Failure extends M
{
    public function __construct($a) {
        $this->a = $a;
    }

    public function then($f) {
        return $this;
    }

    public function otherwise($f) {
        return new Success($this->a)->then($f);
    }
}

public function pop($a) {
    return new Success(substr($a, 1));
}

public function charIs($char) {
    return function($a) use($char) {
        if ($a[0] == $char) {
            return new Success($a);
        }

        return new Failure($a);
    }
}

public function charExists($char) {
    return function($a) use($char) {
        if (strpos($a, $char) === false) {
            return new Failure($a);
        }

        return new Success($a);
    }
}


public function addLoopOperation($operation) {
    return function($a) user ($operation) {
        $operation->addOperation(strpos($a, 0, 1));
        return new Success($a);
    }
}

public function throwException($ex) {
    return function($a) use ($ex) {
        throw $ex;
    }
}

public function addLoop($operation = new LoopOperation()) {
    return function($a) use (&$operation) {
        return new Success($a)
            ->then(charExists("]"))->otherwise(throwException(new LogicException("Neverending loop."))
            ->then(addLoopOperation($operation))
            ->then(pop)
            ->then(charIs("]"))->then(pop)->otherwise(addLoop($operation));
    }

    // Because it's recursed the way it is, it will continue adding operations until it hits the char "]"
}

Study closely and you'll realize the loop operation object where all the operations are added, is lost after the loop interpretation is complete, for this reason I would suggest rather than the way I'm threading the source through all the functions, actually create a structure that has source, and VM, so the functions can parse the source and push operations onto the VM as they go, the resulting code would give you ability to write things like:

while(true)
    new Success($someStructure)->then(charIs("["))->then(addLoop())->otherwise(processOperation)->then(executeOperations);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.