BrainfuckJS-2

brainfuck2.js

class List {
    constructor(array) {
        this.array = array;
    }

    get first() {  
        return this.array[0];
    }

    get tail() {
        return new List(this.array.slice(1));
    }

    get init() {
        return new List(this.array.slice(0, -1));
    }

    get last() {
        return this.array[this.array.length - 1];
    }

    prepend(elem) {
        return new List([elem].concat(this.array));
    }

    append(elem) {
        return new List(this.array.concat([elem]));
    }

    isEmpty() {
        return this.array.length === 0;
    }

    toString() {
        return this.array.join(' ');
    }
}

class Head {
    constructor(left, current, right) {
        this.left = left;
        this.current = current;
        this.right = right;
    }

    moveLeft(n = 1, head = this) {
        if(n === 0) {
            return head;
        } 
        else {
            let h = new Head(
                head.left.init,
                head.left.last || 0,
                head.right.prepend(head.current)
            );
            return this.moveLeft(n - 1, h);
        }
    }    

    moveRight(n = 1, head = this) {
        if(n === 0) {
            return head;
        } 
        else {
            let h = new Head(
                head.left.append(head.current),
                head.right.first || 0,
                head.right.tail
            )
            return this.moveRight(n - 1, h);
        }
    }    

    write(data) {
        return new Head(this.left, data, this.right, this.defaultValue);
    }

    toString() {
        let l = this.left.toString();
        let r = this.right.toString();
        return `[${l}](${this.current})[${r}]`;
    }
}

class CommandState {
    constructor(head) {
        this.head = head;
    }

    // idx 是指令索引，不是指陣列索引
    get idx() {
        return this.head.current;
    }

    // 取得目前的指令
    get current() {
        return this.head.moveRight(this.idx + 1).current;
    }

    // 磁頭在指令區前進 n 個位置
    step(n = 1) {
        return new CommandState(
            this.head.write(this.idx + n)
        );
    }

    // 移動至最近的 ] 指令
    rightBracket() {
        function bracket(commandState) {
            if(commandState.current === ']') {
                return commandState.idx;
            } else {
                return bracket(commandState.step());
            }
        }

        return new CommandState(
            this.head.write(bracket(this))
        );
    } 

    // 移動至最近的 [ 指令
    leftBracket() {
        function bracket(commandState) {
            if(commandState.current === '[') {
                return commandState.idx;
            } else {
                return bracket(commandState.step(-1));
            }
        }

        return new CommandState(
            this.head.write(bracket(this))
        );
    }

    // 將磁頭停靠在「指令索引」位置   
    park(head = this.head) {
        return head.left.isEmpty() ? 
                    new CommandState(head) : this.park(head.moveLeft());
    }

    isRunnable() {
        return this.current !== '\0';
    }         
}

class DataState {
    constructor(head) {
        this.head = head;
    }

    // idx 是資料索引，不是指陣列索引
    get idx() {
        return this.head.current;
    }

    // 取得目前磁頭下的資料   
    get current() {
        return this.head.moveRight(this.idx + 1).current;
    }    

    // 磁頭在資料區前進 n 個位置
    step(n = 1) {
        return new DataState(
            this.head.write(this.idx + n)
        );
    }

    // 在目前位置寫入指定的資料
    writeCurrent(x) {
        let head = this.head.moveRight(this.idx + 1);
        return new DataState(
            head.write(x).moveLeft(this.idx + 1)
        );
    }

    // 將磁頭停靠在「資料索引」位置   
    park(head = this.head) {
        return head.current === '\0' ? new DataState(head.moveRight()) : this.park(head.moveRight());
    }    
}

class Context {
    constructor(head) {
        this.state = new CommandState(head);
    }

    isRunnable() {
        return this.state.isRunnable();
    }

    get data() {
        let head = this.state.head;
        // 呼叫 park 轉移狀態
        let dataState = new DataState(head).park();

        return dataState.head.right.array;
    }
}

class Manual {
    constructor() {
        this.rules = new Map([
            ['+', addOne],
            ['-', minusOne],
            ['>', moveHeadRight],
            ['<', moveHeadLeft],
            ['[', leftBracket],
            [']', rightBracket],
            ['.', convertToChar],
            [',', convertToNumber]            
        ]);

        function head(dataState) {
            return dataState.current;
        }

        function writeCurrent(dataState, x) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.writeCurrent(x).head)
                                      .park().step();
            return new Context(commandState.head);
        }

        // +
        function addOne(dataState) {
            return writeCurrent(dataState, head(dataState) + 1);
        }

        // -
        function minusOne(dataState) {
            return writeCurrent(dataState, head(dataState) - 1);
        }

        // <
        function moveHeadLeft(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.step(-1).head).park().step();
            return new Context(commandState.head);  
        }

        // >
        function moveHeadRight(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.step().head).park().step();
            return new Context(commandState.head);         
        }

        // .
        function convertToChar(dataState) {
            return writeCurrent(dataState, String.fromCharCode(head(dataState)));
        }

        // ,
        function convertToNumber(dataState) {
            return writeCurrent(dataState, head(dataState).charCodeAt(0));
        }

        // [
        function leftBracket(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.head).park();
            if(head(dataState) === 0) {
                return new Context(commandState.rightBracket().head);
            }
            else {
                return new Context(commandState.step().head);
            }
        }

        // ]
        function rightBracket(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.head).park();
            if(head(dataState) === 0) {
                return new Context(commandState.step().head);
            }
            else {
                return new Context(commandState.leftBracket().head);
            }
        }
    }

    next_context(context) {
        let commandState = context.state;
        let cmd = commandState.current;
        // 轉移至資料狀態
        let dataState = new DataState(commandState.head).park();
        return this.rules.get(cmd)(dataState);
    }
}

class Brainfuck {
    constructor(code) {
        this.context = new Context(
            new Head(new List([]), 0, new List(Array.from(code + '\0')))
        );
        this.manual = new Manual();
    }

    execute() { 
        return this.runUntilHalt(this.context).data;
    }

    runUntilHalt(context) {
        return context.isRunnable() ? 
                    this.runUntilHalt(this.manual.next_context(context)) : 
                    context;
    }
}

function println(v) {
    console.log(v.toString());
}

let code = '++++++++[>+++++++++<-]>.<+++++++[>>++++++++++<<-]>>-.<<+++++++[>>>++++++++++<<<-]>>>++++++.<<<+++++++[>>>>++++++++++<<<<-]>>>>++++++.<<<<++++++++[>>>>>++++++++++<<<<<-]>>>>>-.<<<<<++++[>>>>>>+++++++++++<<<<<<-]>>>>>>.<<<<<<+++++++++[>>>>>>>++++++++++<<<<<<<-]>>>>>>>---.<<<<<<<++++++++[>>>>>>>>++++++++++<<<<<<<<-]>>>>>>>>-.<<<<<<<<++++++++[>>>>>>>>>++++++++++<<<<<<<<<-]>>>>>>>>>++.<<<<<<<<<++++++++[>>>>>>>>>>++++++++++<<<<<<<<<<-]>>>>>>>>>>----.<<<<<<<<<<+++++++[>>>>>>>>>>>++++++++++<<<<<<<<<<<-]>>>>>>>>>>>--.<<<<<<<<<<<';

let result = new Brainfuck(code).execute();

// HELLO,WORLD
println(result.slice(1).join(''));