Seclusion
| Paradigm(s) | Imperative |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
In the Universal Turing machine, the memory is linear and data pointer can move one cell at a time. That makes it very hard to work with lists, matrices, graphs, etc. Seclusion is a Turing tarpit programming language, in which data pointer can be moved in infinitely many different directions at any point.
Memory
Memory is represented as a directed graph. There are infinitely many nodes in the graph. Nodes cannot be allocated or deallocated and edges cannot be changed, only values inside nodes. There is a single node which is called the root node. Each node has a value, which is a non-negative integer of arbitrary size. Besides the value, each node has infinitely many pointers to other nodes in the graph and pointers are labeled as 0, 1, 2, 3, and so on. No pointer can point to the node itself. All pointers of a single node point to unique nodes (there are no two different pointers of a single node that point to the same node). Pointers cannot be null.
The root node is denoted with R. If node B can be reached by starting from node A and following pointer p, then we denote it as A[p] = B. Starting from any node in the graph, we can reach the root node only by following pointers labeled as 0. For example, if R[2][11][4] = X, then X[0][0][0] = R. In other words, each pointer leads "towards" the root node if and only if it is labeled as 0. The exception is the pointer 0 of the root node, which does not point to the root node, but it is guaranteed that R[0][0] = R. If we are at a random node in the graph and we follow only pointers labeled as 0 (enough times), we will end up either in R or R[0].
For any two nodes A and B, if A points to B, then B must point to A and at least one of the pointers must be labeled as 0 (and both can be labeled as 0 only for R and R[0]). Between any two nodes in the graph, there are exatly 0 or 2 pointers and there is exatly one path that does not include any node more than once. All nodes have value 0 initially, except the nodes that contain the input string, which is explained in the next paragraph.
Input
The input string is an array of zero or more bytes. The length of the input string is placed in the root node and the bytes are placed in R[0], R[1], R[2], etc. All other nodes have value 0 when program starts. Note: as said above, node values are unbounded non-negative integers, so the string length can be of any size, it can fit into the value of the root node.
Output
After the program halts, the length N of the output string is read from the root node, then bytes of the output string are read from R[0], R[1], R[2], ... , R[N - 1] and only the lowest 8 bits of each value are extracted to form the byte array and it represents the program's output.
Instructions
There are several instructions (and some of them are obviously redundant, but added on purpose). Some instructions take a value as the operand. A value as an operand in this programming language is always an array of integers. Arrays are always flat (cannot be nested). If we specify an array inside another array, it will be flattened at runtime. If we specify a single integer instead of an array, it will be encapsulated into a singleton array at runtime. Empty arrays are also allowed. There are several different operators and each operator is unary (takes a single value as the operand) and returns a single value (not a single integer - value as an operand is always an array of integers).
Multiple threads can be spawned (there is an instruction for that), but threads are deterministic. It means that their executions interleaves with each other in a precisely defined manner. A thread can be restarted from another thread's entry point. Data pointer is used to specify the current node. Each thread has its own data pointer.
Move
Syntax: <value>
This instruction updated the data pointer by examining the integers from the <value> array and following the corresponding pointers sequentially. How exatcly <value> can be represented in the source code will be explained later. One possible way is to specify literal integers inside parentheses.
For example, if the data pointer points to R[1][2] and we execute instruction (1,0,0,5) (which is a valid value for the <value> nonterminal), we will end up in the node R[1][5]. That is because, as we already said above, all 0 pointers lead towards the root node, so R[1][2][1][0][0][5] is the same as R[1][5].
This is the only instruction that has no prefix or code block. If we simply write a <value> at a place in the source code where an instruction is expected, it is interpreted as a Move instruction.
Increment
Syntax: +
Literal character +, if appears in the source code at a place where an instruction is expected, it increments the value of the current node (the node that is pointed by the data pointer). The data pointer remains the same.
Put a number
Syntax: .<value>
If the literal character . is followed by a <value>, it stands for the Put a number instruction. First we define what putting a number inside a node means. To put a number x inside a node that has value y means to write the absolute difference between x and y to the node's value. Obtaining a number from a value (recall: value as an operand is always an array) is done by computing the xor of all numbers in the array. If the array is empty, the xor is 0.
For example, if the data pointer points to a node with value 5 and we want to execute instruction .(2,3,9), then we first compute the xor of all numbers in the array, which is 8 and then we write abs(5 - 8) inside the node, which is 3. So, the new value of the node is 3.
Put an array
Syntax: !<value>
Put the length of the array <value> inside the current node and (assuming the length is N), put the first element into C[0], the next element into C[1], and so on, including the last element into C[N - 1], where C is the current node. Note that the definition of putting a number into a node is explained in the previous instruction.
If non-zero
Syntax: ?{<instructions>;<instructions>}
If the value of the current node is non-zero, execute all the instructions inside the braces, but before the semicolon and then jump out of the if-block, otherwise execute all the instructions after the semicolon and jump out of the if-block. Here <instructions> is a nonterminal that represents an array of zero or more instructions (so ?{;} is a valid syntax). The semicolon is mandatory (cannot be omitted).
If odd
Syntax: :{<instructions>;<instructions>}
Similar to the If non-zero instruction, except the condition is whether the value of the current node is odd.
While non-zero
Syntax: -{<instructions>}
While the value of the current node is non-zero, decrement the value and execute the instructions from the while-block. It is very important to note that decrementing the value is always performed if the value is non-zero. For example, -{} effectively writes 0 into the current node. If the data pointer is changed inside the while-block, the new current node is considered when checking the condition in the next iteration.
While odd
Syntax: /{<instructions>}
While the value of the current node is odd, subtract 1 from the value of the current node, then divide it by 2, and execute the instructions from the while-block. Effectively, an empty while loop /{} drops the rightmost 1s from the binary representation of the current node's value.
Create a thread
Syntax: {<instructions>}
This instruction has no prefix before the braces that denote the code block. The list of instructions inside the block are executed in a new thread and the parent thread skips the block. The initial value of the new thread's data pointer is equal to the current value of the parent thread's data pointer. How threads interleave will be explained later briefly.
Jump
Syntax: ^<value>
Here ^ is a literal character. The sum of all the elements of the <value> array is calculated and the current thread jumps to the first instruction inside the thread-block denoted by the sum. If the array is empty, the sum is 0.
The main thread starts from the first instruction in the source code when the program begins execution. The main thread is not encapsulated into a thread-block, but it is considered to be a thread of depth 0. Depth of a thread is equal to the number of thread-blocks it is encapsulated into. For example, A{B{C}} is a program that performs instruction A and spawns a new thread, the thread then executed instruction B and spawns a new thread, and the last thread executed instruction C (we assume that A, B and C are not Jump instructions). We can also name threads A, B and C respectively. The main thread is thread A and it is at depth 0, the thread B is at depth 1 and the thread C is at depth 2. Depth of a thread is determined by the position of its definition in thesource code and is not related to the thread's parents. For example, if thread X spawns Y and then Y spawns Z and Z spawns B, then B will still have depth 1, because it is syntactically encapsulated into a single thread-block. If a thread jumps out of its block, its depth is updated accordingly.
Instruction Jump moves the instruction pointer of the current thread to the first instruction inside the thread-block whose depth is equal to the current depth of the current thread minus the sum of the <value> array modulo the depth of the current thread. For example, if thread C (from the example above) executes ^(1,2) it will jump to instruction B (because C was at depth 2, the sum is 3, modulo 2 is 1 and 2 - 1 is 1, so C jumps to the thread-block above itself).
This instruction does not create a new thread, it simply updates the instruction pointer. The thread can now spawn a new thread that is defined by the thread-block that it originally started from.
Operators
The <value> nonterminal is usually represented as an array of literal numbers separated by commas and encapsulated into parentheses, for example (1,2,3). If a single number appears where a <value> is expected, it is interpreted as an array that contains a single literal number (for example if 5 appears, it is equivalent to (5)). If a nested array appears, it is flattened, for example ((1),(((2),3)),(),(())) is identical to (1,2,3). Empty array can also be written as # (it is just a syntactic sugar).
There are unary operators that process values. If an operator taking an operand appears where a <value> is expected, it is treated as the array that is represented by result of the operator evaluation at runtime. If an operator appears in an array and it results in a non-singleton array, it is injected into the encapsulating array to form a flat structure. For example, if we have (3,A(4,5),6) where A is an operator and (4,5) is the A's operand and A returns (7,8), then the resulting array will be evaluated to (3,7,8,6).
Scalar reference
Syntax: ~<value>
The result is always a singleton array that contains the value of the node that is reached by starting from the current node (pointed by the data pointer) and moving along the pointers denoted by the <value> array's elements. Data pointer remains unchanged. If a nested scalar reference appears, the current node is the original current node, not the temporarily updated one from the encapsulating scalar reference operator.
For example, if we are in the node C (current node) and the value of C[4][3] is 1, then ~(4,3) results in (1). We can also do more complex referencing. If the value of the current node is 5 and the value of C[2][5] is 11, then ~(2,~#) results in (11).
Array reference
Syntax: %<value>
The result is the array that can be parsed from the node that can be reached by starting from the current node and following the pointers denoted by the numbers from the <value> array. The algorithm for parsing an array from a given node is the same as the algorithm for extracting the output string after the program halts, but instead of the root node, we consider the given node. That is, the length of the array is the value of the given node (does not need to be the current node pointed by the data pointer) and the elements are values of G[0], G[1], G[2], etc, where G is the given node. As said, we reach the G by starting from the current node C and the following pointers denoted by the numbers from the <value> array.
For example, if we are in node C (current node) and the value of C is 3, the value of C[1] is 2 and the value of C[1][1] is 9, then the result of %1 is (3, 9). Note: %1 is equivalent to %(1). Detailed explanation: first, we start at the current node C. The <value> is (1), which means that we should move to C[1] (but keeping the data pointer as is). Not we are in C[1]. The length of the array is the value of this node, which is 2. So, the first element will be the value of C[1][0] and the second element will be the value of C[1][1]. We know that the value of C[1][1] is 9, so we know for sure that the second element is 9. But, how do we know the value of C[1][0]? To answer that, we suggest reading the first paragraph where it says "For any two nodes A and B, if A points to B, then B must point to A and at least one of the pointers must be labeled as 0". Since C points to C[1], then C[1] must point to C and since one of the pointers is labeled as 1, the other one must be labeled as 0. Further, it says in the first paragraph "Between any two nodes in the graph, there are exatly 0 or 2 pointers and there is exatly one path that does not include any node more than once". From that we can conclude that C[1][0] = C. So, the value of C[1][0] is the value of C, which is 3, so the resulting array is (3, 9).
Bridge
Syntax: *<value>
Let arr be the resolved array <value> and let len be the length of arr. If len is 0 then the result is (0). Otherwise let M be the first element of arr and let N be len - 1. Let T be the arr without the first element. The result is a singleton array that contains the time obtained by applying the generalized Bridge and torch algorithm, where M is the maximal number of people that can cross the bridge at once, N is the number of people that need to cross the bridge and T is the array that for each person contains the time needed for that person to cross the bridge. If there is no possible solution (for example M = 0, T = (0) or M = 1, T = (0, 0)), then the result is an empty array ().
Examples:
*() ---> (0) *(0) ---> (0) *(1) ---> (0) *(0, 0) ---> () *(2, 0, A, B) ---> (A + B) // A and B are any numbers *(2, 1, 2, 5, 10) ---> (17) *(3, 1, 1, 4, 4, 4) ---> (8) *(2, %#, 0) ---> (12) // If the value of C is 2, the value of C[0] is 7 and the value of C[1] is 5
Comments
Inline comments start with // and end with the new line (\r or \n characters) or the end of the source code. Multiline comments start with /* and end with the nearest */. Vertical bar character | is also treated as a comment. Comments are treated as whitespace along with \r, \n, \t (tab) and \x20 (space) characters.
Parsing
The parser is greedy, which means that at the given position in the source code the nonterminal with the maximal possible length will be parsed (among the available nonterminal that can appear at the given position). For example, the source code 00 will not be parsed as two Move instructions (like 0 0), but rather as a single Move instruction (any number can be prepended with arbitrary number of zeros). If we want two move instructions, then we should separate them by a whitespace character or a comment (for example 0 0, or 0|0 or 0/**/0).
Also, note that ~#~# is not equivalent to (~#,~#), because the first one will move to C[C.value][C[C.value].value], while the second one will move to C[C.value][C.value], where C is the current node and value represents the value of a node. In this example we also see that there is no need to use whitespace between instructions, unless the first one ends with a digit and the second one starts with a digit.
Threads
The list of threads is represented as a circular linked list. Interpreter has a pointer to the current thread and executes one instruction at a time, then moves the pointer to the next thread, and so on, untill the list is empty. Thread finishes when it reaches the end of the thread block or the end of the source code.
At the beginning, there is only the main thread in the list. If a thread spawns another thread, the new thread will be placed immediatelly after the parent thread in the list and the new thread will perform the next instruction (it is the next one that the interpreter will choose for execution).
Instructions as atomic actions from the thread's perspective are Move, Increment, Put a number/array, Check if/while condition, Spawn a thread, Jump. Operators are not instructions, so a thread can perform arbitrary number of operators in a single instruction. For example .~%*# is an instruction that contains three operators, but a thread performs all three operators in a single atomic instruction.
For example, the following program prints 100 alternating zeros and ones:
!%#.100|0|2.48|0|3.49|0|1.~(0,0)
{-{(0,0,~#).~(0,0,2)(0,0,1)}}#
{-{(0,0,~#).~(0,0,3)(0,0,1)}}
There are two threads (not counting the main thread) and one thread prints zeros, while the other thread prints ones. In the above example, # between the threads as a Move instruction is used for thread synchronization. Basically, Move # (which is an empty array) moves the data pointer to the current node itself (does not change the data pointer), so the instruction consumes one thread tick, but has no effect. You may notice !%# on the beginning. It is used to clear the input (if there is any). You can replace 100 with any number and it will print that number of alternating binary digits.
Here is also an example that demonstrates how the Jump instruction works:
0|1.~(0,0)
{?{.1(0,0,~#).~#.65|0|0|1^#;}}
This program replaces each character from the input string with letter A. As it can be seen, there are no loops, just a thread, if-statement and jump.
Examples
Cat
Of course, the simplest possible program is the Cat program. It leaves the input unchanged by simply doing nothing.
Hello, world!
!%#!(72,101,108,108,111,44,32,87,111,114,108,100,33)
It simply places the literal characters (bytes) around the root node. Again, !%# can be omitted if we know that the input is an empty string.
Print digits from 0 to 9
!%#.10(0,1).~(0,0)-{(0,0,~()).(48,~(0,0,1))(0,0,1)}
Reverse the input
0|2.~(0,0).1|0|5.~#.~(0,1).~(0,2)0|4.~#.*(2,0,~(0,5),~(0,2)).~(0,1)-{0|5.~#.~(0,0,~(0,1))(0,0,~(0,1)
).~#.~(0,~(0,0,2))(0,~(0,0,2)).~#.~(0,0,5)0|0|1+0|2.1|0|5.~#.~(0,1).~(0,2)0|4.~#.*(2,0,~(0,5),~(0,2)
).~(0,1)}
Sort characters alphabetically
0|1.~(0,0)0|5.~(0,1)-{0|3.~#.~(0,2)+0|5.~#.~(0,3).~(0,1)-{.~#.~(0,0,~(0,3)).~(0,0,~(0,2))0|4.~#.*(2,
0,~(0,5),~(0,0,~(0,2))).~(0,0,~(0,3))?{.~#.~(0,0,~(0,3))0(0,~3).~#.~(0,~(0,0,2))0~(0,2).~#.~(0,0,4)0
;}0|3+0|5.~#.~(0,3).~(0,1)}0|2+0|5.~#.~(0,2).~(0,1)}
Add two big integers
0|2.~(0,0).1|0-{+0|0|5.~#.~(0,0,~(0,3)).32?{(0,0,~(0,3)).48|0|0|1;0|1.~#.~(0,3).1}0|3+(0,0,~#)}0|0|5
.~#.~(0,0,~(0,2)).32-{(0,0,~(0,2))-{0~(0,1)+0|0|5.~#.~(0,0,~(0,1)).10?{;0|3.~#.~(0,1)0|5.~#.~(0,0,~(
0,3)).10?{.~#;.~#.1}-{0|3?{;0|4.~#.~(0,2)+-{+0|5.~#.~(0,4).1(0,0,~(0,4)).~#.~(0,~(0,0,5))0|0|4.1}0.~
#1+0|2+|0|3+}(0,0,~#).~#0|0|3.1(0,0,~#)+0|0|5.~#.~(0,0,~(0,3)).10?{.~#;.~#.1}}}(0,0,~(0,2))}0|0|1?{;
0|4.~#.~(0,2)+-{+0|5.~#.~(0,4).1(0,0,~(0,4)).~#.~(0,~(0,0,5))0|0|4.1}0.~#1+0|2+0|1}.1|0|2.1|0|5.~#.~
(0,0,~(0,2)).32}(0,0,~(0,2)).~#.10|0|0|5.~#.~0?{.~#;.~#.1}-{0|3.~#0|5.~#.~(0,2)-{.~#.~(0,3)+(0,0,~(0
,3)).~#.~(0,~(0,0,5))0|0|3+0|5.~#.~(0,3).~(0,2)}0|2.1|0|5.~#.~0?{.~#;.~#.1}}0|2?{;0.~#2.~#.1}0|3.~#0
5.~#.~(0,2).~(0,3)-{(0,0,~(0,3),1).~#.~0|0.~#.*(2,0,48,~1)0|0|3+0|5.~#.~(0,2).~(0,3)}0|0.~#.~(0,2)
Computational class
This programming language is Turing-complete. To prove that, here is a brainfuck interpreter:
0|1.~(0,0)0|4.~(0,1)0|7.2|0|5.~0.59-{0|3+0|5.~#.~(0,0,~(0,3)).59}0|3+0|5.~#.~(0,0,~(0,2)).59-{.~#.~(
0,0,~(0,2)).60?{.~#.~(0,0,~(0,2)).62?{.~#.~(0,0,~(0,2)).45?{.~#.~(0,0,~(0,2)).43?{.~#.~(0,0,~(0,2)).
44?{.~#.~(0,0,~(0,2)).46?{0|8.~#0|5.~#.~(0,0,~(0,2)).91?{0|2.1|0|5.~#.~(0,0,~(0,2)).91-{.~#.~(0,0,~(
0,2)).91?{.~#.~(0,0,~(0,2)).93?{;0|8+};0|8.1}0|2.1|0|5.~#0|8?{0|5.1;0|5.~(0,0,~(0,2)).91}};0|2+0(0,~
7,1)*(2,0,1,~#)?{0|0|0|0|5;0|0|0|0|5.~#.~(0,0,~(0,2)).93-{.~#.~(0,0,~(0,2)).91?{.~#.~(0,0,~(0,2)).93
?{;0|8.1};0|8+}0|2+0|5.~#0|8?{0|5.1;0|5.~(0,0,~(0,2)).93}}0|2+}};0(0,~4).~#.~(0,~(0,0,7),1,*(2,0,1,~
(0,~(0,0,7),1)))0|0|4+0|2+};0(0,~7,1)*(2,0,1,~#).~#0|0|0|0|5.~#.~(0,1).~(0,3)?{(0,0,~(0,7),1,*(2,0,1
,~(0,0,~(0,7),1))).~(0,0,0,~(0,0,0,0,3))0|0|0|0|3+;}0|2+};0|5.~#.~(0,0,~(0,7),1,*(2,0,1,~(0,0,~(0,7)
,1))).255?{(0,0,~(0,7),1,*(2,0,1,~(0,0,~(0,7),1)))+;(0,0,~(0,7),1,*(2,0,1,~(0,0,~(0,7),1))).~#}0|0|0
0|2+};(0,0,~(0,7),1,*(2,0,1,~(0,0,~(0,7),1)))?{.1;.~#.255}0|0|0|0|2+};0|5.~#.~(0,7).3?{(0,0,~(0,7),1
)+0|0|0|2;(0,0,~(0,7),1)?{.1|0|0|0|2;0|0|0|7.~#.2|0|2}}+};0|5.~#.~(0,7).2?{(0,0,~(0,7),1)+0|0|0|2;(0
,0,~(0,7),1)?{.1|0|0|0|2;0|0|0|7.~#.3|0|2}}+}0|5.~#.~(0,0,~(0,2)).59}0|8.~#0|9.~#.~(0,1)0|5.~#.~(0,4
).~(0,9)-{0(0,~8).~#.~(0,~(0,0,9))0|0|8+0|9+0|5.~#.~(0,4).~(0,9)}0|0.~#.~(0,8)
Input string consists of a brainfuck source code and the brainfuck input, separated by a semicolon.