AnnoyStack

AnnoyStack

Paradigm(s)	imperative
Designed by	Jdsj llop llvm
Appeared in	2020
Memory system	tape, stack
Dimensions	one-dimensional
Computational class	Unknown
Reference implementation	Unimplemented
Influenced by	Brainfuck
File extension(s)	no standard ending

AnnoyStack is a stack-based language that is purposely created to be difficult to use. It also has an infinite tape, where each cell is of type char.

Model

AnnoyStack is modeled as a machine with an right-unbounded tape, and unbounded stack. The tape's cells can be in one of 256 states. Since the stack is modified via the tape, the stack's elements are also in one of 256 states. As with Turing machines, the tape is interacted with via a head which moves along it. The head executes a program, which is a simple list of instructions, along with a looping rule.

Programs

All programs must begin with their looping rule:

• repeat X - where X is a bounded natural number of times for the program to loop
• forever - loop the program forever

All programs must also end with:

• end - ends program loop

Loops cannot be used more than once and are required, as the program must be within the loop.

Programs consist of a finite combination of the following instructions, in any order:

Instruction	Behavior
lft	move the tape left, or do nothing if at the leftmost cell
radd	move the tape right and add 1 to the cell
push	push value in current cell to stack
pop	pop value from stack to current cell
inp	input keypress to current cell
outp	output character from current cell

Example

Cat program:

forever
inp
outp
end

Infinitely march without altering the tape:

forever
push
radd
pop
end

Computational Class

As AnnoyStack can only halt after a fixed number of steps or not at all, it is less powerful than combinational logic. One could imagine a finitely bound combinational logic system, however even so, the available commands cannot create AND, OR, or NOT. Further, even if one could make at least AND/OR and NOT, one could not perform conditional no-ops to fill the remaining loops.

AnnoyStack is not total, as some programs can loop indefinitely.