Synacor Virtual Machine.

Just recently I came across the ‘Synacor VM’ challenge. The problem is an interesting exercise in implementing a virtual machine using a supplied architecture definition and then running the VM using the given binary file as input. When run the program is an adventure type game which many people have completed but I have, so far, resisted that temptation. So here’s the spec.

 

I had a couple of attempts at this – in Haskell – and the main thing I learnt from this was…

Yes, the Haskell type system is very expressive and allows for a sophisticated modelling of a problem. However too much can lead to unnecessarily complex programs and a very confused developer!

At first I tried ‘modelling everything’ – registers, memory, stack, program counters, ops, instructions…. and so on! I really couldn’t see the wood for the trees.

So, after deleting everything and then using git to restore – I didn’t want to type in all the ops again! I tried a much simpler representation.

  • Memory – uses a Map – ok it was flattened to a list occasionally but that’s ok.
  • Stack – a simple list will do fine.
  • Extracting operations and parameters out of memory – no, you don’t need Parsers. Pattern matching is perfect for this and simple.
  • Registers – yes a Sum type seemed a good idea – but really registers are just part of the memory (Map).

The operations, Push, Pop, etc I modelled as a Sum type each with 0, 1, 2 or 3 Word16s as appropriate. That way the ‘parsing’ is a simple pattern match using the operations code and the number of expected parameters. Here’s what I mean.

Then extracting successive operations from memory was just a matter of applying a patter matching function on the memory (in list format) at a location given by the program counter.

Here’s the parse function.

The stack, memory etc I represented like this:

 

Running the program – ignoring details of initialisation – resolved to ‘running’ the cpu until the Halt instruction is found. i.e.

and the function executeNextOp gets the next instruction from memory using the parseOperation function and then executes it.

There are a few helper functions for reading/writing memory etc. and type conversions but the whole program is around 250 lines and is shown below.

When the code is run a number of self tests are executed so some feedback is given on correctness and once all the self tests complete correctly this dialog appears πŸ™‚

 

== Foothills ==
You find yourself standing at the base of an enormous mountain. At its base to the north, there is a massive doorway. A sign nearby reads “Keep out! Definitely no treasure within!”

Things of interest here:
– tablet

There are 2 exits:
– doorway
– south

What do you do?

Overall I really enjoyed this problem especially once I’d realised that less is often more when modelling a problem.

The code is here on Github.

And thanks for reading!

 

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top