Daoyu
Dàoyǔ (道语), or DaoLanguage, is an esoteric, homoiconic programming language made by User:Kaynato in 2016, modeled after about two or so tenets of Daoist philosophy. It is inspired by other elegant and minimal programming languages such as Iota, Jot and FALSE, though the actual functionality bears little resemblance to that of those.
The core data structure is a bit tape accessed via a tree. An accessor is called a Reader.
Program execution depends on two readers: One reader to read a bit tape as program, and another reader to read and modify a bit tape as data. It is possible for both these bit tapes to be one and the same. Bit-tapes are associated with each other vertically - each may have a parent and a child bit-tape.
Daoyu has 16 opcodes which are stored in memory with the 16 hexadecimal digits. Therefore, all bytestreams are valid Daoyu programs. However, it is likely that attempting to run most files as Daoyu programs would result in infinitely looping, or quickly self-terminating programs.
Daoyu has been implemented in C (with hazardous eager bit tape) and Nim (with lazy hybrid bit tape).
Terminology
Hex: A group of 4 bits.
Reader: An accessor of a bit tape via a tree.
Executor: An object which steps through the daoyu program. It consists of a reader to access a bit tape as program, and another reader which accesses and modifies a bit tape as data. An executor also holds an additional value called the operating level which may affect the function of the Daoyu operations.
Running a Daoyu Program
Daoyu always operates on bit-tapes of power-of-two length. A bit-tape of a length not a power of two is an unreachable illegal state.
On running a Daoyu program, a bit-tape is generated from the source.
An executor is created with a program reader situated at the first hex of the program data, and a data reader situated at the single bit of a newly allocated bit-tape.
At each step, the hex accessed by the active executor's program reader is read, which selects the operation.
The operation is able to modify the active executor's program reader or any bit tape.
Writing a Daoyu Program
.dao is a text-editable format containing the 16 Daoyu Human-Friendly Symbols, and comments (Both ')' and ']' are interpreted as the same operation, MERGE.):
Regarding comments: All invalid symbols, or characters in a line after ‘@’ will not be read by the compiler.
.wuwei files are interpreted as a raw hexadecimal stream, reading bytes in big-endian order.
Commands
The functionality of the symbols is as follows.
To better represent the effect of the operations on the bit-tape reader and data, we will use a tree representation of the bit tape.
For example:
(P 0) - Represents a node of 2^P zeroes (P 1) - Represents a node of 2^P ones (P (P-1 A) (P-1 B)) - Represents a node of 2^P bits, for which the left half of 2^(P-1) bits is represented by "A", and the right half by "B" (xAC) - Represents a node of 2^3 bits (a byte), which contains the bits of the byte 0xAC (0 0) - Represents a node of a single bit which is zero. (*P ...) - Represents that the reader is currently selecting this node.
| NAME | SYMBOL | HEX | FUNCTIONALITY | EXAMPLE |
|---|---|---|---|---|
| IDLES | . | 0x0 | NOP | <Data not altered> |
| SWAPS | ! | 0x1 | OPLEVEL 0:
When selecting more than one bit, swap the left and right halves of the data reader's bit-tape. Bit-order is preserved. Otherwise, do nothing. |
(*P (P-1 A) (P-1 B)) => (*P (P-1 B) (P-1 A)) |
| LATER | / | 0x2 | OPLEVEL 0-3:
When the data reader is selecting the left child of a node, select instead the right child. When the data reader is selecting the right child of a node, perform MERGE instead. This may move the data reader to the parent bit-tape. (See MERGE) OPLEVEL 4-9: If possible, move the data reader right on the bit-tape by the length of its selection. |
OPLEVEL 0-3: (P (*P-1 A) (P-1 B)) => (P (P-1 A) (*P-1 B)) (P (P-1 A) (*P-1 B)) => (*P (P-1 A) (P-1 B)) OPLEVEL 4-9: (P+1 (P (*P-1 A) (P-1 B)) (P (P-1 C) (P-1 D)))) => (P+1 (P (P-1 A) (*P-1 B)) (P (P-1 C) (P-1 D)))) => (P+1 (P (P-1 A) (P-1 B)) (P (*P-1 C) (P-1 D)))) |
| MERGE | ] or ) | 0x3 | OPLEVEL 0-6:
If the data reader is not selecting the entirety of its bit tape, select the parent node. Otherwise, if the bit tape has a parent bit tape, move the data reader to select the parent's leftmost bit. |
(P (*P-1 A) (P-1 B)) => (*P (P-1 A) (P-1 B)) (P (P-1 A) (*P-1 B)) => (*P (P-1 A) (P-1 B)) (*P (P-1 A) (P-1 B)) => ...(*0 ?)... in parent bit-tape |
| SIFTS | % | 0x4 | OPLEVEL 0-4:
From the data reader rightwards, moves all hexes of 0x0 to the rightmost portion of the program. |
(TBD) |
| EXECS | # | 0x5 | OPLEVEL 0-7:
Create a new Executor with a program reader cloned from the current data reader, and a data reader that selects the root of the currently selected bit-tape's child bit-tape. When no such child exists, a child bit-tape of a single zero bit is created. The old executor is moved onto the stack and the new executor is set to the active executor. |
(TBD) |
| DELEV | > | 0x6 | ALWAYS:
Decrements the operating level of the active executor unless it is zero. |
N/A |
| EQUAL | = | 0x7 | OPLEVEL 0-4:
When the leftmost and rightmost bits under the data reader are not equal, skip the next symbol in the program reader. |
N/A |
| HALVE | ( | 0x8 | OPLEVEL 0-6:
When selecting more than 1 bit, move the data reader to the left child node. Otherwise (when selecting only 1 bit), if there exists a child bit-tape, move the data reader to the root of the child bit-tape. Otherwise (if then there is no child bit-tape) do nothing. |
(*P (P-1 A) (P-1 B)) => (P (*P-1 A) (P-1 B)) (*0 0) => (*P ...) in child bit tape (*0 0) if there is no child bit tape |
| UPLEV | < | 0x9 | OPLEVEL 0-8:
Increment the operating level of the active executor, and return the program reader to its location when the executor owning it was created. |
N/A |
| READS | : | 0xA | OPLEVEL 0-5:
Prints out the bit-tape under the data reader to standard output, as ASCII when at least a byte, otherwise, as a binary string. |
N/A |
| DEALC | S | 0xB | OPLEVEL 0-1:
Halves the length of the bit-tape accessed by the data reader if it is greater than 1 bit. Then, if the selection length is greater than 1 bit, perform HALVE on the data reader. Any readers formerly selecting the now-removed data will be moved left by the length of the deallocation. When the bit-tape is only one bit, this will destroy the bit tape and all its children. Any readers formerly selecting the now-destroyed data will be rendered invalid. Stepping with any reader accessing destroyed data would cause that executor to terminate. |
(*P (P-1 A) (P-1 B)) => (*P-1 A) (P+1 (*P (P-1 A) (P-1 B)) (P (P-1 C) (P-1 D)))) => (P (*P-1 A) (P-1 B)) (P+1 (P (P-1 A) (P-1 B)) (*P (P-1 C) (P-1 D)))) => (P (*P-1 A) (P-1 B)) (*0 0) => [EXECUTOR TERMINATED] |
| SPLIT | [ | 0xC | OPLEVEL 0:
When selecting more than 1 bit, set all bits in the left half of the data reader to 1, and all bits in the right half to 0. Then, perform HALVE on the data reader. OPLEVEL 1-6: Perform HALVE on the data reader. This may move the data reader to the child bit-tape. |
(*P (P-1 A) (P-1 B)) => (P (*P-1 1....) (P-1 0.....)) (P+1 (*P (P-1 A) (P-1 B)) (P (P-1 C) (P-1 D)))) => (P+1 (P (*P-1 1...) (P-1 0...)) (P (P-1 C) (P-1 D)))) => |
| POLAR | * | 0xD | OPLEVEL 0-2:
If the leftmost bit of the data reader is not greater than the rightmost bit, skip the next instruction read by the program reader. |
N/A |
| DOALC | $ | 0xE | OPLEVEL 0:
Double the size of the bit-tape accessed by the data reader, then call MERGE. New bits are always initialized as zeros. |
(*P (P-1 A) (P-1 B)) => (*P+1 (P (P-1 A) (P-1 B)) (P 0...) => (*0 0) => (*1 (0 0) (0 0)) |
| INPUT | ; | 0xF | OPLEVEL 0-5:
Write from input to the selection of bit-tape accessed by the data reader. If the selection is smaller than a byte, the input may be truncated. If the selection is greater than a byte, more than one character may be read. |
(TODO) |
The following table describes the effects of changing the operating level. At the level shown on the left hand column, the functionality of the symbol first defined at level 0 should be altered to that at the appropriate row of level. For example, at level 1, SPLIT is interpreted as HALVE and DOALC is treated as IDLES.
Generally, "Level" is used to selectively disable functionality typically only executed once for the purpose of initialization. For example, DOALC, if looped, can severely confuse the selection length and consume memory, while SPLIT will usually cause information to be lost from future program states. However, as SPLIT also is used to alter the selection location, the first "Level" only causes SPLIT to be interpreted as HALVE.
Data, Selections, and Nesting
Let us have a .dao file that we are running.
The translated binary code from this .dao file that is loaded into the interpreter is called the "Top Level Program," or TLP.
In loading the TLP, the interpreter creates a path with the smallest size greater or equal to that of the TLP, and then reads the TLP into the path data.
Then, the interpreter selects the first bit of the TLP, and calls EXECS, generating a new path owned by the TLP.
Whenever EXECS is called on a path that does not have a child, it creates one with one zero bit.
These paths, being the central data element of Daoyu, are binary strings that may only have bit sizes that are powers of two.
A selection represents the "active range" for commands that may act - for example, SWAPS (!) only switches the bits in the halves of the selection.
A child tape may be destroyed by calling DEALC on it while its length is one - that is, calling DEALC on a tape of only '0' or only '1'.
One may call EXECS on a program that already has a child tape - in that case, that program will execute its data as commands on the pre-existing tape, keeping the existing selection size of the child tape.
.wuwei is a compiled, binary code data file that can be directly read as a Daoyu program.
When a .dao file is compiled, the symbols are replaced with the 4-bit codes as shown in the above table. The interpreter or compiler, when provided with the .wuwei file, should then load the data directly into memory as an unbroken data tape and call EXECS from its beginning.
A .wuwei file can be edited by a hex editor, but is not as human-friendly in editing as .dao files are, since comments are difficult in the limited alphabet of hexadecimal code.
On Writing in Daoyu
Print-out programs: The methods are to: - Make ASCII codes in the data and read over them (see helloworld.dao) - Write ASCII for your intended output inside the source, selecting and reading the appropriate sections.
Input-filtering programs (see truth.dao): Use a combination of SWAPS, POLAR, and EQUAL to check for the bit state of the input. With UPLEV, one can cause the program to re-request a character (or other input), and with DEALC, one may terminate the program (as in truth.dao). It may be necessary to write a program inside your data (preferably at its end, so that the program does not read the data) which also checks and manipulates your data. It is suggested to funnel all unwanted states into the same state.
Counting: (To prove) Identify a permutation cycle on a bit state using the same operations each time. The state should also be able to be read in a different way so as to retrieve the "number."
Memory: (To prove) Keeping bits in a partition before the program's beginning.
Functions: (To prove) Constructing DEALC-terminated programs in different partitions.
Functionality to Explore
Moving the data pointer into the main program and calling EXECS. If the "main program" (Which starts from the beginning) is DEALC-terminated, could this be used to massively simplify "Function" functionality?
Example programs
| NAME | DATE WRITTEN | AUTHOR | SIZE | PURPOSE | MAXIMALLY CONDENSED CODE |
|---|---|---|---|---|---|
| helloworld.dao | 2016-03-23 | Kaynato | 76 Bytes | Comma-less Hello, world! | $$$ (([]!)/([])): ((/[])/([]!/[]!)): (/[]):: [/([]!/[])]!: [[[]]!]: [([]!)/[/[]!]!]: [/([]!/[])]!: [([]!)/(/[])]: ((/[])/[]): (/([]!)): ([[]]!/[[]!]!): [[[]/[]]]!: |
| cat.dao | 2016-03-25 | Kaynato | 4 Bytes | Cat program | $$$>;:< |
| helloworld2.dao | 2016-03-26 | Kaynato | 32 Bytes | More efficient helloworld.dao. However, it will print some null characters. | ))))))))/:((((((S............... %(>#>[>[>;/.==>;=/>[>%/!.:...... |
| truth.dao | 2016-03-28 | Kaynato | 136 Bytes | Truth-machine | $$$;
(
*[=[*] *S=S=S=S=S
( !) =S*S=S=S
(/!) =! *S*S=S=S
)
! =[=] *S=S=S=S
((!)) =[=] *S=S=S=S
(!) =[=] *S=S=S=S
(!)!
$$$$
((/(/(/(/([]!/[])))))
/(((([]!/[]!)/([]!/[]!))/(([/[]!]!/([]/[]))/([/[]!]!/[/[]]!)))
/((([/[]!]!/[/[]!])/(([]/[])/([])))/((([])/([]))/(([])/([]/[]!))))))
((/(/(/(/#))))SSSSSSS
|
| truth_machine_small.dao (Not included in dist.) | 2016-12-03 | a52 | 26 Bytes | An optimized truth machine. It's so small because it self-modifies its own code, and assumes the input is either a 0 or 1. | $$$; @ Takes input =(!*S)=(*S=S=S.............. @ If it's a 0, end the program !:))))))))[[[[[[[[>< @ If it's a 1, delete the first half of the TLP & loop @ Inputs other than 0 or 1 produce unpredictable behavior |
| function.dao | 2016-04-18 | Kaynato | 136 Bytes | Program implementing the idea of writing "functions" directly in the TLP source code. | $$$$$$$( (((([]!/ []!)/([] !/[]!))/ @ 32n (([]!/[] !)/([]!/ []!)))/( (([]!/[] @ 64n !)/([]!/ []!))/(( []!/[]!) /([]!/[] !))))/(( (([]!/[] !)/([]!/ [[]]!))/ @ 128n [[([]!/[ ]!)]])/( (([[]!]/ [/[]!]!) /[/[[]!] ]!)/([/[ []!]]!/( [[]!]/[[ ]!]))))) #SSSSSSS S....... ........ ........ ........ ........ ........ @ 256n (/(/:... SSSSSSSS |
Example Execution (helloworld.dao)
Debug log from running helloworld2.dao with the tree-based nim interpreter:
daox -d=2 run helloworld.dao
Program data (Bit-tape 0)
: : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
: The initial bit-tape is a single-bit zero.
Init lv 0 : data : (Path: [ 1^ ] pow: 0 idx: 0 NPos: Dnk8 (b0))
: path : (b0)
: We immediately navigate upwards and select the second half of the program itself, which contains the encoded ASCII string.
op ) lv 0 : data : (Path: [ 0 v] pow: 0 idx: 0 NPos: Dnk8 (b0))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 1 idx: 0 NPos: Dnk8 (b00))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 2 idx: 0 NPos: Dnk8 (x3))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 3 idx: 0 Node: Dnk8 (x33))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 4 idx: 0 Node: DnkMIX ((x33) (x33)))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 5 idx: 0 Node: DnkMIX (((x33) (x33)) ((x33) (x33))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 6 idx: 0 Node: DnkMIX ((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ) lv 0 : data : (Path: [ 0 v] pow: 7 idx: 0 Node: DnkMIX (((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op / lv 0 : data : (Path: [ 0 v] pow: 7 idx: 0 Node: DnkMIX (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
: We print the string. Due to the way the logging is done, the print result shows up before the debug print for the command.
Hello world!
op : lv 0 : data : (Path: [ 0 v] pow: 7 idx: 0 Node: DnkMIX (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
: We then waste some time and deallocate the second half of the program to avoid execution of the string data.
op ( lv 0 : data : (Path: [ 0 v] pow: 6 idx: 0 Node: DnkMIX ((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ( lv 0 : data : (Path: [ 0 v] pow: 5 idx: 0 Node: DnkMIX (((x48) (x65)) ((x6C) (x6C))))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ( lv 0 : data : (Path: [ 0 v] pow: 4 idx: 0 Node: DnkMIX ((x48) (x65)))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ( lv 0 : data : (Path: [ 0 v] pow: 3 idx: 0 Node: Dnk8 (x48))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ( lv 0 : data : (Path: [ 0 v] pow: 2 idx: 0 NPos: Dnk8 (x4))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op ( lv 0 : data : (Path: [ 0 v] pow: 1 idx: 0 NPos: Dnk8 (b01))
: path : ((((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0))) (((((x48) (x65)) ((x6C) (x6C))) (((x6F) (x20)) ((x77) (x6F)))) ((((x72) (x6C)) ((x64) (x21))) (((x0A) (x00)) (4 0)))))
op S lv 0 : data : (Path: [ 0 v] pow: 0 idx: 0 NPos: Dnk8 (b0))
: path : (((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0)))
op . lv 0 : data : (Path: [ 0 v] pow: 0 idx: 0 NPos: Dnk8 (b0))
: path : (((((x33) (x33)) ((x33) (x33))) (((x2A) (x88)) ((x88) (x88)))) ((((xB0) (x00)) (4 0)) (5 0)))
(...IDLES continue until program terminates...)
Exited with next_cmd 0
Stack length zero, terminating execution