Encapsulation
| Paradigm(s) | String-rewriting |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Turing-complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
Encapsulation is a string-rewriting esoteric programming language.
Details
The computation consists of matching literal patterns of bits and replacing them with other patterns of bits. The input string, which is a finite sequence of bits, is placed in the memory and two extra 0s are placed before the string. Memory is a finite sequence of bits (but can become arbitrary large during the program execution). Program then searches for patterns and replaces them with other sub-sequences. Program ends when either there are no matching patterns, or the first bit becomes 1. The output string is the memory without the first two bits.
Source code consists of substitution definitions. Each substitution has matching pattern and replacement. Matching pattern is a sequence of bits, and there are no wildcards or quantifiers (it is always a literal sequence of bits). Output pattern is in the same format. Input pattern can contain < and/or > meaning that the pattern can be matched only at the beginning and/or the end of the memory, respectively.
Between matching pattern and substitution sequence is dash -. Defintions are separated by whitespace and/or semicolons ;.
Examples:
0 - 1 // Replace each 0 with 1 0101 - 110 // Replace each occurence of 0101 with 110 <001 - // Delete 001 if it is at the beginning of the memory <0> - 1 // If the memory consists only of a single 0, then replace it with 1 - 01 // Keep putting 01 everywhere > - 10 // Add 10 to the end of the memory - // No effects
Evaluation
In each iteration of the program execution, if there are no matching patterns, or the first bit in the memory is 1, then terminate the program. Otherwise, among all definitions from the source code, pick the one that can be matched closest to the beginning of the memory, and if there are multiple such definitions, pick the one that appears first in the source code. When program terminates, remove the first two bits and the remaining bits represent the program's output.
Examples
Cat
Empty source code is the Cat program, because there are no definitions and nothing can be matched, so the program terminates immediately.
Invert bits
<00 - 01000 0000 - 00101000 0001 - 001011000 000> - 0011 001010011 - 00111 0010110011 - 00110 <010011 - 10
Explanation: we couldn't do
0 - 1 1 - 0
for several reasons. The first two bits of the memory are 0 when program starts, so the first substitution will be applied to the first bit in memory, leading to immediate termination. Even if we somehow manage to keep that bit at 0 until we do all other replacements, the main question would be: how to know that we are done (i.e. how to determine whether some 0 or 1 is original or replaced). So, this approach does not work and the original solution above is probably the shortest one.
Reverse bits
<00 - 01000 0000 - 00101000 0001 - 001011000 000> - 00111 <010010 - 0100110 001101001010 - 001010011010 0011011001010 - 0010100110110 0011010010110 - 0010110011010 00110110010110 - 00101100110110 00110100111 - 001110 001101100111 - 001111 <0100111 - 10
Remove the first bit
<000 - 10 <001 - 10 <00 - 10
Remove the last bit
<00> - 10 <00 - 01000 0000> - 0011 0001> - 0011 0000 - 00101000 0001 - 001011000 001010011 - 00110 0010110011 - 00111 <010011 - 10
Extract the first bit
0000 - 000 0001 - 000 0010 - 001 0011 - 001
Sort bits
Push all 0s to the left and all 1s to the right.
<00 - 01000 0000 - 00101000 0001 - 001011000 000> - 00111 <01001010 - 010011010 001101001010 - 0011010011010 0011011001010 - 00110110011010 0010110011 - 00110110011 001011001010 - 001010010110 00110100111 - 001110 001101100111 - 001111 <0100111 - 10
After n-th 1 put n zeros
Input zeros are ignored.
<00 - 01000 0000 - 000 0001 - 0010011000 000> - 001111 00110010 - 0011100100110 0011001110 - 0011100110 0011001111 - 0011110 00111001111 - 0011110 001001111 - 0011111 <01001111 - 10
Truth-machine
The program cannot be terminated until it generates the whole output, so the closest this langauge has to the Truth-machine is:
<000 - 100 1 - 11
Hello, world!
The output is interpreted as little-endian ASCII bits.
00 - 0 01 - 0 - 100001001010100110001101100011011011110110001101000000010011101010111101100100111000110110001001101000010
Computational class
As pointed out by User:A, it is possible to encode Thue programs into Encapsulation's binary alternative, thus proving that Encapsulation is Turing-complete.