Esoteric language 4DL

    4DL was invented in 2001 by Cliff L. Biffle. As he explained, he invented it firstly, because before that there were no languages ​​with four-dimensional programs, and secondly, because four-dimensional space is quite difficult to understand, and you need to give people the opportunity to train their brains.

    Russian Wikipedia relates this language to the "fungoid" family. These are languages originating from the Befunge language , programs in which are written in the form of characters on a rectangular lattice and can be executed in any direction. In 4DL, a four-dimensional lattice is used to represent a program, and its execution directions, respectively, are 8.

    A 4DL program may look, for example, like this:
     X  ,  B  /  \  B  +  2  B  -  <  ?  T  B  -  T
     y  __ 10 __ __ 7  __ __ A  __ __ __ __ 07 __ __ 
    ------------------------------------------------------------------
     __ Y  __ __ __ __ __ __ __ __ .  __ x  __ __ x  ||  __ __ __ __ __ __ __ __ __ __ 20 __ __ __ __ __
     t  X  __ __ __ q  +  2  q  -  <  ?  Z  q  -  Z  ||  z  __ __ __ __ __ __ __ __ .  b  .  x  __ __ x
    

    This program is not written in the "base" language, but in its extension, but more on that later.

    Besides the fact that 4DL is fungoid, it is also stackable. The only data object the program can work with is a stack of integers. Numbers, input characters are put in it, and characters for printing are taken from it.

    Programs on 4DL



    Here is the command system proposed by the author:
    X Rotate the command pointer in the X + direction
    x Turn the pointer to the command in the X- direction
    Y Rotate the command pointer in the Y + direction
    y Turn the command pointer in the Y- direction
    Z Rotate the command pointer in the Z + direction
    z Turn the pointer to the command in the Z- direction
    T Turn the command pointer in the T + direction
    t Turn the pointer to the command in the direction of T-
    P Put on the stack the symbol from the neighboring cell from the side X +
    p Put on the stack the symbol from the adjacent cell from side X-
    B Put on the stack the symbol from the neighboring cell from the Y + side
    b Put on the stack a symbol from a neighboring cell from side Y-
    D Put a symbol from a neighboring cell on the Z + side on the stack
    d Put on the stack the symbol from the neighboring cell from the side Z-
    Q Put a symbol from a neighboring cell on the side of T + on the stack
    q Put a symbol from a neighboring cell on the side of T- on the stack
    + Take the sum of two numbers on top of the stack, put the result on the stack
    - Take the difference of two numbers on top of the stack, put the result on the stack
    , Enter a character from the keyboard and put it on the stack
    . Pull a character from the top of the stack and display
    # Jump over the next cell of the program
    ? Remove the number from the top of the stack, and if it is nonzero, then jump over the next cell of the program
    0 Put the number 0 on the stack
    2 Put on the stack a copy of the number at its top
    % End the program


    As an example of a program, the author cites “Hello, World!” (with at least three errors). Unfortunately, a noticeably more serious language with such commands is not capable of anything (unless you increase the size of the program many times), therefore, for a start, I decided to add a couple more commands to it:

    \ Swap the contents of two cells on top of the stack
    ^ Remove a number from the top of the stack and do nothing with it (equivalent to 2- + or? XX - if moving to the right)


    Life has become much more fun. For example, here's what a program looks like that prints the sum of numbers from an input string:
     0  X  ,  D  -  2  ?  T  D  -  2  ?  T  D  -  Y || __ z  __ 0D __ __ __ __ 13 __ __ __ __ 10
     __ __ Y  D  T  ?  2  -  D  T  ?  2  -  D  ,  x || __ __ __ 10 __ __ __ __ 13 __ __ __ __ 0D
     __ __ X  -  \  2  2  +  2  +  +  2  +  +  __ y
    -------------------
     T  t  __ __ __ __ __ ^  __ __ __ __ x          || __ t
     +  y  +  ^  x  __ __ __ __ ^                   || __ y  __ __ .  B  .  B  x
     D                                              || 01 __ __ __ __ 0A __ 0D
     y  \  +  x
     __ X  __ y
    -------------------
     Y  0  x  \  0  ^  ,  x  +  x                   || __ __ __ __ __ Y  __ __ .  x
     \  __ y  Z  ?  2  \  -  x  y                   || __ __ __ X  +  X  2  ?  t  y
     D  __ __ __ X  +  D  \  y                      || 0A __ __ __ __ __ 3A
     X  \  2  ?  y  D  -  Y                         || __ __ __ __ __ 01
     y  t  ?  2  -  D  \  x                         || __ __ __ __ __ 01  
    


    A few words about recording the program (these are already my fantasies - the author did not describe the input syntax in any way).

    The space in which the program is located is divided into two-dimensional layers in which the coordinates Z and T are constant. The symbols of each layer are written in the form of a rectangular table, starting from the angle X = Y = 0. If it is a character from ASCII-7 (with a code from 33 to 126), it is written explicitly. If not, its two-digit hexadecimal code is written. A space can be designated as 20 or as double underscore. Characters are written through any number of spaces, a line with them begins with a space.

    Rectangles are combined into a two-dimensional table. Horizontally there are layers with the same T value (sequentially: Z = 0, Z = 1, ...), vertically - columns with the same Z value. Stitch lengths in layers, number of lines in a layer, number of layers in a table row can vary - the missing cells will be filled with characters with the code 0. The layers in the table row are separated by the characters || and the lines themselves are lines starting with a minus.

    By default, execution starts from the cell (0,0,0,0) in the X + direction. The starting point can be redefined by inserting the string> x, y, z, t (the numbers x, y, z and t decimal) into the program.

    The execution path of the above program in 4-dimensional space looks something like this:

    In addition to the cells through which the red line passes, there are some more cells with data, but I decided not to display them.

    Turing complete or not?


    It quickly becomes clear that the power of 4DL is entirely determined by the power of the underlying stacking machine. So, if the bit capacity of the number lying on the stack is limited, then it is possible to implement those and only those algorithms that are implemented on finite state machines with stack memory. If the stack is allowed to place arbitrarily long numbers, and we have the operation of exchanging two cells at the top of the stack, the language becomes Turing-complete - but the implementation of the Turing machine on it would be too slow (one operation would be performed at least 2 ^ 2 ^ N steps, where N is the size of the used memory). If the size of the number on the stack is limited, but there is an operation for reading and modifying the cells in the depth of the stack (the offset from the top is also taken from the stack), then we get an almost TP language - the available direct access memory will be limited.

    In any case, the four-dimensionality of the program is almost never used, and any 4DL program can be embedded in two-dimensional space. Moreover, leave the line Y = 0 for the executable code, Y = 1 - for the data, and use the rest of the plane to implement transition commands. This option seems uninteresting.

    Befunge authors stumbled upon the same problem of power limitation. To solve it, they added a mechanism for modifying memory cells into the language (which is correct), but they did this by allowing access to the cells — both for reading and writing — by explicit coordinates. It seemed to me to be too strong a decision.

    4DL + and Turing Machine


    A more moderate version was proposed by the author of one of the implementations of the 4DL language - Bernhard Stoeckner. In the "expanded" system of commands for its implementation, he offers, among other things, the following commands:
    N Put a character from the stack into an adjacent cell from the side of X +
    n Put a symbol from the stack into an adjacent cell from side X-
    F Put a character from the stack into the adjacent cell from the Y + side
    f Put a symbol from the stack into the adjacent cell from the Y- side
    G Put a symbol from the stack into an adjacent cell from the side of Z +
    g Put a symbol from the stack into the adjacent cell from the side Z-
    H Put a character from the stack into an adjacent cell from the side of T +
    h Put a symbol from the stack into the adjacent cell from the side of T-

    It turns out that these commands are enough to make the Turing language complete even with an 8-bit stack cell (not to mention a 32-bit one). To prove this, we will go along the simplest way - we will implement a Turing machine :)

    The main problem with us is that we can read and change the contents of only memory cells adjacent to the current program execution point. For a Turing machine, an infinite, or at least a semi-infinite tape is needed, which means that the program must be self-modifying to communicate with distant cells.

    The first idea was to implement the tape in the form of a “skyscraper”, in which each floor could support the commands “read the tape cell”, “change the contents of the cell”, “move up” and “move down”, and when it reached the top - start the “construction site ”, which grows in a parallel layer of reality, for the construction of a new floor. The problem turned out to be solvable, but rather quickly managed to find a much simpler way.

    It turns out that if you take a line of a program, for example, in the X + direction, fill its left side with spaces, and put the “N” command somewhere (take a character from the stack and write it to the cell to the right), then put certain sequences of commands and data on the stack , and send the program to execute this line, the program can do what you need and go back.

    For example, the sequence [N, x, x, N] turns the line
    __ __ __ __ N
    

    in line
    __ __ __ __ NN x
    

    And if after that we send the sequence [n, n, n, N, n] to this line, we get the line
    __ __ __ N nnx
    

    - the leftmost command “N” will move to the left of the cell. Similarly, in two steps you can execute the commands "move right", "write a character to the next line" and "read the character from the next line." It is most convenient to work with a cell located two positions to the right of the cell in which the “N” command is located.

    The program that implements the Turing machine will consist of three parts. Layer T = 0 will be used for communication between the program and the tape. The program will be in the region T> 0, Z = 0 and will be a finite state machine (with memory) that converts the current character on the tape into a pair (new character, direction of shift). We place the tape on the line Y = Z = T = 1, and the control program will occupy the area T> 0, Z = 1. The ribbon interface complements the program interface: in a pair (symbol, shift direction), it changes the contents of the ribbon, shifts the carriage, and returns a new character that the carriage points to.

    The purpose of the communication layer is to transfer control from program to tape and vice versa, as well as debug printing. In addition, this layer performs the start of the program (implementation costs: to start the execution, the contents of the cell pointed to by the carriage must be explicitly pushed onto the stack).

    The current state of the program is stored using code modification. To perform processing, control is transferred to the point (2,3,0,1) in the T + direction, and goes in a straight line filled with T commands, with the exception of one cell corresponding to the current state. In this cell is the command "x" (go left). The program "goes to the right floor", changes the "x" command to "T", then analyzes the symbol at the top of the stack, puts the desired direction of movement and a new symbol on the stack, after which it gets to the "floor" corresponding to the new state through the side tracks, there puts the “x” command in the cell (2,3,0, T) and goes to the plane Z = T = 0, where it is sent to control the tape.

    Actually, that's all. Here is an example program that implements the doubling of the number recorded on the tape. The program has 7 states, on the tape there is now the number 2 (two units).
    Program
     B  __ Y                          || T  X  2  Y
     01 __ __                         || __ __ __ P  0
     __ __ __                         || y  \  .  +  b  2  x
     __ __ T  .  B  x                 || __ __ 0  X  .  z  __
     Z  __ __ __ __                   || X  2  b  +  .  \  y  
    --------------------------------------------------------------------------------
     __ __ __ __ __ 02 01 __ __ __ __ || Y  t  X  #  ?  __ #  \  __ __ N  __ __ __
     __ T  __ __ X  b  b  __ __ __ Y  || __ __ T  __ __ __ __ __ __ __ FF 00 01 01 00 
     X  b  F  ?  y  B  B  Y  __ __ __ || N  __ p
     y  __ x  x  __ 02 00 T  __ Y  T  || __ __ y
     t  __ f  b  __ __ __ __ __ x  __ || __ __ T
                                      || N  __ p
                                      || __ __ y  __ __ __ __ __ __ __ __ x 
                                      || X  Q  Q  Q  Q  Q  Q  Q  Q  Q  Q  y
    --------------------------------------------------------------------------------
     __ __ __ __ __ 02 00 __ __ __ __ || __ __ t  __ __ __ __ __ __ __ __ x 
     __ T  __ __ X  b  b  __ Y  __ __ || __ __ X  B  B  B  B  B  B  B  B  y
     X  b  F  ?  y  B  B  Y  __ __ __ || __ __ __ 01 #  #  F  x  x  N  N
     y  __ T  x  __ 02 01 Y  T  __ __ || __ __ __
     t  __ f  b  __ __ __ x  __ __ __ || __ __ 2
                                      || __ __ __
                                      || __ __ __
                                      || __ 00 01 #  #  B  x  x  N  01 N
    --------------------------------------------------------------------------------
     __ __ __ __ __ 01 01 __ __ __ __ ||
     __ T  __ __ X  b  b  Y  __ __ __ || 
     X  b  F  ?  y  B  B  __ Y  __ __ ||
     y  __ T  x  __ 02 01 T  Y  __ __ || __ __ __
     t  __ f  b  __ __ __ __ x  __ __ || __ __ ? 
    --------------------------------------------------------------------------------
     __ __ __ __ __ 01 00 __ __ __ __ ||
     __ T  __ __ X  b  b  __ Y  __ __ || 
     X  b  F  ?  y  B  B  Y  __ __ __ ||
     y  __ T  x  __ 01 01 Y  T  __ __ || __ __ t  __ x
     t  __ f  b  __ __ __ x  __ __ __ || __ __ X  ^  y 
    --------------------------------------------------------------------------------
     __ __ __ __ __ 02 01 __ __ __ __ ||
     __ T  __ __ X  b  b  __ __ Y  __ || 
     X  b  F  ?  y  B  B  __ Y  __ __ ||
     y  __ T  x  __ 01 01 __ Y  t  __ || __ __ __
     t  __ f  b  __ __ __ __ x  __ __ || __ __ P  01 
    --------------------------------------------------------------------------------
     __ __ __ __ __ 01 00 __ __ __ __ ||
     __ T  __ __ X  b  b  Y  __ __ __ || 
     X  b  F  ?  y  B  B  __ __ __ Y  ||
     y  __ T  x  __ 02 01 T  __ __ Y  || __ __ __
     t  __ f  b  __ __ __ __ __ __ x  || __ __ - 
    --------------------------------------------------------------------------------
     __ __ __ __ __ __ __ __ __ __ __ ||
     __ T  __ __ %  __ __ __ __ __ __ || 
     X  b  F  ?  y  B  B  Y  __ __ __ ||
     y  __ T  x  __ 00 00 Y  __ __ __ || __ __ __
     t  __ f  b  __ __ __ x  __ __ __ || __ __ ? 
    --------------------------------------------------------------------------------
                                      || 
                                      || 
                                      || __ __ __ __ N  01 x  x  N  
                                      || __ __ t  __ b  b  b  b  b  x
                                      || __ __ X  B  B  B  B  B  B  y
                                      || __ __ __ n  N  n  n  01 n
    --------------------------------------------------------------------------------
                                      || 
                                      || 
                                      || __ __ __ __ N  01 N  x  x  n 
                                      || __ __ t  __ b  b  b  b  b  b  x
                                      || __ __ X  B  B  B  B  B  B  B  y
                                      || __ __ __ N  N  N  __ 01 n  n
    


    If you run this program, it will print
    021 120 020 110 011 110 121 020 021 120 111 110 010 120 121 121 120 120 011 000
    

    Each triple of characters is a new character that needs to be left on the tape (0 or 1), the direction where to move (0 - in place, 1 - to the left, 2 - to the right) and a character that is under the new position of the carriage. You can verify that the program did everything right, and the result is 4.

    With some effort, this implementation can also fit in 2D. But in 4 dimensions, working is a little nicer - much more freedom.

    What's next?


    You can slightly expand the language - add the commands of multiplication, division with the remainder, and popping the number 256 onto the stack (for more convenient division of the number into bytes for writing to memory). True, there will be problems with negative numbers. Instead of 256, you can add the commands “split the low byte” ([x] => [x & 0xff, x >> 8]) and “paste the low byte” ([x, y] => [x + (y << 8)]). But this will only make the language more convenient without changing its essence. It is more interesting to see what is superfluous in the language, and how best to use multidimensional memory.

    For instance:
    • Is it possible to remove the stack and leave only an 8- or 32-bit battery?
    • and if after that add fork (each process with its own battery)?
    • and if instead of batteries we implement a parallel data layer, so that in each cell there will be one command and one byte of data?
    • ... and make all cells work in parallel and at the same time every beat?
    • Is it already a circuit from Minecraft, or not yet? And if not, then I'll drink more ...

    By the way, on esolang a couple more four-dimensional (more precisely, multi-dimensional) languages ​​were discovered. Both are BrainFuck dialects. But in one, the carriage wanders through multidimensional memory, and the program looks like a line on BF, and in the other way around, the program is multidimensional, but the memory is linear. The difference from 4DL is that in both cases the management and work with memory are separate.

    References


    4DL page on esolang
    Page from the author’s blog A
    site with the
    Befunge interpreter and its
    Brainfuck dialects with multidimensional memory
    Brainfuck with a multidimensional program

    Also popular now: