Golden sunrise

From Esolang
Jump to navigation Jump to search
Golden sunrise
Paradigm(s) String-rewriting
Designed by Hakerh400
Appeared in 2020
Computational class Category: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:

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.

Interpreters

Interpreter
Random source code generator

References

Template:Reflist