Golden sunrise
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2020 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
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 - . # - /
Computation:
(01011) 1011
Extract first bit
Program:
0a - a 0# - / 1 - / # - /
Computation:
(01011) 1
Remove first bit
Program:
0a - . 0# - / 1 - / # - /
Computation:
(01011) 011
Remove last bit
Program:
0ab - a(0b.) 0a# - / 0# - / 1 - / # - /
Computation:
(01011) 1(0011) 10(011) 101(01) 101
Invert bits
Program:
0a - ~a(0.) 0# - / 1 - / # - /
Computation:
(01011) 0(0011) 01(011) 010(01) 0100(0) 0100
Reverse bits
Program:
0a - (0.)a 0# - / 1 - / # - /
Computation:
(01011) (0011)1 (011)01 (01)101 (0)1101 1101
Sort bits
Program:
00 - 0(0.) 01 - (0.)1 0# - / 1 - / # - /
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 - / # - /
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# - / # - /
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# - / # - /
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# - / # - /
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
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.