Register machine visualiser & emulator

Kovacsics Robert

February 9, 2019

This is a visualiser and evaluator for register machines (the theoretical kind, not a specific CPU). The model is the Lambek/Minsky register machine from 1961 with increment and decrement-with-test instructions.

The example is the same as on slide 30 of the Cambridge Computer Science course, Computation Theory lecture notes.

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

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

Source code

The source code is a bit of a hack currently. It uses a lot of instanceofs where proper OO/Prototyping approaches (e.g. visitor pattern, or dynamically extending the prototypes) would be more OO, 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.

MIT license header

⟨register-machine.js⟩+≡

// 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="module" src="https://kovirobi.uk/tangle/register-machine.js"></script>

and something along this to the <body> tag:

<div id="register-machine-0">
  <textarea cols=60 rows=9>
Init R1 3
Init R2 4

L0: R1- -> L1,L2
L1: R0+ -> L0
L2: R2- -> L3, L4
L3: R0+ -> L2
L4: Halt</textarea>
  <div>
    <input type="button" value="Run"/>
    <input type="button" value="Plot"/>
  </div>
  <blockquote><p></p></blockquote>
</div>

<script type="module">
import { plot, run } from "/tangle/register-machine.js"
let div = document.getElementById("registerm-machine-0")
let textarea = div.getElementsByTagName("textarea")[0]
let output = div.getElementsByTagName("blockquote")[0]
let run_button = div.getElementsByTagName("input")[0]
run_button.addEventListener("click", e => run(textarea, output))
let plot_button = div.getElementsByTagName("input")[1]
plot_button.addEventListener("click", e => plot(textarea, output, '600px'))
// To plot on load
plot(textarea, output, '600px');
</script>

Parsing

Since our input language is very simple assembly, our parser is also just a very simple one, more of a lexer than a full context-free grammar parser.

Somewhat tediously, first we define the tokens, which just hold some state relating to the string they parsed.

⟨register-machine.js⟩≡

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;
}

Then our parse table is just a bunch of regular expressions to try, and which token to construct when it matched. Capture groups supply the arguments.

Apologies that this is so wide, but perhaps it’s still easier to read with scrolling but alignment, than split over multiple lines.

⟨register-machine.js⟩+≡

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)]
    ];

The parser just tries each regex in turn. The sticky regex is there to help us match only from a given index onwards, so that we don’t have to keep slicing the string up for each parsed token.

⟨register-machine.js⟩+≡

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;
}

Resolving labels and trace option

Once we have parsed our assembly, the only analysis step is just resolving labels. We first parse each token in turn, assigning a label to it if it has a preceding label, or likewise for tracing.

The fixup function just looks at the target of the token, and uses numbers as offsets, otherwise maps the target to the line/index the label is on.

⟨register-machine.js⟩+≡

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;
}

Evaluating

Evaluation just proceeds instruction by instruction, optionally printing some trace message. The variable at_pc represents the token currently being executed, PC is a traditional acronym for program counter (from mainframes before personal computers were even a thing).

⟨register-machine.js⟩+≡

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 on ` +
        `line ${at_pc.line}: ${at_pc.str}`);
      throw "PC out of bounds"
    }
    if (++steps > 1000) {
      trace_fn("Done 1000 steps, bailing!");
      break;
    }
  }
  return regs;
}

Drawing the graph

The graphviz dot language is a very handy language to plot graphs (though it is not interactive, so not quite the web experience).

⟨register-machine.js⟩+≡

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;
}

Hence I have made a visualiser for vis-network https://visjs.org as it was also easy to use.

⟨register-machine.js⟩+≡

import { Network } from "vis-network"

function to_vis(output, tokens, options) {
  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 new Network(output, { nodes: nodes, edges: edges }, options);
}

Tying it together

We have a simple log to a div element for user error messages.

⟨register-machine.js⟩+≡

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;
  }
}

Though developer errors are instead logged to the console.

To run, we just find, parse, link, and evaluate.

⟨register-machine.js⟩+≡

export function run(textarea, output) {
  let ruler = document.createElement("hr");
  output.prepend(ruler)

  let parsed = parse(textarea.value, log_fn(output, "Parse"));
  let linked = resolve(parsed, log_fn(output, "Link"));
  let RM = (...regs) => evaluate(linked, log_fn(output, "Trace"), regs);
  let 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`
  }
}

For plotting, we just need to parse and link.

⟨register-machine.js⟩+≡

export function plot(textarea, output, height) {
  if (height === undefined) height = `${Math.round(window.innerHeight * 0.85)}px`;
  let ruler = document.createElement("hr");
  output.prepend(ruler);

  let parsed = parse(textarea.value, log_fn(output, "Parse"));
  let 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 = to_vis(graph_output, linked, { height: height });
}