Realm

Realm

Paradigm(s)	Graph-rewriting paradigm
Designed by	Hakerh400
Appeared in	2019
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

The main purpose of designing and implementing Realm is to construct a programming language that is as simple as BF, but more essential than lambda calculus. While implementing interpreter for Functasy, designers of Realm noticed that any execution state of a Functasy program can be represented in Realm, thus making Realm easy for implementing a functional programming language (which, in contrast, seems very hard in BF). At the same time, it is easy to implement classes, objects, loops, if-else statements, etc, which suggest that Realm can also be considered to be of object-oriented or imperative paradigm.

Details

Memory consists of a directed graph. Each node in the graph has exactly two pointers, labeled as 0 and 1. Each pointer must point to another node in the graph (pointers cannot be null). There is one root node and all addressing are performed relatively to it. A Node can be allocated explicitly, but can be deallocated only implicitly (when there is no paths from the root node to the given node). Each node is unique - two nodes are considered to be equal only if they represent the same node (their addresses point to the same node). Nodes do not contain any extra information except the two pointers.

An address in memory is represented as sequence of bits, where each bit means which pointer to pick when following path - we start from the root node, then pick pointer 0 or 1 from the root node (depending on the first bit of the address), then the second bit, etc. Address can be arbitrary large, but it can also be empty and in that case it represents the root node (note that the root node may also be accessed using some other address if it points to root node).

At the beginning of the program execution, the memory consists of a single node (root node) and both pointers point to the root node.

Instructions

There are 4 different types of instructions:

1. Assign a node from address A to address B
2. Create a new node that points to nodes from addresses A and B and assign to address C
3. Output a sequence of bits
4. Repeat a sequence of instructions while node at address A is equal to the node at address B

Input is not a special instruction. It can be performed in any instruction by inserting question mark signs ? into any sequence of bits. For example, address 10??1? can be resolved to 8 different addresses depending on the bits from the input stream. Address resolution is performed each time the instruction is executed, so a single address from the source code that contains question marks can be resolved to different addresses if it is in a loop.

I/O format

Both input and output are streams of bits.

Syntax

Assignment

Assigning node from address B to address A is syntactically represented as

A.B

where A and B are sequences of zero or more zeros, ones and question marks. Here are some examples (comments on the right represent what the instruction does and root stands for the root node):

0.1    // root[0] = root[1]
00.    // root[0][0] = root
.1?10  // root = root[1][readBit()][1][0]
.      // root = root ---> Note: this instruction has no effects

Allocation

Allocating a new node which points to nodes at addresses B and C respectively and assigning that node to address A:

A.B.C

Examples:

1.0.1  // root[1] = new Node(root[0], root[1]) ---> Note: right hand side is evaluated first, so now root[1][1] points to the previous value of root[1]
0..0   // root[0] = new Node(root, root[0])
..     // root = new Node(root, root) ---> Note: this does not mean that root now points to itself, but that both pointers of the new root point to the old root

Output

Output sequence of bits A:

A

Examples:

1011  // writeBit(1); writeBit(0); writeBit(1); writeBit(1)
0?1   // writeBit(0); writeBit(readBit()); writeBit(1)
?     // writeBit(readBit())

Note: sequence of bits must contain at leaast one bit (since the instruction cannot be empty)

Loop

Perform a sequence of instructions while the node at address A is equal to the node at address B:

A.B (
  // here goes the loop body
)

Examples:

.()         // while (root == root) {} ---> Note: this is an infinite loop
0.1(0..)    // while (root[0] == root[1]) { root[0] = new Node(root, root); } ---> Note: this will iterate at most once
.0(1.(..))  // while (root == root[0]) { while (root[1] == root) { root = new Node(root, root); } }

Note: syntax parser is "greedy", which means that at the given location in the source code the instruction of the maximal length will be parsed. Therefore, A.B() cannot be interpreted as assignment B to A, because the are parentheses after it, so it represents a loop.

Examples

In the next examples we assume the following I/O implementation: input, which is a sequence of bytes, is converted to bit array by converting each byte to bit array (prepend zeros to make it of length 8), then reversing bits of each byte, then concatenating all bits together, prepending bit 1 before each bit, then appending infinitely many zeros. Output format is the same as input format, except there are no prepending bit 1. For example, input string abc converts to input bit array

111010101011111010111010101111101111101010111110000000000...

while the following output bit array represents the same string abc

100001100100011011000110

Cat

0..
?.(
  1.?
  1.(
    1
    1..
  )
  1.0(
    0
    1..
  )
  1.
)

Try it online

Note: the whole program can be simplified to

0.. ?.(?)

Try it online

but the intention here is to demonstrate nested loops and other things that may not be clear from the specification.

Truth-machine

?.
0..
?.(
  .(
    10001100
  )
)
00001100

Try it online

Interpreters

Realm interpreter