AnnieFlow

AnnieFlow is a StackFlow derivative that has mostly the same behavior, except for the following:

1. It is much terser than StackFlow, with more condensed syntax. Every program is naturally in binary
2. There is no halt command; rather, there is one predefined output stack (Stack 0), and popping from this stack ends the program, while pushing onto it outputs the pushed symbol
3. Symbols are represented by natural numbers rather than strings, and there is no way to refer to an invalid symbol due to the way they are represented
4. Rather than requiring a symbol at the end of every stack that pushes itself back on or halts the program, there is a default rule for each stack that triggers on popping from it when it is empty
5. Multiple symbols may be pushed on the same stack in the same rule
6. There is a single input stack, and it is the last stack. A program can optionally request input from the user, and it will be pushed onto the input stack. The input stack is the first stack popped from
7. There are no initial symbols
8. Stacks are not required as part of the language. Any object that is like a stack (queues, sets, etc.) can take the place of any stack in the program, in theory, though there is no support for that at this time in the current implementation.

Besides that, it works the same as StackFlow once it is compiled.

Syntax

First we will define the types of numbers the source code of any program represents, then what number types it expects when.

Number representations

The first thing to know is that there are two types of numbers in AnnieFlow's syntax:

• Unbounded natural numbers (UNs)
• Natural numbers bounded by some positive integer K (BNK, i.e. BN5 for K=5)

UN is one of the following strings:

• 11
• 0+UN
• 10+UN

Effectively, a list of "0"s and "10"s ended with "11". To convert this to the represented number, drop the "11", then change all of the "10"s to "1"s, then convert the resulting number to an integer as if it were binary. The "11" is an ending marker. Here are the first 5 numbers, starting with 0:

• 11
• 1011
• 10011
• 101011
• 100011

However, note that leading 0s do nothing, so by default every number starts with 1. Therefore the numbers are instead represented as 1,011,0011,01011,00011, and a 1 is appended to the front before interpretation. This representation is much better than unary (1, 01, 001, etc.) for numbers greater than 4. This same process can be done in reverse it obtain which representation one should use in a program.

The representation of BNKs is more complicated. For K=2^n, it is exactly the same as normal n-bit number representations (i.e. for k=8, we have 000, 001, 010, 011, 100, 101, 110, 111 to represent 0-7). Otherwise, we need to merge some representations. For example, if k=6, start with the nearest power of 2 above it, 8 in this case, and write all of its representations in order. Starting at the top of the list, merge two adjacent numbers until you have the proper number, in this case 6. We get:

000\
   |00
001/
010\
   |01
011/
100|100
101|101
110|110
111|111

so our representations in order are 00,01,100,101,110,111

The idea is that every long enough string will start with exactly one of these representations, so we can pull out a BNK whenever we ask for one, if the program is valid.

Compilation and syntax

First, the program pulls the first bit. If it is 1, allow the user to input some characters before you start the program. If 0, the input will start empty. Then the program pulls a UN, m. The number of stacks will be S=m+1. If S is 1, the input stack and output stack are the same, and the program is either the cat program if input was allowed or the empty program otherwise, and no more bits are requested. Otherwise the rest of the program starts with a list of characters, and that is how many symbols are allowed in the output (and input, if the input bit is 1) stacks, and which character each symbol represents for IO. To stop listing characters and start the body of the program, put any already listed character again and it will start the program proper. So if you wanted some program P with characters "01 ", you might write "01 0"+P. Now everything else should be in binary. Now look at the source code as simply an endless stream of bits we can request. If the stream runs out before we're done, because our program is too short, the program is invalid and the compiler errors.

If running the interpreter from the command line with the argument being the code, you can add an additional argument, a list of unique characters, and you should then remove it from your code, making the actual code completely binary.

Now pull S-1 UNs, which represent the number of symbols in each stack from 1 to S-1. If input was not allowed, now request the number of symbols for stack S, since we don't know it yet. Store all this in an array B such that B[i] is the number of symbols in Stack i. Now for each stack besides stack 0, and each symbol+1 for empty rule, get a rule, which looks like this:

UN,BN(S),BN(B(prev)),BN(S),BN(B(prev)),...BN(S),BN(B(prev)), BN(S)

The first number is the size of the list, the stack-symbol pairs are the pushes, and the last BN(S) is the next stack to pop from. Pushes are performed from left to right.

Computational Class

AnnieFlow mostly has strictly more features and power than StackFlow, the only step back is the lack of initial symbols. However, these can be duplicated by a single default instruction on a stack that pushes all desired symbols on their stacks to duplicate initial conditions. The input stack is popped first, so simply have every symbol in the input pop to a different stack, put the same default in each one, and pop from the input stack again, also push a symbol onto each of the proxy stacks that just redirects back to the input and does what the input would have done without pushing anything else besides itself. The initial symbols will be pushed exactly once on the first pop. Because StackFlow is no stronger than AnnieFlow and is Turing-complete, AnnieFlow is also Turing-complete.

Examples

Program that prints 0 forever:

001100101101

Truth-machine:

101101001100000110111111

External Resources

• Interpreter and Advanced Interpreter (GitHub)