Today’s challenge at /r/dailyprogrammer asks to implement an assembler for a small virtual machine. It has only 16 mnemonics which in unique opcodes (each instruction can have multiple forms for if they’re accessing memory or literals), so it’s a simple virtual machine indeed. As a challenge, you’re supposed to write an interesting program (I actually wrote a virtual machine as well to test them). As an even better challenge, we’re supposed to prove that Tiny is Turing complete. Well, let’s get to it!

read more...

It’s been rather a while since I’ve worked out a Programming Praxis problem, but they posted a new one yesterday, so now seems as good a time as any. The problem is relatively simple:

Given a linked list, swap the kth node from the head of the list with the kth node from the end of the list.

Since all lists in Scheme are linked lists, that part seems easy enough. To make the problem a little more interesting however, I’m going to work it out in a purely functional manner: no mutation.

read more...