Leafuck

Leafuck (originally named Navitree) is an esoteric programming language and Turing tarpit created by User:Rainwave in 2026. This language is a brainfuck derivative that operates on a dynamically growing binary tree instead of a tape. It's defining operation is the leaf check ([), which functions as a replacement for brainfuck's zero check. Thus, it receives the name Leafuck (with uppercase L, unlike brainfuck which is typically written in lowercase).

Language Description

Data Structure

The language operates on a dynamically growing binary tree. Each node contains no features other than its connections to other nodes. The tree starts with exactly one node, the root node.

Pointer

A pointer points to a node, initially the root node. This pointer may get assigned to other nodes at runtime.

Program

A program consists of a string of instructions. There are six available instructions:

Instruction	Description
<	Set the cursor to the left child of current node. This instruction may create the left child if it doesn't already exist
>	Set the cursor to the right child of current node. This instruction may create the right child if it doesn't already exist.
^	Set the cursor to the parent of current node. It is undefined behavior if this instruction is performed while the pointer points to the root node, though the reference implementation treats this as a runtime error.
.x	Print a single character parameterized by $x$.
[	If the cursor currently points to a leaf node, jump to the instruction after this instruction's matching ].
]	Jump to this instruction's matching [.

Note:

• A pair of [ and ] forms a loop. Loops may be nested. A [ without a corresponding ] after it is a syntax error.
• A . that appears as the last symbol in a program is treated as syntax error.
• Any other characters that do not fit into one of these six instructions are ignored.

It is worth noting that during execution, no nodes are ever deleted. Thus, the size of the tree is non-decreasing.

Examples

Hello world!

Program:

.H.e.l.l.o. .w.o.r.l.d.!

Output:

Hello world!

3x5 rectangle

Program:

<<<^^^
[
  >>>>>^^^^^
  [.*>]
  ^^^
  .
  <
]

Output:

*****
*****
*****

Computational Class

Leafuck is Turing complete as Bitwise cyclic tag can be compiled into it.

A proof presented by Rainwave can be seen here.

Implementation

Here's an implementation of Leafuck interpreter in Python

import argparse
import sys

arg_parser = argparse.ArgumentParser(description='Python implementation of Leafuck by Rainwave',
                                     exit_on_error=True,
                                     )
arg_parser.add_argument('program', type=str)
args = arg_parser.parse_args()

class BTNode:
    def __init__(self, parent=None) -> None:
        self.parent: BTNode | None = parent
        self.left_child: BTNode | None = None
        self.right_child: BTNode | None = None

    def is_leaf(self) -> bool:
        return not (self.left_child or self.right_child)

def parse(ins) -> {int, int}:
    i = 0
    open_braces = []
    jump_map = {}

    while i < len(ins):
        if ins[i] == '.':
            i += 1
        elif ins[i] == '[':
            open_braces.append(i)
        elif ins[i] == ']':
            if len(open_braces) == 0:
                print(f"Error: Unmatched ']' at index {i}", file=sys.stderr)
                exit(1)
            jump_map[open_braces[-1]] = i
            jump_map[i] = open_braces[-1]
            open_braces.pop()
        i += 1

    if ins[-1] == '.':
        print(f"Error: '.' without argument at the end of file", file=sys.stderr)
        exit(1)
    if len(open_braces) > 0:
        if len(open_braces) == 1:
            print(f"Error: Unmatched '[' at index {open_braces[0]}", file=sys.stderr)
        else:
            print(f"Error: Unmatched '[' found:", file=sys.stderr)
            for brace in open_braces:
                print(f"\tat index {brace}")
        exit(1)

    return jump_map

def run(ins, node: BTNode, jump_map):
    i = 0
    while i < len(ins):
        op = ins[i]
        if op == '>':
            if node.right_child is None:
                node.right_child = BTNode(node)
            node = node.right_child
        elif op == '<':
            if node.left_child is None:
                node.left_child = BTNode(node)
            node = node.left_child
        elif op == '^':
            if node.parent is None:
                print(f"Error: '^' executed from root at index {i}", file=sys.stderr)
                exit(1)
            node = node.parent
        elif op == '[':
            if node.is_leaf():
                i = jump_map[i]
        elif op == ']':
            i = jump_map[i] - 1
        elif op == '.':
            print(ins[i + 1], end="")
            i += 1
        i += 1

def main():
    program_file = args.program
    try:
        with open(program_file, 'r') as file:
            ins = file.read().strip('\n')
            tree = BTNode()

            jump_map = parse(ins)
            run(ins, tree, jump_map)
            exit(0)
    except FileNotFoundError:
        print(f"Error: File {program_file} not found", file=sys.stderr)
    except PermissionError:
        print(f"Error: Cannot read file {program_file}", file=sys.stderr)
    except Exception as e:
        print(f"Error: Unexpected error when reading program file. Message: {e}", file=sys.stderr)

    exit(1)

if __name__ == '__main__':
    main()