Encapsulation

From Esolang
Jump to: navigation, search
Intramodular Transaction
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.

// noop

Example:

Input: 0100110100100110001000
Output: 0100110100100110001000

Invert all bits

<00 - 01000
0000 - 00101000
0001 - 001011000
000> - 0011
001010011 - 00111
0010110011 - 00110
<010011 - 10

Example:

Input: 0110110110000000100110001011011000010010110110
Output: 1001001001111111011001110100100111101101001001

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 the sequence

<00 - 01000
0000 - 00101000
0001 - 001011000
000> - 00111
<010010 - 0100110
001101001010 - 001010011010
0011011001010 - 0010100110110
0011010010110 - 0010110011010
00110110010110 - 00101100110110
00110100111 - 001110
001101100111 - 001111
<0100111 - 10

Example:

Input: 11100111101100000011010
Output: 01011000000110111100111

Remove the first bit

<000 - 10
<001 - 10
<00 - 10

Example:

Input: 1100001010010011011011011100110100
Output: 100001010010011011011011100110100

Remove the last bit

<00> - 10
<00 - 01000
0000> - 0011
0001> - 0011
0000 - 00101000
0001 - 001011000
001010011 - 00110
0010110011 - 00111
<010011 - 10

Example:

Input: 11110101110001100111101011
Output: 1111010111000110011110101

Extract the first bit

0000 - 000
0001 - 000
0010 - 001
0011 - 001

Example:

Input: 101110010011100111100010110010
Output: 1

Sort the sequence

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

Example:

Input: 01000000101001001010100100110
Output: 00000000000000000001111111111

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

Example:

Input: 0001111000001101001111101010100
Output: 101001000100001000001000000100000001000000001000000000100000000001000000000001000000000000100000000000001000000000000001000000000000000

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.

Interpreters

Interpreter