PointsCopy

PointsCopy is an esolang made by User:Simple9371. Its data can be thought of as points in the non-negative real number line.

Documentation

PointsCopy has no stdin and stdout. A PointsCopy program has two parts: data initialization and copy conditions. Those parts must be written in that order. Comments are optional when implementing the language, but to aid in describing, we'll use the // single line comment.

Data Initialization

The data structure needs to be discussed first. Think of the data as points in the non-negative real number line, but with "parent-child" relationship. Points are indicated similar to "version numbers": a sequence of non-negative integers $x_{1}.x_{2}.\ \cdots \ .x_{n}$ such that

• $x_{1}.x_{2}.\ \cdots \ .x_{n}.1$ and $x_{1}.x_{2}.\ \cdots \ .x_{n}.2$, for example, are "children" of point $x_{1}.x_{2}.\ \cdots \ .x_{n}$.
• $x_{1}.x_{2}.\ \cdots \ .x_{n}$ and $x_{1}.x_{2}.\ \cdots \ .x_{n}.0$ ("trailing zero") refer to the same point.
• The "version ordering" gives us the ordering of points. For example, 0 < 0.1 < 0.2 < 1. Here is a visualization of the four points:

|-----------/-----------/-----------|-------->
|           |           |           |
0 = 0.0     0.1         0.2         1 = 1.0

0.1 and 0.2 are direct children of 0.
Hierarchy of point symbols: "|" is parent of "/".

These indications are not names of the points, but are assigned relative to the zero point (0). For example, if we "forget" the point 0.1 in the above visualization, the point that was once called "0.2" will now be called "0.1".

|-----------------------/-----------|-------->
|                       |           |
0 = 0.0                 0.1         1 = 1.0

Now we can specify the data initialization: just a listing of points separated by whitespace, always starting with the zero point, and ends with semicolon. For example,

0
    0.0.1
      0.0.1.1
  0.1
  0.2
    0.2.1
  0.3
1  1.0.1  1.1  2;

Here is a corresponding visualization:

|---x-------:---------/-----/-----x-------/-----|----x-------/----|-------->
|   |       |         |     |     |       |     |    |       |    |
0   0.0.1   0.0.1.1   0.1   0.2   0.2.1   0.3   1   1.0.1   1.1   2

Hierarchy of point symbols: "|" is parent of "/" is parent of "x" is parent of ":".

Adding trailing zeros is permissible, thus it is alright if the "0" in the code above is "0.0.0.0" instead.

Code error occurs if

• There is "horizontal" skip or the skip between "sibling" points. For example, points 0.1 and 0.3 are listed, but not 0.2.
• There is "vertical" skip or the skip on upper-in-hierarchy points that bound lower points. For example, point 0.0.0.1 is listed, but not 0.0.1.

Copy Conditions

Grouping points needs to be discussed first. Let $p=x_{1}.x_{2}.\ \cdots \ .x_{n}$ be a point. Then $gp$ is the interval from $p$ (exclusive) to its farthest "descendant" (inclusive), consisting of all its children, grandchildren, and so on. This is where trailing zero will become important. For example, in the data initialization example above, g0 is the ordered set 0.0.1, 0.0.1.1, up to 0.3, because 0.3 is the last descendant of 0 before 1. However, g0.0 is the ordered set 0.0.1 and 0.0.1.1 because 0.0.1.1 is the last descendant of 0 before 0.1. Lastly, both g0.0.0.0 and g0.3 are empty sets.

Now we can describe a copy condition (p_i are points):

<condition> ::= p_1 p_2 ... -> gp_3 to gp_4, gp_5 to gp_6, ... ;

A condition has two parts:

1. The pattern (the p_1 p_2 ... before the ->): the p's are listed with no skipping points like in data initialization and must end on a point in gp_1 or the next sibling of p_1. These points will serve as the pattern to match the current data. If there is the match, then the condition activates: gp_1 (and the current assigned numbering to those points) will be saved somewhere else in memory, all the points in the pattern will be forgotten except p_1, and then all the copy commands will be executed based on the saved gp_1.
2. The copy (these are after ->, there should be one or more, separated by comma): the children of the point before to (e.g., p_3 in the above first instance of a copy) will be appended to the children of the point after to (e.g., p_4 in the above first instance of a copy). If p_3 doesn't have children, no copy occurs. If p_4 doesn't have children, then the children of p_3 are inserted as the new children of p_4 instead. Then the grandchildren and so on, are copied appropriately relative to the newly copied children. This will be clear in the sample run section below. Code error occurs here if there is any duplicate point mentioned, and runtime error occurs here if

