Spin4

spin4 is an esoteric programming language created by Michael that uses 4D rotations for computations.
spin4's main philosophy is to write programs by rotating the 4D space which encodes a state, this state is then used to increment or decrement an accumulator vector. The accumulator components can then be put on the stack, the later can also be rotated in one direction.
== Overview ==
Ultimately, a spin4 program has
* An accumulator vector with 2 components, register X and Y
** We can accumulate values as we perform rotations by doing addition, substraction, multiplication or integer division
** We can operate on its component X or Y
** The value of the accumulator is incremented/decremented as we rotate in the 4D-space
* A single stack
** We can push the value of the accumulator one component at a time i.e. push the value of X or Y
** We can perform a push with the standard input
** We can rotate it from left or right
** We can pop the top element to one register at a time
** We can print the top element
** We can push the user input to the top
== Examples ==
=== Hello World ===
This program displays Hello World
 {(+1>)x?y}(+0000>)*[<][<][y]y[>][>][x]x*[>][>][y]y[<][<][x]+[x]+[.c] [x]x+[x]+[x]+[x]+[<][yx]y[>]-(+1054<5401>012111<)x(+0>)x[.c][<][<][<]
 [<][yx]xy[>][>][>][>]+[xy]y+[.c][.c][x]x[<][<][<][y]y[>][>][>]+[.c][x] x+[>][>][x]x[<][y]x[<][<][<][<][<][<][.c][<][<][.c]y[.c][y][xy][yx][xy]
 [y][.c][xy][.c][yx][.c]
=== Fibonacci sequence === 
This program displays the terms of the Fibonacci sequence up to a number from STDIN.
 [,n](+00>)y*[y]*[x]*[>][x](-00<)(+0>)xxx[.n][<][.c][>][.n][xy]xy{[xy]+x[xy]xy[<][.c][>][.n][>][>][yx]y-[yx]yx[>][>][>]?y}
=== Is Even ===
This program takes an unsigned integer from STDIN, prints 1 if it is even, 0 otherwise.
 x(+0>)yy[,n][yx]+yx[yx]+[x](+0>)y[yx]xxy{[yx]/y[>][>][>][yx]+y[<][<][<]?x}[yx]*[yx]-[.n]
Derivation:
 x "0"
 (+0>)y "1"
 y "/!\ push an extra 1 to the stack : remove this part for an 'is-odd' program"
 [,n] "stack 0, 1, n"
 [yx]+yx[yx]+[x] "/!\ stack 0, 1, (n + 1) : /!\ remove this part for an 'is-odd' program"
 (+0>)y[yx]xxy "stack = 0, 1, (n + 1), (n + 1), 2 .. acc = (n + 1), 2"
 
 {
 [yx] "first iter -> stack 0, 1, (n + 1) .. acc = (n + 1), 2"
 / "first iter -> stack 0, 1, (n + 1), ((n + 1) // 2) .. acc = (n + 1), 2"
 y "first iter -> stack 0, 1, (n + 1), ((n + 1) // 2), 2 .. acc = (n + 1), 2"
 [>][>][>] "first iter -> stack n, ((n + 1) // 2), 2, 0, 1"
 "increments the quotient q"
 [yx]
 +
 y
 [<][<][<]
 ?x}
 
 "The stack should look like 1, 1, (n + 1), q, 2"
 "if n is even then (n + 1) = 2*q + 0"
 
 [yx] "acc = q, 2"
 * "stack = 1, 1, (n + 1), q * 2"
 [yx] "acc = (n + 1), q * 2"
 - "stack = 1, 1, r with r = (n + 1) - q * 2 = (n + 1) (mod 2)"
 [.n] "prints 0 if n is even, 1 otherwise" 
== Concepts ==
=== Rotation < for -π/2 and > for +π/2 ===
In 4D space, we can generate a total of 6 planes from the base vectors, a plane of rotation is the equivalent concept to the center of rotation in 2D i.e. there is always an invariant plane under a 4D rotation.
* xy as 0 (xy-plane is invariant)
* xz as 1 (xz-plane is invariant)
* xw as 2 (xw-plane is invariant)
* yz as 3 (yz-plane is invariant)
* yw as 4 (yw-plane is invariant)
* zw as 5 (zw-plane is invariant)
We start a rotation or a sequence of rotations with the syntax
 (main_operator seq_of_rotation)
After a rotation, we have
* The accumulator vector state is changed: X and Y increment/decrement
* The system becomes oriented in some way
Conceptually, in order to compute the next state of the accumulator vector, spin4 takes the two only base vectors which can generate the same plane as \vec{u} = (1 \quad 0 \quad 0 \quad 0)^T and \vec{v} = (0 \quad 1 \quad 0 \quad 0)^T.
Suppose for example that we have the columns (0 \quad -1 \quad 0 \quad 0)^T and (1 \quad 0 \quad 0 \quad 0)^T in the system matrix, the orientation signature becomes [-1, 1], we can then compute the next accumulator state acc <- acc + [-1, 1].
To find the signature, an interpreter may iterate through each column pair combination (\vec{u}', \vec{v}') that satisfies the projections \vec{u}.\vec{v}'=0 and \vec{u}'.\vec{v}=0, which basically guarantees that the generated plane is congruent to the initial plane generated by the first and second column of the identity matrix.
Such computation can be rewritten as:
T \leftarrow R_{Index, Dir} T
 (Acc_X \quad Acc_Y) \leftarrow 
 (Acc_X \quad Acc_Y)
 +
 \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\end{pmatrix}
 T
 \begin{pmatrix}1 \\ 1 \\ 1 \\ 1\end{pmatrix}
This results on the fact that a ±π/2 rotation applied on the 4 x 4 identity matrix or a signed permutation of its columns will always result on a generalized permutation matrix whose non-zero entries are -1, 1.
=== Instruction list ===
* Arithmetic operators +, -, /, *, _ (no op).
* Rotation sequence (Op Seq)
** Op can be any of the above binary operator
** Seq is a sequence of ordered rotation
For example (+1>1<01>) is equivalent to (+01>)
* x or y : push a specific component of the accumulator to the stack.
** (+03<5>)x => push -1 to the stack, accumulator [-1, 1]
*** stack := ... -1
** (+03<5>)yx => push 1 then -1 to the stack, accumulator [-1, 1]
*** stack := ... 1 -1
** (+03<5>)* => push -1 (or x=-1 * y=1) to the stack, accumulator [-1, 1]
*** stack := ... -1
** (+03<5>)x+y => push -1 then 0 then 1, accumulator [-1, 1]
*** stack := ... -1 0 1
** (+03<5>)yx/+x => push 1, -1, -1, 0, then -1, accumulator [-1, 1]
*** stack := ... 1 -1 -1 0 -1
* [<], [>]: rotate stack left or right
* [x], [y], [xy] or [yx] : pop the stack then put the value(s) in the corresponding accumulator component in order
* [.n] : print the top element as a number
* [.c] : print the top element as a char
* [,n] : number input (int32)
* [,c] : char input
* Loop { .. ?t}, t is either x or y i.e. it checks a single accumulator component and breaks if the value is 0. 
** {(+50>)?x}y stops as soon as the accumulator x component is 0 then pushes y component value to the stack
== Interpreters ==
* Spin4
Category:2022 Category:Stack-based Category:Turing complete Category:Implemented