Simple Register Machine Emulator

1. Source code

Syntax:

// All but the "eval" statements are case-insensitive.
init r0 10         // Initialise R0 to 10
                   // All registers are 0 by default
foo: R0+           // Set a label called foo, increment R0 and jump to
                   // the next statement
R0+ -> foo         // Increment R0 and jump to foo (jump -1)
bar: R1- ->,bar    // If R1>0 then decrement it and jump +1, else jump
                   // to label bar
R1- -> foo         // If R1>0 then decrement it and jump to foo, else
                   // jump +1
R1- -> foo, bar    // If R1>0 then decrement it and jump to foo, else
                   // jump to bar

trace R0+ -> foo   // Log the value of R0 every-time execution
                   // reaches this line (logs value before
                   // increment/decrement)
R0-                // Just subtracts R0 no matter what, can be useful
                   // with trace, with the following combination:

trace R0+
R0-

R0+ -> +0          // Loop forever (relative offset of +0
halt "reason"      // You can give a reason for halting, to have
                   // fail/success halt
halt               // Otherwise it just halts with "Halt"

// And some special code: eval, though you can only name registers
// previously used, and they must be lower case
eval "Random integer between 0 and 1024"
     r0 ::= Math.round(Math.random()*1024);
// For simplicity of code, also needs a next-instruction
halt

Example from slide 30

Init R1 3 Init R2 4 L0: R1- -> L1,L2 L1: R0+ -> L0 L2: R2- -> L3, L4 L3: R0+ -> L2 L4: Halt

Output goes here

Same, with shorthand. Note that offsets are statement relative, not line-relative.

Init R1 3 Init R2 4 R1- -> +1,+2 // Could leave +1 out, like below R0+ -> -1 R2- -> , +2 R0+ -> -1 Halt

Output goes here

1 Source code

The source code is a bit of a hack currently. It uses a lot of instanceof's where proper OO/Prototyping approaches (e.g. visitor pattern, or dynamically extending the prototypes) would do better, but they would also be more code.

It can be embedded into websites by linking to register-machine.js, and is available under the permissive MIT license.

// Copyright 2019 by Robert Kovacsics
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use, copy,
// modify, merge, publish, distribute, sublicense, and/or sell copies
// of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

To embed, add the following to the <head> tag:

<script type="text/javascript" src="https://www.cl.cam.ac.uk/~rmk35/register-machine/register-machine.js"></script>

and something along this to the <body> tag:

<textarea cols="80" rows="22">
Init R1 3
Init R2 4

L0: R1- -> L1,L2
L1: R0+ -> L0
L2: R2- -> L3, L4
L3: R0+ -> L2
L4: Halt</textarea>
</p>
<p>
 <button onclick="run_rm(this)">Run</button>
<!-- Alternatively to the below <script>, for manual visualisation:
 <button onclick="plot_rm(this)">Run</button>
 -->
</p>
<blockquote> <p> </p> </blockquote>
<script type="text/javascript">
{ let btn = closestHTMLneighbour(document.currentScript, -1, "BUTTON");
  plot_rm(btn, '600px'); }
</script>

1.1 Parsing

This is more of a tokeniser than a proper parser. It uses the first match.

"use strict";

function lower(s) { if (typeof s == "string") return s.toLowerCase(); else return s; }
var parser_line = 1;

function Newline() { ++parser_line; }
function Label(s, str) { this.str = s; this.line = parser_line;
                         this.name = lower(str); }
function Trace(s) { this.str = s; this.line = parser_line; }
function Init(s, reg, val) { this.str = s; this.line = parser_line;
                             this.reg = lower(reg); this.val = parseInt(val); }
function Inc(s, reg, next) { this.str = s; this.line = parser_line;
                             this.reg = lower(reg); this.next = lower(next); }
function Dec(s, reg, tru, fals) { this.str = s; this.line = parser_line;
                                  this.reg = lower(reg);
                                  this.tru = lower(tru); this.fals = lower(fals); }
function Halt(s, reason) { this.str = s; this.line = parser_line;
                           this.reason = reason; }
