ZeroStack2D

ZeroStack2D

ZeroStack2D is a stack-based, 2D grid esoteric programming language, designed to be Turing-complete. It draws inspiration from Befunge and Brainfuck, combining 2D instruction pointer movement with a minimal stack-based execution model.

Overview

ZeroStack2D operates on a 2D grid of characters, where an instruction pointer (IP) moves across the grid, executing commands. The language's core is a single stack, which is used for all data storage and manipulation.

Instructions

Command	Description
>	Set IP direction to right
<	Set IP direction to left
^	Set IP direction to up
v	Set IP direction to down
0/!	Push 0 onto the stack
+	Pop a value, add 1, push the result
-	Pop a value, subtract 1, push the result
:	Duplicate the top stack value
\	Swap the top two stack values
$	Pop and discard the top stack value
?	Read a character from input, push its ASCII value
～	Read an integer from input, push it
.	Pop a value and print it as a number
,	Pop a value and print it as a character
	Pop a value; if non-zero, set direction up, else down
_	Pop a value; if non-zero, set direction right, else left
@	Terminate the program

Turing completeness

ZeroStack2D is Turing-complete, as it can simulate a Minsky counter machine (P), which is known to be Turing-complete. This is achieved by using the stack to represent counters and the conditional jump instructions to control the flow.

Implementations

This is Python reference implementation, which interprets ZeroStack2D source files from a 2D grid:

<code>
#!/usr/bin/python3
import os, sys

class Element():
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def __bool__(self):
        return self.head is not None

    def push(self, data):
        new_node = Element(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if not self:
            return 0
        data = self.head.data
        self.head = self.head.next
        return data

    def swap(self):
        if not self:
            self.push(0)
        a = self.pop()
        b = self.pop() if self else 0
        self.push(a)
        self.push(b)

    def add(self, b):
        a = self.pop()
        self.push(b + a)

with open(sys.argv[1]) as f:
    program = f.readlines()

stack = Stack()
x = 0
y = 0
d = 0

while True:
    cmd = program[y][x]

    if cmd == ">":
        d = 0
    elif cmd == "<":
        d = 2
    elif cmd == "^":
        d = 1
    elif cmd == "v":
        d = 3

    elif cmd in "!0":
        stack.push(0)
    elif cmd == "+":
        stack.add(1)
    elif cmd == "-":
        stack.add(-1)
    elif cmd == ":":
        k = stack.pop()
        stack.push(k)
        stack.push(k)
    elif cmd in "\\/":
        stack.swap()
    elif cmd == "?":
        stack.push(ord(input()))
    elif cmd == "～":
        stack.push(int(input()))
    elif cmd == "$":
        stack.pop()
    elif cmd == ".":
        print(stack.pop())
    elif cmd == ",":
        print(chr(stack.pop()))

    elif cmd == "|":
        if stack:
            a = stack.pop()
            if a:
                d = 1
            else:
                d = 3
            stack.push(a)
        else:
            d = 3

    elif cmd == "_":
        if stack:
            a = stack.pop()
            a = stack.pop()
            if a:
                d = 0
            else:
                d = 2
            stack.push(a)
        else:
            d = 2

    elif cmd == "@":
        break

    if d == 0:
        x += 1
    elif d == 1:
        y -= 1
    elif d == 2:
        x -= 1
    elif d == 3:
        y += 1
</code>