Writing a programming language: A stack implementation for DVM01
As with past code examples, I’m mainly going to show pieces of code along with some commentary. Also, the complete source is at my github archive, so all you need is a browser and/or node.js installed to play around :)
Okay, so what about the design decisions? Here’s what I want / need in a stack implementation:
- (Just as a reminder): A stack consists of a piece memory that acts in a first in, last out way. The thing you stored last will be the first one when fetching an item. Traditionally, those functionalities are called “push” (to save), and “pop” (to read). Additional functionality might inspect the stack without altering it, but we’re not goint that far today.
- When having a stack, the need for certain fixed addresses for certain fixed purposes diminishes. You can just push/pop on the stack if you need something. This lead to the idea that even the entry points to the push/pop code itself should not be fixed. In other words, I don’t want to change all the code only because I had to insert something above those two “functions”. Note that I’m trying hard not to actually call them functions just yet - They’re just pieces of code that do something, then return. The ideas behind this might lead to some actual working subroutine implementation later on.
- Using the stack access functionality should be as easy as possible. With a bit of address mangling, I think I have figured out a way that is as close as it gets with the current VM implementation. More on that in a minute.
Data structure
So, with these things in mind, I set about setting up some data structure for the stack implementation. What we need are a few things:
- Some pointers to the push and pop code, so we don’t have to know the actual entry point for the push/pop
- A counter for the current stack size - so we know where to put the next value in a push, or where to fetch the last one in a pop.
- Some pre-allocated space for the stack’s content
- A placeholder for passing a value to be pushed, and a place to fetch the freshly-popped value
- A pointer for the return address: Where should the program continue after the stack operation?
With a stack size of 10 elements, this leads us to the following code:
START #0 - program counter, as usual NOP #1 - placeholder for push/pop value NOP #2 - pointer to return address NOP #3 - pointer to PUSH code NOP #4 - pointer to POP code NOP #5 - stack position pointer NOP #s - Stack bottom ( 0) NOP #s - Stack ( 1) NOP #s - Stack ( 2) NOP #s - Stack ( 3) NOP #s - Stack ( 4) NOP #s - Stack ( 5) NOP #s - Stack ( 6) NOP #s - Stack ( 7) NOP #s - Stack ( 8) NOP #s - Stack ( 9) NOP #s - Stack (10)
The START statement is, as noted in my first post, always used as the program counter. This feature will be used and abused quite a lot later on.
The next few lines are pretty simple - we initialise some of the above values. No further comment needed I think:
# Initialize stack data SET 2 0 # return address pointer SET 5 5 # position pointer
Registering subroutines
Now before we continue with the actual implementation of the push/pop functionality, I want to explain in more detail how we “register” the push/pop operations in our placeholder registers. There’s some trickery involved that might not be obvious at first. But let’s have a look at the relevant code:
# Begin PUSH code. Assume the following facts: # * @1 is the value to be pushed # * @2 is the address to continue after pushing # * @5 points to the memory cell at the top SET 3 @0 # start address of next instruction is now in @3 ADD 3 6 # move start address past this add instruction and the JMP of the next line ADD 0 21 # JMP well below the PUSH code's body. Only executed once, while initializing!
Okay, so what is going on here? We want to register our code so it can be accessed via a jump to the address in register 3. But in the first run, we don’t want to actually execute the push code, so this leads us to a bit of a problem: We need to store the start address of the actual code, then skip to the next “subroutine” definition and do the same there.
The above code does exactly that: The first SET statement stores the current address in the register 3. If we would jump to that address now, we would end up at the statement after the SET. That would be great, but we still need code to skip over the implementation, so this address is not correct yet. The next line takes care of that: It adds 6 to the pointer in register 3 - it will now point to the first instruction after the lines shown above (Both add statements are 3 memory locations big each). The next ADD statement is the the skipping functionality. It abuses the fact that address 0 is the program counter to do a relative jump forward.
After this, the “body” of the actual implementation follows. If it wouldn’t fit into 21 memory positions, we could simply increase our ADD statement a little bit. To make the implementation a wee bit simpler, I’ve added another gadget: After the implementation, I’ve added a couple of NOP statements, so we won’t have to count the statements in the implementation very precisely: Instead, we can just jump a good bit ahead and land within a construct called a “NOP slide”, which we already know:
NOP # Some NOPs to catch the relative jump above (ADD 0 21) NOP NOP NOP NOP # That should be enough...
Depending on how sure you are about the length of your “subroutine”, you can make that slide a bit longer or shorter, and count the operations from the VM debug output.
Calling the code, and some unholy magic to make the “user” happy
Now that we have all the tiny bits in place, we’re almost ready to actually move on to the implementation. But there’s one requirement we haven’t covered yet: Simplicity of the call! The absolute minimum possible in DVM01 would be the following code:
SET 1 1 # first value SET 2 @0 # Return address JNZ @3 1 # Call PUSH
As you remember from above, memory location 1 is our exchange placeholder: When doing a push, we put the value there before running the push code, and when doing a pop, the popped value will be there after the call.
The second SET statement tells the function where to continue, and the last JNZ statement is a tiny hack to make a non-conditional jump to the push code. But WAIT! Wouldn’t the push code return to the JNZ statement after executing? Yes, it would, therefore creating an infinite loop, which would sooner or later start to overwrite our program, which would then inevitably fail.
This is where the unholy magic comes in: After the actual implementation of the operation, we have the following snippet of code:
ADD 2 3 # UNHOLY MAGIC! Increase return address by 3 registers. Syntactic sugar! JNZ @2 1 # Jump back to the return address
Just before jump back to the return address, we increase that address by 3. Since we know that the JNZ to call the code uses three spaces, this causes the jump back to land exactly where it should - namely at the next instruction after the JNZ of the caller.
The implementation
Okay, you were brave enough to continue all the way down here. And what do I have for you now? Behold, the full implementation of the push and pop routines, of course with some comments in the code, as usual. All the important bits of magic and trickery have been explained, so I think it’s enough to just show you the code.
# Begin PUSH code. Assume the following facts: # * @1 is the value to be pushed # * @2 is the address to continue after pushing # * @5 points to the memory cell at the top SET 3 @0 # start address of next instruction is now in @3 ADD 3 6 # move start address past this add instruction and the JMP of the next line ADD 0 21 # JMP well below the PUSH code's body. Only executed once, while initializing! ADD 5 1 # Increase stack pointer SET @5 @1 # Store value to top of stack ADD 2 3 # UNHOLY MAGIC! Increase return address by 3 registers. Syntactic sugar! WRITEC 43 # Write "+", for logging PUSH WRITEI @1 # Log PUSH value WRITEC 10 # Newline after logging JNZ @2 1 # Jump back to the return address NOP # Some NOPs to catch the relative jump above (ADD 0 12) NOP NOP NOP NOP # That should be enough... # Begin POP code. Assume the following facts: # * @1 is the value to be pushed # * @2 is the address to continue after pushing # * @5 points to the memory cell at the top SET 4 @0 # start address of next instruction is now in @4 ADD 4 6 # move start address past this add instruction and the JMP of the next line ADD 0 24 # JMP well below the POP code's body. Only executed once, while initializing! COPY 1 @5 # Fetch stack top into register 1 SET @5 0 # Clear stack content - just for debugging purposes SUB 5 1 # Decrease stack pointer by 1 ADD 2 3 # UNHOLY MAGIC! Increase return address by 3 registers. Syntactic sugar! WRITEC 45 # Write "-", for logging POP WRITEI @1 # Log POP value WRITEC 10 # Newline after logging JNZ @2 1 # Jump back to the return address NOP # Again, some NOPs to catch the jump NOP NOP NOP NOP
That’s it! Now, you have a stack that can store 10 elements - and if you need more, just insert some NOPs at the right place. No ugly re-finding the entry points, and usage of the stack is fairly easy as well!
To do a push, the following instructions do just that:
SET 1 2 # Store value "2" SET 2 @0 # Return address JNZ @3 1 # Call PUSH
And a pop is even simpler:
SET 2 @0 # Return address JNZ @4 1 # Call POP
So, there you have it! If you’re interested, the code is at my github repository.
Lessons learned
I’ve learned quite a bit while implementing (and debugging) this stack implementation. Mostly, I learned what’s missing most in my current VM, and so, a few ideas have arosen for the next VM - DVM02. You might find a few hints towards this in the git repo, but I’ll write another blog post about it when the time comes.
The most sorely missed things is definitely an aliasing functionality, so you can give a name to any given address. If implemented right, these could be used as jump targets. Another thing are macros - the ability to give a certain piece of code a name, and then reuse it.
These two features would probably already be enough to implement a complete stack-based virtual machine that would allow some comfortable procedural programming. I’m going to have to think about it for a bit, but I believe that it should be possible to only change the parser/compiler, without even touching the VM itself! Well, we will see…