qoob

From Esolang
Jump to navigation Jump to search
qoob
Paradigm(s) imperative
Designed by User:stkptr
Appeared in 2025
Memory system queue
Dimensions one-dimensional
Computational class Turing complete
Reference implementation see page
Influenced by Cyclic tag, brainfuck, G85, Queuenanimous
File extension(s) .qoob

qoob (/kub/ or /qub/, for queue + loop + based) is a queue-based language with 3 constructs.

  • 0 enqueue a zero at the back of the queue
  • 1 enqueue a one at the back of the queue
  • [...] dequeue a value from the front of the queue
    • If it is one, then execute the contents before looping back around to dequeue and check again
    • If it is zero, skip beyond the matching ]

The behavior of dequeueing an empty queue is undefined. Programs derived from the proof of completeness will never dequeue from an empty queue. A canonical but unnecessary result from dequeueing from an empty queue is to treat the null result as a 0.

By convention, non-interactive input is either prepended as 1 and 0 commands before the program, or the queue is initialized with input. Non-interactive output is done by printing the queue when the program halts.

All qoob programs are qoobular. Canonical qoob programs consist of only 0, 1, [, and ] and are displayed in a font where 0 is a 180° rotationally symmetric circle or oval with a dot, and 1 is a vertical line (also rotationally symmetric), with [ and ] being self-vertical symmetric, but mutually horizontal and 180° rotationally symmetric. A super qoobular program is a qoob program where its canonical representation is horizontally mirror, vertical mirror, and 180° rotationally symmetric. A simple qoobular program is a non-super qoobular program.

It is unknown if super qoob is Turing complete. That is, it is unknown if for any Turing machine, one can produce a rotationally symmetric qoob program which, when given the Turing machine's input encoded with some scheme, halts iff the Turing machine halts.

Computational class

The language is Turing complete by reduction from tag systems. There is likely a simpler reduction from cyclic tag.

This reduction is based on the observation that 0 at the head of the queue executes a while loop (with no nested statements) no times, and 10 executes it once. From there, it uses the general structure of Cook's proof for the completeness of cyclic tag.

To convert an arbitrary 2-tag system with halting symbols and input into the language:

  1. Assign each of the s many symbols an index i, then replace every symbol with a one-hot vector paired with a halting flag, according to:
    • Non-halting symbols begin with a 1 (the non-halting flag), then s zeroes, where the ith zero is replaced with 10
    • Halting symbols are made up of s zeroes
  2. Order the productions by the matching/left hand side symbol's index. Discard the left hand side and wrap the production string with square brackets.
  3. Add s many extra empty productions, each given the index s+1, s+2, etc. These are also wrapped.
  4. Place all of the productions in order into an overarching loop.
  5. Put the encoded input at the very beginning.

This scheme produces a qoob program with identical halting conditions as the tag system, assuming the tag system only halts when encountering one of its halting symbols, and never from queue exhaustion.

This Python function converts 2-tag systems with halting symbols into equivalent qoob programs. The input program must have all symbols have productions. The productions for the halting symbols of course do not matter since the system will halt immediately upon encountering them. 

def two_tag_to_qoob(productions, indata, halting=[]):
    # ensure a consistent order, strictly unnecessary
    ordered = list(productions.items())
    # Construct the one-hot vectors
    lookup = {
        s: "1" + "0" * i + "10" + "0" * (len(productions) - i - 1)
        for i, (s, p) in enumerate(ordered)
    }
    # And the halting symbols
    for s in halting:
        lookup[s] = "0" * len(productions)
    lookup = str.maketrans(lookup)
    # Put the input at the start
    program = indata.translate(lookup)
    # Overarching loop
    program += "["
    # Productions
    for s, p in ordered:
        program += "[" + p.translate(lookup) + "]"
    # Empty discard productions
    for s, p in ordered:
        program += "[]"
    program += "]"
    return program

# Example
halt_system = {
    "a": "ccbaH",
    "b": "cca",
    "c": "cc",
    "H": ""
}

print(two_tag_to_qoob(halt_system, "baa", halting=["H"]))

Implementations

The following is a qoob to Python transpiler, in Python. 

def compile(program):
    out = "q = []\n"
    indent = ""
    last = None
    for c in program:
        if c == "0":
            out += indent + "q.append(0)\n"
        elif c == "1":
            out += indent + "q.append(1)\n"
        elif c == "[":
            out += indent + "while q.pop(0):\n"
            indent += " "
        elif c == "]":
            if last == "[":
                out += indent + "pass\n"
            if len(indent) - 1 == -1:
                raise SyntaxError("Unmatched closing bracket")
            indent = " " * (len(indent) - 1)
        last = c
    if indent:
        raise SyntaxError("Unmatched opening bracket")
    return out

This META II program compiles qoob programs to a virtual assembly where there are ENQ and DEQ mnemonics. The DEQ instruction dequeues a bit and sets the flags register accordingly. 

.SYNTAX PROGRAM

PROGRAM = BLOCK .,
BLOCK = $ STMT .,
STMT = ZERO / ONE / LOOP .,
ZERO = '0' .OUT('ENQ 0') .,
ONE = '1' .OUT('ENQ 1') .,
LOOP = '[' .LABEL *1 .OUT('DEQ') .OUT('JZ ' *2) 
     BLOCK
     ']' .OUT('J ' *1) .LABEL *2 .,

.END

This META II based implementation compiles qoob to Dequeasm: 

.SYNTAX PROGRAM

PROGRAM = BLOCK .OUT('HLT') .,
BLOCK = $ STMT .,
STMT = ZERO / ONE / LOOP .,
ZERO = '0' .OUT('PSH 0') .,
ONE =  '1' .OUT('PSH 1') .,
LOOP = '[' .OUT(*1 ':')
           .OUT('~PSH 1') .OUT('~XOR')
           .OUT('~PSH ' *2) .OUT('~JNZ')
       BLOCK
       ']' .OUT('PSH ' *1) .OUT('JMP')
           .OUT(*2 ':') .,

.END

This is a qoob interpreter in Python, where it must compile the program into an intermediate representation before running it, and prints the state of the queue after every instruction: 

def compile(program):
    stack = [[]]
    i = 0
    for c in program:
        if c == "0":
            stack[-1].append(False)
        elif c == "1":
            stack[-1].append(True)
        elif c == "[":
            stack.append([i])
        elif c == "]":
            if not stack:
                raise SyntaxError("Unmatched closing bracket")
            top = stack.pop()
            back = -(top[0] + 1)
            forward = i + 1
            top[0] = forward
            top.append(back)
            stack[-1].extend(top)
        else:
            i -= 1
        i += 1
    if len(stack) > 1:
        raise SyntaxError("Unmatched opening bracket")
    return stack[0]


def run(compiled, debug=False):
    q = []
    i = 0
    while i < len(compiled):
        c = compiled[i]
        i += 1
        if type(c) is bool:
            q.append(c)
        elif c > 0:
            if not q.pop(0):
                i = c
        elif c < 0:
            if q.pop(0):
                i = abs(c)
        if debug:
            print("".join(map(str, map(int, q))))
Retrieved from "https://esolangs.org/w/index.php?title=Qoob&oldid=156581"