FML. A silly virtual machine.

Introduction

I have spent this summer designing and writing a virtual machine that no one will ever use. I have written roughly 6000 lines in an assembly language that no one else will ever learn. And it has been absolutely awesome.
This machine has been named FML for reasons described in the background section. The machine has been designed to be easy to implement and easy to use with a simple but powerful instruction set.
As of now the machine has been implemented in Java and I have also written a surprisingly usable assembler for the machine.

In this post only gives a brief explanation of how the machine works.

And here is a little demo I wrote for it:

I Hate this demo. I’m so ashamed of it.The music is not played by the VM! This is the first demo I have ever written and i know its not that good. I  also decided to have the demo done by the start of the semester so I had to scratch some plans for cooler effects. If you want to you can go to its pouet site and down vote it 🙂

Background story

Well. Once upon a time not that long ago I decided to write a virtual machine as the final project in my CS 101 class. So me and two of my friends sat out on the ridiculous quest to write a working VM from scratch in SML.
Now this project was slightly overkill and my friends where utterly confused and had little to no idea what I was talking about. We had to write the whole thing in SML which is a slightly pointless and annoying functional programming language and thus the name (for obvious phun based reasons). And if anyone of you are one of those “Everything looks better in a functional language” you can go sod yourself. Anyhow by the time the due date was up we had a fully functional assembler , a slightly working VM implementation and a ridiculous long report.

I was still quite happy with the general design of the VM and I had this crazy notion that i was going to write my own programming language as a neat little summer project. But i needed some platform that the language was going to compile to. So i decided to redo the project in Java and “pimp” the general design of the VM and the ISA in order to make it slightly less sucky.

When i first tried to do his thing I started out by just writing a Java implementation of the VM and use the old  SML assembler. I wrote the VM in accordance with the documentation we had written as part of the project. This turned out to be a bad idea since the ISA we had specified in the documentation only vaguely corresponded to the actual output of the assembler (luckily for us no one bothered to read the entire 37 page report). So i decided to fix those issues in the assembler. So I opened up the SML code for the assembler and immediately closed it again since the code was completely unreadable. So i decided to build the VM using the output of the assembler as the specifications instead. Halfway trough I gave up on this idea since i realized that it was stupid and that the assembler was crap and the ISA had some shortcomings. So i decided to redesign the ISA from scratch and write a complete java implementation of both the VM and the assembler.

And that is the story of how the worlds most pointless VM came to be.

General

The entire FML machine has a retro feel to it and is fairly minimalistic. This is partially due to the fact that the only real experience i have with writing assembly code is for the C64 and I also feel that modern CPU architectures are just not as pretty as they used to be. They literally just try to squeeze in as much crap possible onto the chip. This implementation of the FML machine works with 32 bit signed integers(mostly due to java not supporting unsigned integers.)

Another reason is that the main goal of this VM is that it should be fun to work with. This is why I have tried to keep the instruction set to a minimum but at the same time trying not to sacrifice usability for minimalism. I want people who try to do stuff with the FML machine (and by people I mean only me.) to be able to just start of writing stuff as quickly as possible without having to read trough a bunch of documentations and other annoying crap.

The architecture.

The architecture is very straight forward. FML only consists of a few basic components:

• Two general purpose register ( referred to as X and Y )
• One general purpose stack ( referred to as S )
• One program counter (containing a jump stack)
• And a RAM memory ( wittily referred to as the RAM )

A very general flowcharty picture of the VM

The FML has 16 IRQ lines. Each of which has a corresponding memory address ( the addresses is implementation dependent) and when the machine receives an interrupt request it will do a subroutine jump to the address stored in the memory location corresponding to what IRQ line is being used.

As of now the machine uses no virtual addressing due to the fact that I have not had any need for it as of now. But it could easily be implemented.

ISA

The ISA is as previously mentioned designed to be easy to use and to understand.

Each instruction is made up by 16-bits. The word lengths can be either 16bit, 48bit or 80bit each instructions may use up to two 32bit constants. The memory is not word aligned.

In each instruction the bits in the instruction word corresponds to the following:

• bits 0-3: The first argument
• bits 4-7: The second argument
• bits 8-11: Specifies whether or not this is an Operation instruction and in that case which operation.
• bits 12-15: Specifies whether or not this is an Action type instruction and which sort of action it is.

Each of the the four bits specifying each of the two arguments are decoded as following:

• bits 0-1:
  00: The Stack
  01: X register
  10: Y register
  11: Numeric constant
• bit 2:
  0: Use argument as value
  1: Use argument as address
• bit 3:
  0: This argument is used
  1: This argument is not used.

Whether or not the argument is to be read from or written to depends upon the instruction itself.

A slightly more detailed description of the ISA can be found here.

Operation type instructions.

The operation type instructions are the instructions that does stuff with things. Such as adding, subtracting, comparisons and such. All operations apart from the increment (INC) and decrement (DEC) always pushes its result onto the stack. All operations takes at least one argument.

Action type instructions

These are the operation that does stuff to the VM. Such as moving data, jumping, conditional branches and this is actually pretty much all of what they do. FML has two different types of conditional branches: The skip operations and the jump on stack operations. The skip operations are a bit weird and i don’t really know why i decided to implement conditional branching like that but it has turned out quite nice. The skip operations work by taking two arguments and if the condition (depends on the instruction) holds the machine will skip the next instruction. The conditional skip method of doing branches have actually been a fairly good design choice. The skip branching works great for branches which only require one condition to be tested which the majority of all the branches in the programs I have written have been. There is also another way of doing conditional branching. It is the jump on zero, jump on one, subroutine jump on one and subroutine jump on zero. They execute the jump if the top element of the stack is either one or zero depending on the instruction these are slightly more neat looking especially when the condition is more complex.

