The Marriage of Sorted! and C
It is with great joy that p-nand-q.com announces the marriage of Sorted! (born 2000, of no fixed version) and C (born 1972, of Bell Labs). The bride wore undefined behaviour, which she was asked to leave at the door.
The courtship
Sorted! and C have been seeing each other since 2000. Back then, the interpreter could already write any Sorted!
program as C, using the /C switch. It was an engagement, and a bad one: the C it wrote printed every number
as a raw byte, so that fibo.s stammered binary garbage instead of "one, one, two, three", and it moved the NUL
byte of itoa.s from the front to the back. The bride had been promised a faithful likeness and was given someone
else's face. The engagement was broken off by Caput VIII
of the bull, and the old translations are kept as relics.
In 2026 the relationship got serious. For a while the documentation filed it under Young Adult Romance. Then the Church found out, and the romance was elevated to a sacrament, as these things are.
The vows
The marriage goes both ways, as a marriage should:
sorted --from-c prog.c # C comes to Sorted!: compiles C into Sorted! and prints it
sorted --to-c out.c hello.s # Sorted! goes back to C, then runs as usual
sorted --from-c prog.c --to-c obfuscated.c --lang ja
The vow is the round trip. Every C program in the test suite is compiled into Sorted!, sung, run, translated back into C, compiled again, and must print exactly what clang makes of the original. Whoever makes the round trip comes back unchanged in deed, however changed in appearance.
The household rules
The bride brings her law, and the groom keeps it:
- Every constant of C becomes a declared number, each declared exactly once. Thou shalt not have the same cardinal more than once, and that includes the 42 in your loop.
- Variables live in cells. Arithmetic becomes sums, ordered differences, products and ratios. Comparisons become
conditions, and
ifandwhilebecome labels and jumps, which is what they always were, deep down. - Pointers honour the doctrine of the indexed cells. In Sorted!, reading "the cell indexed by" a value takes the cell one before the one that writing to it would take. Let no one call this an off-by-one: it is a teaching on humility, as Caput II explains. So every C pointer comes in two: one for reading, one for writing.
- A function exists exactly once, as all things in Sorted! exist once, because there is no call stack. To return, it jumps through a chain of questions, asking at every place it could have been called from: was it you?
- Bitwise operators are arithmetic where possible.
~xis-1 - x. Whatever cannot be done arithmetically is built from NANDs, which only Very Sorted! has, so such programs come out very. - What C leaves undefined stays outside. A shift by more bits than a word has is refused at the door.
Everything else gets a precise "not supported in Sorted! (yet)", with line and column. There is no malloc: one big
block of memory, 193719 cells, the same as in 2000.
The kinks
Every marriage has some. Everything the compiler writes in English or German must get past the parser of 2000 unchanged, which takes some detours:
- "the eight number". "The eighth number" does not read back: the parser matches the cardinal "eight" and trips
over the "h" it left over. So the compiler says "the eight number", and "the twentyeight number".
itoa.sdid that all along, and nobody knew why. Now we know. - German endings, sometimes. "der ersten Zahl" works, "der einhundertersten Zahl" works, "der zwanzigsten Zahl" does not. The compiler tries the correct ending and falls back to bad German wherever the parser would trip.
- No "dem". The parser knows die, das, der and den, but not dem. Native speakers are advised to look away.
- "eins Sprungziel". One label is "eins", because the parser reads "ein" as no number at all.
The children
The first song had to be the obvious one: 99 Bottles of Beer, written in plain C and compiled into English, German, Italian, French, Portuguese, Japanese, and Mandarin in hanzi and in pinyin. Every version is about 630 lines, every line is singable, and every verse prints exactly what the C program prints. It begins, of course, by declaring its numbers:
This code uses the numbers
seventyeight,
onehundredeleven,
thirtytwo,
onehundrednine,
onehundredfourteen,
onehundredone,
onehundredten,
...
(78 is "N", 111 is "o", 32 is a space and 109 is "m": the beginning of "No more bottles of beer on the wall". Since every number may be declared only once, the rest of the song has to make do with the letters it already has. Sing along.)
The same in Mandarin and in pinyin:
这个程序使用数字 Zhège chéngxù shǐyòng shùzì
七十八、 qīshíbā,
一百一十一、 yībǎiyīshíyī,
The obfuscation, with a warranty
--to-c turns any Sorted! program into C that prints exactly what the program prints and resembles nothing at all.
Every sum, difference, product, ratio and condition becomes a function named after its place in the tables (S41,
D7, C12). Every statement becomes a case of one big switch. Every variable becomes a cell of _[193719]. The number
words come along too, in case the program prints cardinals. Take your C program to Sorted! and back, and you get a C
program that does the same thing and that nobody, including you, will ever understand again.
This is obfuscation with a warranty. As far as I know, it is the first.
Quicksort, at last
Every mature programming language has a quicksort, and p-nand-q.com has collected them for years: C#, C++, Java and Python. A language called Sorted! went twenty-six years without one, which was frankly embarrassing.
So I took a perfectly ordinary quicksort in C from the internet and gave it to the compiler. The compiler's first words were:
sorted: quicksort.c:53:13: not supported in Sorted! (yet): 'sizeof'
Fair enough. A cell is a cell, so sizeof became the number 5, and since putchar is the only output a married
Sorted! has, printf became a small function that prints a number one digit at a time. The algorithm itself was not
touched: quicksort.c. It compiles to
389 lines of Japanese, which begin like this:
Kono puroguramu wa kazu
yon,
ni,
go,
san,
ichi,
zero,
sanjūni,
jū,
yonjūhachi,
nijūsan,
nijūyon
to roku o tsukaimasu.
yon, ni, go, san, ichi is the array to be sorted, { 4, 2, 5, 3, 1 }, declared as numbers, each exactly once.
Only at the end of the list does the program say what it does with them (tsukaimasu, "uses"), as Japanese does. And
then, after the obligatory statement that the program is illogical:
$ sorted quicksort.ja.s
1 2 3 4 5
The array has been sorted by a program that is, as always, sorted. Translated into a Mandarin, Vaud French and Italian
Babel mix with --mix singable, it still prints 1 2 3 4 5. It ends with 这个程序非常非常酷。, which is entirely fair.
Turing completeness
Sorted! is Turing complete. The proof is a reduction from Brainfuck: every Brainfuck command becomes one line of C, and the C becomes Sorted!. Nothing in that translation needs anything newer than the grammar of 2000, so Sorted! was Turing complete in 2000 already. Nobody had written the compiler yet.
There is also a Brainfuck interpreter written in Sorted!, at about 600 singable lines. It reads a Brainfuck program
up to a !, and then runs it on whatever follows:
$ sorted examples/brainfuck.s < examples/brainfuck.in
Hello World!
$ printf ',[.,]!Ordinata non errant' | sorted examples/brainfuck.s
Ordinata non errant
That is a Brainfuck program, running in a Sorted! program, that came from a C program, reciting the papal bull. If anyone asks you what you did this year, this is your answer.