Abacus Machine Simulator

Abacus machines, sometimes called register machines, are abstract machines that form a mathematical model of computation. They are equivalent to Turing machines, so any possible Turing machine algorithm can be implemented on an abacus machine and vice-versa. An interesting alternative to Turing machines, to be sure, but only really used in academia.

While in Brown, I was introduced to these machines in a class taught by Prof. Richard Heck. For class credit, I designed a language to describe abacus machines and wrote a compiler, runtime, and debugging tools for it. It includes features like:

• Built-in testing, with where blocks at the end of each function definition. Tests are automatically run on each compilation, and tests are marked as passed or failed.
• Static analysis is performed, detecting some types of infinite loops, unexitable functions, and unreachable lines.
• Runtime analysis detects recursion (which is not permitted by the abacus machine model), and loops without exit conditions.
• A debugger with the ability to:
  • step into, through, over, and out of functions,
  • halt execution at user-set breakpoints, and —
  • inspect (and change!) the current stack frame.
• A compiler that can take a set of functions, each its own abacus machine, and compiles it down to a single abacus machine with no dependencies. The ability to reduce any program without recursion into a single program with a finite number of states is an important theoretical property, and this compiler provides constructive proof of that property.
• Graphviz output.

The compiler can be run in a browser and comes with an implementation of division from first principles. Take a look!