(())

(()), also known as Empty Nest, is a string re-writing scheme designed by User:DocHerrings to use only properly nested parenthesis, and to be completely impossible to read. The syntax is very simple. Every program consists of a list of productions, with the last item being the data. The interpreter iterates through the productions, testing them in order for a match within the program (all matches are greedy). If a match is found, the match substring is replaced with the productions replacement substring. If the production was non-terminating, then execution starts from the beginning of the productions and data. Otherwise, execution ends and the data is returned. A production of only one object matches the empty string. These rules are the same as certain descriptions of Markov algorithms, meaning the language is Turing complete.

A (()) program is made up of the following parts:

((productions) (data))
productions -> (non-terminating) | ((terminating))
non-terminating | terminating -> (match)(replace)

Examples

Binary Increment

Let 0 = (())
Let 1 = (()())
Let A = ((()))
Let B = ((()()))

To increment the binary number 1001, the following productions are used:

A1 -> 1A
A0 -> 0A
A -> B
1B -> B0
0B -| 1
B -| 1
-> A

Written in (()) form:

((((()))(()()))((()())((()))))
((((()))(()))((())((()))))
((((())))(((()()))))
(((()())((()())))(((()()))(())))
((((())((()())))((()()))))
(((((()())))((()()))))
((((()))))

The entire program, without line breaks:

((((((()))(()()))((()())((()))))((((()))(()))((())((()))))((((())))(((()()))))(((()())((()())))(((()()))(())))((((())((()())))((()()))))(((((()())))((()()))))((((())))))((()())(())(())(()())))

Interpreter

Here's an interpreter for (()), written in Python 3:

class Tree:
    def __init__(self,treelist):
        self.branches=treelist
    
    def __eq__(self,other):
        return other==None or self.branches==other.branches 
    
    def __str__(self):
        return "("+" ".join([(s.__str__() if type(s)!=type(None) else "n") for s in self.branches])+")"
   
    def __getitem__(self,key):
        if type(key)==int:
            return self.branches[key]
        elif len(key)==1:
            return self.branches[key[0]]
        return self.branches[key[0]][key[1:]]
   
    def __len__(self):
        return len(self.branches)
   

def str2(tree):
    string=""
    indent=0
    for paren in str(tree):
        if paren=="(":
            string+="\n"+"\t"*indent+paren
            indent+=1
        elif paren==")":
            indent-=1
            string+="\n"+"\t"*indent+paren
        else:
            string+="\n"+"\t"*indent+paren
    return string

def split(string):
    index=0
    i=0
    if string=="":
        return []
    elif string[0]==" ":
        return split(string[1:])
    for paren in string:
        i+=1;
        if paren=="(":
            index+=1
        elif paren==")":
            index-=1
        if index==0:
            return [string[:i]]+split(string[i:])

def tree(string):
    if string=="n":
        return None
    if len(split(string))!=1:
        return [tree(s) for s in split(string)]
    return Tree([tree(s) for s in split(string[1:-1])])

def subfinder(mylist, pattern):
    matches = []
    for i in range(len(mylist)):
        if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
            return i

def emptyNestInterpreter(string):
    t=tree(string)

    productions=[[(s2[1:-1] if len(split(s[1:-1]))>1 else (split(s2[1:-1]) if len(split(s2[1:-1]))>1 else s2[1:-1])) for s2 in split(s[1:-1])] for s in split(str(t[0])[1:-1])]

    #print(productions)

    data=split(str(t[1])[1:-1])

    #print(data)

    end=False
    while not end:
        for production in productions:
            if type(production[0])==list:
                prod=[production[0][0][1:-1],production[0][1][1:-1]]
                end=True
            elif len(production)==1:
                prod=production
                data=prod+data
                break
            else:
                prod=production
            i=subfinder(data,split(prod[0]))
            try:
                data=data[:i]+split(prod[1])+data[i+len(split(prod[0])):]
                break
            except TypeError:
                pass
            end=False
        #print(data)
    return data