StackLinearModulo2

StackLinearModulo2 is an esoteric stack-based programming language by islptng, focused on bitwise operations and stack manipulation, with all logic ultimately reducible to the NAND operation. It operates on a stack of custom bitset objects, allowing for linear algebra-like manipulations over the field GF(2) (modulo 2 arithmetic), hence the name.

Overview

StackLinearModulo2 programs are sequences of single-character commands. The language manipulates a stack of Bitset objects, each representing an unbounded twos-compliment integer as a binary string (with sign, for finite representation). The language supports basic stack operations, bitwise NAND, and simple looping constructs.

Bitset Representation

• Each stack element is a Bitset object.
• Every bitset corresponds to an integer and vice versa.
• A bitset is a string of bits, with the LSB at the beginning, and an infinite suffix which is called its sign.
• Bitsets with a sign of 0 are positive (infinite suffix of all zeros) and those with a sign of 1 are negative (infinite suffix of ones).

Commands

Command	Description
+	Shift right (arithmetic): multiplies the top of the stack by 2 (inserts a 0 at the LSB).
-	Shift left (arithmetic): divides the top of the stack by 2 (removes the LSB).
:	Duplicate the top element of the stack.
/	Swap the top two elements of the stack.
<	Rotate the stack so the top element moves to the bottom.
>	Rotate the stack so the bottom element moves to the top.
|	Pop the top two elements, push their bitwise NAND result.
[	Start a loop. Push a copy of the current top element to a loop stack for comparison.
]	End a loop. If the top of the stack is not equal to the value at the start of the loop, jump back to the matching [.

Input and Output

• The program reads two lines:
  • The first line is the StackLinearModulo2 program (a string of commands).
  • The second line (optional) is a space-separated list of integers, which are converted to Bitset objects and pushed onto the stack. If no input is provided, the stack is initialized to have a single 0 on it.
• After execution, the stack is converted back to integers and printed as a space-separated string.

Examples

The following is a set of convenient concatenative operations. The language does not support aliases, so code containing these aliases must have them replaced with the rightmost breakdowns in order to be run with the official interpreter.

nand = |
dup = :
swap = /
pre0 = +
clip = -

not = dup nand = :|
and = nand not = |:|
or = not swap not nand = :|/:||

0 = dup dup not and = :::||:|
m1 = 0 not = :::||:|:| = :::||
1 = m1 pre0 not = :::||+:|

# TOS = stack
# pushes 1 if the TOSTOS is set, otherwise 0
test = dup 1 and = ::::||+:||:|
# TOS = stack
pop = clip = -
# TOS = bit to push, NOS = stack
push = swap pre0 or = /+:|/:||

In general any number in the form $2^{n}-1$ can be pushed to the stack with :::||k:|, replacing k with n many +.

Note that since there are no operations which take in one element and delete it (pop), and the stack starts with at least one element, the stack can never become empty. The constant push programs like 0 use the fact that there will always be something on the stack. The 0 program in particular duplicates the TOS, then duplicates it again. It then inverts one of the duplicates, and ANDs the two duplicates together. Since a AND (NOT a) is always 0, this program will push a 0 to the stack regardless of the stack's arrangement.

Reference Implementation

The reference implementation is in Python:
Try it online!