The Assembler

In conjunction with the actual virtual machine i also wrote an assembler which is fairly trivial but quite usable. The assembler has a small number of nice features such as the handling file inclusions in a nice way avoiding conflicts, the ability do declare arrays and giving somewhat sensible error messages.

Below follows a short example of assembly code for a subroutine which puts a pixel on the screen and does bounds checking for the coordinates .

// x

Hopefully you can understand what the code does. arguments starting with $ are references to a memory address. So for example : MOV  $std.screen.color  $s
moves what is at the memory address std.screen.color (which will be resolved to a number by the assembler) to the address which is at the top of the stack.

Lines starting with # are labels and they will be resolved into the address of the operation immediately following it. Lines starting with a @ are pointers/variables they will an assigned an arbitrary address. A declaration of a pointer can be augmented with a plus sign and a number such as @name+100 which would tell the assembler to not use the 100 addresses after the address assigned to name. This is used to create arrays.

I will not go into any more detail on the operation of the assembler. You can spam me if you want more info on how it works in more detail.

Conclusion

In contrast to most of my other projects this endeavor has been a great success. Both the assembler and the VM work really well and I have had no need to do any major changes to the original design. But the most important thing is that the FML machine is actually easy to write code for. The code is easy to read and journey from idea to code is not that long at all.It has been really interesting to learn to program a language of my own design. No naming or indentation standards. No one to ask for help. No libraries. As of now I feel that the FML machine and its assembler is definitely in a good enough state for me to start writing a language for it without having to worry about any shortcomings of the target machine. There are some minor issues with the java implementation of FML mostly concerning its performance. The only real thing left to do before starting work on my own language is to write a good disassembler and runtime monitor.

Before you all start complaining about the flaws and obvious stupid design choices I just want to make it clear that i have no real experience with any of these kind of things.

If you have any questions just fire away! All the code for the project is available at https://github.com/TheGrandmother/jFML.

A silly self-learning asteroids-like game.

I have for the last month or so been working on a neat little self learning asteroids game. The game itself is very basic. There are a few ships flying around in 2D trying to shoot each other. Which in and of itself is not super exciting but the neat part is that the ships learn how to behave without the need of any human intervention. This is accomplished trough the use of a genetic algorithm.

All the source code(Java) for this project can be found here.

Lets start with the basics.
First of all the space in which everything happens is a closed rectangle. So when things collide with the walls they either die or bounce. There are only three kind of objects: Ships or Crafts as they are referred to in the code, Missiles and Asteroids. Since the ships are the objects where the cool things happen i will focus mostly on them. I have also found that including asteroids yield less cool results so we wont discuss them or use them in any example.

The Ships

Lets go in to some detail of how the ships work.

Input

The only input that the ship receives is what the ship can see which is three cones: one cone looking straight forward, one to the left and one to the right. And in each of these cones only one thing can be chosen as input. Even though several objects can reside in the cones only the object that has the highest priority will be chosen. In practice this is fairly boring since we only have ships and we let the missiles have 0-priority so they get ignored. So the ship can at any one time see at most three different objects.
For each of the objects seen only three attributes are recorded: The type of the object, its heading(relative to the observer) and weather or not it is within firing distance.

The game in debug mode.

The AI

The AI is very simple in its construction. It simply just maps a input to a decision. Each decision is just a set of actions such as move,accelerate,fire etc. This is represented as a hash-map using the input as keys and the decision as values. When the ship encounters a input it has not previously seen a random decision will be mapped to that input. Each ship will have its own AI.

The Genetic Algorithm

So, on to the fun part. The genetic algorithm here is the thingamagoop which makes the ships AI get better(or it’s at least supposed to do that). This is done in a fairly trivial way. The algorithm chosen for this project uses tournament selection, random crossover and a fitness function  defined as the total score(the score accumulated trough it entire life) of the ship divided by the age of the ship. The age of the ship is the number of times it has been in a tournament.

Lets go trough the algorithm step by step.

1. First a set of ships is created. This set will be referred to as the phenotypes.
2. Then a series of “warm-up rounds” are played. These are played in order to fill the decision hash-map with some entries before the actual tournaments get started.
3. A tournament is started.
4.        Chose N distinct ships from the set of phenotypes.
5.        Have these ships battle each other in several battles of epic proportions. With each these N ships partaking in only one battle.
6. From these N ships. Find the two ships with the highest fitness and the one ship with the lowest fitness.
7. Let the two best ships get on with some sweet sweet love making. The resulting offspring will have a combination of the two parents decision-map. This is accomplished trough a random crossover.
8. Sacrifice the crappiest ship in public to set an example for the other ships and let the new offspring take its place.
9. Return to step 3.

Conclusion

Well.This project has turned out pretty crappy. For several reasons. First of all, i suck at coding. This project has been full of serious bugs. Especially really dumb things in the code which makes me wonder why my parents didn’t just say “No hes going to be shit at coding. Throw it away” when I was born. Also the genetic algorithm has been really annoying. I have had a lot of problems getting it right. Both due to bugs in the code and other stupid stuff such as poor choices of fitness functions etc.

Lessons learned:

• I suck at programming.
  This was something I already knew but this project has really shown me the extent of my incompetence.
• Be careful when you copy paste your own code!!
  Several serious bugs in the program has been due to me copy pasting some loops and such and forgotten to change all of the details.
• Don’t do humpty-dumpty half assed refactoring.
  A lot of bugs has been introduced trough me saying “ouu I should change all of this to do things better” and only changed some of that and
  ended up breaking things.
• Fix ugly code when you realize that it’s ugly and not later when you have forgotten how that ugly code actually works.
• Never underestimate how annoying genetic algorithms can be.  You might have to tweak seven thousand different parameters to get good results.

And here is a little video.

It looks cooler than it is.