function Eval(s, desc, reg, code) { this.str = s; this.line = parser_line;
                                    this.desc = desc; this.reg = lower(reg); this.code = code; }

var parseTable =
    [[/\n/y, Newline],
     [/\/\/[^\n]*/y, null],
     [/\s+/y, null],
     [/(\w+):/y, (s, lbl) => new Label(s, lbl)],
     [/trace/yi, (s) => new Trace(s)],
     [/init (\w+) (\d+)/yi, (s, r, v)   => new Init(s, r, v)],
     [/(\w+)\+\s*->\s*(\w+)/y,     (s, r, next)   => new Inc(s, r, next)],
     [/(\w+)\+\s*->\s*([+-]\d+)/y, (s, r, offset) => new Inc(s, r, parseInt(offset))],
     [/(\w+)\+/y,                  (s, r)         => new Inc(s, r, +1)],
     [/(\w+)-\s*->\s*(\w+)\s*,\s*(\w+)/y,         (s, r, tru, fals) => new Dec(s, r, tru,           fals)],
     [/(\w+)-\s*->\s*([+-]\d+)\s*,\s*([+-]\d+)/y, (s, r, tru, fals) => new Dec(s, r, parseInt(tru), parseInt(fals))],
     [/(\w+)-\s*->\s*,\s*(\w+)/y,                 (s, r, fals)      => new Dec(s, r, +1,            fals)],
     [/(\w+)-\s*->\s*,\s*([+-]\d+)/y,             (s, r, fals)      => new Dec(s, r, +1,            parseInt(fals))],
     [/(\w+)-\s*->\s*(\w+)\s*,?/y,                (s, r, tru)       => new Dec(s, r, tru,           +1)],
     [/(\w+)-\s*->\s*([+-]\d+)\s*,?/y,            (s, r, tru)       => new Dec(s, r, parseInt(tru), +1)],
     [/(\w+)-\s*/y,                               (s, r, tru)       => new Dec(s, r, +1,            +1)],
     [/halt\s+"([^"]*)"/yi, (s, reason) => new Halt(s, reason)],
     [/halt/yi,             (s)         => new Halt(s, "Halt")],
     [/eval\s+"([^"]*)"\s+(\w+)\s*::=\s*([^;]*);/yi, (s, desc, reg, code) => new Eval(s, desc, reg, code)]
    ];

function parse(input, log_fn) {
  let matched = true;
  let index = 0;
  let tokens = [];
  parser_line = 1;
  while (matched) {
    matched = false;
    for (let [re, fn] of parseTable) {
      console.assert(re.sticky, `RegExp ${re.toString()} should be sticky!`);
      re.lastIndex = index;
      let m = re.exec(input);
      if (m != null) {
        matched = true;
        index = re.lastIndex;
        if (fn) {
          let matchArray = Array.from(m);
          let fn_res = fn.apply(undefined, matchArray);
          if (fn_res) tokens.push(fn_res);
        }
        break;
      }
    }
  }
  if (index != input.length) {
    let line = (input.substring(0, index).match(/\n/g)||[]).length+1
    log_fn(`Failed to fully parse input, problem on line ${line} from ${input.substring(index)}\n`);
    throw "Parsing failure";
  }
  return tokens;
}

1.2 Resolving labels and trace option

// The instanceof is not the best from a maintenance perspective, but
// suffices here
function resolve(tokens, log_fn) {
  let trace = false;
  let label = null;
  let newTokens = [];
  let index = 0;
  let labelMap = new Map();
  for (let token of tokens) {
    if (token instanceof Label) {
      label = token.name;
      labelMap.set(label, index);
    } else if (token instanceof Trace) {
      trace = true;
    } else {
      token.trace = trace;
      token.label = label;
      newTokens.push(token);
      trace = false;
      label = null;
      ++index;
    }
  }

  index = 0;
  function fixup(token, prop, index, log_fn) {
    if (typeof token[prop] == "string") {
      if (/^\d+$/.test(token[prop])) { // Absolute label
        token[prop] = parseInt(token[prop]);
      } else { // String label
        let new_prop = labelMap.get(token[prop]);
        if(new_prop === undefined) {
            log_fn(`Could not find label ${token[prop]}!`);
            throw "Looking up label fail!";
        }
        token[prop] = new_prop
      }
    } else if (typeof token[prop] == "number") {
      // Convert relative to absolute
      token[prop] += index;
    }
  }
  for (let token of newTokens) {
    if (token instanceof Inc) {
      fixup(token, "next", index, log_fn);
    } else if (token instanceof Dec) {
      fixup(token, "tru", index, log_fn);
      fixup(token, "fals", index, log_fn);
    }
    ++index;
  }
  return newTokens;
}

