BF-PDA

From Esolang
Jump to: navigation, search

BF-PDA is a simple programming language by User:ihope127, designed to be of use in a compression algorithm. An interpreter was written by User:Madk in 2010.

Commands

@ Flips the bit on top of the stack.
. Outputs the bit on top of the stack (doesn't pop it).
< Pushes a 0 bit onto the stack.
> Pops a bit from the stack and throws it away.
[ While the bit on top of the stack is 1...
] End while.

If the stack ever runs out of bits, a zero is automatically pushed: that is, popping an empty stack doesn't do anything, and loops terminate when trying to peek at empty stacks.

Computational class

Any BF-PDA program can be easily simulated on a push-down automaton, so it is certainly not Turing-complete.

Possible modification

A modification of this language adds a new stack which < pops from and > pushes to, however this stack has a finite length: pushing something onto it while it's full results in the bottom element being erased, and popping it while empty yields a 0-bit. The size of this stack is defined by the programmer. Equivalently, the "tape" extends to the left for some number of cells.

Another modification allows this language to store numbers up to a predefined number. For numbers greater than 2, @ is replaced with + and -, and [ loops while nonzero.

External resources

Download interpreter (dead link)