PDAsephone

PDAsephone (pronounced pee-duh-sef-oh-nee) is an esolang by User:BoundedBeans. PDAsephone is a language which depends on pushdown automata (something decidedly not Turing-complete) for possible Turing-completeness, and has them as first class values.

Storage

There are two locations, the character stack and the PDA stack. All pushdown automata represent their state, stack symbols, and input alphabet as unicode characters. Pushdown automata stacks notably cannot contain newlines, but return a newline when empty. The main character stack can have newlines, because they are needed to specify conditions. Note if you want to store the fact that the stack was empty before, you can make the transition put something else, like a tab, space, period, underscore, etc., onto the stack in the case that the stack returns a newline (the stack is empty).

Defaults

By default a pushdown automata has state '0' and has no transitions. By default a transition does not pop, pushes nothing, and keeps the state the same.

Missing features

Notably lacking from these instructions are important things like arithmetic or conditionals. Generally, you'll have to make a pushdown automata yourself to do these things. For most cases, you'll need to do many combinations.

An adder automata taking two digits off of its stack. Start in state 0 (as normal). If in state 0 and stack returns '0': pop, state=Z If in state 0 and stack returns '1': pop, state=1 If in state 0 and stack returns '2': pop, state=2 If in state 0 and stack returns '3': pop, state=3 … If in state Z and stack returns '0': If in state Z and stack returns '1': … If in state 1 and stack returns '0': pop, push 1 If in state 1 and stack returns '1': pop, push 2 … …

You'll have to specify every possible combination. Such is the value of a Turing tarpit. Note that input makes this even worse, but you can of course make sure that you always feed it the same input.

Instructions

@ - pushes a new pda onto the pda stack. It will have an empty stack, no transitions, and it will be in state '0'.
% - pops u, v, w, x, y, and z off the character stack. Installs the transition on the top pda:
    If input u, state v, and stack returns w, pop if x isn't '0', push y unless y is a newline, change state to z.
    Newlines can be used to not push anything.
! - run a transition on the top pda, with input of the top character on the stack, popping that character
^ - pop a character off of the stack of the top pda, push it onto the character stack. If the pda's stack is empty, push a newline.
. - print the top character on the character stack to the console
, - input a character, push to the character stack
" - move the instruction pointer 1 forward, and push that character onto the character stack. In other words, push the following character. 
    In the original implementation, this does not work with a newline.
_ - push a newline onto the character stack
v - pop a character off of the character stack, push it onto the top pda's stack. If the character is a newline, push a space instead
: - duplicate the top element on the character stack
; - duplicate the top element on the pda stack. Note: If pda's are references in your implementation, this operation should copy the contents. They should not reference the same object; changing one should not change the other
/ - swap the top two characters
\ - swap the top two pdas
$ - discard the top character
# - discard the top pda
| - weird go-to. This pops the top character off of the stack. If it is a capital letter, move the 
    instruction pointer forward until that character is reached not following a " command 
    (if it runs into the letter following quotes, it will continue looking). 
    If it is a lowercase letter, move backwards. You will need to use multiple of these to get around sometimes.

For an example of the weird go-to, take this program:

"C|aA"C|bB"a|aA"b|C"a|

Here's a little trace:

"C|aA"C|bB"a|aA"b|C"a|
                  ^
"C|aA"C|bB"a|aA"b|C"a|
             ^
"C|aA"C|bB"a|aA"b|C"a|
        ^
"C|aA"C|bB"a|aA"b|C"a|
   ^
"C|aA"C|bB"a|aA"b|C"a|
                  ^
"C|aA"C|bB"a|aA"b|C"a|
             ^
          ...

So you can have multiple of the same letter label, you'll just go to the closest in the direction corresponding to their case. In order to get to the other ones, you'll need to make them closer. You can't do something like a@a"a|, since that will just go back to the start of the label you're currently on. You can do something like a@b"a|a"b| instead, using intermediate labels. (These examples use @ as the target command, and assume the instruction pointer is at the last letter not following a quote)

Note: the letters u, v, w, x, y, and z, both capital and lowercase, are reserved for further commands, and cannot be used as labels. v is already used.

Comments

If a line begins with ">>>>", it will be ignored. It and the comment text must be the only things on the line, and the >>>> must not be preceded with whitespace.

Examples

Hello world

"!"d"l"r"o"w" "o"l"l"e"H............

Alternatively:

"H."e."l."l."o." ."w."o."r."l."d."!.

Cat

a,."a|

Adder of numbers from 0-3

@

"z_"1"0"0"0%
"1_"1"1"0"0%
"2_"1"2"0"0%
"3_"1"3"0"0%

"0"0"1"0"z"0%
"0"1"1"1"z"0%
"0"2"1"2"z"0%
"0"3"1"3"z"0%
"0"1"1"0"1"0%
"0"2"1"1"1"0%
"0"3"1"2"1"0%
"0"4"1"3"1"0%
"0"2"1"0"2"0%
"0"3"1"1"2"0%
"0"4"1"2"2"0%
"0"5"1"3"2"0%
"0"3"1"0"3"0%
"0"4"1"1"3"0%
"0"5"1"2"3"0%
"0"6"1"3"3"0%

,,vv"0!"0!^.

Computational class

Brainfuck is Turing-complete while only incrementing zeroes to ones, with nesting two levels deep, and no I/O. PDAsephone has the ability to swap two PDAs and insert external characters onto their stacks, meaning we can have a tape.

Here is a semi-trivial substitution from Brainfuck minus - with two level max loop depth.

Program start:
@"Bv@"Bv

<:
^:"K|a"A|K|Bv\"av\"K|A\v\K

>:
\^\:"K|a"A|K|B\v\"av"K|AvK

+:
^$"av

Outer loop:
^:@
"0"c"1"a"0"0%
"0"C"1"A"0"0%
v"0!^#/v"L|c"M|L|M[code]
^:@
"0"c"1"a"0"0%
"0"C"1"A"0"0%
v"0!^#/v|C

Inner loop:
^:@
"0"d"1"a"0"0%
"0"D"1"A"0"0%
v"0!^#/v"N|d"O|N|O[code]
^:@
"0"d"1"a"0"0%
"0"D"1"A"0"0%
v"0!^#/v|D

Implementation

The implementation can be found on the talk page.