Liberation
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | User: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