What is Vulcan?

Vulcan is an imaginary computer: it doesn't (yet) exist as a real chip, but there are a couple emulators which allow other computers to run Vulcan programs. Vulcan programs are a sequence of numbers stored in memory; each number is an instruction and the computer runs them in sequence to manipulate the state of the machine. Some memory locations in Vulcan are tied to (emulated) devices like a monitor, mouse, keyboard, and mass storage, so reading or writing those locations allows Vulcan to interact with the outside world.

Writing programs as a sequence of numbers is obviously very convenient and easy, but I've written some tools anyway: the first is an assembler which will translate textual names of instructions into the numbers they correspond to (as well as do some other bookkeeping). Because even writing assembly language can be tedious, there is also a high-level language called NovaForth that runs on Vulcan itself, and a different high-level language which runs on a normal computer but compiles programs which run on Vulcan.

Vulcan is a stack machine

The model of computation Vulcan uses is called a stack machine, because instructions manipulate a stack of values in memory and most data transfer in the machine is done through that stack. There are 42 Vulcan instructions, each of which might consume values from the data stack or leave other values on top of the stack. Each instruction can also take a single optional argument, which is pushed to the stack before the instruction runs.

Stack machines are a very common model for imaginary computers, although most hardware computers are register machines instead, for efficiency. Vulcan's main design goal is simplicity, over speed, though, so it's appropriate here. It's also very common to emulate a stack machine using a register machine, and translating between the two computation models isn't hard.

First program

Here's a short example program: 

push 2
push 3
add
hlt

