# Rings

Paradigm(s) imperative User:Ardemit 2022 Cell-based one-dimensional Linear-bounded automaton Original `.rn`, `.hrn`

Rings is a simple programming language designed around the idea of working with rotating memory strips. The language was originally designed to compete in the June 2022 Esolang Discord competition.

## Language overview

The language revolves around turnable rings of varying length (or capacity if you want to picture them as all being the same size). Each ring can store up to 255 unsigned 8 bit integers (but cannot be zero-length) and can rotate counter-clockwise up to 255 steps at once (rotary right shift). == NB: Due to a bug in the interpreter, this is not accurate. See below. == All operations working with values stored on the rings only use the currently selected value, usually represented on a state diagram as being the leftmost value on the ring. Imagine looking at a vertical rod, on which the rings are stacked. You are the interpreter and can only see the values in front of you. If you want to access other ones, you need to rotate the rings around. There can be at most 256 rings.

The language's interpreter represents a ring as a list of integers along with an index representing where the current value is. To rotate a ring of length L by N steps, the new value of the index should be (index+N)%L. However, there is a bug in the source code that causes this math to be done with integers that are too small. The end result is that the new value of the index becomes ((index+N)%256)%L instead. This causes rotations to act erroneously in some cases. It also means that the current value of the index, which should be a mere implementation detail, affects the result.

### Table of instructions

Arguments are represented in the form <number of arguments><signed: i, unsigned: u><number of bits>.
HumanRings Rings Arguments Description
mkr 0x0 1u8 Creates a new ring. The argument specifies the length.
put 0x1 2u8 The first argument specifies a ring, the second a literal value, that will be put onto said ring.
rot 0x2 2u8 The first argument specifies a ring, the second a literal value, that will tell the ring how many steps to rotate.
swp 0x3 2u8 Both arguments represent rings. The values of these rings will be swapped.
inp 0x4 1u8 Reads a value from stdin and puts it onto the ring specified by the argument.
out 0x5 1u8 Writes the value on the ring specified by the argument to stdout.
err 0x6 1u8 Writes the value on the ring specified by the argument to stderr.
add 0x7 3u8 All arguments represent rings. Add the values of the first two rings and put them onto the third. (A+B=C)
sub 0x8 3u8 All arguments represent rings. Subtract the second ring's value from the first ring's value and put them onto the third. (A-B=C)
mul 0x9 3u8 All arguments represent rings. Multiply the values of the first two rings and put them onto the third. (A*B=C)
div 0xA 3u8 All arguments represent rings. Divide the first ring's value by the second ring's value and put them onto the third. (A/B=C)
jmp 0xB 1u16 The argument is an instruction pointer, that the interpreter unconditionally jumps to.
jeq 0xC 2u8 1u16 The first two arguments represent rings, the third an instruction pointer. If the ring's values are equal, jump to the pointer. (A=B)
jgt 0xD 2u8 1u16 The first two arguments represent rings, the third an instruction pointer. If the first ring's value is greater than the second ring's, jump to the pointer. (A>B)
jlt 0xE 2u8 1u16 The first two arguments represent rings, the third an instruction pointer. If the first ring's value is less than the second ring's, jump to the pointer. (A<B)
hlt 0xF 1u8 Halts the program, with the argument representing an exit code literal. Special behavior with the argument being 0xFE and 0xFF.

### The hlt instruction

The hlt instruction has special behavior when it's argument is 0xFE (254) or 0xFF (255). In all other cases, the argument simply represents the program's exit code. The two special cases are used for debugging purposes and shouldn't be included in programs intended for release. When the compiler encounters either of these instructions, it prints the current Rings working environment to the default terminal, regardless of the intended method of handling stdout. Specific purpose interpreters can ignore this special behavior. The interpreter starts with the first ring (index 0) and continues up, printing one ring per line in the following format:

```0x<ring index>: (+<ring rotation offset>)[<selected value>][<previous value>]<..>[<next value>]
```

Example `hlt 254` output at one point during the execution of a sorting program (all numbers are in hex):

```0x00: (+00)[FF][FF][FF][D6][D8][DF][F3][FF][FF][FF][FF][FF][FF][FF][FF]
0x01: (+00)[08][00]
0x02: (+01)[0F][01][0C]
0x03: (+08)[00][D1][C3][A9][9E][94][89][5A][4B][00][00][00][00][00][00]
```

