A Pathological Challenge: Prime Programming in NULL

Leave a reply

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 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?

0 thoughts on “A Pathological Challenge: Prime Programming in NULL”

  2. Flaky

    Damn, that’s a tricky language. I’m a bit sceptical about it being turing-equivalent.
    Can Add and Subtract really manipulate the program in Y with sufficient control over the result, as the previous instruction always keeps being multiplied to Y and you can only add or subtract a number between 0 and 255 to Y?
    It even seems to be quite tricky to map state machines to this language.
    I think I’ll give up.

    Reply ↓
  4. arensb

    The one thing I don’t care for is having to figure out which prime a given number is (i.e., having to know that 47 is the 15th prime). If I were designing this, I would’ve used
    p = 2op0 * 3op1 * 5op2 * 7op3 * …
    ignored the actual primes and simply used the exponents directly as opcodes.

    Reply ↓
  5. Mark C. Chu-Carroll

    arensb:
    Yeah, that’s probably how I would have done it too… Made it more like Fractran with opcodes so that you could do input and output.

    Reply ↓
  7. Nikolas Coukouma

    Every time I run the example program it only prints “Hello, ” without a newline or anything (tested Python 2.3, 2.4, and 2.5). Combined with the interpreter looking fugly and limiting, I’m not inclined to do anything with this at the moment.

    Reply ↓
  8. Craig Pennington

    Partially denullifying hello:
    initially, qindex = 0, q = [[],[],[]], X=(the above number), Y=1
    3: Previous, qindex = 2
    3: Previous, qindex = 1
    3: Previous, qindex = 0
    17: AddY, Y=459 (=3^3 * 17), q[0] = [203] (203 = 459 mod 256 i.e. the low byte of Y)
    31: Enqueue, Y=14229, q[0] = [149,203]
    73: AddY, Y=1038717, q[0] = [149, 72] (72 = (203 + 1038717) mod 256)
    127: Output, 72 is ASCII for ‘H’
    Wow. Y=131917059, which would be the “Display an ‘H'” program. I’m going to drink now.
    BTW, I once decided to see what the Goedel number of the undecidable statement looked like. This reminds me very much of that effort (which succeeded — in base 13, I computed all the non-zero digits and computed how many zero digits there there were in the middle, but only after cheating on the numbering method using Tarski and using Peano with exponentiation — the method pretty much stolen directly from Smullyan’s Oxford guide on Goedel, chapters 1-3.)

    Reply ↓
  9. Anonymous

    The complete “Hello, world!” message only appears if you add more primes to plist in nullrun.py. The last prime “executed” is 2357 so you will need to add all the primes up to that number.
    Get a better prime number generator here:
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/366178
    The nullrun.py program evaluates the program given it, so it is entirely possible to write python code in that program to generate the nth prime without writing down the explicit prime. Then all you would have to do is multiply the numbers at the end. In a sense, you could execute the opcodes directly…

    Reply ↓
  10. Anonymous

    I don’t see how to effectively control looping, since a lot depends on the prime number (modulo 256) at that point. Utterly confusing. I can’t even figure out how to do multiplication of arbitrary numbers sanely, unless you keep generating noops (rotating the queue back to its starting point, or pushing and popping random crap on/off the queues) just to get the number you want in order to get the opcode AND the correct number to multiply by. Obviously there is such a number, but the end result of all those “space-filler” primes multiplied together is going to be huuuuge.
    I think I’ll join Craig Pennington for that aforementioned drink.

    Reply ↓
  11. Xanthir, FCD

    Hmm… I think I could probably do something with this. It doesn’t seem too difficult once you get the hang of loop operations. Past that, it’s just a queue based language. Simple and annoying to work with, but not confusing.

    Reply ↓
  12. Michael Ralston

    The trick I see is loop control, and getting useful values to places, since addition gets messy when you’ve been multiplying.

    Reply ↓

Leave a Reply