Parentheses only

Parentheses only

Paradigm(s)	String-rewriting
Designed by	Hakerh400
Appeared in	2020
Computational class	Unknown
Major implementations	Interpreter (written by User:Kamba)
File extension(s)	.txt

Parentheses only is an esolang which consists only of parentheses.

Syntax

All parentheses must be balanced. Other characters are ignored. Pair of balanced parentheses represents a group. Group can be either empty, or can contain other groups (concatenated).

For example, this is a valid program:

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

Global group is a group that is not inside any other group. This program has three global groups: (()((())())), (()()(())) and ().

Computation

• If there are no global groups, then halt the program.
• If the first global group is empty and it is the only global group, then halt the program.
• If the first global group is empty and the second global group is also empty, then remove one of them.
• If the first global group is empty and the second global group is non-empty, then swap them.
• If the first global group has exactly one element, then replace the first global group with the content of that element (so, fo example, ((()())) will be replaced with ()()).
• If the first global group has two or more elements and it is the only global group, then halt the program.

If none of the above is true, select the first two global groups (we color the first one green and the second one blue):

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

Let's call the first one A and the second one B. First, we remove B:

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

We first select the first element of A (let's call it C and color it red):

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

Now, we remove C and then we remove parentheses of A:

((())()) ()

Finally, for each remaining element of A (the groups that are left green after removing C and parentheses of A), we recursively substitute C with B. How substitution works is explained in the next paragraph.

Do all these steps iteratively until the program halts.

Substitution

Given a group X, we substitute Y with Z according to the following five rules (apply the first one that can be applied):

1. If X is Y, replace it with Z
2. If X is empty, leave it untouched
3. If X has exactly one element, then substutute Y with Z in that element
4. If the first element of X is Y, leave it untouched
5. In each element of X starting from the second element, substutute Y with Z

Back to the example

Currently we have:

((())()) ()

Now, we want to substutute C (which is ()) with B (which is (()()(()))) in all elements that are green (and that is only one element ((())())).

So, we want to substitute () with (()()(())) in ((())()). We read the five rules and try to apply the first one that can be applied. The first rule cannot be applied, because ((())()) is not (). The second rule cannot be applied, because ((())()) is not empty. The third rule also cannot be applied, because ((())()) does not have exactly one element. Fourth rule cannot be applied, because the first element of ((())()) is (()), which is not equal to (). Finally, we can apply the fifth rule, which says that in each element of ((())()) starting from the second element (that is () only) we substitute () with (()()(())). So, in order to substitute () with (()()(())) in () we can apply the first rule, so we obtain:

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

We continue, because we have two global groups. Now, we mark new A, B and C:

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

Substitute (()) with () in (()()(()))). We apply rule 5, so we substitute (()) with () in ()(()). On the first one we apply rule 2 and on the second one we apply rule 1. Now we have:

(()()())

There is only one global group and it has three elements, so the program halts here.

I/O format

Input is in the same format as the source code. We simply concatenate the input to the source code when the program starts. Both source code and the input independently must have balanced parentheses. The output is the final state of the program that cannot be reduced further.

Interpreters

An implementation in Lua is written by User:Kamba.

It reads the source/input from stdin and writes the result to stdout.

It will ignore input after excess ) and append sufficient ) to make the input balanced.

Source on pastebin. https://pastebin.com/y4pSmvNY