Splaytime
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Ukeharu |
| Appeared in | 2022 |
| Memory system | Tree-based |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Major implementations | Original |
| Influenced by | Brainfuck |
| File extension(s) | .txt, .st |
Splaytime is an esoteric language designed by User:Ukeharu in 2022, that is based wholly around the concept of splay trees. The language was designed to be minimalistic in the number of command characters, with all of them being single-character in length and few in number (three less than Brainfuck). The language is loosely inspired by Brainfuck, but with many of its commands supplanted by features specific to the splay tree at its core, and the addition of a few commands.
Language Description
Splaytime operates on a splay tree, instead of cells like in Brainfuck or other languages, where the individual data-storing units are nodes of a binary search tree (BST). This means that Splaytime has the functionality and characteristics of a BST, being that it is sorted, with inter-node relativity preserved throughout actions, and that search operations are generally faster (O(log n) compared to O(n) in an unsorted cell-based data structure such as an array or linked list), while also having the functionality of a splay tree (described in more detail in a later section).
The individual nodes of the splay tree are much like memory addresses or indexes, with each node having a unique key that they are sorted by, and a data value. The nodes are immutable, and cannot be modified upon creation, only replaced. Commands are performed onto, or relative to, the root of the tree, which can change.
The root of the tree changes with each search and insertion operation, and can be manually changed (while preserving the relative order of nodes) through commands. Input modifies the data value of the root node, and output likewise outputs the data value of the root node.
Other than the tree-related functions, namely searching, insertion, and moving of the root node, and input and output, Splaytime also allows for branch commands that can be conditional (dependent the data value of the root node), namely the jz (jump if zero) command.
Prior to the execution of any commands, the splay tree has one node with the key and data values being 0. Unlike the unbounded tape model, nodes have to be inserted before being accessed. Moreover, unlike languages like Brainfuck, negative indexes exist in Splaytime.
List of Commands
Whitespace and other characters are ignored.
| Command | Description |
|---|---|
{x {x|y {x|y± |
Insert node with key x and value y, or y±1 if a sign is specified. (values of x and y can be the data value of another node of index i, by writing [i instead of a numerical value, or the data value of another node of index equal to the data value of node j, by writing [[j)
|
. |
Print the character signified by the data value of the root node. |
, |
Input a character and store its ASCII value into the root node. |
@x |
Jump to character x of the instruction string if the data value of the root node is 0. (values of x can be the data value of another node of index i, by writing [i instead of a numerical value)
|
$x |
Jump to the node with the key value of x. (values of x can be the data value of another node of index i, by writing [i instead of a numerical value)
|
Things to note:
- EOF has a value of 0.
{makes the inserted node the new root node.- Indexing with
[iwhen jumping with@xwill make the indexed node the new root. - Indexing with
[iwhen there is no node with index i will create a node at that index with value 0. - However, this changing of root only applies after the command is run. This means that
$0{[-1|[jumps to node 0 and inserts a node at the index described by the value of node -1, with the value described by the value of node 0. - Omitting y in
{x|y±, or x in@xor$xwill result in a default value of 0. - Omitting either x or i in
{xor[iwill result in a default value equal to the current pointer. {x±without the separator will cause the ± to be ignored.- When performing jumps, the character number used does not include whitespace, and starts from 0.
- Jumping to a character outside the instruction string will immediately terminate the program.
- There are no double negatives, so trying
{--2will result in an error. {|-defaults to{0|0-and not{0|-1;{|[-defaults to{0|[0-and not{0|[-1.
Programming Tips
Due to the fact that jumping is character based, the author encourages the use of a character counter (set to ignore whitespace) when coding, to mitigate the need for manual counting of characters.
To add breakpoints into the code, simply jump to a node with a data value of 0 and jump to a character outside the instruction string. For instance, if node 0 is the zero register, $0@1000 would usually suffice unless your code is longer than 1000 characters.
Conversion from Brainfuck
It is possible to transpile any code from Brainfuck into Splaytime. One simply needs to ensure that there is a node that stores the cell pointer, and another that serves as a register. An easy way to do this is to run a fixed line of code at the start of every program; for instance, if we allocate node -1 to store the cell pointer (with the 0th cell having index 1 as node 0 is reserved), and node 0 as the zero register (as the example code below assumes), the code to initialise the program would be {-1|1$1 (For versions of Brinafuck interpreters that allow for negative cells, one would simply need to shift all their indexes such that the first cell has an index of 1.)
As part of the initialising of the program, one would also have to initialise all the nodes that are accessed by the code. This can be done by running through the Brainfuck code and keeping track of what cells are accessed, and then initialising them one by one using `{index` before the code provided above.
It follows from this that Splaytime is also Turing complete, since proving that one is able to transpile Brainfuck code into Splaytime also proves that one can simulate Brainfuck in Splaytime, due to the fact that one is able to implement a Brainfuck interpreter in Brainfuck as it is Turing complete. As such, Splaytime is computationally equivalent to Brainfuck.
| Command | Description |
|---|---|
>
|
{-1|[-1+$[-1
|
<
|
{-1|[-1-$[-1
|
+
|
{[-1|[+
|
-
|
{[-1|[-
|
.
|
.
|
,
|
,
|
[ instruction ]
|
@XX$[-1 instruction @XX$0$YY, where XX is the character index of the character after the sequence, and YY is the character index of the first character of the $ instruction.
|
For every command, if the root node is not the cell that is pointed to by node -1, simply run $[-1 before running the instruction.
However, it should be noted that some instructions can easily be shortened, such as the repeated use of + and - when initialising a cell, which can simply be {[-1|value in Splaytime instead of repeated uses of {[-1|[±.
Example Conversion from Brainfuck
Given a Brainfuck code:
++
>>
[
-
]
<<
[
-
>>
+
<<
]
With the spaces removed:
++>>[-]<<[->>+<<]
Which moves the value of the current cell (value 2) to the cell two cells to the right (remove the cell's data if any), the equivalent (directly transpiled) Splaytime code would be:
{1{2{3 (initialising nodes)
{-1|1$1 (initialising pointer)
{[-1|[+{[-1|[+
{-1|[-1+$[-1{-1|[-1+$[-1
@73$[-1
{[-1|[-
@73$0@54
{-1|[-1-$[-1{-1|[-1-$[-1
@177$[-1
{[-1|[-
{-1|[-1+$[-1{-1|[-1+$[-1
{[-1|[+
{-1|[-1-$[-1{-1|[-1-$[-1
@177$0@101
With the spaces removed:
{1{2{3{-1|1$1{[-1|[+{[-1|[{-1|[-1+$[-1{-1|[-1+$[-1@73$[-1{[-1|[-@73$0@54{-1|[-1-$[-1{-1|[-1-$[-1
@177$[-1{[-1|[-{-1|[-1+$[-1{-1|[-1+$[-1{[-1|[+{-1|[-1-$[-1{-1|[-1-$[-1@177$0@101
However, it is clear that this is most certainly not the most efficient way to perform the desired action. As mentioned earlier, several Brainfuck operations can be shortened. Moreover, due to the difference in functionality between Brainfuck and Splaytime, the much more elegant and efficient way to implement the desired action is to simply code directly in Splaytime using its semantics and functionality, which would result in something even shorter than the original Brainfuck code:
{|2{2|[0{0
Which can be even shorter if the behaviour of erasing the data from the original node is not needed:
{|2{2|[0
Splay Trees
In essence, splay trees are a type of BST with an order-preserving rotation operation (like that in AVL trees). A splay tree extends on the simple rotation operation into a new operation called splaying, which brings frequently used elements closer to the root of the tree to speed up operations by reducing the average required tree traversal depth.
Splay trees, unlike AVL or Red-Black trees, do not need to store additional information such as balance factors and colours and hence have a smaller memory footprint, and are generally quite fast. However, the existence of degenerate (skewed to be linear) splay trees means that in the worst case, the time complexity of search operations is O(n), compared to the others' worst case of O(log n), as it would be no different than a linked list. Nonetheless, such a case is rare, and still can perform operations in O(log n) amortised time, and is quicker for cases where the tree is frequently modified and accessed due to the more frequently referenced nodes being closer to the top.
Splaying is in essence the repeated performing of single or double rotation operations to bring a node up to the root while preserving the relative order of the nodes in the tree. There are six kinds of rotations, termed Zig, Zag, Zig-Zig, Zig-Zag, Zag-Zig and Zag-Zag, which are described in the subsection below.
Rotation
For brevity's sake, only the rotations for one side (left-handed side) will be elaborated, the other three rotations are simply mirror reflections of the ones discussed.
A single rotation will shift a node up one rank, and involves making the parent the left or right child of the node (depending on whether the node was the left or right child of the parent), and having the node's current child replace the node as the current parent node's child (meaning that the node's child will be the node's grandchild after the rotation). A rotation where the node is the left child of the parent node is termed a clockwise rotation. Conversely, the rotation where the node is the right child of the parent node is termed a counter-clockwise or anti-clockwise rotation.
(I recommend taking a look at the visualisation of a splay tree linked below for a graphical explanation)
Zig
This rotation is a simple, single clockwise rotation, and is only done as the last rotation when the parent node is also the current root node.
Zig-Zig
This rotation involves first a clockwise rotation about the grandparent of the node, where both the node and its parent are the left child of their respective parents, followed by another clockwise rotation about the parent of the node.
Zig-Zag
This rotation involves first a clockwise rotation about the grandparent of the node, where the parent node is the left child of the grandparent node, but the node is the right child of the parent node, followed by a counter-clockwise rotation about the grandparent (now the node's parent after the clockwise rotation) of the node.
Sample Programs
Here are some sample programs written in Splaytime.
Infinite Loop
The infinite loop is trivially easy to implement, and is just one character:
@
Hello World
The traditional first program:
{|72.{|101.{|108..{|111.{|32.{|87.{|111.{|114.{|108.{|100.{|33.
A slightly more compact version:
{|72.{|101.{|108..{1|111.{2|32.{|87.$1.{|114.$0.{|100.{|33.
Cat
It is almost trivially simple to code out a cat program in Splaytime, which is simply:
{1$0,@13.$1@2
Note that the program will not end if input is from stdin, as the return key is taken to be a newline.
Truth Machine
A truth machine is less trivial to code, but it is still relatively simple. Unlike Brainfuck, due to the fact that Splaytime allows for initialisation of nodes to have non-zero values, one can simply take an input, subtract by 48, terminate if 0 or set the root node to a reference node storing the value for "1" (49) and print it out endlessly.
{3|49{2|12{1,.$2@53{2|[2-{1|[1-{|[-{|[-{|[-$2@53$0@19$1@66$3.$0@58