Unary
Unary is an esoteric programming language designed by Lode Vandevenne in 2005. Unary uses the bijective unary number system as source code. To write a program in Unary, use the following steps:
1. Write your program in Brainfuck.
2. Replace the Brainfuck commands with binary representation as follows:
| Brainfuck | Binary |
|---|---|
>
|
000 |
<
|
001 |
+
|
010 |
-
|
011 |
.
|
100 |
,
|
101 |
[
|
110 |
]
|
111 |
3. Place these commands behind each other, and put an extra "1" in front, so that together they form one large binary number. The last Brainfuck command makes the 3 least significant bits, and the most significant bit is always 1.
4. Convert this binary number to the unary number system, using 0 digits (e.g. 1001 in binary becomes 000000000 in unary).
Number of symbols
According to the specification, Unary uses only one symbol. Some say the EOF character has to be counted as well, thus Unary uses 2 symbols. However, in most other Turing tarpits the EOF symbol isn't counted. Unary still has one symbol less than a Turing tarpit that uses two symbols in its specification, since such a language also has an extra EOF symbol.
Examples
Program that gets a single character and outputs it again
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Infinite loop that does nothing but repeat (line breaks added for readability)
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Cat program, EOF returns 0:
Too large to show here. It's 56623 zero digits in a row, about 7 kilobytes.
Hello, World:
Has 142,209,095,870,573,693,396,245,504,627,320,468,349,603,549,841,832,242,891,887,476,756 zeroes.
Quine
There is a quine, which is a very long string of 0s that is quite impossible to be presented here or run to completion in an interpreter. A file containing the program in Unary would be about 6.1e+4391 bytes. See the talk page:
Progressive Unary
One flaw with Unary programs is that, as specified above, they do not allow any meaningful work to be done until the EOF character has been read, and there is no way of locating the EOF character better than reading the characters sequentially from memory and counting them off as you go. Thus, every program, even normally very fast algorithms, require time linear in the unary size of the program to run. This means that they require time exponential in the size of the resulting Brainfuck program to run.
Progressive Unary is a modification of Unary by User:Quintopia that, while still requiring programs to be stored in unary (and still requiring that the length of the program be the only piece of information which encodes its functionality), allows them to run in time only linear in the size of the resulting Brainfuck program, which is as good as possible. Moreover, much of the work of the program can already be done/in progress while the end of the program is being sought.
We have to make one new assumption to make this work: Every Progressive Unary program uses a different symbol as its one instruction, and all of memory which is empty is filled with the EOF/blank character.
With this assumption, we no longer need to seek the end of the program sequentially, as we can tell when we've gone too far: We no longer see our program's unique symbol. We can skip ahead by leaps and bounds until we pass it, and then find it in time logarithmic in the size of the remaining search space.
In fact, this is exactly the algorithm we will use. Let's assume that the program we are reading uses the 'O' character. Starting at the beginning of the program we step ahead towards the end, doubling the step size each time. At each step, we test the character at that location, and the first time it is not the 'O' character, we stop. If the length of the program is n, this will take log(n) (base 2) steps.
Next, we begin a binary search for the place where the program ends. Every time we read a 'O' character, we record a '1' and each time we read some other character, we record a '0'. Every 3 bits recorded, we convert into the corresponding BF instruction and execute them as soon as it makes sense to do so. This will also take time log(n)-1 (base 2) steps. Since n is only exponential in the size of the corresponding binary BF program, and reading this program requires only about 2*log(n) steps, it only takes about twice as long to read this program as it does to read the corresponding binary BF program.
More importantly, it takes logarithmically less time to read than the equivalent Unary program. The only downside is that it may take up to twice as much space to encode the program.
One final note: since only logarithmically many of the characters in the program will be read, one could reasonably figure out which characters these will be in advance and write other programs into the remaining space. Since the length of the program encodes all information about it, it's not very paradigm-destroying to mix together programs in memory: what came between the boundaries didn't matter all that much anyway.
Conclusion
Suffice to say, the Brainfuck program Lost Kingdom would generate a very large source file in Unary.
See also
- Nullary
- Ellipsis
- Ecstatic
- Digitial
- MGIFOS
- Golunar
- Lenguage
- Len(language,encoding)
- dotfuck
- OCPL
- The Language That Explodes