Qdeql

Qdeql is an esoteric programming language devised by Scott Feeney that provides a single queue of bytes as the only form of memory available to programs.

Instructions

Instruction		Description
=	NEXT	Dequeue a byte and enqueue it again
-	DEC	Dequeue a byte, subtract one (wrapping around), and enqueue it
\	BEGIN	Dequeue a byte and skip to the instruction after the corresponding END if the byte is zero; otherwise, enqueue the byte again, followed by two zero bytes
/	END	Go back to the corresponding BEGIN
&	INPUT	Read a byte from stdin and enqueue it (0 for EOF)
*	OUTPUT	Dequeue a byte and write it to stdout

If the queue is empty, any instruction that would normally use a value from the queue instead uses 0.

Computational capability

Qdeql is Turing-complete, as brainfuck with a fixed number of unbounded non-negative cells can be reduced to it. (See Collatz function for a proof that 3-cell brainfuck is Turing-complete.) A Haskell program is available for performing such a translation, as well as some translated examples.

Qdeql was originally thought to be unusable for computation due to the difficulty of accessing a particular byte more than once when the queue is of arbitrary size. However, Ørjan Johansen observed that the code \\/\// will skip over (dequeueing and re-enqueueing) an arbitrary length string of nonzero 0 0 triples terminated by a 0, with the mild inconvenience that the terminating 0 at the end will be deleted.

Factory

A fundamental building block in the n-cell brainfuck to Qdeql translation is the "factory" construction of the following table. It consists of two alternating patterns and a subprogram such that when the subprogram is applied with either pattern at the beginning of the queue, it is deleted while four zeros followed by the other pattern are appended to the queue.

An alternative subprogram leaves out the final 255 0 0 in the resulting pattern, instead absorbing it from whatever is to the pattern's right.

With our brainfuck cell representation, the zeros are used to replenish those consumed by other actions, while the absorption feature allows a quicker decrement operation.

The factory patterns/programs can conceptually be divided into three subregions:

• The rightmost producer region (which flips between two phases on each cycle) either creates or absorbs value 255 cells, passing them on to
• The decrementer region, which gradually decrements non-zero cells, and when they reach 2 passes them on to
• The stretcher region, which decrements non-zero cells down to zero, while adjusting the intermediate zero cells so that a total of four zeros are passed on leftward per cycle. (Four zeros are just enough to allow us to increment a brainfuck cell in a single cycle.)

Factory

	Stretcher	Decrementer	Producer
Queue layout	1 0 0 0 1 0 0 2 0 0	2 3 0 0 3 4 0 0 ... 254 255 0 0 0	255 0 0 255 255 255 0 0 255 0 0 255 0 0 255 0 0
			0 255 0 0 255 0 0 255 0 0 255 0 0 255 255 255 0 0
Production program	- = = = \ / = - = =	\ - \/\/ /	\ = = \ / \/\ / - = / \ = \/\ / - = \/\/\ / / \ / \/
Absorption program			\ = = \ / \/= = = = \/\/= / \ = \/= = = = \/\/= \/\/ \ / / ===

Cell layout and command translation

Once initial setup is finished, the queue consists of the patterns for the brainfuck cells, conceptually arranged in a circle.

Each brainfuck cell consists of three regions in order: its factory, its data (encoded as repetitions of 255 0 0), and its zero padding. Occasionally an additional scratch region is temporarily inserted before the data region of the "current" cell.

The main part of the Qdeql program consists of a sequence of regional actions: a factory action is followed by a data action, which is followed by a padding action, which is followed by a factory action for the next cell in the queue, etc. At each point in the Qdeql program we always know the type of region being passed through, as well as the relative position of the current brainfuck cell in the queue.

With the exception of < and >, which simply change which relative position in the queue is considered the "current" brainfuck cell, the translation of a brainfuck command consists of a sequence of actions to be applied to particular regions of the current brainfuck cell. This frequently requires first inserting NOP/default actions to navigate to the current cell and the correct region, and then inserting the substantial action.

The NOP/default actions work as follows:

• The data action moves the data section to the end of the queue, except that the final zero is deleted.
• The padding action deletes the 0 0 0 padding.
• The factory action replenishes the four zeros deleted by the previous actions, and moves the factory section to the end of the queue.

Sometimes several consecutive brainfuck commands can be translated without navigating the queue between them. E.g. the actions generated by -[+>-]+ all act on consecutive regions in the queue.

The I/O commands are more complicated than the others, as they need to convert between unary representation and bytes (using a temporary scratch region), and so these take more than one regional action to translate. This is done in order of row, then column/region.

brainfuck cell

	Factory	Scratch	Data	Padding
Layout	Factory		255 0 0 255 0 0 ... 255 0 0 0	0 0 0
NOP/Default	Production program		\ \/\/ /	\/\/\/
>	No action, adjust in which cell next action is performed
<	No action, adjust in which cell next action is performed
+				- = =
-	Absorption program
[			\ \/\/\ \/\/ /
]			/
.				- = =
		= - \/	\ \/= \ \/\/ /
		- =	\ \/\/ / /
		\ =
		-\/\/-
		/ *
,			\ \/\/\ \/\/ /
	Absorption program		/ &
		\
		- \/\/		- = =
		/

Initial setup

The following table shows how to build n brainfuck zero cells from a 0 + 7n times 255 pattern. Cells are built "in parallel", sharing the main loop of the first one.

After this initial setup the queue will be correctly positioned for a data action.

Growing cells

First cell	Each additional cell
=\/
-\/\/\/=\--=========\/	-\/\/\/=\--=========\/
\-\/\/ \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/	\-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/
-\/\/ \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/	-\/\/ \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/
/ -==- -== \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/	\/ -==- -== \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/
==== \/=-== \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/	==== \/=-== \-\/\// \==\/\/\/-=/ \=\/\/-=\/\/\// \/\/

Example structure

The following table shows, top to bottom, left to right, the structure of the Qdeql program translating the brainfuck program ++++[->++++++++<]>. (which prints a space). Non-default parts of commands are marked.

BF commands	Cell 1			Cell 2
	Factory	Data	Padding	Factory	Scratch	Data	Padding
	Initial setup of 2 cells
+		\\/\//	-==	Production		\\/\//	\/\/\/
+	Production	\\/\//	-==	Production		\\/\//	\/\/\/
+	Production	\\/\//	-==	Production		\\/\//	\/\/\/
+	Production	\\/\//	-==	Production		\\/\//	\/\/\/
[	Production	\\/\/\\/\//	\/\/\/	Production		\\/\//	\/\/\/
->+	Absorption	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
+	Production	\\/\//	\/\/\/	Production		\\/\//	-==
<]>; some of .	Production	/	\/\/\/	Production		\\/\//	-==
Rest of .	Production	\\/\//	\/\/\/	Production	=-\/	\\/=\\/\//	\/\/\/
	Production	\\/\//	\/\/\/	Production	-=	\\/\///	\/\/\/
	Production	\\/\//	\/\/\/	Production	\=	\\/\//	\/\/\/
	Production	\\/\//	\/\/\/	Production	-\/\/-	\\/\//	\/\/\/
	Production	\\/\//	\/\/\/	Production	/*

See also

• Sceql, a revised version of Qdeql. Considerably more practical and easy to program in than Qdeql.

External resources

• Qdeql implementation and source code