Going line-by-line through this program: the first instruction is a push instruction with an argument of 2. The push has no actual effect on the machine (in fact, it's another name for the instruction nop, for "no operation"). But, the fact that it has an argument means that the argument will be added to the top of the stack, so, after this line, the stack contains a 2. The second instruction is the same, and pushes its argument on top of the 2, so after that line the stack contains 2, 3. The next instruction, add, has no argument, but the function of the instruction is to remove the top two values from the stack and push their sum in their place: now the stack contains 5. Finally the hlt instruction (short for "halt") tells the machine to stop running.

Why halt? Because Vulcan memory starts out initialized to random values, like all memory: without this, we would continue to run, executing random memory contents as instructions, forever (or until we executed a combination of instructions that caused the machine to enter an error state and reset).

Instruction encoding

In memory, this program is represented by six bytes: two bytes each for the push instructions, one byte each foo add and hlt. Vulcan instructions are always between one and four bytes long: 

Instruction     Argument bytes
     |          |            |
     v          v            v
  |------##|--------|...|--------|
         ^
         |
     Number of
   argument bytes

The higher six bits of the first byte determine which instruction it is, and the lower two bits determine how many bytes the argument is: 0-3 bytes, because a standard memory cell in Vulcan is 24 bits (3 bytes) long. The instruction push 2 is therefore two bytes long, 0x0102: 

00000001 00000010

The instruction 0 is push (or nop), it has one byte of argument, and that one byte is the number 2. The entire program above is: 1, 2, 1, 3, 4, 116.

Because any instruction can take an argument, which is treated as a push, we can shorten this program by one instruction: 

push 2
add 3
hlt

Any time there's a push followed by an instruction with no argument, we can remove the push and move its argument to the following instruction. This makes Vulcan programs somewhat easier to understand than otherwise, and also saves some memory; this program is only five bytes long: 1, 2, 5, 3, 116

Memory layout

Properly, each of these programs should start with a directive telling the assembler where they should go in memory. The default location is fine for these examples (they will run the same way no matter where they are) but we can place them somewhere with a .org (short for "origin") directive: 

.org 0x400
push 40
mul 40
hlt

The default Vulcan memory map looks like this:

The first 256 bytes of memory are reserved for I/O control registers: reading and writing these may affect devices like the screen, serial device, keyboard controller, etc. Not all are used, but you shouldn't use them in your program because someday they might be.

The next 768 bytes are the stack: since Vulcan uses a word size of 24 bits, stack cells are 24 bits long, which means the stack is 256 cells long. It can be moved around or made smaller or larger using the setsdp instruction, but that’s where it starts.

Immediately after the stack is location 1024, or 0x400: this is where your program is initially loaded, and when the machine is powered on (or reset) this is where it will start reading and executing instructions.

Everything after that is available for use by your program, up to a usual total memory size of 128k... Although for programs that use video, a large portion of that memory is used by the video display.

The call stack

The Vulcan stack isn't just one stack, there are two: the basic one we've already seen is the data stack, growing upward from location 256, but there is also a call stack (sometimes called a return stack or R stack) growing downward from location 1023. Here’s an example program that uses both stacks: 

.org 0x400
push 2 ; Push a couple values to the stack
push 3
pushr ; Move the one on top to the other stack
pop ; Remove the 2…
popr ; Move the 3 back
hlt

This puts a couple values on the stack and then deletes the one second-from-the-top, by first moving the top value to the other stack to get it out of the way. The pushr and popr instructions move the top value from the data to the call stacks and back again, respectively; pop removes the top value from the data stack.

Just having a second stack for temporary storage is somewhat handy, but the actual purpose of the call stack is the call and ret instructions: when you execute a call Vulcan stores the address of the next instruction in the call stack and starts running code at a different address (whatever is on top of the stack). A ret does the opposite; pops an address from the call stack and goes back to running code there. We can use call and ret to make a subroutine and call it repeatedly: 

.org 0x400
push 1
call triple
call triple
call triple
hlt

triple:
mul 3
ret

There are a few new concepts in this snippet, so we’ll tackle them one-by-one: first, the line triple: is called a label; it doesn't correspond to an instruction, it just tells the assembler to give a name to a particular location in the program so we can refer to it elsewhere. Whatever the memory address of the next instruction is, whenever we write triple in our program, it will be replaced with that address.

The next instruction is mul 3, which does exactly what it sounds like: just like add, mul pops two values and pushes their product.

Which leaves the call and ret lines: we're pushing a 1 and calling triple three times; each call will jump the execution to the mul 3 line, then to the ret line, which will jump to the location after each call. After tripling a 1 three times we're left with a 27 on the stack and we halt.

In terms of a higher level programming language, triple could be a function that takes a single number as a parameter and returns that number times 3: 

function triple(x) {
  return x * 3
}

Branching and conditionals

The true power of any computer is its ability to change its operation based on its input: to make decisions; do one thing with one piece of data and a different thing with another. Vulcan has instructions to do this: brz and brnz are short for "branch if zero" and "branch if non-zero," and will move to running a different part of the program depending on whether the top-of-stack value is zero or not. Here’s an example program: 

.org 0x400
push 1
call collatz
push 2
call collatz
hlt

collatz:
dup
mod 2
brz @halve
mul 3
add 1
ret
halve:
div 2
ret

The Collatz Conjecture is an unsolved problem in mathematics: suppose you take any positive integer and, if it’s even, divide it by two; if it’s odd, multiply it by three and add one. Repeat this process indefinitely and it will eventually enter a loop going from 1 to 4 to 2 back to 1. But, there is no known proof that this is true, there might be other numbers that form Collatz loops and don’t return to 1.

The first part of this program is pretty basic: call the collatz function on the numbers 1 and 2. Where it gets interesting is what that function does: first it uses dup (short for "duplicate," pushes another copy of the top-of-stack to the stack) and mod 2 (short for "modulus," returns the remainder when two numbers are divided) to tell whether the number is odd or even: an even number will leave a 0 on the stack, and odd number a 1.

Then we use brz to branch to halve if there's a zero (if the number is even). It's important to note the @ in front of halve, the brz instruction takes a relative address, and it's a common mistake to leave off that operator and instead use an absolute address.

Relative vs absolute addresses are a simple concept that's easy to forget about: an absolute address is just the address of a given instruction in memory; every instruction has one absolute address, and instructions like call and jmp use this number. A relative address is the address of another instruction minus the absolute address of this instruction; you can think of it as "move this many bytes forward or backward." Just like remembering labels, the assembler will calculate relative addresses for us, if we prepend an @ on to the name.

Why use relative addressing? To allow for position-independent code: if we used absolute addressing everywhere, our program would only work when loaded into memory at a particular location. Eventually we'll want to write an operating system that loads programs from disk at arbitrary locations and runs them; since the program won't know where it's loaded, it will need to use relative addresses to refer to parts of itself.

Whether it actually goes to the other branch or not, brz consumes the zero-or-one from the stack. If it was a 1, then we just continue on this branch: multiply by 3, add 1, return. If it was a 0, then we skip those three lines, jumping straight to halve, and divide by 2 and return.

We can also use this to write loops: 

.org 0x400
push 1
loop:
dup
add 1
dup
lt 10
brnz @loop
hlt

This will leave the numbers 1-10 on the stack: we start with a 1, duplicate it and increment it, and then check if the result is less than 10 (lt, "less than," consumes two numbers and pushes a 1 if the second is less than the first, 0 otherwise). If it is, we branch back to the loop label and do it again; otherwise halt. Note that we have to dup the number before the lt 10 check because lt consumes both numbers: we need a copy to save on the stack and a copy for lt to consume!

Variables and memory

So far all our programs have used the stack to store their data, but of course we have 128k of memory we can store whatever we want in. Here’s a program that puts some of that to good use: 

.org 0x400
push 1
loop:
dup
loadw sum
add
storew sum
add 1
dup
lt 101
brnz @loop
pop
loadw sum
hlt
sum: .db 0

Starting with the last line first: the .db directive is short for "define byte" and, like .org, doesn't represent an instruction: it just causes the assembler to put three bytes containing whatever value we want into the program. It needs to go at the end because if it were at the start Vulcan would try to execute it as code (which in this case would actually be safe, because three bytes of 0 is just three nop instructions, but still).

Having reserved a memory location for our variable and given it a name (the label sum) we can do a loop much like the previous example: load the value from sum, add the top of the stack to it, store it back into sum, increment the top of the stack, repeat for every number between 1 and 100. Finally throw away the now-useless counter variable and load sum one last time, leaving the sum of the numbers 1-100 (5050) on top of the stack.

Vulcan has four instructions for reading and writing arbitrary memory:

Most variables in Vulcan are one word long; reading and writing single bytes is usually used for manipulating individual characters in strings.

Assembler macros

Certain structures in assembly are very common to write, like an if / else condition or a loop. In order to prevent errors writing these the Vulcan assembler provides several macros that generate these common structures for us. Importantly, these aren't new instructions, they're commands to the assembler to generate sequences of instructions (and single-use labels) for us.

The simplest of these is the #if macro: 

.org 0x400
push 10
#if
push 1
#else
push 2
#end
hlt

When the assembler encounters an #if it generates a brz to the corresponding #else or #end. Just like a conditional in a high-level language, #if constructs can have #else branches (which are executed if the top-of-stack is false) and can be nested inside one another. There is also an #unless macro that acts the same as #if but inverted: it only executes its body if the top-of-stack is 0: 

.org 0x400
push 0
#unless
push 1
#else
push 2
#end

The other macro construct is #while, which is used to create loops: 

.org 0x400
#while
loadw counter ; Load the loop counter…
lt 101 ; and check if it’s still 0..100
#do
loadw counter ; Increment the sum by the counter
loadw sum
add
storew sum
loadw counter ; Increment the counter by 1
add 1
storew counter
#end
loadw sum ; Finally load the sum and stop
hlt
counter: .db 0
sum: .db 0

The loop is divided into two sections: one condition between the #while and #do, and a body between #do and #end. The condition is executed first, and only if it leaves a nonzero on the stack (which is consumed) is the body executed. Then the condition is executed again, and so on. Just like #if, these can be nested (and nested inside conditionals and conditionals inside them), and there's an inverted version called #until: 

.org 0x400
#until
loadw counter ; Load the loop counter…
gt 100 ; and check if it’s still 0..100
#do
loadw counter ; Increment the sum by the counter
loadw sum
add
storew sum
loadw counter ; Increment the counter by 1
add 1
storew counter
#end
loadw sum ; Finally load the sum and stop
hlt
counter: .db 0
sum: .db 0