Fueue
Fueue is a queue-based esoteric programming language created by Nathan van Doorn in 2012. Everything is stored in a single queue. The source of the program is converted to this queue on execution.
Evaluation proceeds as follows:
- Look at the front element of the queue.
- If it is a numeric value, convert it to a character and print.
- If it is a function, and there are enough values of the appropriate type directly behind it in the queue, the function and those values are popped, and the result is pushed back to the end of the queue.
- Otherwise, it is simply sent to the back of the queue.
- If the queue reaches this last stage many times and so does a full rotation without changing at all, a character is taken from input and its unicode value is added to the back of the queue.
The only things allowed in a program are nonnegative integers (in base 10), the functions described below, square bracket encoded subprogram blocks (which are actually queues), and whitespace.
Functions
| Function | Effect | Before | After |
|---|---|---|---|
+ |
Adds two numbers | +ab... |
...(a+b)
|
- |
Negates a number | -a... |
...(-a)
|
* |
Multiplies two numbers | *ab... |
...(a*b)
|
/ |
Integer divides two numbers | /ab... |
...(a/b)
|
% |
Logically inverts a number (0 to one, n to 0) | %a... |
...(!a)
|
: |
Duplicates a value | :a... |
...aa
|
~ |
Swaps two values | ~ab... |
...ba
|
! |
Pops a value | !a... |
...
|
$ |
Pushes a number of copies | $ab... |
...(a lots of b)
|
( |
Turns a value into a block | (a... |
...[a]
|
< |
Adds another value into a block | <[foo]b... |
...[foob]
|
) |
Deblocks a block | )[foo]... |
...foo
|
H |
Halts immediately | H... |
Examples
Cat program/Null program
In Fueue, the null program is a cat, although it doesn't handle end of file.
Hello, world!
72 101 108 108 111 44 32 119 111 114 108 100 33 10 H
Infinite loop
):[):]
Even shorter, but less generalizable:
::
A finite loop printing the alphabet
)$2[)$--------2~)~~[)[)~(~[~[$~H~]~)%+~91-):]~1+:])]]~[$~H~])%+-91)[65][65]
Thue-Morse sequence
Original version:
48 ~!~)): [[48 [)):] [~!~)):] ~~) !][49 [~!~)):] [)):] )~]]
Shorter version inspired by the Kolakoski sequence program:
)):[[48][49~]~~:))~:~:~]
Kolakoski sequence
49)50:[[50:])~)~:~[[49]:~))~:~~]~]
Made for this PPCG answer, which also includes some explanation.
Truth-machine
[[)[~~~~()+1])])][[)$-----~1-[~:)~)[)[~:)~)]~:]:]~[~[$~H~~%~+])~48-):])~)~:])][)~[0]])$
The above program shows how one may, although awkwardly, in principle achieve usable input in Fueue.
Numbers in Fueue are unstable, which means that they cannot be used as (top level) elements in a queue that needs to be unchanging for an entire cycle so that input can be triggered. Also, unless protected by e.g. being inside a block, they must be used immediately after they are produced. This includes the number produced as input.
Only the functions -%$ are capable of using a number appearing, while at the same time having both themselves and their other arguments do nothing for an entire preceding cycle. Of these, only $ doesn't just postpone the problem again to the next cycle.
The method used here, which might be the only one possible, is to let a $ function use the appearing number to duplicate a number of blocks, after which a ) function starts executing the first one.
Once this has been achieved, we have enough control of timing to arrange for the blocks to perform arithmetic to reconstruct the original number, but this time protected inside a block.
Deadfish interpreter
- The code for the interpreter is at Deadfish#Fueue.
Brainfuck interpreter
- A nicer formatted version (but still utterly unreadable to known humanity) is available.
This interpreter simulates 8-bit cells, and makes no attempt to prepare for I/O characters larger than 255 if you should get a Fueue interpreter which takes Unicode seriously. It will treat input characters ≤0 all the same, and assumes EOF has this form, which I think so far only applies to the C interpreter. However it also supports the common ! convention for ending the code, thus allowing the brainfuck program to get input.
):[)~$)[[)[~~~~()+1])][0]$%~~1)][[)~<[)$%+-~)~~~43[)[~:~~~)<[)~~[)$--1[)~]<~~<)<[)$$7--1]][~~~)%[~~)~:(+- )(~)+-1*256]+-~)255:]~]]!]~][)~<[)$%+-~)~~~45[)[~:~~~)<[)~~[)$--1[)~]<~~<)<[)$$6-%0]][~~~)*[)~(:+~~-)+1]- --256%):]~]]!]~][)~<[)$%+-~)~~~62[)[~:~~~)<[)~~[)$--1[)~]<~~<)<[)$--%0]][))(($3~)<(]~]]!]~][)~<[)$%+-~)~~ ~60[)[~:~~~)<[)~~[)$--1[)~]<~~<)<[)$--%0]][~~)<~~~(]~]]!]~][)~<[)$%+-~)~~~91[)[)~~[)~<[<<<~(~~~<)~][)[))$ 12~[:]<<$4~~~<[)$--1[$8~)$4<[)$$6-%0[)]]<]~)~:~]~[!~)~~[)[)$--1[)~~~[)$4~[~):~~[~:~)~[)$$6-%0~~[$~])~]<~] <~<]$3~[)$~~~%~~)]<~(~~<]~~<<~[0]]<<<:]]]<<[1)]])(~~)~]~~]<~[[~)~~!]):]]!]~][)~<[)$%+-~)~~~93[)[[85 110 109 97 116 99 104 101 100 32 93 46H][)~[))$11~<<~:(~:<]]~)~~~]!]~][)~<[)$%+-~)~~~46[)[~:~~~)<[)~~[)$--1[) ~]<~~<)<[)$%0]][):]~]]!]~][)~<[)$%+-~)~~~44[)[~:~~~)<[~~~~<)[)))~$([[)[~~~~()+1])][0]$%~~1)][)[)[~[0]~])] [~!]]]~]]!]~][)~<[)$%+-~)~~~33[)[[)~[)[H]]~!][85 110 109 97 116 99 104 101 100 32 91 46H]~)~~~]!]~][)~<[) $%+-~)~~~0[)[[)~[)[H]]~!][85 110 109 97 116 99 104 101 100 32 91 46H]~)~~~]!]~][)[~:)~]!]:]:]:]:]:]:]:]:] :]:][0]~]][[0]:[[0]<:[[0]<:]][73 110 116 101 114 110 97 108 32 101 114 114 111 114 58 32 116 111 112 108 101 118 101 108 32 114 117 110 116 105 109 101 32 93 46H])~!][~)]
Quines
See List of quines#Fueue.
Computational class
The following reduction of a subset of Underload to Fueue should show that Fueue is Turing-complete. A Haskell program to perform this conversion is available. (It makes programs quite a bit larger. You may have to increase some size limits in the C Fueue interpreter to test the results.)
The only restriction on the Underload programs is that S can only be translated as a command when it literally follows a parenthesized element in the program. Some other programs that never use the same element as runnable program and printable text can be converted into this form by replacing lone S by ^ and printable text elements (...) by ((...)S). (This is compatible with combining printable strings with *, but alas not with a.) The -S option of the above linked conversion program can add this extra step automatically for Underload programs that never print an Underload command character except with a literal (...)S command sequence. However, expect strange errors if they do.
The Fueue representation of an Underload program A is written as {A} in the translation below. To run an Underload program A on an empty stack, you run the Fueue program
{A} [[] 46 46 46 111 117 116 32 111 102 32 115 116 97 99 107 33 10 H] [H]
The translation is continuation passing style: When run, the Fueue representation of a running Underload subprogram is followed by blocks representing the Underload stack and the Underload continuation.
| Underload | Fueue translation | Remarks |
|---|---|---|
~ |
~[)~~[~[:~)<(]~)~)]<[<(]])~)~)
|
|
: |
)~)[)~([~~)<]~!]:
| |
! |
:~~!))
| |
* |
):~[):~[)~<~[:~~<)(]:~<]~[)~~]<~<][):~~<]~)~)
| |
(A) |
~~)<[[{A}]]
|
A is an Underload subprogram
|
a |
)~<~[:~~<)(]~([~~)<])
|
|
^ |
))
| |
)~ |
The null program | |
AB
|
):~~<[{A}][)[{B}]~]~ or ):~~<[{A}][)~~[{B}]]~
|
A and B are Underload subprograms, preferably nonempty
|
(xy)S |
120 121 )~
|
Printing strings other than "xy" is left as an exercise
|
Turing-completeness of queue sections
The latest version of this translation has been modified so that no command ever "wraps around" from the end of the encoding to the beginning. (Ironically, while such wrapping was originally used, in the belief that it was an "obvious" shortcut, no part of the translation got longer after the change.)
This proves that it is not necessary for a computation to have access to the entire queue to be Turing-complete, only to its own section of it.
As an amusing consequence, it is now possible to convert two different Underload programs, concatenate the results, and see the programs running "in parallel", with interspersed output.
This technique does have some obvious limits: H remains global, and adding input handling seems impossible to combine with non-communicating queue sections.
Fueue tips
To a very first approximation, programming in Fueue is similar to programming in a functional stack language like Underload. You move data around on the queue to get it in position for applying functions, and for more complicated stuff you construct subprogram blocks out of data to run later. A minor twist is that in Fueue it is often easier to move the function you want to apply to the data rather than the other way around.
But the major issue that gives Fueue a quite different feeling to Underload is that you cannot just immediately apply the next function you want to the result you have just calculated; you have to go around the queue, and this will evaluate everything on the queue. Moreover Fueue elements differ quite a lot in how easy it is not to evaluate them when you don't want to. As a result you need to keep track of all elements as time passes, and constantly synchronize evaluation across the whole queue, to make sure elements don't evaluate before the time is right.
As a result it is vital to have methods to delay evaluating parts of the queue. Perhaps the cleanest way of delaying evaluation for a single cycle is to encapsulate elements in a block:
)[delayed contents]
If you only need to delay an element or two, it is often shorter to use ~ as a trick - whenever this function swaps two following elements, they will not be evaluated in this cycle. However this method tends to blow up exponentially in length if you use it to delay for more than a couple of cycles, as the ~ itself is a very unstable element that needs to be delayed. Also, redoing the placements of ~'s and substantial elements across several cycles because of a minor bug correction near the final steps of your evaluation wears a little thin after a while.
If you cannot afford swapping it with a neighbor, a single element can also be delayed for a cycle by putting $1 in front of it.
If you need to delay evaluation for many cycles, you can use the following trick, where each cycle removes one -. (Note that the number of -'s needs to be even, although a ~ can get around that.)
)$------1[delayed contents for 8 cycles] )$$97--1[delayed contents for 100 cycles]
Lastly, if a subcomputation takes an unpredictable amount of time, then the part of the queue corresponding to the next subcomputation cannot be synchronized all by itself. Instead you may let the first computation, when it is finishing, put a ) in front of the block containing the delayed computation to run next. This can work essentially like continuation passing style.
External resources
- Implementations in C and Ocaml by Stephan Kunne
- A small modification of the C version to remove an initial program size limit
- Implementation in Haskell by Nathan van Doorn
- Fueue on Try It Online!, based on the Haskell implementation