1.3 Evaluating

function evaluate(tokens, trace_fn, argsArray) {
  let steps = 0;
  let index = 0;
  let regs = new Map();
  regs.at = function(idx) {
    if (!this.has(idx)) this.set(idx, 0);
    return this.get(idx);
  }
  argsArray.forEach((v, i) => regs.set(`R${i}`, v));
  while (true) {
    let at_pc = tokens[index];
    if (at_pc instanceof Init) {
      if (at_pc.trace) trace_fn(`line ${at_pc.line}: Initialising: ${at_pc.reg} with ${at_pc.val}\n`);
      regs.set(at_pc.reg, at_pc.val);
      ++index;
    } else if (at_pc instanceof Halt) {
      if (at_pc.trace) trace_fn(`line ${at_pc.line}: Halting: ${at_pc.reason}\n`);
      break;
    } else if (at_pc instanceof Inc) {
      let r = at_pc.reg;
      if (at_pc.trace) trace_fn(`line ${at_pc.line}: ${at_pc.str} was ${regs.at(r)}\n`);
      regs.set(r, regs.at(r)+1);
      index = at_pc.next;
    } else if (at_pc instanceof Dec) {
      let r = at_pc.reg;
      if (at_pc.trace) trace_fn(`line ${at_pc.line}: ${at_pc.str} was ${regs.at(r)}\n`);
      if (regs.at(r) > 0) {
        regs.set(r, regs.at(r)-1);
        index = at_pc.tru;
      } else {
        index = at_pc.fals;
      }
    } else if (at_pc instanceof Eval) {
      // Construct
      let r = at_pc.reg;
      if (at_pc.trace) trace_fn(`line ${at_pc.line}: ${r} ::= ${at_pc.desc}\n`);
      let code = "{ ";
      for (let [k,v] of regs) { code += `let ${k} = ${JSON.stringify(v)};\n  `; }
      code += at_pc.code + "}";
      regs.set(r, eval(code));
      ++index;
    }
    if (index >= tokens.length) {
      trace_fn(`PC out of bounds from instruction line ${at_pc.line}: ${at_pc.str}`);
      throw "PC out of bounds"
    }
    if (++steps > 1000) {
      trace_fn("Done 1000 steps, bailing!");
      break;
    }
  }
  return regs;
}

1.4 Drawing the graph

In graphviz dot

function to_dot(tokens) {
  let nodes = "  Start [shape=box];\n";
  let edges = "";
  let index = 0;

  for (let token of tokens) {
    if ((!(token instanceof Init)) && edges == "") {
      edges += `  Start -> ${index};\n`;
    }

    if (token instanceof Inc) {
      nodes += `  ${index} [label="${token.reg}+"];\n`;
      edges += `  ${index} -> ${token.next};\n`;
    } else if (token instanceof Dec) {
      nodes += `  ${index} [label="${token.reg}-"];\n`;
      edges += `  ${index} -> ${token.tru};\n`;
      edges += `  ${index} -> ${token.fals} [arrowhead="veevee"];\n`;
    } else if (token instanceof Halt) {
      nodes += `  ${index} [label="${token.reason}",shape=box];\n`;
    } else if (token instanceof Eval) {
      nodes += `  ${index} [label="${token.desc}",shape=box];\n`;
      edges += `  ${index} -> ${index+1};\n`;
    } else if (token instanceof Init) {
    } else {
      console.assert(false, "Unknown token: ", token);
    }
    ++index;
  }

  let output = "digraph {\n";
  output += nodes;
  output += edges;
  output += "}\n";
  return output;
}