• any mentioned point (p_3, p_4, p_5, p_6, ...) does not exist in current data
• points p_3, p_5, ... are not in gp_1
• some point in gp_1 is not "used": there is a point in gp_1 that is not in the pattern, not p_3, p_5, ..., nor belonging to any of gp_3, gp_5, ....

The copies constitute the changes of the program to the data. The program halts when either none (success) or multiple conditions have match with data (runtime error). This restriction is to enforce a single match among the conditions at all times.

A Sample Run

Let's add two copy conditions to the above data initialization example to complete the program.

0
    0.0.1
      0.0.1.1
  0.1
  0.2
    0.2.1
  0.3
1    1.1    2;
1 1.0.1 1.1 -> g1 to g0.0; // let's call this condition 1
0.0.1 0.0.1.1 0.0.1.2 -> g0.0.1 to g0.3; // let's call this condition 2

Here is a corresponding visualization of initial data again:

|---x-------:---------/-----/-----x-------/-----|----x-------/----|-------->
|   |       |         |     |     |       |     |    |       |    |
0   0.0.1   0.0.1.1   0.1   0.2   0.2.1   0.3   1   1.0.1   1.1   2

The program run begins by checking all conditions. Upon inspection, condition 1 is a match (the sequence 1, 1.0.1, 1.1 is there), but condition 2 is not. Since there is exactly one matched condition, the run continues and condition 1 activates. The points in g1 are "saved", the points 1.0.1 and 1.1 are forgotten in the current data, and then g1 is copied and appended to g0.0:

• Saved point 1.1 (child of 1) "becomes" 0.0.2 (child of 0.0) because 0.0.1 already exists.
• Saved point 1.0.1 then becomes 0.0.1.2 because it was the point before 1.1, so it will be after the already existing 0.0.1.1.

Since all points of g1 are both in the pattern and are copied, all points are used, hence no runtime error.

Here is a visualization of the data after update with asterisk above indicating the new points:

                      *         *                                   forgetting here
|---x-------:---------:---------x-------/-----/-----x-------/-----|-----------------|-------->
|   |       |         |         |       |     |     |       |     |                 |
0   0.0.1   0.0.1.1   0.0.1.2   0.0.2   0.1   0.2   0.2.1   0.3   1                 2

Checking all conditions again, condition 1 is not a match, but condition 2 is (sequence 0.0.1, 0.0.1.1, 0.0.1.2 is now there). Again, exactly one matched condition, so the run continues and condition 2 activates. The points in g0.0.1 are saved, the points 0.0.1.1 and 0.0.1.2 are forgotten in the current data, and then g0.0.1 is copied to g0.3:

• Saved point 0.0.1.1 becomes 0.3.1.
• Saved point 0.0.1.2 becomes 0.3.2.

Since all points of g0.0.1 are both in the pattern and are copied, all points are used, hence no runtime error.

Here is a visualization of the data after update with asterisk above indicating the new points:

           forgetting here                                        *       *
|---x---------------------------x-------/-----/-----x-------/-----x-------x-------|---|-------->
|   |                           |       |     |     |       |     |       |       |   |
0   0.0.1                       0.0.2   0.1   0.2   0.2.1   0.3   0.3.1   0.3.2   1   2

Checking all conditions again, condition 1 is not a match, and neither is condition 2. There is no matched condition, thus the program halts.

Computational class

PointsCopy is Turing-complete. Every Queue Automaton can be translated to a PointsCopy program. Points will serve two purposes: to separate "spaces", and to represent states and letters (of alphabet). The idea of this representation is that the number of children points corresponds to a state/letter: 1 child corresponds to state/letter 1, 2 children corresponds to state/letter 2, and so on.

Data Initialization

We'll just describe the initial data, because showing a listing would be lengthy and obscure the ideas. There are three main sections: the queue, the transition outcomes, and the automaton initialization. The queue consists of points separating the spaces corresponding to characters of the queue string. Each space is further divided into three: one for the character itself, one for the "current state" which is initially empty, and one contains one child that serves as "trigger" to be copied to a transition outcome. Here is a visualization of the queue:

Queue of length n (first character is in g0.0)

|---:---------x-------x-------:---------/-----:---------x-------x-------:---------/-- ... --/-----|---->
|   |         |       |       |         |     |         |       |       |         |         |     |
0   0.0.0.1   0.0.1   0.0.2   0.0.2.1   0.1   0.1.0.1   0.1.1   0.1.2   0.1.2.1   0.2       0.n   1

Explanations:

