A Pathological Challenge: Prime Programming in NULL

Todays pathological language is actually in the form of a challenge for you. (Isn't that
exciting?) It's a very clever numerical programming language in the vein of Conway's href="http://scienceblogs.com/goodmath/2006/10/prime_number_pathology_fractra.php">Fractran,
called NULL. The author of NULL describes it
as a reaction to 2 and 3 dimensional languages in the Befunge tradition; NULL is a 0
dimensional language - a program is just a single point. It's quite clever in its way; the only
problem is that is that there's only one example program written in it. So the challenge is
to see if you can actually come up with some implementations of interesting programs.

A program in NULL is a single very large number. The way that it executes is dependent
on its prime factorization, as in Fractran. But NULL is more expressive than Fractran; it's
a real programming language with input and output.

In a NULL program, you actually have 3 queues containing bytes of which one is the
current queue at any particular time, and two registers that can contain arbitrarily large
integers. The queues are named by number: 0, 1, and 2; and the registers are named X and Y. When the
program starts, the X register contains the program, and the Y register contains the number 1, all
three queues are empty, and the current queue is 0.

Program execution in NULL is a simple loop:

while (X != 0 and X != 1) do
   let op be the smallest prime factor of X.
   X = X/op
   Y = Y×op
   execute opcode op
end

Every prime number is interpreted as an opcode. Since there are only 14 opcodes, the way that it
works is that the opcodes cycle over the primes - so, for example, both 2 (the first prime) and 47 (the 15th prime) are the same opcode. The opcodes are:

2: Next

Switch the current queue to the next, wrapping around from 2 to 0.

3: Previous

Switch the current queue to the previous, wrapping around from 0 to 2.

5: Output

Output the character from the front of the current queue.

7: Input

Input one character, and replace the byte at the front of the current queue with it.

11: Subtract

Subtract the byte at the front of the current queue from Y. (If the result is less than 0,
then set Y to 0.)

13: Add

Add the byte at the front of the current queue to Y.

17: AddY

Add the lowest-order byte of Y to the byte at the front of the current queue.

19: RotateRight

Remove the byte at the front of the current queue, and append it to the tail of the next queue.

23: RotateLeft

Remove the byte at the front of the current queue, and append it to the tail of the previous queue.

29: Discard

Remove the first byte from the current queue and discard.

31: Enqueue

Enqueue the lower-order byte of Y to the tail of the current queue.

37: Drop

If the selected queue is empty, or it first byte is 0, then find the smallest prime factor p of X, set X = X/p, and set Y = Y×p.

41: Swap

Swap X and Y.

43: Halt

Halt

If you look at the instructions, you should be able to see that it's Turing-equivalent. You can do loops, because each instruction is added to Y as it's removed from X - so by swapping X and Y using Swap, you repeat a loop iteration. You can skip instructions - effectively doing a conditional, using Drop. You can modify the program, adding or removing instructions, using Add and Subtract. And the queues clearly provide unbounded storage. So we've got an effective computing system here. Just an incredibly devious one.

The one sample program is a hello world. It's the number:

15360939363786950397128283933599538624
89217432048303485700335501579138988589
76126298703504031567456769368158187308
36908075646108694411913908753341542249
057283074613678144889367

There's an implementation of NULL in Python available here.

So - anyone up to implementing something simple like a Fibonacci series generator, or a factorial program?