Yoctostack

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Yoctostack is an esolang made by User:Otesunki (talk) (and further whittled down by User:Quintopia (talk)) based loosely on Minsky machines and operates on a stack.

Commands

Command	Meaning
+	Increment the top of the stack, then pushes 0.
-	If the top of the stack is non-zero, decrement it. otherwise (or if the stack is empty), branch.
%	Swap the top two elements on the stack.
:	If not branching, restart the program with the current stack.

All other characters are comments, and when the end of the program is reached, the IP goes back to the start.

Turing completeness proof

First, start with a program written in Portable Minsky Machine Notation that uses 2 counters, for example:

inc(1)
inc(1)
while (dec(1)) {
  inc(0)
  inc(0)
  inc(0)
}
[...]

Label it as state 1:

(1) inc(1)
    inc(1)
    while (dec(1)) {
      inc(0)
      inc(0)
      inc(0)
    }
    [...]

Then, use the following table to convert the program into an FSA (combined with two registers)

Find	Replace with
inc(0);	+-:
inc(1);	%+-:%
dec(0); [code A]	if (dec(0)) { [code A] } else { [code A] }
dec(1); [code A]	if (dec(1)) { [code A] } else { [code A] }
(x) [code A] while([code B]) { [code C] } [code D]	(x) [code A] goto y (y) if ([code B]) { [code C] goto y } goto z (z) [code D] (where x, y, and z are different numbers)
if ([code A]) { [code B] } [code C]	if ([code A]) { [code B] [code C] } else { [code C] }
(x) [code A] if ([code B]) { [code C] } else { [code D] } [code E]	(x) [code A] if ([code B]) { [code C] [code E] } else { [code D] [code E] }
(x) [code A] if ([code B]) { [code C] } else { [code D] }	(x) [code A] if ([code B]) { goto y; } else { goto z; } (y) [code C] (z) [code D] (where x, y, and z are different numbers)
(x) [code A] if (dec(0)) { [code B] } else { [code C] }	(x) A-B:+%-%C:
(x) [code A] if (dec(1)) { [code A] } else { [code B] }	(x) A%-%B:+%-C:
goto N;	+%-%, repeat +-: N times, :

Applied to the above example, produces:

(1) %+-:%%+-:%+%-%+-:+-::
(2) -+%-%+-:+-:+-:::+%-%+%-%+-:+-:+-:+-:::
(3) +-:+-:+-:+%-%+-:+-::
(4) [...]

Next, add the following 0 state:

(0) +%-%+%-%+%-%:::

Now we can start writing the final program. Count the total number of states (including 0) and write that many -s, followed by the same amount of :s, on seperate lines. For the above example:

-----
:
:
:
:
:

Finally, write the code for each state, in backward order (0 on bottom, 1 above it, etc...).

-----
:[...]
:+-:+-:+-:+%-%+-:+-::
:-+%-%+-:+-:+-:::+%-%+%-%+-:+-:+-:+-:::
:%+-:%%+-:%+%-%+-:+-::
:+%-%+%-%+%-%:::

Reference Interpreter

#include <stdio.h>

int main()
{
  char prg[65536], *i;
  int stack[64]={0}, *s=stack+1, nest;
  fgets(prg, sizeof(prg), stdin);
  for (;;) for (i=prg;*i;++i)
    switch (*i) {
    case '+': ++*s; *++s=0; break;
    case '-': if(*s) --*s;
              else for (--s,nest=1;nest;++i)
                nest+=(i[1]=='-')-(i[1]==':');
              break;   /* jump to matching : */
    case '%': nest=*s,*s=s[-1],s[-1]=nest; break;
    case ':': i=prg;
    }
}