Golden sunrise

Golden sunrise is a language which performs computation by replacing groups of bits with sequences of bits and/or another groups of bits.
== Overview ==
This language works with bits. Input is a sequence of bits. The only two things in this language are bits and groups.
A Group encapsulates zero or more bits and can contain nested groups. Groups are represented using parentheses:
 10(11(0)111()0)
Above we have a sequence containing bits 10, then a group follows. The group contains 11(0)111()0, that is: bits 11, then another group which contains 0, then sequence of bits 111, after that an empty group, and at the end a single bit 0.
There is a main list containing elements. Each element is either a bit or a group (containing a list itself).
Computation is performed by searching for bit patterns inside the main list (including sublists) and replacing them with other patterns.
== Syntax ==
Source code consists of one or more rules.
Each rule contains left side and right side, separated by a hyphen. On the left side, there is a pattern that the interpreter is searching for inside available groups. On the right side, there is a sequence of bits and/or groups that the pattern will be replaced with.
Example:
 101 - 11
This example means: try to find a group that has 101 on the beginning and replace that group with literal bits 11. Suppose we have the following list:
 10(101001)00
It will be replaced with:
 101100
because the group (101001) starts with 101 and therefore that rule is applied.
We can also include the "rest" of the group using . symbol:
 101 - 11.
and now 10(101001)00 will be replaced with 101100100 (because 001 is the rest of that group after matching the pattern). The rest can also be empty.
If we want to match exact content inside a group, we can add #:
 101# - 11
Now, (101001) can no longer be matched using that rule, but (101) can.
Of course, we can add more complex list on the right side:
 11010 - .(0.1).(11)0.1
Each . will be replaced with the rest of the actual group when matched. Note: . is not allowed if # is specified (because there is no point of using it).
If we want to match any pattern, we can use /:
 / - 10
but then it must be the only rule in the program. Rules cannot overlap (they must be prefix-free). There cannot be a situation when a group can be matched against two different rules, or that some group cannot be matched. At any point in time, if there are groups, at least one of them must be possible to match against exactly one rule (interpreter takes care of that and reports errors during parsing if rules are malformed).
It is also possible to replace a pattern with nothing:
 1 - /
It will replace 0(1)0 with 00.
== Syntactic sugar ==
To make programming easier and code shorter, identifiers are allowed in patterns. For example
 ab - ba
is identical to
 00 - 00
 01 - 10
 10 - 01
 11 - 11
If multi-character identifiers are needed, they can be encapsulated into brackets:
 [ident1][ident2] - [ident2][ident1]
It is also allowed to use inverted value of an identifier:
 a - ~a
is identical to
 0 - 1
 1 - 0
== I/O format ==
Input is a sequence of bits. When program starts, the main list is a group which contains a bit 0 and the input string. For example, if the input string is 11, then the main list at the beginning is
 (011)
Program halts when there are no more groups. The literal sequence of bits that remain in the main list is the program's output.
Note: The order of matching rules is not important (the result will be the same). However, consider this situation:
 0 - 1
 # - ()()
and given the main list (0()), if we start from the most inner group, we will end up adding more and more groups, and the program will never terminate. However, if we started from the outer group, we could apply the first rule and replace the entire group with just a single bit 1. Therefore, it is recommended to always try to match the most outer group and if not possible (inner groups are not evaluated enough to match any rule yet), then try to evaluate inner groups (from left to right).
== Examples ==
In all examples here, we use the same input string: 1011. We also provide step-by-step computation for each program. The main list is always (01011) at the beginning (because we use the same input).
=== Cat program ===
Program:
 a - .
 # - /
Try it online
Computation:
 (01011)
 1011
=== Extract first bit ===
Program:
 0a - a
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 1
=== Remove first bit ===
Program:
 0a - .
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 011
=== Remove last bit ===
Program:
 0ab - a(0b.)
 0a# - /
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 1(0011)
 10(011)
 101(01)
 101
=== Invert bits ===
Program:
 0a - ~a(0.)
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 0(0011)
 01(011)
 010(01)
 0100(0)
 0100
=== Reverse bits ===
Program:
 0a - (0.)a
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 (0011)1
 (011)01
 (01)101
 (0)1101
 1101
=== Sort bits ===
Program:
 00 - 0(0.)
 01 - (0.)1
 0# - /
 1 - /
 # - /
Try it online
Computation:
 (01011)
 (0011)1
 0(011)1
 0(01)11
 0(0)111
 0111
=== Xor bits ===
Program:
 00a - (0a.)
 01a - (0~a.)
 0a# - a
 0# - 0
 1 - /
 # - /
Try it online
Computation:
 (01011)
 (0111)
 (001)
 (01)
 1
=== Increment binary number ===
Program:
 0 - (10(11(10.)))
 10a - (10.)a
 10# - /
 110 - 1.
 111 - 0(11.)
 11# - 1
 1# - /
 # - /
