In last week we have announced thue, our C++ implementation of the Thue interpreter. This time we give a simple example of Quine in Thue, which consists of only three alphabets {:, =, ~}.This is the minimum set of alphabets as the production symbol "::=" and output prefix "~" are required in any Thue program generating output.
~::::=~:
~:=::=~=
~=::::=~
~=:=::=~~
~==:::=~::=
~===::=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=:=::::==:=:=::=::=:=:::===:=:=:==::=:=:=::::==:=:==::=:=:=:::===:=:==:==::=:=:=:=::==:=:===:=::=:=:=:=:===:=:=====::==:=::====::
::=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=:=::::==:=:=::=::=:=:::===:=:=:==::=:=:=::::==:=:==::=:=:=:::===:=:==:==::=:=:=:=::==:=:===:=::=:=:=:=:===:=:=====::==:=::====::
It is 419-byte long; smaller than the known Quine due to Laurent Vogel.
You can confirm whether it prints itself by running thue:
% ./thue quine.t
Earlier drafts of our Quine help understand how to produce it. The first version uses the ternary (base 3) fixed-length code to encode output.
_00::=~0
_01::=~1
_02::=~2
_10::=~
_11::=~~
_12::=~_
_20::=~::=
_21::=~___________________________________________________________1200002011001012000120110110120002201102101201002011101201012011111012010220111210120200201120101202012011211020102110
::=
___________________________________________________________1200002011001012000120110110120002201102101201002011101201012011111012010220111210120200201120101202012011211020102110
Note that the underscore character, which is for a trick to make output in order, can be replaced with the tilde without breaking the Quine. At the same time we optimized the code's size by the manner of Huffman coding, as follows:
~00::=~0
~01::=~1
~100::=~
~101::=~~
~110::=~::=
~111::=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~101000011010100100101000111010101100101010000110101100101010001110101101100101010100110101110100101010101110101111100110100111100
::=
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~101000011010100100101000111010101100101010000110101100101010001110101101100101010100110101110100101010101110101111100110100111100
The final step was to replace the binary code '0' and '1' with ':' and '=', respectively. It leaves a room for microptimization, e.g., removing the trailing newline for brevity, but we stop here for now.