Flasmi

Flasmi is a language where each command operates on the commands right after it. It doesn't have loops; instead, the program can extend itself infinitely.
== Specification ==
The program consists of the following instructions: K, S, and code blocks of the form (...). The instructions K and S are called elementary instructions. A block of one instruction is equivalent to that instruction. A block in the beginning of the program or a block is equivalent to its contents.
The instructions operate on the instructions after them. They can operate on instructions outside a block they are in, but can't operate on instructions inside a block they aren't; instead, they operate on the block as a whole.
There is also a "separator" instruction, which can't be initially in the program, but can be inserted by S. Instructions before it can't access instructions after it; they run completely independently. If an instruction is in the end of the program or is immediately succeeded by the separator, it is called final.
Each elementary operation leaves the instruction right after itself (hereafter A0) unchanged and operates on the instructions after A0. The first instruction after A0 will be called A1. If the executed instruction or A0 is final, it just prints itself and does nothing.
K just removes A1. S creates a copy of the instruction after A1 (hereafter A2), appends it to the end of A1, and moves A1 to after A2. If A1 is final, S, instead of all that, prints "(" and puts the separator between A0 and A1. The separator prints ")" when executed.
== Example ==
Here, * denotes the instruction pointer. How the example was written will be explained below.
Program: S(SKK)(SKK)(S(SKK)(SKK))
 *S(SKK)(SKK)(S(SKK)(SKK))
 S*(SKK)(S(SKK)(SKK))(SKKS(SKK)(SKK))
 S(*SKK)(S(SKK)(SKK))(SKKS(SKK)(SKK))
 S(S*K)(S(SKK)(SKK))(K(S(SKK)(SKK)))(SKKS(SKK)(SKK))
 S(SK*)(S(SKK)(SKK))(SKKS(SKK)(SKK))
 S(SK)(*S(SKK)(SKK))(SKKS(SKK)(SKK))
 S(SK)(S*(SKK))(SKKS(SKK)(SKK))(SKKSKKS(SKK)(SKK))
 S(SK)(S(*SKK))(SKKS(SKK)(SKK))(SKKSKKS(SKK)(SKK))
 S(SK)(S(S*K))(SKKS(SKK)(SKK))(SKKSKKS(SKK)(SKK))(K(SKKSKKS(SKK)(SKK)))
 S(SK)(S(SK*))(SKKS(SKK)(SKK))(SKKSKKS(SKK)(SKK))
This program doesn't halt.
== Simple operations ==
First, let's construct an operation that just removes the operation right after it.
You can use K followed an instruction to remove the next instruction; however, the second instruction will be executed. You can make it a no-op, but first you need one, and it hasn't been constructed here yet. Instead, you can put S instead of K, which will insert an unwanted instruction after the one after the one being removed, and then use K to remove it. So, the operation removing the instruction right after it is
 SK
Indeed,
 *SKXY
 S*KY(XY)
 SK*Y
Note that this doesn't work at the end of the program (when X is final).
You can add any instruction after it to create a no-op. It will be hereafter denoted with
 I (=SKK)
Note that it must be put in parentheses when it is not in the beginning of a block or the program. When it is, it doesn't affect the behaviour, so hereafter, we will omit it. You can use S or a block instead of the second K.
You can duplicate an instruction with
 SII
Indeed,
 *SIIX
 S*IX(IX) = S*IXX
 SI*XX
This operation applied to itself creates an infinite loop, which is what was shown above.
If you have several instructions that ignore the instruction right after them (i.e., leaves it unchanged and doesn't use it), you can chain them with a constant as that instruction as follows:
 A(B(C(DX)))
where A, B, C, D are the operations and X is the constant as the ignored instruction.
Using this, you can make a block instruction that groups the first two instructions after it and then executes a constant instruction with
 S(KA)
Indeed,
 *S(KA)XY...
 S*(KA)Y(XY)...
 S(*KA)Y(XY)...
 S(K*A)(XY)...
In particular, if A ignores the first instruction after it, this makes it ignore the first two instructions after it and apply what A applies to the instructions after the first one to the instructions after the second one.
To make an instruction that ignores the first instruction after it and groups the first two instructions after it, you can use the above construct twice:
 S(KS)K
Indeed,
 *S(KS)KABC
 S*(KS)A(KA)BC
 S(*KS)A(KA)BC
 S(K*S)(KA)BC
 S(KS*)(KA)C(BC)
 S(KS)(K*A)(BC)
Finally, let's build a block that swaps the two instructions after the instructions right after it. To do so, we'll use S and then K to remove the copy of what was called A2 above:
 SA(KX)
Indeed,
 *SA(KX)Y
 S*AY(KXY) = S*AYX
Now, it's easy to get
 S(K(SA))K
We once again need to swap two instructions, but this time we can do that with
 S(S(KS)(S(KK)S))(KK)
Indeed,
 *S(S(KS)(S(KK)S))(KK)A
 S*(S(KS)(S(KK)S))A(KKA)
 S(*S(KS)(S(KK)S))A(KKA)
 S(S*(KS))A(S(KK)SA)(KKA)
 S(S(*KS))A(S(KK)SA)(KKA)
 S(S(K*S))(S(KK)SA)(KKA)
Later, (S(KK)SA) and (KKA) will become K(SA) and K, respectively:
 S(S(K*S))(S(KK)SA)(KKA)X
 S(S(KS*))(S(KK)SA)X(KKAX)
 S(S(KS))(*S(KK)SA)X(KKAX)
 S(S(KS))(S*(KK)A(SA))X(KKAX)
 S(S(KS))(S(*KK)A(SA))X(KKAX)
 S(S(KS))(S(K*K)(SA))X(KKAX)
 S(S(KS))(S(KK*)(SA))(KKAX)
 S(S(KS))(S(KK)(*SA))(KKAX)
and then
 S(S(KS))(S(KK)(*SA))(KKAX)Y
 S(S(KS))(S(KK)(S*A))Y(KKAXY)
and, when (KKAXY) is executed,
 *(KKAXY[...])
 (*KKAXY[...])
 (K*KXY[...])
 (KK*X[...])
== Trivia ==
* The line S*IX(IX) above can be read as "SIX IX", from which it's easy to get 69 (a meme number).
* Flasmi is an example of how a version of a paradigm turns out to be equivalent to another paradigm.
** Maybe a language extending the Flasmi paradigm that isn't will be created later.
Category:Unimplemented Category:2022 Category:Turing complete