Nothing to see here, just goofing around with virtual machines.

Just a silly dual-stack arithmetic machine.

Yep. Like I said, just goofing around with some of the concepts.

The virtual machine has an 8-bit stack for operators, and a 16-bit stack for values. The instructions may be grouped into two segments: control and operators. The control instructions are

STOP

end execution

IMM

push a 16-bit integer onto the stack

DO

pop the top two values from the stack, pop an operator off the operator stack, and apply the operator to the two values. The result is pushed back onto the value stack.

The operators are

• ADD
• SUB
• MUL
• DIV

These operators all act on 16-bit unsigned integers.

The VM accepts a single binary file on the command line, and will run it. A typical run looks something like

$ ./kamvm compiled/prog1.bin 
Loading 13 byte program.
Starting VM.
> 20
OK

The program size is reported. If the program is loaded successfully, the VM is started, executes the program, and reports the result after the > prompt. If no error occurred, an “OK” is printed, and the VM exits. Typically, if the VM runs into errors, it will dump core with a call to abort(2) to facilitate debugging.

The syntax is extremely simple: everything should be enclosed in parenthesis, and normal numbers are used. The simplest program is

(2 + 2)

As a consequence of the way this is implemented, Lisp-style notation is also possible.

• source/notlispy.sm

((2 * 3) + (10 / 2))

• source/lispy.sm

(+ (* 2 3) (/ 10 2))

If no source file is given on the command line, the compiler will read source from standard input; the write stage happens when an EOF (for example, C-d) is encountered.

Rudimentary syntax checking is provided through use of a pair of counters, the active values and active operators counters. When a value is encountered, the active value counter is incremented; similarly, when an operator is encountered, the active operators counter is incremented. When a DO is encountered, the compiler will check to ensure that there is at least one active operator and at least two active values present. If there are, compilation continues and both of these counters are decremented. The values counter is decremented only once due to the fact that, after applying the operator to the two values, the VM pushes the result back onto the stack. Despite popping two values, one value is pushed back onto the stack, giving a net loss of only one value. When the compiler reaches EOF in the source file, it warns the user if there are any operators left on the operator stack or if a single value (including no values) are left on the value stack.

At this stage, the compiler is still in a rather primitive state, and illegal programs are likely still permitted.

• Convert the compiler to lex/yacc.

Eventually, I’d like to design and build register machines, symbolic machines, and some combination of the two. I’ve got lots of ideas, and limited time for hacking, though.

I was watching the Algorithms 1 lectures (from the Coursera class) for this week, and the professor mentioned dual-stack machines. That put a bug in my head that I needed to get out.