Ring-around-the-Rosie

Designed by User:Salpynx so that all source code is represented by a ring surrounding a single unbounded register; a wikipedia:Wheel graph W_n, which is always embeddable in a 2D plane. Inspired by Wire-crossing_problem, Minsky machines, and User:Salpynx/Braneflage.

It is designed to be Turing complete and show that control flow and memory access can be arbitrarily simplified when diagrammed if the mechanics of the language compensate. The control flow "sequential" ring allows for arbitrary addressing with skips, and the "single" register simulates any finite number of prime encoded registers, including one to store the current active node address.

Syntax

The first three columns of a source file represent the 'ring'. * characters are the nodes, and R is the central (unbounded) register.

Nodes are labelled clockwise, with the node closest to the register designated 1. For the purposes of simplifying the source representation: R must be on the same row as exactly one node. R cannot occur on the first or last lines since these represent edges of the ring. R can only occur in the second column, inside the ring.

Non-register lines can contain more than one node (2 on the opposite sides of the ring, or up to 3 on the top and bottom edges). They will share the same code body, but their trigger ids will differ.

Symbols after the first three columns represent the node commands. Nodes can be empty, but executing an empty node will cause the program to enter an infinite loop.

Node Commands

• :digits: ([1-9][0-9]*) : If R Mod :digits: is not equal to zero, execute the following super and/or subscripts, otherwise proceed to the next :digits:
• :superscript: ^{(([1-9][0-9]*([0-9]+)))+} : Multiply R by :superscript: (a series of concatenated exponents)
• :subscript: _{(([1-9][0-9]*(^[0-9]+)))+} : Divide R by :subscript: (a series of concatenated exponents)
• i  : read one byte of input and multiply R by 2^byte_value
• 0  : set R to 0 (i.e. Halt condition)
• .  : output characters following . to EOL (no newline). This is done regardless of other commands at the node, even if there is a halt.
• :  : output characters following : to EOL + a newline. This is done regardless of other commands at the node, even if there is a halt.

Program execution

• The register R is initialised to 2.
• The instruction pointer, n, proceeds around the ring in order, starting from 1.
• If R/2ⁿ results in an odd integer, the commands at the current node n are executed, otherwise the pointer moves to the next node.
• If R is zero, execution halts.

Examples

Hello World

*

 R* 0:Hello, World!

 * 

Truth machine

***
* *
* *
* *
* *
* *
* *
* *
* *
* *
  * 0:0
  * .1
* *
 R* i
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
***

Count to Ten

Demonstrates forward and backwards 'jumps' using the sub and superscript notation. The 3 :digit: represents a test on a zeroed virtual prime-register, so it always fires, modifying the 2 prime-register, which represents the next node target.

*     32:Four
  *   324:Five
  *   326:Nine
  *   32:Eight
  *   32:Seven
  *   32:Six
 R*   322:One
  *   0:Ten
*     32:Three
* *   322:Two

99 bottles of beer

*
  *
  *
 R* 373102#{init units in v.reg 3}
  * 375102#{init tens in v.reg 5}
  * 37571152# 1st tens
  * 37115112
  * 37223
  * 37371132# 1st units
  * 37113112
  * 3713220
  * 372: bottles of beer on the wall,
  * 37571152# 2nd tens
  * 37115112
  * 37132216
  * 37371132# 2nd units
  * 37113112
  * 37133213
  * 372: bottles of beer.
  * 3723 35310 373 35 529 35 373:Take one down, pass it around,
  * 375711 52# 3rd tens
  * 37115112
  * 3713428
  * 37371132# 3rd units
  * 37113112
  * 3713525
  * 372: bottles of beer on the wall.
  * 372:
  * 37223
  * 0:No more bottles of beer on the wall.
    # Output digit from v.reg 7, return stored in v.reg 13:
  * 3722772
  * 37219.0
  * 3722772
  * 37217.1
  * 3722772
  * 37215.2
  * 3722772
  * 37213.3
  * 3722772
  * 37211.4
  * 3722772
  * 3729.5
  * 3722772
  * 3727.6
  * 3722772
  * 3725.7
  * 3722772
  * 3723.8
  * 3722772
  * 372.9
  * 372 13243# jump back after 1st tens
  * 37213 13241# jump back after 1st units
  * 37213 13238# jump back after 2nd tens
  * 37213 13236# jump back after 2nd units
  * 37213 13232# jump back after 3rd tens
  * 37213 13230# jump back after 3rd units
***

Ouput:

99 bottles of beer on the wall,
99 bottles of beer.
Take one down, pass it around,
98 bottles of beer on the wall.

...

01 bottles of beer on the wall,
01 bottles of beer.
Take one down, pass it around,
No more bottles of beer on the wall.

This could be improved with a few more checks to drop leading zeros and use singular 'bottle' for 1, but this is the first 99 bottles I'm aware of written for a single register Minsky Machine.

Recalculating jump offsets after adding new nodes seems to be the main challenge with this language. The subscripts and superscripts indicate virtual registers changes surprisingly well

This program was created to be sufficiently complex and large to test the different execution strategies: sequential, random walk, and arithmetic.

Variations

Random-walk-around-the-Rosie

Since the entire state of the program is encoded in the single unbounded register, and the physical-machine circling instruction pointer is just a conceit to demonstrate non-branching control flow embeddable on a 2D plane without wire-crossing; this language behaves identically if the physical instruction pointer starts and moves randomly about the wheel graph. In this variation, the central R node (n = 0) can be visited. The eventual computation and output will be identically deterministic, however the execution time will be non-deterministic.

Despite the 'real' effective active node pointer / program-state being distinct from the 'physical' machine's current node, a real test operation is carried out at every visited node, taking real machine cycles to complete. The path and operation at these randomly (or sequentially) visited nodes is 'real' in an objective sense.

Branchless: ɾ

The dimensionality and structure of this language can be reduced even further by using a branchless evaluation technique to control the register value:

${\text{ɾ}}_{i}={\text{ɾ}}_{i-1}\sum _{j=0}^{n}\left[\left({\frac {{\text{ɾ}}_{i-1}}{2^{j}}}{\bmod {2}}\right)\prod _{k=0}^{|t_{j}|}a_{j,k}^{[t_{j,k}|{\text{ɾ}}_{i-1}]}\right]$ {note: needs review, I think the concept is sound, but this formula may be off}

Where:

• The single unbounded register is denoted ɾ U+027E (visual pun on branchless r...)
• There are n 'nodes'
• $t_{j,k}$ represents the virtual-prime-register 'trigger' for the kth trigger of the jth node
• $a_{j,k}$ represents the final multiplier to apply if $t_{j,k}$ is activated

The pure arithmetic interpretation lacks IO side-effects, but evaluates all nodes at every step, further messing with the idea of "control-flow" and dimensionality.

IO side-effects

We could add a side-effect array: at every step check n (i.e. contents of virtual-2-reg) and run the nth side effect. Input (as currently specified in ratr) has an additional guard based on ɾ. However, input could be made unconditional, in the same way as output. This would not change the computational class of the language. Passing ɾ to the blocking side-effect would also work.

Possible extension for side-effect efficiency: use v.reg.3 as a bool to indicate whether there is a side effect to look up at all. Maybe this doesn't save much; IO side-effects somewhat break the branchless arithmetic regardless.

There is likely a way to branchlessly compile an output string followed by 0 or 1 input prompts at every iteration based on the current value of ɾ. That would be the purest implementation.

Summary of Control-flow strategies

• ratr : sequential
• rwatr : random
• ɾ : all and simultaneous (arithmetic nature breaks IO)

Computational class

Ring-around-the-Rosie is effectively a single register Minsky machine, with the modulus testing ability and multiplication / division abilities required to simulate an arbitrary number of prime encoded virtual registers, making it Turing complete. The notable difference is that it requires its single register to encode the effective instruction pointer location in the '2' prime virtual register instead of having the operating machine track this element of state separately.