Grid
| Paradigm(s) | Imperative |
|---|---|
| Designed by | Hakerh400 |
| Appeared in | 2019 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
Computation in Grid is represented by applying transformations to unbounded two-dimensional grid.
History
Grid is not initially intended to be a programming language, but since it turned out that some instructions have interesting properties, it may be worth to document the computational capabilities of it. The main idea dates from around 2007. First formal rules were established in around 2009, while the first working implementation appeared in 2017. There had been a very large number of edge cases and issues with the interpreter, but all of them were fixed in 2018. At the end of 2018, the first working interpreter that covers all edge cases was published.
However, that interpreter worked only for bounded grid (arbitrary, but fixed size). The first interpreter that works for unbounded grid was published later in 2019. and now Grid can be considered a well-documented programming language with precisely defined instructions and I/O format.
Motivation
The idea behind this language was to design a language which has the following properties:
- Rules for transforming grid are very complicated
- Once learned, a human can relatively easy do computation without making a mistake
- It is very hard to write an interpreter that covers all edge cases
Overview
Grid can be considered a Turing tarpit. It has small number of instructions and basic loops, but there is also one very powerful instruction that transforms the whole grid. Memory consists of 2D square grid, unbounded in all four directions. Squares (grid cells) are called tiles. Each tile can contain one of four different entities and can be bordered by up to four lines (for each side of the tile). The entities are:
- Black circle
- White circle
- Wall
- Void
A single tile can contain at most one entity. Tiles that have no entities and no lines are called empty tiles. Lines are shared between adjacent tiles. For example, if one tile has line on the top, then the tile above has line at the bottom. Deleting the top line from the below tile also deletes the bottom line of the tile above. Similarly applies to other directions. There are some constraints, though. If a tile contains wall, then it also contains all four lines. If two adjacent tiles both contain voids, then there cannot be a line between them. Tiles are considered adjacent if they share a side (see Von Neumann neighborhood).
Cursor
There is a cursor that points to a single cell. All instructions are performed relatively to the cursor. Cursor can be moved to any of the four adjacent cells in a single instruction. Except the instructions for moving the cursor, there are also instructions for adding/removing lines and entities in the tile that the cursor points to. After executing an instruction, the constraints regarding lines must be satisfied (four lines around wall and no lines between two voids), if any constraint is not satisfied, lines are implictly updated to match the constraining rules.
Tiles
There are two types of tiles: external and internal. External tile is any tile that satisfies at least one of the following conditions:
- It contains a void
- There is a path from the tile to another tile which contains a void
- There is a path to arbitrary distant tile
Internal tiles are all tiles that are not external. Here "path" means the sequence of adjacent tiles such that there is not a line between any two consecutive tiles. Note that type is not an intrinsic property of a tile - it can change over time depending of the tile content.
Lines
There are three types of lines: external lines, boundary lines and internal lines. External line is any line that is inbetween two adjacent external tiles. Boundary line is any line that is inbetween an external and an internal tile. Internal line is any line that is inbetween two internal tiles.
Instructions
At the beginning of the program execution, all tiles are empty and the cursor is placed in a single tile (there are no absolute coordinates). On the image on the right we see the cursor (red plus) and some lines. The size of the captured grid region is irrelevant, because the grid is unbounded (the image shows only 9x9 grid region near the cursor). Internal cells are blue, while external ones are white.
In all images in this article internal cells are blue, except if there is a wall in the cell. Each cell that contains a wall is also an internal cell. It follows from the abovementioned rules:
- If a tile contains a wall, it also contains all four lines
- If there is no path from the tile to a void (or a distant tile) that does not cross a line, then the tile is internal
Therefore, all tiles that have walls are internal. Instructions allow moving the cursor or adding/removing entities and lines. There are if statements and while loops, and there are also instructions for reading from stdin and writing to stdout.
The most powerful instruction, called "A", is what brings the power to the language and makes computation even more hard to predict. It is thoroughly explained in this article.
Syntax
Only ASCII characters are allowed in the source code. Whitespace is ignored (even if appears in the middle of an instruction). The language is case-insensitive.
I/O format
Both input and output are streams of bits.
Instructions
Move the cursor
^- Move the cursor one tile up>- Move the cursor one tile rightv- Move the cursor one tile down<- Move the cursor one tile left
Since the language is case-insensitive, both uppercase V or lowercase v can be used to move the cursor down. There are no limits regarding cursor movement: it can cross any line and any entity. Moving the cursor does not modify any tile. Note that the cursor is not an entity - it does not interact with lines and entities and it does not subject to any constraint.
Edit line
Letters U, R, D and L are used to modify the top, right, bottom and left line, respectively. Lines are modified in the tile that is being pointed by the cursor. After the letter, one of the characters +, - or ~ may appear. It means: add, remove or toggle the line, respectively. If omitted, toggle is used by default.
In case there is already the specified line, + has no effects. Similarly, if there is no specified line, - has no effects. The instruction can be performed only if it does not violate any constraint, otherwise the instruction has no effects. For example, if the cursor points to a tile that contains a wall, instruction U- has no effects, because each wall must be surrounded with four lines. Another example: if the cursor points to a tile that contains a void and the tile on the right also contains a void, then the instruction R~ has no effects.
Edit entity
Letters B, W, X and I are used to edit black circle, white circle, wall and void, respectively. Similarly, +, - or ~ can be used. Adding an entity will add it unconditionally, removing another entity from the tile if there was one. Similar applies to toggling. Removing entity from a tile that does not contain the specified entity has no effects.
Removing walls will keep the surrounding lines. Removing two adjacent voids will not re-create the line inbetween, even if there was one before adding the voids. For example, B-W-X-I-U+R+D+L+ is equivalent to X+X-.
Code block
Code blocks are denoted by parentheses and used to group instructions. They can contain zero or more instructions and can be nested. Examples: (), (>B+), (BW(X)I). They are useful in if statements and while loops, but can also appear anywhere in the source code. Code block is treated as a single instruction. Character , is syntactic sugar for ().
If statement
Denoted by one of U, R, D, L, B, W, X or I, followed by question mark ?. After the question mark, two instructions are expected. If the line or entity denoted by the character before the question mark is present in the current tile, then execute the first instruction after the question mark, otherwise execute the second instruction after the question mark. Code blocks can be used. Examples:
I?^> // If there is a void, go up, otherwise go right D?()W~ // If there is bottom line, do nothing, otherwise toggle the white circle L?(<B)(Bv) // If there is left line, go left and toggle black circle, otherwise toggle black circle and go down W?U?>v< // If there is not a white circle, go left, otherwise if there is top line, go right, otherwise go down X?,() // No effects
While loop
Denoted by one of U, R, D, L, B, W, X or I, followed by * or :. While the line or entity denoted by the first character is present (denoted by *) or not present (denoted by :), execute the next instruction. If the condition is not satisfied, the loop ends and the next instruction is skipped. Examples:
U*> // While there is top line, go right B:(^I^) // While there is no black circle in the current cell, go up, toggle void and go up again IX:, // Infinite loop
Input
Dot . followed by ?, * or :. Examples:
.?^> // Read a bit from stdin, if it is 1, go up, otherwise go right .*(W-<) // While the next bit from stdin is 1, remove the white circle and go left .:, // Read bits from stdin until 1 is found (and also consume that 1)
Output
Dot . followed by one or more 0s and 1s. Examples:
.10101100 // Write ASCII digit 5 to stdout
Transform grid
Denoted by letter A. This instruction is always a single character. It performs grid transformation by following precisely defined rules. This instruction is explained in deteails in a separate paragraph.
Computational class
Grid is trivially Turing-complete, as any Boolfuck program can be written in Grid using the following conversions:
< ---> < > ---> > + ---> U , ---> .?U+U- ; ---> U?.1.0 [ ---> U*( ] ---> )
This also proves that the language would be Turing-complete even without the instruction A. Note: U can be replaced with any of R, D, L, B, W, X or I, but it needs to be done consistently in all instructions.
Grid transformation
Instruction A transforms the grid. There are 7 steps in grid transformation. Note: in the following steps, when we say internal tile, it means internal tile which does not contain a wall.
Step 1. Enumerate fragments
The first action that is taken is to enumerate fragments. A fragment is a set of tiles such that any tile can be reached from any other tile by moving along non-void tiles. In other words, a fragment is an "island" of non-void tiles separated from other fragments by voids. There is exactly one unbounded fragment and zero or more bounded fragments.
Each fragment is treated as a separate realm. Whatever happens in one fragment does not affect other fragments. Instruction A may change lines, circles and walls, but can neither add nor remove voids. Remaining steps are applied to each fragment separately. Voids are not a part of a fragment.
Step 2. Get rid of external lines and entities
Step 2.1. Mark tiles
First mark each external tile that either:
- Is in the 8-neighborhood (see Moore neighborhood) of a wall and that wall can be reached in exactly two 4-neighborhood moves without crossing a void
- Is in the 8-neighborhood of an external line and the tile that contains that line can be reached in exactly one 4-neighborhood move without crossing a void
- Contains a circle
Step 2.2. Draw border around marked tiles
For each marked tile, set all lines in that tile which either shares a side with a non-marked tile, or satisfy all of these conditions:
- The line does not touch any previously external line
- The line does not touch any tile that contains a wall
- The line does not share a side with any tile that contains a circle
Step 2.3. Recalculate internal tiles
Unmark all tiles and update the set of internal tiles to match the grid after the added lines. After this step, there are no external lines and there are no entities in external tiles.
Step 3. Connect external shapes
Here we introduce terms external shape and internal shape. External shape is a set of internal tiles such that any tile can be reached from any other tile by moving along internal cells. Internal shape is a subset of an external shape such that any tile can be reached from any other tile by following a path that does not cross a line.
We also introduce terms best tile and best set of tiles. The best tile from a given set of tiles is the most upper tile, if there are multiple such tiles, the best tile is the leftmost one. The best set of tiles from a given set of sets of tiles is the set that contains the best tile of the union of all given sets and no other set contains that tile. This also applies to paths, because path is a set of adjacent tiles.
Step 3.1. Remove circles
First, for each internal shape, remember whether that shape contains at least one circle or not. This information is used later in the algorithm. Then remove all circles from all shapes.
Step 3.2. Add black circle
Add a black circle in the best tile that contained a black circle before Step 3.1 If there is no such tile, then add a black circle in the best internal tile. This does not modify the information from previous step about which shapes contained circles. The external/internal shape that contains black circle is called main external/internal shape.
Step 3.3. Find paths between external shapes
In this steps, walls do not count as a part of external shape. In other words, if two parts of a single external shape are connected only by a wall, then they count as two different external shapes. Repeat the following two cases until there is only one external shape:
Case 1:
- Mark the best shortest path of non-void external tiles that connects the main external shape and any other external shape
- For each marked tile put all lines that are not inbetween two marked tiles.
- Unmark all tiles and update the set of internal tiles
Case 2:
- Mark the best shortest path of walls that connects the main external shape and any other external shape (as said, in this steps walls are not a part of external shape)
- Remove walls from all marked tiles, but keep their surrounding lines
- Unmark all tiles and update the set of internal tiles
Cases are applied in the following way: apply case 1 as long as it can be applied, then apply case 2 as long as it can be applied, then again case 1, and so on, until there is only one external shape.
Step 4. Fill internal shapes that did not contain circles
Enumerate all internal shapes that did not contain circles before step 3.1 Also, all internal shapes that are created (explicitly or implicitly) in step 3.3. are in this set. Do the following for each enumerated internal shape:
- Start from the best tile of the internal shape and mark that tile
- Move to the best non-marked adjacent tile in the same internal shape and mark that tile
- Repeat step 4.2 untill there is no available moves
Then for each marked tile put all lines that are not inbetween two consecutive tiles in the path (this also applies to lines between a marked and a non-marked tile). After that, unmark all tiles, but remember that the internal shape that contained the marked tiles is finished and do not process it again. Repeat step 4 until all internal shapes that did not contain circles are finished. Note that new non-finished internal shapes may be formed during step 4.3 - they also need to be processed.
Step 5. Fill internal shapes that contained circles
Enumerate all internal shapes that contained circles before step 3.1 Do the following for each enumerated internal shape:
- Find the best shortest loop
- Put right line in the best tile of the loop
- Repeat steps 5.1 - 5.2 until there are no more loops
Here loop is a set of internal tiles such that at least one tile can be reached from at least one another tile in at least two different paths that do not cross any line and that are both subsets of the loop. If there are no loops in the given internal shape at the beginning of step 5, then skip that shape.
Step 6. Connect internal shapes
At the beginning of this step, since all previous steps are done, we know for sure that in the current grid fragment:
- There is exactly one black circle and no white circles
- There is exactly one external shape
- There is one or more internal shapes
In this step, all internal shapes will be connected into a single internal shape without loops. That is done in the following manner:
- Enumerate all sets of two adjacent internal tiles, one belonging to the main internal shape and the other not belonging to the main internal shape
- Find the best set among the enumerated sets
- Remove the line between the two tiles from the chosen set (note that there must be a line between them, because they belong to different internal shapes)
- Repeat steps 6.1 - 6.3 until there is only one internal shape
Of course, if there is only one internal shape at the beginning of the step 6, it is skipped. After this step, there is only one internal shape and there are no loops. Any internal tile (except walls) can be reached from any other internal tile in exactly one path that does not cross any lines.
Step 7. Put white circles
Put white circles in all internal tiles that have exactly three lines and no black circle.
Special situations and edge cases
One may notice that in some steps we assumed something that, in general, may not be true. For example, in step 3.2 we assumed that there is at least one internal tile, but actually there could be none. This paragraph covers all special situations. When one of the following cases is encountered, all 7 steps are skipped and the situation is handled in a special way.
All walls
The unbounded fragment cannot be completely filled with walls (because it is infinite in size), but a bounded fragment may contain a wall in each tile. In that case, just put a black circle in the best tile of the fragment, implicitly removing the wall from there. Keep the lines that were around the wall.
All empty tiles
If there are no lines or entities in any tile, then there are two cases:
- Case 1 - if there is at least one void, put all four lines and a black circle in the best empty tile that is adjacent to a void
- Case 2 - If there are no voids (the grid is completely empty), then put all four lines and a black circle in the tile pointed by the cursor
Note: void is, is negeral, not a part of a fragment, but we consider them in this special case.
Unchanged fragment
If all tiles in the given fragment are exactly the same before and after applying the instruction A (but before considering this edge case), then there are two cases:
- Case 1 - If there is at least one external tile, then put all four lines around the best external tile that is adjacent to an internal tile and apply all the steps again
- Case 2 - If there are no external tiles, do nothing (except if all tiles are walls, then consider the "All walls" edge case)
The Unchanged fragment edge case does not apply if All empty tiles edge case can be applied.
Other edge cases
All edge cases are covered in the video.[1] The grid region that is shown in all tests that appear in the video represents a bounded fragment, surrounded by voids. Each of the 21 tests shows the fragment before and after applying instruction A.
Examples
Instead of concrete examples, we provide random source code generator.[2]
Patterns
Here are some useful patterns that may help in writing programs.
Draw spiral
This program draws infinite spiral.
R+D+L+^L+U+> I:( D*(U+>)U+R+v L*(R+v)R+D+< U*(D+<)D+L+^ R*(L+^)L+U+> )
Find black circle
If the cursor is at any position in some internal shape, this piece of code will move the cursor to the tile that contains black circle. If there is no such tile, it will roam in the shape forever.
AIAIAI^
X:B?(
^I-v>I-<vI-^<I->
IAIA<Iv
)(
vI?(
I^I
L?U?R?v>^<
)(^>I?(
I<I
D?L?U?>^<v
)(<^I?(
IvI
R?D?L?^<v>
)(
v<I>I
U?R?D?<v>^
)))
)