Basic Stack

From Esolang
Jump to navigation Jump to search
Basic Stack
Designed by User:Nguyendinhtung2014
Appeared in 2025
Memory system Stack-based
Computational class Turing complete
Major implementations The only one
Influenced by Length
File extension(s) .bs

Basic Stack is an esolang by the user User:Nguyendinhtung2014.It consists of a "transparent" stack (whick means any value in the stack can be looked at but only can we do actions with the top value), a register, push-pop commands, conditionals and gotos.

Commands

Fist, the stack was emptied and the register will get set to 0

Basic Stack has the following commands (note that commands with arguments will have it in the same line as the command (e.g push 1) and commands can be seperated by a semicolon (e.g push 65;out)):

table of commands
Commands function
push push the argument value on the stack (if the argument is reg, push the register value instead)
pop pop the top value
+ add top 2 value, pop them and push them on the stack
- pop value a, pop value b, push value b-a
set set the register to the top value
cond if the top value is the argument, execute the next line. If the condition isn't statisfied, skip it (if the argument is reg, compare with the register value instead)
condr same as cond, but it looks at the value pointed to at the register pointer (stack[register])(if the argument is top, compare with the top value instead)
goto same as other esolang's goto
istop if the register is pointing to the top of the stack,execute the next line
in push the ASCII value of the next character in stdin stream (EOF is the same as NULL)
out output the character correspond to the top value of the stack
stop stops executing, say congratulations to the programmer for writing a sucessful program (optional)

Example programs

Note that because the author forgot how to read a file, after the program, the user must input a RUN command, though it is just for the interpreter to know that it should run the program and does not have any other functionality

Hello world

Using semicolons for shorter program

push 72;out;push 101;out;push 108;out;push 108;out;push 111;out;push 32;out;push 119;out;push 111;out;push 114;out;push 108;out;push 100;out;push 33;out;stop
RUN

More readable form

push 72
out
push 101
out
push 108
out
push 108
out
push 111
out
push 32
out
push 119
out
push 111
out
push 114
out
push 108
out
push 100
out
push 33
out
stop
RUN

Truth machine

goto 4
out
goto 2
in
cond 49
goto 2
out
stop
RUN

Cat program

in
cond 0
goto 6
out
goto 1
stop
RUN

99 bottles of beer on the wall

It is 900 lines if you don't count the RUN command to run 

push 99
set
pop
push reg
push reg
push 0
set
pop
cond 0
goto 37
cond 1
goto 37
cond 2
goto 37
cond 3
goto 37
cond 4
goto 37
cond 5
goto 37
cond 6
goto 37
cond 7
goto 37
cond 8
goto 37
cond 9
goto 37
push reg
push 1
+
set
pop
push 10
-
goto 9
push reg
push 48
+
out
pop
push 48
+
out
pop
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 32
out
pop
push 111
out
pop
push 110
out
pop
push 32
out
pop
push 116
out
pop
push 104
out
pop
push 101
out
pop
push 32
out
pop
push 119
out
pop
push 97
out
pop
push 108
out
pop
push 108
out
pop
push 44
out
pop
push 10
out
pop
set
push reg
push reg
push 0
set
pop
cond 0
goto 170
cond 1
goto 170
cond 2
goto 170
cond 3
goto 170
cond 4
goto 170
cond 5
goto 170
cond 6
goto 170
cond 7
goto 170
cond 8
goto 170
cond 9
goto 170
push reg
push 1
+
set
pop
push 10
-
goto 142
push reg
push 48
+
out
pop
push 48
+
out
pop
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 10
out
pop
push 84
out
pop
push 97
out
pop
push 107
out
pop
push 101
out
pop
push 32
out
pop
push 111
out
pop
push 110
out
pop
push 101
out
pop
push 32
out
pop
push 100
out
pop
push 111
out
pop
push 119
out
pop
push 110
out
pop
push 44
out
pop
push 32
out
pop
push 112
out
pop
push 97
out
pop
push 115
out
pop
push 115
out
pop
push 32
out
pop
push 105
out
pop
push 116
out
pop
push 32
out
pop
push 97
out
pop
push 114
out
pop
push 111
out
pop
push 117
out
pop
push 110
out
pop
push 100
out
pop
push 10
out
pop
set
push 1
-
set
pop
push reg
push reg
push 0
set
pop
cond 0
goto 358
cond 1
goto 358
cond 2
goto 358
cond 3
goto 358
cond 4
goto 358
cond 5
goto 358
cond 6
goto 358
cond 7
goto 358
cond 8
goto 358
cond 9
goto 358
push reg
push 1
+
set
pop
push 10
-
goto 330
push reg
push 48
+
out
pop
push 48
+
out
pop
set
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 32
out
pop
push 111
out
pop
push 110
out
pop
push 32
out
pop
push 116
out
pop
push 104
out
pop
push 101
out
pop
push 32
out
pop
push 119
out
pop
push 97
out
pop
push 108
out
pop
push 108
out
pop
push 33
out
pop
push 10
out
pop
push 10
out
pop
cond 0
goto 465
pop
goto 4
push 78
out
pop
push 111
out
pop
push 32
out
pop
push 109
out
pop
push 111
out
pop
push 114
out
pop
push 101
out
pop
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 32
out
pop
push 111
out
pop
push 110
out
pop
push 32
out
pop
push 116
out
pop
push 104
out
pop
push 101
out
pop
push 32
out
pop
push 119
out
pop
push 97
out
pop
push 108
out
pop
push 108
out
pop
push 44
out
pop
push 10
out
pop
push 110
out
pop
push 111
out
pop
push 32
out
pop
push 109
out
pop
push 111
out
pop
push 114
out
pop
push 101
out
pop
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 46
out
pop
push 10
out
pop
push 84
out
pop
push 104
out
pop
push 101
out
pop
push 114
out
pop
push 101
out
pop
push 39
out
pop
push 115
out
pop
push 32
out
pop
push 110
out
pop
push 111
out
pop
push 116
out
pop
push 104
out
pop
push 105
out
pop
push 110
out
pop
push 103
out
pop
push 32
out
pop
push 101
out
pop
push 108
out
pop
push 115
out
pop
push 101
out
pop
push 32
out
pop
push 116
out
pop
push 111
out
pop
push 32
out
pop
push 102
out
pop
push 97
out
pop
push 108
out
pop
push 108
out
pop
push 44
out
pop
push 10
out
pop
push 98
out
pop
push 101
out
pop
push 99
out
pop
push 97
out
pop
push 117
out
pop
push 115
out
pop
push 101
out
pop
push 32
out
pop
push 116
out
pop
push 104
out
pop
push 101
out
pop
push 114
out
pop
push 101
out
pop
push 39
out
pop
push 115
out
pop
push 32
out
pop
push 110
out
pop
push 111
out
pop
push 32
out
pop
push 109
out
pop
push 111
out
pop
push 114
out
pop
push 101
out
pop
push 32
out
pop
push 98
out
pop
push 111
out
pop
push 116
out
pop
push 116
out
pop
push 108
out
pop
push 101
out
pop
push 115
out
pop
push 32
out
pop
push 111
out
pop
push 102
out
pop
push 32
out
pop
push 98
out
pop
push 101
out
pop
push 101
out
pop
push 114
out
pop
push 32
out
pop
push 111
out
pop
push 110
out
pop
push 32
out
pop
push 116
out
pop
push 104
out
pop
push 101
out
pop
push 32
out
pop
push 119
out
pop
push 97
out
pop
push 108
out
pop
push 108
out
pop
push 46
out
pop
push 10
out
pop
stop
RUN