• g0.0, g0.1, ..., g0.(n-1) are spaces for characters of the queue string.
• g0.0.0, g0.1.0, ..., g0.(n-1).0 are the actual characters. In the above example, the first character of the queue is the "letter 1" because 0.0.0 has 1 child (0.0.0.1), and the second character is also "letter 1" because 0.1.0 has 1 child (0.1.0.1).
• g0.0.1, g0.1.1, ..., g0.(n-1).1 are initially empty, but will be inserted with the current state once these points become 0.0.1 (after the forgetting of earlier points).
• g0.0.2, g0.1.2, ..., g0.(n-1).2 contain 1 child. This 1 point will be copied as trigger to a transition outcome.
• g0.n is empty, as space for strings to be appended.

The transition outcomes are assigned to combinations of the current state of the automata and the current first character of the queue. Each space is an outcome, further divided into three: one for the trigger, initially empty and will be populated by copy conditions from the queue, one for the string to be appended at the end of the queue, and one for the next state. Here is a visualization of a transition outcome:

|---x-- string to be appended --x-------:---------:---------:---------/-- ... --|---->
|   |                           |       |         |         |         |         |
1   1.0.1                       1.0.2   1.0.2.1   1.0.2.2   1.0.2.3   1.1       2

Explanations:

• g1.0, g1.1, ... are spaces for transition outcomes.
• g1.0.0, g1.1.0, ... are initially empty, but will be inserted with a trigger point from queue.
• g1.0.1, g1.1.1, ... are the strings to be appended. This can be empty (that is, g1.0.1, for example, is empty), or else, the space is formatted the same as the initial queue section: children points separate the spaces corresponding to characters, which each space further divided into three, and so on.
• g1.0.2, g1.1.2, ... are the next states. In the above example, the next state of transition outcome 0 (g1.0) is the "state 3" because 1.0.2 has 3 children (1.0.2.1, 1.0.2.2, 1.0.2.3).

The last section is the automaton initialization, indicating the first state. It consists of two spaces: one containing one child that serves as trigger for the unique initialization copy condition, and one containing the initial state. Here is an example visualization:

|---x-------/-----x-------x-------|---->
|   |       |     |       |       |
2   2.0.1   2.1   2.1.1   2.1.2   3

Explanations:

• 2.0.1 is the trigger for the initialization copy condition which is the first one to activate.
• The initial state is "state 2" because 2.1 has 2 children (2.1.1 and 2.1.2).

Copy Conditions

The initialization copy condition is the only one that will activate initially:

2 2.0.1 -> g2.1 to g0.0.1;

The state indicated in g2.1 will be copied to g0.0.1, which is the first "current state" space in the queue. After the activation, point 2.0.1 will never exist again, preventing this condition to run again.

The next copy condition that should activate will be one of the "queue checkers" that checks for the first character in the queue and the current state besides it:

// letter 1 & state 1 (plus the trigger point which always matches) -> outcome 3 (g1.3.0)
0.0 0.0.0.1  0.0.1 0.0.1.1   0.0.2 0.0.2.1 0.1 -> g0.0.2 to g1.3.0;

// letter 2 & state 1 (plus the trigger point which always matches) -> outcome 0
0.0 0.0.0.1 0.0.0.2  0.0.1 0.0.1.1   0.0.2 0.0.2.1 0.1 -> g0.0.2 to g1.0.0;

// letter 1 & state 2 (plus the trigger point which always matches) -> outcome 6
0.0 0.0.0.1  0.0.1 0.0.1.1 0.0.1.2   0.0.2 0.0.2.1 0.1 -> g0.0.2 to g1.6.0;
...

Notice that the zero point in the pattern is written as 0.0 and the last point is its next sibling, 0.1. The zero point is written that way to prevent the runtime error of unused points, and the last point is the next sibling so that the forgetting resembles the "out" of the first character from the queue. The pattern in each condition here corresponds to a combination of letter and state, and the copies just send the trigger point 0.0.2.1 to a transition outcome.

The next copy condition that should activate will be one of the "outcomes":

1.0 1.0.0.1 -> g1.0.1 to g0, g1.0.2 to g0.0.1; // outcome 0
1.1 1.1.0.1 -> g1.1.1 to g0, g1.1.2 to g0.0.1; // outcome 1
1.2 1.2.0.1 -> g1.2.1 to g0, g1.2.2 to g0.0.1; // outcome 2
...

The pattern consisting of only the initial point and the trigger point means that the trigger point gets forgotten immediately upon activation. Then the activation proceeds: the "string to be appended" is appended to the queue (to make sense of to g0, bear in mind how the children, grandchildren, etc. are copied), and the next state is again copied to the new first "current state" space in the queue.

This means that the next copy condition that should activate goes back to one of the queue checkers. Hence the runtime cycles between the two groups of copy conditions, until the queue is empty, which means no more 0.1, which means no queue checker activates, which halts the program.