SHRUB
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:ZM |
| Appeared in | 2022 |
| Computational class | see text |
| Reference implementation | |
| Influenced by | Subleq |
| File extension(s) |
SHRUB (SHift Right, set Uppermost bit and Branch on discarded bit) is an OISC found by User:ZM in late 2022.
Overview
in general SHRUB systems operate on a number of memory cells each holding a string of bits with a fixed identical length, and a sequence of instructions. each instruction specifies a memory cell, a pair of boolean values R and S and two instructions as jump targets. when executing an instruction, the bitstring contained in the memory cell pointed to is shifted one step to the right and the leftmost bit in the string set to the bit that was shifted out, ANDed with R then XORed with S (thus, setting R to true rotates the string by one step to the right with S inverting the new leftmost bit, while setting R to false sets the highest bit to S). execution then continues at one of the two specified instructions, depending on the value that was shifted out.
specific implementations of SHRUB may specify a memory cell size, map instructions into regular memory and/or use a less general control flow system, like specifying only a single instruction that is jumped to if the discarded bit had one of the two possible values, with execution continuing at the next instruction in the list otherwise.
Examples
the following examples specify instructions using the format [label:] mem R S [target0 [target1]]. both jump targets are specified if necessary, one if both are identical and none if execution continues with the next instruction in both cases. memory cell size is left unspecified and memory cells assumed to be zero-initialized; instructions are not memory-mapped.
nearly all computation in SHRUB involves rotating multiple input values by one bit at a time and writing a result bit by bit. to keep track of the current location within such a loop, a counter can be used, initialized to zero except for the highest bit, which is set to one. this approach also allows the program to function regardless of memory cell size. to reach this state from an all-zero register the register in question needs to be shifted right once with S set:
counter 0 1
copying a value into another register requires rotating the first register and writing each bit into the second, using the counter to keep track of the number of rotations that have been carried out:
start: a 1 0 a0 a1 a0: out 0 0 checkIter a1: out 0 1 checkIter checkIter: counter 1 0 start exit
bitwise operations can be handled in a similar manner, using AND as an example:
start: a 1 0 a0 a1 a0: b 1 0 false a1: b 1 0 false true false: out 0 0 checkIter true: out 0 1 checkIter checkIter: counter 1 0 start exit
incrementing a value in register a:
start: a 1 1 carry noCarry finish: a 1 0 noCarry noCarry: counter 1 0 finish exit carry: counter 1 0 start exitOverflow
subtracting one value from another:
start: a 1 0 a0 a1 carry: a 1 0 a-1 a0 a-1: b 1 0 b-1 b-2 a0: b 1 0 b0 b-1 a1: b 1 0 b1 b0 b-2: out 0 0 checkCarry b-1: out 0 1 checkCarry b0: out 0 0 check b1: out 0 1 check checkCarry: counter 1 0 carry exitCarry check: counter 1 0 start exit
replacing the jumps to exit and exitCarry with jumps to the starts of other subtractions allows compiling SBN programs into SHRUB.
Computational class
SHRUB is capable of performing complex operations on arbitrary memory values and features arbitrary control flow, thus making it very likely capable of emulating a bounded-storage machine whose tape length is proportional to the amount of memory the program has access to. however, SHRUB programs can only ever access a predetermined finite amount of memory: if its memory cells were infinitely large, it would take infinitely long to read a previously written value, and the number of accessible memory cells is finite and constant in the case that instructions aren't memory-mapped, and (at best) bounded exponentially by their size if they are (depending on the instruction encoding); SHRUB therefore isn't Turing-complete.
if the size of each memory cell is proportional to the size of the input, SHRUB without instruction memory mapping is (probably) equivalent to a linear bounded automaton, while SHRUB with memory mapping (again, potentially) has access to an amount of memory exponentially bounded by its input size.
Implementations
SHRUB is currently unimplemented.