In https://visjs.org

function to_vis(tokens) {
  let nodes = [{id: -1, label: "Start", shape: "box"}];
  let edges = [];
  let index = 0;

  for (let token of tokens) {
    if ((!(token instanceof Init)) && edges.length == "") {
      edges.push({from: -1, to: index, arrows: "to"});
    }

    if (token instanceof Inc) {
      nodes.push({id: index, label: `${token.reg}+`});
      edges.push({from: index, to: token.next, arrows: "to"});
    } else if (token instanceof Dec) {
      nodes.push({id: index, label: `${token.reg}-`});
      edges.push({from: index, to: token.tru, arrows: "to"});
      edges.push({from: index, to: token.fals, arrows: "to, middle"});
    } else if (token instanceof Eval) {
      nodes.push({id: index, label: token.desc, shape: "box"});
      edges.push({from: index, to: index+1, arrows: "to"});
    } else if (token instanceof Halt) {
      nodes.push({id: index, label: `${token.reason}`, shape: "box"});
    } else if (token instanceof Init) {
    } else {
      console.assert(false, "Unknown token: ", token);
    }
    ++index;
  }

  return { nodes: nodes, edges: edges };
}

1.5 Tying it together

These are globals, which constitute a poor-man's API, using the browser console

var parsed = null;
var linked = null;
var RM = null;
var result_regs = null;

This finds the closest element to source of tag-name target above/below (if direction is less than/greater than 0 respectively).

function closestHTMLneighbour(source, direction, target) {
  while (source != null && source.tagName != target) {
    while ((direction < 0 ? source.previousElementSibling
                          : source.nextElementSibling) == null) {
      source = source.parentElement;
      if (source == null) return null;
    }
    source = direction < 0 ? source.previousElementSibling
                           : source.nextElementSibling;

    if (source.tagName != target &&
        source.hasChildNodes() && source.children.length > 0)
      source = direction < 0 ? source.lastElementChild
                             : source.firstElementChild;
  }
  return source;
}

function log_fn (output, cause) {
  let d = document.createElement("div");
  output.prepend(d);
  let empty = true;
  return text => {
    if (empty) {
      empty = false;
      d.innerText = `Log [${cause}]:\n`;
    }
    d.innerText += text;
  }
}

function run_rm(btn) {
  let textarea = closestHTMLneighbour(btn, -1, "TEXTAREA");
  let output = closestHTMLneighbour(btn, 1, "BLOCKQUOTE");
  console.assert(textarea != null, "Couldn't find textarea above button!");
  console.assert(output != null, "Couldn't find output below button!");
  let ruler = document.createElement("hr");
  output.prepend(ruler)

  parsed = parse(textarea.value, log_fn(output, "Parse"));
  linked = resolve(parsed, log_fn(output, "Link"));
  RM = (...regs) => evaluate(linked, log_fn(output, "Trace"), regs);
  result_regs = RM();

  let regs_output = document.createElement("div");
  regs_output.innerText = "Register values on completion:\n";
  output.prepend(regs_output)
  for (let [reg,val] of Array.from(result_regs).sort()) {
    regs_output.innerText += `${reg}: ${JSON.stringify(val)}\n`
  }
}

function plot_rm(btn, height) {
  if (height === undefined) height = `${Math.round(window.innerHeight * 0.85)}px`;
  let textarea = closestHTMLneighbour(btn, -1, "TEXTAREA");
  let output = closestHTMLneighbour(btn, 1, "BLOCKQUOTE");
  console.assert(textarea != null, "Couldn't find textarea above button!");
  console.assert(output != null, "Couldn't find output below button!");
  let ruler = document.createElement("hr");
  output.prepend(ruler)

  parsed = parse(textarea.value, log_fn(output, "Parse"));
  linked = resolve(parsed, log_fn(output, "Link"));

  let graph_output = document.createElement("p");
  output.prepend(graph_output);
  let graph_options = {
    height: height
  };
  let machine_graph = new vis.Network(graph_output, to_vis(linked), graph_options);
}