Attack of the Underflow

In principle, the last major piece of Wallace has landed: randomly generating solutions, evaluating them, throwing away bad ones, and generating new solutions through asexual (cloning and mutating) and sexual (using crossover) reproduction.

However, there’s two small problems. First, the stack-based VM is exceptionally prone to crashing. Second, the stack-based VM is exceptionally prone to crashing. Now I know technically speaking that’s only one problem, but I thought it was such a big one, it was worth mentioning twice.[0]

The implementation of the VM, of course, is fine. (At least, there aren’t any known bugs in it.) Rather, the programs that are running within the VM have a tendancy to perform an illegal operation and crash. There are four ways in which a program can crash inside the VM, most common first:

  • Stack underflow: It tries to pop a value off the stack, but the stack is empty.
  • Reserved opcode: It tries to execute an opcode that has no operation associated with it.
  • Stack overflow: It tries to push a new value onto the stack, but the stack is already full.
  • Divide by zero: Because you can’t.

Reserved opcodes could be eliminated by assigning them to something, but the stack underflows are quite problematic. Out of 89 operations the VM supports, only 6 of those don’t try to pop anything off the stack. The vast majority of operations not only need to pop their operands, but they also leave the stack with fewer values on it than it originally had. So naturally, when you’re randomly generating programs to run in the VM’s instruction set, most of the time they’ll trigger a stack underflow and crash.

In fact, the vast majority of programs crash on their very first instruction. Furthermore, in a trial using a population size between 100 and 500 candidate solutions, measuring fitness solely by how many instructions got executed before a crash, even after 50 generations the typical candidate solution still only managed to successfully execute 2 instructions before crashing.

Granted, that’s up from a median of 0, but it’s still not very encouraging. And to keep this in perspective, you’ll obviously want these programs executing more than one instruction per emulated frame, and there’s slightly over 60 such frames per second. Programs that die after only a handful of instructions aren’t going to get anywhere.

(As a side note, however, one candidate solution — one of the initial randomly-generated ones — actually managed to hit the 6000-instruction timeout I arbitrarily set! I wasn’t able to peek into it and see what it was doing, but I strongly suspect it managed to jump into the “uninitialized” portion of memory, which would be filled with 0 bytes, all of which map to nop. Whatever it did, that “gene” never got passed on to anyone else in the population.)

I’m forced to conclude that, despite the stack-based VM being attractive from an implementing-the-VM perspective, it’s quite unsuitable when throwing random code at it. A register-based VM would be infinitely more robust, since the registers the instructions operate on will always be there; just the values stored inside them would change. Alas, this change involves replacing just about everything in the VM except for the mutation engine, which is a large chunk of tedious (but relatively straightforward) coding. But unfortunately, it must be done.


[0] To steal a line from my laptop’s namesake.