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:

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 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.