xii.tex: Deciphering a TeX Puzzle
xii.tex
is a famous TeX puzzle by David Carlisle. The document source is
terribly obfuscated. The following document is an attempt at deciphering the
puzzle, i.e. an explanation of the various processes and TeX tricks.
The original puzzle can be found at CTAN/xii.
Here is a copy:
\let~\catcode~`76~`A13~`F1~`j00~`P2jdefA71F~`7113jdefPALLF PA''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx :76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI I71Fo71dPA!!FRgiePBt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz; ;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,% s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e doTsW,Wk;Rri@stW aHAHHFndZPpqar.tridgeLinZpe.LtYer.W,:jbye
Catcodes
The first step is to understand the TeX catcodes. It stands for category codes, i.e. the semantic of the various ASCII characters.
- 0: Escape character (default
\
) - 1: Beginning of group (default
{
) - 2: End of group (default
}
) - 3: Math shift (default
$
) - 4: Alignment tab (default
&
) - 5: End of line (default
^^M
≡ ASCII return) - 6: Macro parameter (default
#
) - 7: Superscript (default
^
and^^K
) - 8: Subscript (default
_
and^^A
) - 9: Ignored character (default
^^@
≡ ASCII null) - 10: Space (default
^^I
≡ ASCII horizontal tab) - 11: Letter (default
[A-Za-z]
) - 12: Other character (everything not listed above or below)
- 13: Active character (default
~
and^^L
≡ ASCII form feed) - 14: Comment character (default
%
) - 15: Invalid character (default
^^?
≡ ASCII delete)
The first line
\let~\catcode~`76~`A13~`F1~`j00~`P2
applies the following catcodes:
~
=\catcode
j
= “\ ” (backslash + space)7
=#
A
= active characterF
={
P
=}
Command defining commands
Next we have
jdefA71F~`7113jdefP
which, in proper TeX, would be
\def A #1{\catcode `#1=13 \def}
From then on, A
will turn the first next character to an active character and
define the second next character to what follows.
Example with the first application of A
:
ALLF P
(The linefeed matters.) It gets expanded to
\catcode `L=13 \def L { }
So L
is now a space.
The same process gets repeated throughout the following lines:
A''FwPA;;FPAZZFLaLPA//71F71iPAHHFLPAzzFenPASSFthP;A$$FevP A@@FfPARR717273F737271P;ADDFRgniPAWW71FPATTFvePA**FstRsamP AGGFRruoPAqq71.72.F717271PAYY7172F727171PA??Fi*LmPA&&71jfi Fjfi71PAVVFjbigskipRPWGAUU71727374 75,76Fjpar71727375Djifx :76jelse&U76jfiPLAKK7172F71l7271PAXX71FVLnOSeL71SLRyadR@oL RrhC?yLRurtKFeLPFovPgaTLtReRomL;PABB71 72,73:Fjif.73.jelse B73:jfiXF71PU71 72,73:PWs;AMM71F71diPAJJFRdriPAQQFRsreLPAI I71Fo71dPA!!FRgieP
To sum up:
L
:{ }
(Space)'
:{w}
;
:{}
(Nothing, useful to avoid globing)Z
:{ a }
/
:#1{#1i}
H
:{ }
(Space, used for last sentence shift from “a” to “and a”.)z
:{en}
S
:{th}
$
:{ev}
@
:{f}
R
:#1#2#3{#3#2#1}
D
:{ing}
(Note: Rgni = ing)W
:#1{}
(Globing)T
:{ve}
*
:{stmas}
G
:{our}
q
:#1.#2.{#1#2#1}
Y
:#1#2{#2#1#1}
?
:{istmas m}
&
:#1\fi{\fi#1}
(Key command)V
:{\bigskip R}
W
:G
(Useless command)U
:#1#2#3#4 #5,#6{ \par #1#2#3#5ing \ifx:#6 \else &U#6\fi}
(Key command)
L
: (Useless command)K
:#1#2{#1l#2#1}
X
:#1{\bigskip On the #1th day of Christmas my true love gave to me}
(Key command)B
:#1 #2,#3:{\if.#3.\else B #3:\fi X{#1} U#1 #2,#3:}
(Key command)W
:s;
(Useless command)M
:#1 {#1di}
J
:{ird}
Q
:{ers}
I
:#1{o#1d}
!
:{eig}
Core text
The above definitions did not produce any text, they merely served for laying down the foundations of the obfuscation.
The remaining text will generate the song:
Bt'el@ lTLqdrYmu.Q.,Ke;vz vzLqpip.Q.,tz; ;Lql.IrsZ.eap,qn.i. i.eLlMaesLdRcna,;!;h htLqm.MRasZ.ilk,% s$;z zLqs'.ansZ.Ymi,/sx ;LYegseZRyal,@i;@ TLRlogdLrDsW,@;G LcYlaDLbJsW,SWXJW ree @rzchLhzsW,;WERcesInW qt.'oL.Rtrul;e doTsW,Wk;Rri@stW aHAHHFndZPpqar.tridgeLinZpe.LtYer.W,:jbye
Generative commands
The fundamental idea behind the text generation is that one command will loop over a list of sentences and run another command over each sentence.
The loop command is B
. It recurses over the argument list using the ,
separator.
The sentence building command is X
.
There is one last trick: the U
command is used to propagate itself recursively
on the #6 argument. Since there is no delimiter for #6, only one character is
passed to U
. The use of the &
command shifts expands into another U
called
right after itself. Thus the rest of the #3 argument from B
is successively
passed to U
.
Readable version
This version uses the same algorithm with human readable names.
% This is used to define active characters. \catcode`@13 \def@#1{\catcode`#113\def} % Nothing, useful to prevent globing. @;;{} % Space, used for last sentence shift from "a" to "and a". @HH{\ } % Character globing; used to glob extra commas, "ing" in some verses and "th" % in ordinal numbers. @WW#1{} % Note that '#1' is everything from '&' to '\fi'. In our case, it is 'U#6'. @&\fi{\fi#1} @UU#1#2#3#4 #5,#6{\par#1#2#3#5{ing}\if:#6\else &U#6\fi} \def\day#1{\bigskip On the #1{th} day of Christmas my true love gave to me} \def\gen#1 #2,#3:{\if.#3.\else \gen#3:\fi\day{#1}U#1 #2,#3:} % Note that comments at the end of the lines are mandatory. \gen twelf lve drummers drumm,% eleven ven pipers pip,% ten ; lords a leap,% nin e ladies danc,% eigh ht maids a milk,% seven en swans a swimm,% six ; geese a lay,% ;fif ve gold ringsW,% four r calling birdsW,% ;th{ird}W ree french hensW,% ;;;secondW two turtle dovesW,% ;;;firstW aH@HH{nd a }partridge in a pear tree.W,: \bye
Simple version
This version uses an idea similar to the original, but without all the catcode intricacies.
\def\endverse{} \def\verse#1 #2,#3:{\if.#3.\par #2{}\else\par#2\verse#3:\fi} \def\day#1{\bigskip On the #1 day of Christmas my true love gave to me} \def\gen#1 #2,#3:{\if.#3.\else \gen#3:\fi\day{#1}\verse#1 #2,#3:} \gen twelfth twelve drummers drumming,% eleven eleven pipers piping,% tenth ten lords a leaping,% ninth nine ladies dancing,% eighth eight maids a milk,% seventh seven swans a swimm,% sixth six geese a lay,% fifth five gold rings,% fourth fourr calling birds,% third three french hens,% second two turtle doves,% first \endverse\def\endverse{and }a partridge in a pear tree.,: \bye
References
- The TeXbook, Donald E. Knuth
- TeX by Topic, Victor Eijkhout
- TeX for the Impatient, Paul Abrahams, Kathryn Hargreaves, Karl Berry