Source: Duet

Part 1: Create a virtual machine with the following instruction set:

• snd X plays a sound with a frequency equal to the value of X
• set X Y sets register X to Y
• add X Y set register X to X + Y
• mul X Y sets register X to X * Y
• mod X Y sets register X to X mod Y
• rcv X recovers the frequency of the last sound played, if X is not zero
• jgz X Y jumps with an offset of the value of Y, iff X is greater than zero

In most cases, X and Y can be either an integer value or a register.

What is the value recovered by rcv the first time X is non-zero?

Another virtual machine! These are my favorite. 😄

This time, assuming that we’ll use it again¹, I’m going to create an open class and use decorators to actually create the methods. It’s a bit weird to do it this way, but it’s nicely flexible:

class VM(object):
    vms = []

    def __init__(self):
        '''Initialize a VM.'''

        self.tick = 0
        self.pc = 0
        self.registers = collections.defaultdict(lambda : 0)
        self.output = []
        self.messages = queue.Queue()

        self.id = len(VM.vms)
        self.registers['p'] = self.id
        VM.vms.append(self)

        self.state = 'ready'

    @staticmethod
    def register(f, name = None):
        setattr(VM, name or f.__name__, f)
        return f

    def value(self, key):
        '''If key is a number, return that number; if it's a register, return it's value.'''

        val = self.registers.get(key, key)
        try:
            return int(val)
        except:
            return val

    def __call__(self, code, daemon = False):
        '''Run the given code with the given VM.'''

        if daemon:
            t = threading.Thread(target = self, args = [code])
            t.daemon = True
            t.start()
            return t

        try:
            self.state = 'running'

            while 0 <= self.pc < len(code):
                self.tick += 1
                cmd, *args = code[self.pc]
                getattr(self, cmd)(*args)
                self.pc += 1

        except StopIteration:
            pass

        self.state = 'exited'

        return self.output

There are a few bits that we don’t need just yet (not until part 2). The important bits are the register function and the __call__ function (specifically the getattr in the main loop).

In the register function, we have the ability to add attributes to the VM class that any objects created from it will have access to. So for example:

@VM.register
def set(vm, x, y):
    vm.registers[x] = vm.value(y)

@VM.register
def add(vm, x, y):
    vm.registers[x] += vm.value(y)

@VM.register
def mul(vm, x, y):
    vm.registers[x] *= vm.value(y)

@VM.register
def mod(vm, x, y):
    vm.registers[x] %= vm.value(y)

That means that if we have a VM object, we could theoretically call any of those methods on it:

>>> vm = VM()
>>> vm.set('a', 2)
>>> vm.set('b', 5)
>>> vm.mul('a', 'b')
>>> dict(vm.registers)
{'p': 1, 'a': 10, 'b': 5}

Alternatively, implementing the __call__ function in a class means that objects of that class can be called as if they were functions. In this case, I will run code provided to them this way:

>>> vm = VM()
>>> vm([
...     ('set', 'a', 2),
...     ('set', 'b', 5),
...     ('mul', 'a', 'b'),
... ])
[]
>>> dict(vm.registers)
{'p': 2, 'a': 10, 'b': 5}

I don’t know about you, but I think that’s pretty cool. 😄

The remaining three functions (for part 1) are:

@VM.register
def snd(vm, x):
    vm.output.append((vm.tick, vm.value(x)))

@VM.register
def jgz(vm, x, y):
    if vm.value(x) > 0:
        vm.pc += vm.value(y) - 1

@VM.register
def rcv(vm, x):
    if vm.value(x) != 0 and vm.output:
        print(f'Recovered {vm.output[-1]}')
        raise StopIteration

I’m specifically using StopIteration since that’s the Pythonic way of breaking out of a generator².

That’s all we need to run part 1:

code = [line.split() for line in lib.input()]

vm = VM()
vm(code)

We don’t have to output anything since the implementation of rcv above does it for us. Coolio.

But that’s not everything I want to do here. Supposedly, the snd instruction is playing a note. What does this actually sound like?

Well, we can use midiutil to write MIDI files, lets see what it sounds like:

class VM(object):
    ...

    def write_midi(self, filename):
        '''Write all of the output of the program so far as a MIDI file.'''

        import math
        import midiutil

        if self.output:
            offset = self.output[0][0]
        else:
            offset = 0

        clock = lib.param('clock')

        midi = midiutil.MIDIFile(1)
        midi.addTempo(
            0,          # Track
            0,          # Start time
            120,        # Tempo (BPM)
        )

        for tick, frequency in self.output:
            # https://en.wikipedia.org/wiki/MIDI_tuning_standard#Frequency_values
            pitch = int(69 + 12 * math.log(frequency / 440))
            midi.addNote(
                0,      # Track
                0,      # Channel
                pitch,  # Pitch of the note (midi data values)
                (tick - offset) / clock, # Tick to add the note
                1,      # Duration (beats)
                100,    # Volume (0-127)
            )

        with open(filename, 'wb') as fout:
            midi.writeFile(fout)

There are a few complications / tuning factors here. Specifically, we are arbitrarily choosing 120 BPM for the tempo along with parameterizing how fast the virtual CPU can run compared to that tempo. Also, the output values appear to be raw frequencies, so we need toconvert them to MIDI notes before playing them using text=“this formula” page=“MIDI_tuning_standard#Frequency_values”.

Writing this out for part 1, we can generate the output as a MIDI file. Using one of various programs³, we can convert this to an MP3:

It’s … not quite as interesting as I expected, but kind of haunting. Mostly I think it’s just cool that it’s playing something that was completely generated by running a ~40 line assembly language problem. That’s just cool⁴.

Part 2: Rewrite the following two instructions:

