Over the weekend I finished the homework assignment for the “Theory of Computation” chapter of Computer Science: An Overview, Ninth Edition, by J. Glenn Brookshear. Brookshear defines a very minimal programming language called Bare Bones, in which variables may contain arbitrarily large non-negative integers. The only operations available are:
- clear var; — set a variable to zero
- incr var; — increment a variable
- decr var; — decrement a variable, unless it is already zero
- while var not 0 do; <statement list> end; — loop
- copy var1 to var2; — introduced for convenience
Bare Bones is universal, in that it can compute any function that can be computed by a Turing machine. In fact, it would be universal even without the clear and copy statements, as those can be synthesized from the remaining statements. Needless to say, writing programs in this language can be tricky. I wasn’t confident that the programs I wrote for the homework exercises were correct, and decided to write a Bare Bones interpreter to check them. It’s released under the GPLv3.
I wrote example Bare Bones programs to compute factorials and fibonacci numbers, and they are included with the interpreter.