Computational class

By showing that we can translate any Bitwise Cyclic Tag program to Basic Stack (note that in the Basic Stack version, the register indicates the leftmost bit and the delete leftmost bit command will increase the register instead)

translation table
in Bitwise Cyclic Tag in Basic Stack 
0
 
push reg;push 1;+;set;pop;istop;stop
11
 
condr 1;push 1;istop;stop
10
 
condr 1;push 0;istop;stop

And in the end,add 

goto 1

Thus showed that Basic Stack is Turing-complete.

Implementations

Python

stack=[]
reg=0
program=""
line=input()
while line!="RUN": #Program is inputted until the RUN command because I dont want to read a file lol
    program+=line
    program+=";"
    line=input()
lines=program.split(";")
inp=input("input:")
inpid=0
i=0
while True:
    token=lines[i].split()
    if token[0]=="push":
        if token[1]=="reg":
            stack.append(reg)
        else:
            stack.append(int(token[1]))
        i+=1
    elif token[0]=="pop":
        stack.pop()
        i+=1
    elif token[0]=="+":
        a=stack[-1]
        stack.pop()
        b=stack[-1]
        stack.pop()
        stack.append(a+b)
        i+=1
    elif token[0]=="-":
        a=stack[-1]
        stack.pop()
        b=stack[-1]
        stack.pop()
        stack.append(b-a)
        i+=1
    elif token[0]=="set":
        reg=stack[-1]
        i+=1
    elif token[0]=="cond":
        if token[1]=="reg":
            if stack[-1]!=reg:
                i+=1
        else:
            if stack[-1]!=int(token[1]):
                i+=1
        i+=1
    elif token[0]=="condr":
        if token[1]=="top":
            if stack[reg]!=stack[-1]:
                i+=1
        else:
            if stack[reg]!=int(token[1]):
                i+=1
        i+=1
    elif token[0]=="goto":
        i=int(token[1])-1
    elif token[0]=="in":
        try:
            stack.append(ord(inp[inpid]))
        except:
            stack.append(0)
        inpid+=1
        i+=1
    elif token[0]=="out":
        print(chr(stack[-1]),end="")
        i+=1
    elif token[0]=="stop":
        break
    elif token[0]=="istop":
        if reg!=len(stack)-1:
            i+=1
        i+=1
Retrieved from "https://esolangs.org/w/index.php?title=Basic_Stack&oldid=166099"