The only difference between `hlt 254` and `hlt 255` is that `hlt 255` halts and returns 255 as exit code, while `hlt 254` continues with execution and is useful to debug loops for example.

### Source code structure

The competition imposed several restrictions on the language, one of them being, that a program sorting a list of integers must be at most 100 bytes long. As such, readability has been sacrificed for compression.

Rings uses `.rn` files as the source code. The entire file is in Big-endian. Since the instruction opcodes are only 4 bits, the first byte contains two instruction opcodes. The first 4 bits represent the instruction that is executed first (first instruction). The second instruction are the remaining 4 bits.

```instr1 = byte & 0b1111;
instr2 = byte >> 4;
```

Following are the arguments for the first instruction, then the second instruction. Since the interpreter knows how many arguments the instructions take, there is no terminator at the end of a block. Consider this Rings source code (each pair represents a byte):

```10 08 00 05
```

Because programming directly in native Rings would be very difficult, there is a human-readable variant called HumanRings that compiles into native Rings source code. The code above can be represented in HumanRings as:

```mkr 8
put 0 5
```

### HumanRings

HumanRings is a dialect of Rings that is meant to be programmed in by humans and compiles into Rings source code that the interpreter can execute. A HumanRings compiler should be included standard with general purpose Rings interpreters. HumanRings programs should use the `.hrn` file extension, but the file is written in plain text, so `.txt` can also be used.

In HumanRings, each line corresponds to a single instruction. Leading and trailing whitespaces are ignored, but arguments must be separated by a single regular space (U+0020). HumanRings use all the instructions from native Rings as seen in the table above, but assign a human-readable three-letter name to each. In addition, there is a HumanRings exclusive instruction that declares labels. In native Rings, jump instructions use 16 bit instruction pointers that represent a specific instruction index from the start of the file. If a programmer were to change the previous instructions, the pointer (and all the ones that follow) would start pointing towards wrong instructions. Instead of this system, HumanRings use labels to mark specific instructions and use them in jump instructions instead of absolute values.

Labels are defined using the `:` (colon) character, followed by the name of the label. Names must not contain any whitespaces, so `:lbl_test` is a valid label, but `: lbl_test` or `:lbl test` are not. Jump instructions are then passed the label names (including the colon) instead of instruction pointers.

Literal values are defined using prefixes. Hexadecimal values can use both uppercase and lowercase characters, but the prefix must be lowercase.

System Prefix Example Decimal value
Decimal 182 182
Octal 0 0266 182
Binary 0b 0b10110110 182

Any line beginning with the `#` character is considered a comment and is ignored.

Short HumanRings example program using all the rules described in this section:

```# Declare a ring for no reason and put 241 on it
mkr 13
put 0 0xF1

# Still a comment. Leading and trailing whitespaces are removed!
#Also, noone cares there isn't a space after the hashtag.
# Infinite loop
:go_here
jmp :go_here
```

This program compiles into the following Rings source code:

```10 0D 00 F1 0B 00 02
```

## Computational class

Rings was meant to participate in the aforementioned competition. As such, there are several restrictions imposed upon it. One of them is, that it must be possible to write a program for sorting lists of integers in under 100 bytes. For this reason, Rings is internally limited to 8 bit ring addresses, 8 bit ring lengths and 8 bit unsigned values.

If there weren't any of these restrictions and all of the aforementioned would be unbounded, Rings would be Turing complete. But since these restrictions are in place, Rings is much closer to being a linear bounded automaton.

## Notable problems

• Rings doesn't have a straightforward way of handling EOF, because it only works with unsigned 8-bit integers and thus cannot distinguish what is a valid input and when EOF has been reached. In most cases, 0xFF should be considered EOF.
• Rings has no error handling mechanism, so programmers must take care to handle all possible problems before executing instructions. One of the most common problems are illegal arithmetic operations, that would put an invalid value onto a ring.

## Example programs

All examples are written in HumanRings.

### Count 11 to 20

```mkr 1
mkr 2
put 0 10
put 1 1
rot 1 1
put 1 20

:loop
rot 1 1
out 0
rot 1 1
jlt 0 1 :loop
```

### Cat

A simple cat program. Takes bytes until EOF (0xFF) and outputs them.

```mkr 1
mkr 1

put 1 0xFF

:loop
inp 0
out 0
jlt 0 1 :loop
```

## External resources

User:Ardemit, the author, has created an interpreter for Rings, that can be found on GitHub.