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 andX!= 1) do letopbe the smallest prime factor ofX.X=X/opY=Y×opexecute opcodeopend

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?

AI guess it would be fun to have a number which, when expressed as a NULL program, factored itself.

FlakyDamn, 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.

Anonymoushuh, executing the number only gives me ‘hello, ‘

arensbThe 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.

Mark C. Chu-Carrollarensb:

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.

Blake StaceyClearly, then, we need to modify the language. We could call the new version “NULL-Prime”. . . or, perhaps, “nullity“?

Nikolas CoukoumaEvery 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.Craig PenningtonPartially 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.)

AnonymousThe 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…

AnonymousI 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.

Xanthir, FCDHmm… 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.

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