Encapsulation

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.
Try it online
=== Invert bits ===
 <00 - 01000
 0000 - 00101000
 0001 - 001011000
 000> - 0011
 001010011 - 00111
 0010110011 - 00110
 <010011 - 10
Try it online
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
Try it online
=== Remove the first bit ===
 <000 - 10
 <001 - 10
 <00 - 10
Try it online
=== Remove the last bit ===
 <00> - 10
 <00 - 01000
 0000> - 0011
 0001> - 0011
 0000 - 00101000
 0001 - 001011000
 001010011 - 00110
 0010110011 - 00111
 <010011 - 10
Try it online
=== Extract the first bit ===
 0000 - 000
 0001 - 000
 0010 - 001
 0011 - 001
Try it online
=== 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
Try it online
=== 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
Try it online
=== 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
Try it online
=== Hello, world! ===
The output is interpreted as little-endian ASCII bits.
 00 - 0
 01 - 0
 - 100001001010100110001101100011011011110110001101000000010011101010111101100100111000110110001001101000010
Try it online
== 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.
== Interpreters ==
Interpreter
Category:Languages
Category:Turing_complete
Category:Implemented
Category:2019
Category:String-rewriting paradigm