• snd X plays a sound with a frequency equal to the value of X and send X to the other program’s message queue
• rcv X read a value from this program’s message queue (send by the other program’s snd command)

Initialize a special register p to 0 for the first VM and 1 for the second one.

Eventually, the two programs will deadlock (both will be waiting for the other to send a value). When that happens, how many times has the second program (p = 1) send a value before this happened?

Okay. That’s interesting. The main two challenges here are implementing the message queues and detecting when a deadlock has occurred.

@VM.register
def snd(vm, x):
    if not hasattr(vm, 'send_count'): vm.send_count = 0
    vm.send_count += 1

    index = VM.vms.index(vm)
    VM.vms[(index + 1) % len(VM.vms)].messages.put(vm.value(x))

    vm.output.append((vm.tick, vm.value(x)))

@VM.register
def rcv(vm, x):
    vm.state = 'waiting'

    value = vm.messages.get()
    if value == StopIteration:
        raise StopIteration
    else:
        vm.registers[x] = value

    vm.state = 'running'

Essentially, we’re going to use the messages objects we built into the simulations earlier in order to send messages along with a class variable vms on VM that will keep track of all VMs running. In this case, there are only two, but this code is currently flexible enough for arbitrarily many VMs running together. In that case, each would send all values to the VM that was initialized next after them with the last sending to the first.

For the second requirement (deadlocks), we’re going to keep track of the current VM state. While the VMs are running, vm.state will be running, but while we are waiting to receive a value from the message queue, they will go to waiting. If we detect that both end up in waiting at the same time (plus some time to avoid just waiting for the VMs to realize the other has sent a message), we have a deadlock.

while True:
    if vm0.state == vm1.state == 'waiting':
        time.sleep(1)
        if vm0.state == vm1.state == 'waiting':
            vm0.messages.put(StopIteration)
            vm1.messages.put(StopIteration)
            break

For this to work, both VMs have to be in the waiting state twice a second apart. This isn’t perfect, since they could both be waiting on Python’s GIL to be doing something else at both times, but in practice I didn’t have that problem. This worked. We’ll also specifically use StopIteration again, this time in the message queues to tell the VMs to stop executing.

After that, we wait again for both to exit and print out how many times p = 1 sent a value:

while True:
    if vm0.state == vm1.state == 'exited':
        break

print(vm1.send_count)

And just like last time, we can generate MIDI files for each program (vm0, vm1) and then play them together as a single MP3:

Turns out, it takes rather a while for those to settle down (around an hour at the given tempo). There are some interesting features too. Starting around five minutes in, you can see vm1 run down a scale and them vm2 follow it:

This happens more and more often as the song goes on with less noise before it and longer descents until finally the noise goes away completely and the two programs deadlock:

That’s kind of neat.

The problem is… it’s not correct.

The problem is that I’m using locking queues for my messages and not advancing the VMs clock while they are waiting. So if vm0 sends a value at tick=100 but vm1 already ran rcv back at tick=50, the timestamps between the two machines are off by rather a bit. Instead of using the same tick values, it will always take exactly 1 tick to rcv. How do we fix that?

One option would be to not use a blocking get but rather to rewrite rcv to rcv a value if there is one to receive and do nothing (but not wait) if there isn’t (not advancing the pc either, so it will rcv again the next tick). This will be a lot closer, but it’s still not correct, since the two machines clocks don’t have to run at the same speed. Instead, they will each run as quickly as they can, so that rcv may be waiting anywhere between 0 and 50 ticks in the example above.

Another option would be to tie the VMs together even more so that I specifically execute one instruction on each VM per tick. This is actually the one I went with. What we want to do is add a second mode to the __call__ function:

def __call__(self, code, daemon = False, generator = False):
    '''
    Run the given code with the given VM.

    If daemon is True, spawn a background thread to run the program in.
    If generator is True, return a generator that yields once per tick.
    '''

    try:
        self.state = 'running'

        while 0 <= self.pc < len(code):
            self.tick += 1
            cmd, *args = code[self.pc]
            getattr(self, cmd)(*args)
            self.pc += 1

            if generator:
                yield

    except StopIteration:
        pass

    self.state = 'exited'

    return self.output

All that really changed here is that if we tell the __call__ function to return a generator, it will yield on each tick. This does force the client running the virtual machines to manually advance the generator, but they know what they’re getting into, so it works.

Next, we need to tweak the rcv function to not block:

@VM.register
def rcv(vm, x):
    vm.state = 'waiting'

    try:
        value = vm.messages.get(block = False)
        if value == StopIteration:
            raise StopIteration
        else:
            vm.registers[x] = value

        vm.state = 'running'

    except queue.Empty:
        # Run the rcv command again next tick
        vm.pc -= 1

By specifying block = False, the get will raise a queue.Empty exception, which we can catch. If we do, that means we need to try to rcv again on the next tick, so undo advancing the pc.

Finally, the main loop needs to run one tick on both VMs in step:

while True:
    next(generator0)
    next(generator1)

    if vm0.state == 'waiting' and vm1.state == 'waiting':
        break

Once nice thing here is that the deadlock detection is much easier to implement.

If we run it through, we see that we get exactly the same answer as before. We can then generate the corresponding two MIDI files (vm0, vm1) and the new (much better sounding) MP3:

It really does sound like the two machines playing a duet with one another, bouncing back and forth in some parts and actually playing together in others. It’s just as long as before (which makes sense), but sounds much better.

It took quite a bit longer to write up the MIDI half of that and this post then it did to originally solve the problem. But I think it was worth it. 😄

$ python3 run-all.py day-18

day-18  python3 duetvm.py input.txt --part 1    0.10424304008483887     Recovered 3188
day-18  python3 duetvm.py input.txt --part 2    1.1558499336242676      7112