Liberation

From Esolang
Jump to navigation Jump to search
Liberation
Designed by Hakerh400
Appeared in 2020
Computational class Turing complete
Major implementations Interpreter
File extension(s) .txt


Liberation is a string-rewriting esolang which works with a string of active and passive elements.

Overview

There is a main string which contains active and passive elements.

Passive elements are bits. They can be either 0 or 1.

Active elements are denoted by . and they can perform rewritings around themselves.

Syntax

Source code consists of one or more rules. Each rule has a pattern on the left and a replacement on the right, separated by a hyphen.

Pattern must contain exactly one symbol . and can contain zero or more bits before and after . symbol. Before the pattern and/or after the pattern symbols # may appear - they represent start/end of the entire string.

Replacement is the new substring that will be added instead of the pattern if the pattern is matched. It can contain bits and/or arbitrary number of . symbols. It also can be empty, and that is denoted by / symbol.

Example:

#10.1 - 1..10.

It means that each time 10.1 appears on the beginning of the main string, it will be replaced by 1..10.

Errors

It is a syntax error if it is theoretically possible to match a single . symbol against multiple rules in some string.

It is a runtime error if no rule can be applied to any . and there is still at least one . in the main string.

I/O format

Input is a sequence of bits. The main list is formed by simply prepending a single . symbol before the input string.

Program halts when there are no more . symbols in the string. The string of bits that is left is the output.

Replacing

Replacing is performed in batchs. In each iteration (replacement) all . symbols that can be matched against a single rule are marked and their surrounding (that is matched with the pattern of the rule) is deleted, then they are replaced with the replacement of the rule.

Example

Given the following source code:

0.1 - 0
1.0 - 1
11.# - 10

and the following main string before some iteration:

100.1.01.

There are three . symbols. The first one can be matched against the first rule and the second one can be matched against the second rule. The third . cannot be matched in this iteration. Note that bit 1 between the two . symbols is common to both of them. All bits that are part of at least one matched pattern are removed and each . symbol that is successfully matched will be replaced accordingly. After this iteration the main string will be:

10011.

In the next iteration, the third rule will be aplied and we will have:

10010

which is also the end of the program execution.

Examples

In all examples we use input string 1011 for explaining computation steps.

Cat

Program:

. - /

Computation:

.1011
1011

Extract first bit

Program:

#.# - /
#.0 - 00.
#.1 - 10.
0.0 - 0.
0.1 - 0.
0.# - /

Computation:

.1011
10.011
10.11
10.1
10.
1

Remove first bit

Program:

#.# - /
#.0 - /
#.1 - /

Computation:

.1011
011

Remove last bit

Program:

#. - 0.
0.00 - 00.0
0.01 - 00.1
0.10 - 10.0
0.11 - 10.1
0.0# - /
0.1# - /
0.# - /

Computation:

.1011
0.1011
10.011
100.11
1010.1
101

Invert bits

Program:

.0 - 1.
.1 - 0.
.# - /

Computation:

.1011
0.011
01.11
010.1
0100.
0100

Reverse bits

Program:

#. - 00.
00.0 - 0000.
00.1 - 0100.
00.# - 01.
001. - 01.0
101. - 01.1
#01. - 10.
10.0000 - 0010.00
10.0001 - 0110.00
10.0100 - 0010.01
10.0101 - 0110.01
10.001 - 01.101
10.011 - 01.111
10.00# - 01.10
10.01# - 01.11
10.1 - 11.1
10.# - /
11.10 - 011.
11.11 - 111.
11.# - /

Computation:

.1011
00.1011
0100.011
010000.11
01000100.1
0100010100.
0100010101.
010001001.1
01000101.01
0100001.101
010001.0101
01001.00101
0101.000101
001.1000101
01.01000101
10.01000101
0010.010101
000110.0101
00010110.01
00010101.11
0001001.111
000101.0111
00001.10111
0001.010111
001.0010111
01.00010111
10.00010111
0110.000111
010110.0011
010101.1011
01001.11011
0101.011011
001.1011011
01.01011011
10.01011011
0110.011011
0101.111011
001.1111011
01.01111011
10.01111011
01.11111011
10.11111011
11.11111011
111.111011
1111.1011
11011.11
110111.
1101

Interpreters

Interpreter