Newbiefuck

Newbiefuck is an accidental derivative of the brainfuck language. It has the same commands, except that [ is a NOP:

Command	Description
>	Move the pointer to the right
<	Move the pointer to the left
+	Increment the memory cell under the pointer
-	Decrement the memory cell under the pointer
.	Output the character signified by the cell at the pointer
,	Input a character and store it in the cell at the pointer
[	Do nothing
]	Jump back to the matching [ if the cell under the pointer is nonzero

Newbiefuck has had many implementations, as the majority of first-time brainfuck implementers accidentally implement it instead at some point in the process, thus the name.

This happens because [ is the only brainfuck command that requires some kind of parsing in order to find a matching point in not already seen code, something which many first time implementers stumble on.

Examples

Example Program

++++++++[->+++++++++<]>.----[--<+++>]<-.+++++++..+++.[-][++++[->++++++++
<]>.[--<+++++>]<--.[--->++++<]>---.<++++++[>+++<-]>.<+++++++[>---<-]>.++
+++++.----.[-]<]++++++++++.[-]

$ bf hi.b
Hello
$ newbiefuck hi.b
Hello Newbie
$

Basic truth machine

,[.]

Basic cat

+[>,.<]

Computational class

It can be shown that Newbiefuck is Turing-complete by the following translation to Bitwise Cyclic Tag, which is implemented here.

We assume without loss of generality that the queue always has at least 2 elements, and that the source program does not end with a 1, to simplify the construction. The queue is represented on the tape in the following format:

0 0 0 X Y ... 0
      ^

X represents the frontmost element in the queue, Y the element after it, and the rest of the queue follows as consecutive cells terminated by a 0. In the queue, bits are stored as 1 and 2 instead of 0 and 1, so that they can be differentiated from the zeroes at either end of the queue. We will start the main loop with the tape head on the first element in the queue and return there after each instruction. For example, if the data string is simply 1, the code begins >>>+[.

Translating the 0 command is trivial: it becomes [-]>, which clears X and shifts the queue forward on the tape so that Y is the new tape head. The 10 and 11 commands are more complicated, because it is conditional: we must test the value of X to know whether or not we should push to the end of the queue, which is difficult with only do-while loops. We solve this by manipulating the tape so that the loop that pushes to the queue will serve two purposes: the first time it runs, it will set up a condition for itself, and the second time it runs (if it does at all) it seeks to the end of the queue and pushes to it.

This manipulation is done as follows, with simple move and copy loops (which work normally even in Newbiefuck):

>[-<<<+>>>] move Y out of the way
<[-<+<<+>>>]<[->+<]> copy X

The new state of the tape:

X Y 0 X 0 ... 0
      ^

We have stored X and Y in a safe place behind the queue, and replaced Y's original cell with a 0, which we will refer to as the "hole". Now we have the code to push (or not push) to the queue. The behaviour of the loop on its first run, while the hole is there, is written first, while the behaviour on the second run follows in parentheses.

[
  [>]    seek to the hole (seek to the end of the queue)
  +      plug the hole (push the value)
  [<]>-  seek back to X and decrement it
]

This is the code for 10. If the bit to be pushed is a 1, ++ should be used instead of +.

After this code loops a single time, the state of the tape will be as follows:

X Y 0 (X-1) 1 ... 0
      ^

Since X has been decremented, its value is either 0 or 1, so this causes the desired branching. If it is 0, the loop ends; but if it is 1, the loop will run again. Without a hole, it will seek all the way to the end of the queue and append a value there, decrementing X a final time in the process. This leaves the tape in a convenient state, with a new value possibly pushed to the end:

X Y 0 0 1 ... 0
      ^

Now only trivial operations are necessary to restore the saved values of X and Y again, leaving the tape ready for another instruction.

>-              erase the 1 (should be >-- if translating 11 and not 10)
<<<<[->>>+<<<]  restore X
>[->>>+<<<]     restore Y
>>              move forward to front of queue

Translating each command this way in sequence and putting a loop around it yields a Newbiefuck program that emulates the behaviour of any desired Bitwise Cyclic Tag program, which shows that the language is Turing-complete.