Try it online
Computation:
 (01011)
 (10(11(101011)))
 (10(11(10011)1))
 (10(11(1011)01))
 (10(11(101)101))
 (10(11(10)1101))
 (10(111101))
 (100(11101))
 (10(11101))0
 (100(1101))0
 (10(1101))00
 (1011)00
 (101)100
 (10)1100
 1100
=== Add n zeros after n-th 1 ===
Input zeros are ignored.
Program:
 0 - (11(101.))
 1000 - 0(100.)
 1001 - (100.)
 100# - /
 1010 - (101.)
 1011 - 1(101.)
 101# - /
 110 - /
 111 - 10(100.)(11.0)
 11# - /
 10# - /
 1# - /
 # - /
Try it online
Computation:
 (01011)
 (11(1011011))
 (111(101011))
 10(100(101011))(11(101011)0)
 10(100(10111))(11(101011)0)
 10(1001(1011))(11(101011)0)
 10(100(1011))(11(101011)0)
 10(1001(101))(11(101011)0)
 10(100(101))(11(101011)0)
 10(100)(11(101011)0)
 10(11(101011)0)
 10(11(10111)0)
 10(111(1011)0)
 1010(100(1011)0)(11(1011)00)
 1010(1001(101)0)(11(1011)00)
 1010(100(101)0)(11(1011)00)
 1010(1000)(11(1011)00)
 10100(100)(11(1011)00)
 10100(11(1011)00)
 10100(111(101)00)
 1010010(100(101)00)(11(101)000)
 1010010(10000)(11(101)000)
 10100100(1000)(11(101)000)
 101001000(100)(11(101)000)
 101001000(11(101)000)
 101001000(11000)
 101001000
=== Determine if there is same number of 0s and 1s ===
If number of 0s is equal to the number of 1s output 1, otherwise output 0.
Program:
 0 - (1001(1000.))
 10000 - 0(1000.)
 10001 - (1000.)1
 1000# - /
 10010 - (1010(10110.)(1001(111(1100.))))
 10011 - 0
 1001# - 1
 100# - 1
 10100 - 0
 10101 - (1010.)
 1010# - 1
 1011ab - (1011b.)
 1011a# - a
 1011# - /
 101# - /
 10# - /
 110a - .
 110# - /
 111ab - a(111b.)
 111a# - /
 111# - /
 11# - /
 1# - /
 # - /
Try it online
Computation:
 (01011)
 (1001(10001011))
 (1001(1000011)1)
 (10010(100011)1)
 (1010(10110(100011)1)(1001(111(1100(100011)1))))
 (1010(10110(10001)11)(1001(111(1100(100011)1))))
 (1010(10110(1000)111)(1001(111(1100(100011)1))))
 (1010(10110111)(1001(111(1100(100011)1))))
 (1010(1011111)(1001(111(1100(100011)1))))
 (1010(101111)(1001(111(1100(100011)1))))
 (1010(10111)(1001(111(1100(100011)1))))
 (10101(1001(111(1100(100011)1))))
 (1010(1001(111(1100(100011)1))))
 (1010(1001(111(100011)1)))
 (1010(1001(111(10001)11)))
 (1010(1001(111(1000)111)))
 (1010(1001(111111)))
 (1010(10011(11111)))
 (10100)
 0
=== Hello, World! ===
 / - 00010010101001100011011000110110111101100011010000000100111010101111011001001110001101100010011010000100
Try it online
== Computational class ==
Any Cyclic tag system can trivially be translated into Golden sunrise, which makes it Turing-complete.
Consider a cyclic tag system with productions 011, 10, and 101. We can construct golden sunrise program based on the given productions:
 0 - (100.)
 1000 - (101.)
 1001 - (101.011)
 100# - /
 10# - /
 1010 - (11.)
 1011 - (11.10)
 101# - /
 110 - (100.)
 111 - (100.101)
 11# - /
 1# - /
 # - /
Suppose the input string is 1, the computation will go like this:
 (01)
 (1001)
 (101011)
 (1111)
 (1001101)
 (101101011)
 (110101110)
 (100101110)
 (10101110011)
 (111110011)
 (100110011101)
 (10110011101011)
 (11001110101110)
 (10001110101110)
 (1011110101110)
 (1111010111010)
 (1001010111010101)
 (101010111010101011)
 (1110111010101011)
 (1000111010101011101)
 ...
If you drop prefixes 100, 101 and 11, you will get exactly what the cyclic tag program would produce.
These prefixes (100, 101 and 11) are unrelated to productions. They can be any prefix-free sequences of bits that start with 1. Each prefix either appends the production (in case of 1), or does nothing (in case of 0). In each case, it prepends the next prefix.
== Similarities to other esolangs ==
Golden sunrise is a mixture of Intramodular Transaction and Encapsulation. It is also similar to Lazy expander, but function names are replaced with bit prefixes.
== Interpreters ==
Interpreter
Random source code generator
Category:Languages
Category:Turing complete
Category:Implemented
Category:2020