ByT
ByT is an esoteric programming language designed to be Turing-complete with as few commands for stack manipulation as possible.
Syntax
A ByT program consists on a list of stack declarations. The order of the declarations doesn't matter, but each one must be in its own line and match the format <name of the stack> = <list of elements>. The elements of the stack can be either 0, 1 or the name of any stack. The list of elements starts with the bottom element and ends with the top element, so in the following example the top of the main stack is abc.
main = 123 1+1=2 main abc abc = 0 123 0 1 123 = main 1+1=2 = 0 0 1 1 0
Indentation doesn't matter and // starts comments. If two string are not separated by spaces or tabs, they will be interpreted as one name (e.g. main= 1// comment is neither a valid declaration nor does it contain a comment).
Execution
The program starts by taking all the input from STDIN. The bits of the input are stacked on the execution stack with the most significant bit of the first byte on top. Above the input is stacked the main stack. The EOF is a null byte, so the execution stack always has 8 zeros at the bottom.
This is what the execution stack of a program would look like after taking "Ab" as input:
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 main
The execution of the program begins once the execution stack is ready. Each step involves popping one command from the stack and executing it. If a 0 or 1 command doesn't have enough arguments, the program halts.
0
If the 0 command is popped, then create a new stack containing the second and third elements of the execution stack, and then replace them by the name of the new stack.
... d c b a 0 --> ... d aux a where aux = c b
1
If the 1 command is popped, then swap the top two elements of the execution stack.
... d c b a 1 --> ... d c a b
<name>
If the name of a stack is popped, then stack its elements on the execution stack.
a = z y x ... d c b a --> ... d c b z y x
Let's execute the following code step by step, with input "A":
nop = aux 1 aux // does nothing aux = 1 0 0 main = nop
Execution:
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 main // 'main' gets replaced by its definition 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 nop // 'nop' gets replaced by its definition 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 aux 1 aux // the rightmost 'aux' gets replaced by its definition 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 aux 1 1 0 0 // '0' creates a new stack called 'foo' 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 aux foo 0 where foo = 1 1 // '0' creates a new stack called 'bar' 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 bar foo where bar = 0 aux // 'foo' gets replaced by its definition 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 bar 1 1 // '1' swaps the 'bar' and '1' 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 bar // and so on 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 aux 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 baz 0 where baz = 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 qux baz where qux = 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 qux 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 qux 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 // it correctly went from '... 0 0 1 0 nop' to '... 0 0 1 0' 0 0 0 0 0 0 0 0 1 0 0 0 quux 1 where quux = 0 0 ... // skipping a lot of boring steps 0 corge 0 0 0 where corge = 0 0 0 grault 0 where grault = corge 0
The next step would be executing the 0 command, however, the stack doesn't have enough elements for that, so the program halts. The final state of the stack is 0 grault, without the command that couldn't be executed.
Output
After the program halts, the result is read from the final state. If any of the steps in this part are not possible, then nothing is printed. Firstly, the top element of the stack is deleted. Then the bits of the stack are recursively printed in big-endian, from the top to the bottom. If the output size is not a multiple of 8, then the output is padded with zeros. The null character represents the EOF, so if it is printed, the output ends.
In the previous example the final state would first change, from 0 grault to just 0, and then the 0 is printed. The 0 is padded with 7 extra 0s at the end, becoming a null character, and nothing is printed.
For a more interesting output example, consider this final state:
b ??
where
a = a 1 0
b = 1 a 0
The ?? gets deleted, leaving b. The first 0 of b is printed, followed by the bits of a and a final 1. The bits of a are 01 followed by the bits of a, therefore this will print infinitely many bits (the final 1 of b ends up not being printed). The final result is 0 01 01 01 01 ..., which represents "*????..." (here ? is whatever character 0xAA happens to be).
Example programs
Cat
main = main 0
The first few steps of the execution would be:
... bit_2 bit_1 bit_0 main
... bit_2 bit_1 bit_0 main 0
... bit_2 bits_10 main where bits_10 = bit_1 bit_0
... bit_2 bits_10 main 0
... bits_210 main where bits_210 = bits_2 bits_10
...
all_bits main
all_bits main 0
The 0s concatenate all the input bits until there is nothing left to concatenate. When this happens the main gets deleted and the concatenated input bits are printed.
Hello, world!
main = ! d l r o W _ , o l l e H print print = print 0 H = 0 0 0 1 0 0 1 0 e = 1 0 1 0 0 1 1 0 l = 0 0 1 1 0 1 1 0 o = 1 1 1 1 0 1 1 0 , = 0 0 1 1 0 1 0 0 _ = 0 0 0 0 0 1 0 0 W = 1 1 1 0 1 0 1 0 r = 0 1 0 0 1 1 1 0 d = 0 0 1 0 0 1 1 0 ! = 1 0 0 0 0 1 0 0
The print stack works like in the cat example, but concatenating the characters instead of the input. This program assumes there is no input, if there is, then it gets concatenated too.
Compiler
The empty program is a ByT compiler. If there are any comments, spaces, newlines, etc. it wont work. If there is no code, then there can be no bugs. The compiler is perfect and can be completely trusted to compile OSs.
Boolfuck interpreter
// The Boolfuck code goes inside the { }
main = { + [ [ > + > + [ < ; ; ; ] < ] > + > > ] > } // example from https://codegolf.stackexchange.com/a/182731
< = i a
> = j a
[ = k a
] = l a
+ = m a
; = n a
{ = m'
} = f' o k' f' g' n' 0
a = 0 r' A' r'
b = F' z'
c = 1 n' 3 W' K' E'
d = 1 n' 3 P' K' E'
e = X s' B' B'
f = T A' A'
g = k' e c
h = k' f d
i = p L b
... there's like 100 more lines after this
The full Boolfuck interpreter can be found in the external resources. This shows that this language is Turing-complete. Input is not supported and the output is weird, because they are not necessary for Turing-completeness, so I didn't bother making them work perfectly.
External resources
- Another compiler and more examples can be found here.