Brainfuck interpereter in ReQL

bf-reql.js

var charLookup = "??????????\n????????????????????? !?#$%&?()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[?]^_`abcdefghijklmnopqrstuvwxyz???~?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????";

var bailoutSteps = 60000;

r.expr({
  program: "rot13 (from Wikipedia):"+
"-,+[                         Read first character and start outer character reading loop"+
"    -[                       Skip forward if character is 0"+
"        >>++++[>++++++++<-]  Set up divisor (32) for division loop"+
"                               (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero)"+
"        <+<-[                Set up dividend (x minus 1) and enter division loop"+
"            >+>+>-[>>>]      Increase copy and remainder / reduce divisor / Normal case: skip forward"+
"            <[[>+<-]>>+>]    Special case: move remainder back to divisor and increase quotient"+
"            <<<<<-           Decrement dividend"+
"        ]                    End division loop"+
"    ]>>>[-]+                 End skip loop; zero former divisor and reuse space for a flag"+
"    >--[-[<->+++[-]]]<[         Zero that flag unless quotient was 2 or 3; zero quotient; check flag"+
"        ++++++++++++<[       If flag then set up divisor (13) for second division loop"+
"                               (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero)"+
"            >-[>+>>]         Reduce divisor; Normal case: increase remainder"+
"            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient"+
"            <<<<<-           Decrease dividend"+
"        ]                    End division loop"+
"        >>[<+>-]             Add remainder back to divisor to get a useful 13"+
"        >[                   Skip forward if quotient was 0"+
"            -[               Decrement quotient and skip forward if quotient was 1"+
"                -<<[-]>>     Zero quotient and divisor if quotient was 2"+
"            ]<<[<<->>-]>>    Zero divisor and subtract 13 from copy if quotient was 1"+
"        ]<<[<<+>>-]          Zero divisor and add 13 to copy if quotient was 0"+
"    ]                        End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3)"+
"    <[-]                     Clear remainder from first division if second division was skipped"+
"    <.[-]                    Output ROT13ed character from copy and clear it"+
"    <-,+                     Read next character"+
"]                            End character reading loop",
  input: "Uryyb, ErguvaxQO!",
}).do(function (base) {
  // Remove all non-instruction characters.
  base = base.merge({
    program: r.add(r.args(base("program").split("").filter(function (ch) {
      return r.expr(["-","+","<",">",",",".","[","]"]).offsetsOf(ch).count().gt(0);
    }))),
  });
  
  // Special optimized instruction: [-] and [+] are replaced with 0, which zeroes the current cell.
  base = base.merge({
    program: base("program").split("[-]").concatMap(function (s) { return s.split("[+]") }).fold(
      {str: "", first: true},
      function (state, part) {
        return r.branch(state("first"),
          { first: false, str: part },
          { first: false, str: r.add(state("str"), "0", part) }
        );
      })("str"),
  });
  
  // Create a map of loop points; one entry per [, pointing at the instruction after its matching ].
  base = base.merge({
    loops: base("program").split("").map(r.range(), function (ch, i) { return [ch, i] }).fold({
      stack: [],
      out: [],
    }, function (state, pair) {
      var ch = pair(0);
      var idx = pair(1);
      return r.branch(
        ch.eq("["), state.merge({ stack: state("stack").add([idx]) }),
        ch.eq("]"), state.merge({
          stack: state("stack").slice(0, -1),
          out: state("out").add([[state("stack").nth(-1).coerceTo("STRING"), idx.add(1)]]),
        }),
        state
      );
    })("out").coerceTo("OBJECT"),
  });
  
  return r.range().fold(base.merge({
    ram: [0],  // grown dynamically as needed
    at: 0,     // ram pointer
    pc: 0,     // program counter
    stack: [], // the pc of the starts of loops we're in right now

    output: "",
    bailedOut: false,
  }), function (state, totalSteps) {
    var current = state("program").slice(state("pc"), state("pc").add(1));
    var nextPC = state("pc").add(1);
    var cell = state("ram")(state("at"));
    function splice(fn) {
      return state("ram").changeAt(state("at"), fn(cell));
    }

    return current.do(function (current) { // Evaluates "current" once, rather than once per branch statement
      return state.merge(r.branch(
        // Infinite loop avoidance
        totalSteps.ge(bailoutSteps), {
          bailedOut: true,
        },

        current.eq("+"), {
          ram: splice(function (v) { return v.add(1).mod(256) }),
          pc: nextPC,
        },

        current.eq("-"), {
          ram: splice(function (v) { return v.add(255).mod(256) }),
          pc: nextPC,
        },

        current.eq("0"), {
          ram: splice(function () { return 0 }),
          pc: nextPC,
        },

        current.eq(">"), {
          ram: state("ram").count().le(state("at").add(1)).branch(
            state("ram").add([0]), state("ram")),
          at: state("at").add(1),
          pc: nextPC,
        },

        current.eq("<"), {
          at: state("at").sub(1),
          pc: nextPC,
        },

        current.eq("["), r.branch(
          cell.eq(0),
          { pc: state("loops")(state("pc").coerceTo("STRING")) },
          {
            stack: state("stack").add([state("pc")]),
            pc: nextPC,
          }
        ),

        current.eq("]"), {
          stack: state("stack").slice(0, -1),
          pc: state("stack").nth(-1),
        },

        current.eq("."), {
          output: state("output").add(r.expr(charLookup).slice(cell, cell.add(1))),
          pc: nextPC,
        },

        current.eq(","), r.branch(
          state("input").eq(""),
          {
            ram: splice(function () { return 255 }),
            pc: nextPC,
          },
          {
            ram: splice(function () {
              // 63 = "?"
              return r.expr(charLookup).split("").offsetsOf(state("input").slice(0, 1)).nth(0).default(63);
            }),
            input: state("input").slice(1),
            pc: nextPC,
          }
        ),
        
        // Should never be reached.
        { pc: nextPC }
      ));
    });
  }, {emit: function(oldState, _, state) {
    return r.branch(
      state("pc").ge(state("program").count()).or(state("bailedOut")),
      [state.pluck("bailedOut", "output")],
      []);
  }}).limit(1)
});