Goal: reverse a list of characters, going from \def\mylist{abcdefgh}
to \def\mylist{hgfedcba}
. This is easy using a marker which does not appear in the list, such as \relax
:
\def\mylist{abcdefgh}
\def\reverse #1%
{\edef #1{\expandafter \reverseloop #1\relax \marker }}
\def\reverseloop #1#2\marker
{\ifx#1\relax\reverseend\fi \reverseloop #2\marker #1}
\def\reverseend #1\marker #2{}
\reverse\mylist
\show\mylist
So far, so good. Unfortunately, this wastes a large amount of memory, and trying to apply the same function when \mylist
has a few thousand characters already blows up. Indeed, each call to \reverseloop
reads the whole token list as its #2
argument, and this is not flushed from TeX's memory via tail recursion, because TeX never reaches the end of the replacement text of \reverseloop
, or rather, only reaches it at the very end, once all the \reverseloop
macros have been expanded. You can see this from the call trace in
\def\fiveup{\edef\mylist{\mylist\mylist\mylist\mylist\mylist}}
\fiveup \fiveup \fiveup \fiveup
\tracingall
\reverse\mylist
Thus, the whole process consumes a memory proportional to the square of the number of characters, reaching millions, typical size of TeX's main memory. How can I implement such a reversal using only a linear amount of memory?
It should easily scale up to 100000 characters, albeit maybe be a bit slow there: of course we cannot avoid a quadratic time. I don't care too much about expandability.
\def\i{a}\def\ii{b}\def\iii{c}\iii\ii\i
. That is, index the string via macros and expand them from the last back. Of course it's not "linear".