DJ Qarkegs - Above The Sky
Jump to navigation
Jump to search
| Paradigm(s) | Imperative, Stack-based |
|---|---|
| Designed by | User:Hakerh400 |
| Appeared in | 2020 |
| Computational class | Turing complete |
| Major implementations | Interpreter |
| File extension(s) | .txt |
DJ Qarkegs - Above The Sky is a Turing-complete stack-based language. It has a single stack and no other data storage locations.
Overview
There is a single stack of bytes. All values on the stack are unsigned 8-bit integers. Incrementing 255 gives 0. Removing or reading the top byte throws an error if the stack is empty. Input is an array of bytes. Reading after EOF gives 0.
| Command | Description |
|---|---|
0
|
Push the next input byte to the stack |
1
|
Pop a byte from the stack and output it |
2
|
Pop a byte from the stack |
3
|
Duplicate the top byte of the stack |
4
|
Increment the top byte of the stack |
5
|
Reverse the stack |
(...)
|
Perform ... as long as the top byte of the stack is nonzero
|
Other characters are not allowed (except whitespace characters).
Computational class
It is Turing complete because any brainfuck program can be converted to it using the following conversion rules:
< → 3(4)5(*545)25 > → 53(4)5(*545)2 + → 4 - → * , → 0 . → 31 [ → ( ] → )
where * is character 4 repeated 255 times. After conversion, prepend the obtained code with 0(4) followed by a lot of 3 characters.
This method does not work always, as we need to know in advance how many memory cells the program will use and we also lose the first input character (to initialize the stack). However, this can be resolved in a more complicated way. We would need to use two stack bytes per one brainfuck cell to keep track of the delimiter between the two ends of the stack. Also, the byte that we lose for initializing the stack can be saved by keeping a copy of it at the other side of the delimiter and we can extract it later during the program execution.
Examples
Cat
0(10)
Hello, World!
Converting the following brainfuck program:
+[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.
gives:
0(4)3333333334(4444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444453(4)5(44444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444444444444444444444545)244444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444(53(4)5(444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444545)253(4)5(444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444444444444444444444444545)2453(4)5(4444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444545)244444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444443(4)5(444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444545)253(4)5(44 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444545)25)3(4)5(4444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444545)254444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444443(4)5(444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444454 5)25444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444)53(4)5(44444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444545)2444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444443153(4)5 (444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444545)253(4)5(44444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444545)253(4)5(44444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444545)243153 (4)5(44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444545)253(4)5(4444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444545)23131444(3153(4)5(444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444545)2)3(4)5(444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444444444444444444545)253(4)5(44444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444545)253(4)5(44444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444545)253(4)5(44444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444444545)253144431444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444313(4)5(44444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444444444444444444444444444444444444545)253(4)5(4444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 444444444444444444444444444444444444444444444545)254444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444443153(4)5(4444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444545)253(4)5(444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444545)253(4)5(444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444545)253(4)5(444444444444444444444444444444444444444444444444444444444444444444444444444444444444 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444 44444444444444444444444444444444444444444444444444444444444444444444444545)2431