# Golden sunrise

Paradigm(s) String-rewriting Hakerh400 2020 Category:Turing complete Interpreter `.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:

```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 as a 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
```

## 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.