Writing a programming language: First programs for DVM01

April 06, 2012

Anything that can be programmed must have a few things: Documentation, and a few examples. This being about programming, it’s tradition to write a “Hello World” program first. So without further ado, let’s have a go:

Hello World!

This program just writes out that well-known message to it’s output, then quits:

START

WRITEC 72
WRITEC 101
WRITEC 108
WRITEC 108
WRITEC 111

WRITEC 32

WRITEC 87
WRITEC 111
WRITEC 114
WRITEC 108
WRITEC 100
WRITEC 33

END

Pretty simple, huh? The numbers are just the ASCII (and, because of Javascript’s inner workings, also Unicode) representations of the letters, space and interpunction of the message. The only really important thing is this: The program MUST start with the “START” statement, and it MUST end. Why?

Intermission: VM guts

As described in the previous article, the VM doesn’t have any registers - it just uses a well-defined memory section for certain types of work. As a program gets executed, the VM needs to know which statement comes next. Traditionally, this information is stored in a place called the “program counter”. I didn’t want to make an exception to the above rule for this important piece of information, so, by convention, the program counter lives at the first location in memory, which is the address 0.

Now - The program, after having been parsed, is also loaded into memory. To not complicate it any further, the program starts at address 0. OOOOppps! When loading the program into memory, we just overwrite the program counter! Damn. This is how the START command came into life.

If you need any space to store temporary values, you can employ a technique called “NOP slide” to reserve memory at well-known locations that you can later use. Our next code example shows what I mean.

Implementing the Fibonacci series

Some interesting “problem” that shows up in many programming courses and examples is the generation of the Fibonacci series. Simply put, it’s a series of numbers, where each number is the sum of the previous two.

The series starts with the numbers 1, 1. The next value, then is the sum of both, 2. Summing up 1 and 2, we get 3. Repeat that with 2 and 3, and you get 5, and so on.

There are many ways to implement a program that outputs that series, most people prefer a recursive way (which however is not very efficient if you’re not careful). Our VM doesn’t support recursive function calls, or rather, we would have to write a lot of code to emulate it, so we take another route: Since the series only ever cares about the previous two numbers, it’s of no use to carry all the others with us - so we don’t.

Here’s the implementation. I’ve added plenty of comments, so you should get a rough idea of how it works.

# First, initialize a nop slide for "registers". Note that
# the first one is required, as address 0 is used by the
# VM to store the program counter.

START # 0: contains program counter
NOP   # 1: first accumulator
NOP   # 2: second accumulator
NOP   # 3: helper
NOP   # 4: loop counter
NOP   # 5: stores loop jump address

# Initialisation: Address 4 is used as a countdown loop counter.
# Set it to a higher number to get more fibonacci numbers :)
SET 4 30 

# Initialize accumulators 1 and 2
SET 1 1
SET 2 1

# Be clever: store the program counter to address 5 as a loop "marker".
# This way, we don't have to worry too much about changing the program -
# the marker will adjust accordingly.

SET 5 @0

# The loop begins here.

SET 3 @1  # Use the helper "register", put the value of accumulator 1 in it
ADD 3 @2  # Add value of accumulator 2 to the helper
WRITEI @1 # Output the value in accumulator 1
WRITEC 10 # Newline - we don't have explicit text support
SET 1 @2  # Add content of accumulator 2 to accumulator 1
SET 2 @3  # Set new sum of both accumulators in accumulator 2.

# Decrease iteration counter.
SUB 4 1

# Jump to beginning of the loop, unless the counter is zero.
# This uses the clever "marker" from further up to know where
# to jump.

JNZ @5 @4

# If the counter was zero, the jump didn't happen, and the program
# must end.

END

Okay, that’s two examples on how to program for the DVM01. I’m trying to come up with some more advanced programs next, implementing the Sieve of Eratosthenes for example, or implementing Subroutine calls. Those will be covered in another article, so stay tuned :)