path: root/macros/generic/laan/fifo.art

%FIFO and LIFO sing the BLUes (cgl, fifo.art)
%Version: 30 Aug 92
\input tugboat.sty
\def\rtitle{\hbox to \pagewd{\tenrm MAPS92.2\hfil
                             {\it FIFO and LIFO sing the BLUes}}
}
\def\rfoot{\hbox to\pagewd{\sevenrm \rlap{Draft: \today}\hfil-\the\pageno-
\hfil\llap{\copyright cgl}}
}
\pageno=1
\overfullrule=0pt
\def\star{*}
\title * FIFO and LIFO sing the BLUes\footnote\star
{Earlier versions appeared in MAPS92.1 and proceedings Euro\TeX\ 92.} *
\author * Kees van der Laan *
\address * Hunzeweg 57, 9893PB\\
           Garnwerd (Gr), The Netherlands *
\netaddress * cgl@rug.nl *
\article
%Footnote counter and footnote indexer
\newcount\fcnt
\def\ftn#1{\global\advance\fcnt1 \footnote{${}^{\the\fcnt}$}{#1}}
\let\ea=\expandafter
%
\head * Abstract *
FIFO, First-In-First-Out, and LIFO, Last-In-First-Out, are well-known
techniques for handling sequences. In \TeX\ macro writing
they are abundant but are not easily recognized as such.
\TeX{} templates for FIFO and LIFO are given and their use illustrated.
The relation with Knuth's |\dolist|, ex11.5,
and |\ctest|, p.376, is given.
%
\subhead*Keywords* FIFO, LIFO, list processing, plain \TeX,
education, macro writing.
%
\head * Introduction *
It started with  the programming of the Tower of Hanoi in \TeX, van der
Laan (1992a). For printing each tower
the general FIFO\Dash First-In-First-Out\ftn{See Knuth (1968), section
2.2.1.}\Dash approach was considered.\ftn{In the Tower of Hanoi article
Knuth's list data\-structure was finally used\Dash\TeX book Appendix D.2\Dash
with FIFO inherent.}
In literature (and courseware) the programming of these kind of things
is done differently by each author, inhibiting intelligibility. In pursuit
of Wirth (1976), \TeX\ templates for the FIFO (and LIFO) paradigm
will hopefully improve the situation.
%
\head * FIFO *
In the sequel, I will restrict the meaning of FIFO to
an input stream which is processed argument-wise.
FIFO can be programmed in \TeX\  as template
\verbatim
\def\fifo#1{\ifx\ofif#1\ofif
  \fi\process#1\fifo}
\def\ofif#1\fifo{\fi}
\endverbatim
\noindent
Printing of a tower
\def\fifo#1{\ifx\ofif#1\ofif
  \fi\process#1\fifo}
\def\ofif#1\fifo{\fi}
\def\process#1{\hbox to3ex{%
\hss\vrule width#1ex height1ex\hss}}
\vbox{\baselineskip1.1ex\fifo12\ofif}
can be done via
\verbatim
\def\process#1{\hbox to3ex{%
\hss\vrule width#1ex height1ex\hss}}
\vbox{\baselineskip1.1ex\fifo12\ofif}
\endverbatim
\noindent
For the termination of
the tail recursion the same \TeX nique
as given in the \TeX book, p.379, in the macro |\deleterightmost|,
is used.
This is elaborated as |\break| in Fine (1992),
in relation to termination of the  loop.
The idea is that when |\ofif| is encountered in the input stream,
all tokens in the macro
up to and including |\fifo|---the start for the next level of
recursion---are gobbled. Because the matching |\fi| is gobbled too,
this token is inserted via the replacement text of |\ofif|.
This \TeX nique is better than Kabelschacht's, (1987), where
the token preceding the |\fi| is expanded after the |\fi| via
the use of |\expandafter|. When this is applied the exchange occurs at
each level in the recursion.  It also better than the |\let\nxt=...|
\TeX nique, which is used in the \TeX book, for example in
|\iterate|, p.219, because there are no assignments.

\smallskip\noindent
My first version had the two tokens
after {\tt\char92ifx} reversed\Dash a cow flew by\Dash
and made me realize the  non-commutativity of the
{\it first level\/} arguments of \TeX's conditionals.
For example, |\ifx aa\empty...| differs from |\ifx\empty aa...|,
and |\if\ab\aa...| from |\if\aa\ab...|, with |\def\aa{aa}|, |\def\ab{ab}|.
In math, and in programming languages like PASCAL,
the equality relation is commutative,\ftn{So are
\TeX's {\tt\char92if}-s after expansion.}
and no such thing as expansion comes in between.
When not alert with respect to expansion, \TeX's |\if|-s can surprise you.
\smallskip\noindent
The |\fifo| macro is a basic one.
It allows to proceed along a list\Dash at least conceptual\Dash and
to apply a (user) specified process to each list element. By this approach
the programming of going through a list is {\it separated\/} from
the various processes to be applied to the elements.\ftn{If a list
has to be {\it created,} Knuth's list data\-structure might be used, however,
simplifying the execution of the list. See \TeX book Appendix D.2.}
It adheres to the separation of concerns principle, which I  consider
fundamental.
\smallskip\noindent
The input stream is processed  argument-wise, with the consequence
that first level braces will be gobbled. Beware!
Furthermore, no outer control sequences are allowed, because no
|\long| has been provided before the |\def|.
%
\smallskip\noindent
A general approach---relieved from the restrictions on the input stream:
{\it every  token\/} is processed until |\ofif|---%
is given in the \TeX book ex11.5 (|\dolist...|) and on p.376
(|\ctest...|). After adaption to the |\fifo| notation and to
the use of macros instead of token variables, Knuth's
|\dolist| comes down to
\verbatim
\def\fifo{\afterassignment\tap
\let\nxt= }
\def\tap{\ifx\nxt\ofif\ofif
   \fi\process\nxt\fifo}
\def\ofif#1\fifo{\fi}
\endverbatim
\noindent This general approach is indispensable for macro writers.
My less general approach can do a lot already, for particular
applications, as will be shown below.
But, \dots beware of its limitations.
%
\subsubhead*Variations*
The above |\fifo| can be seen as a
template for encoding tail recursion
in \TeX, with arguments taken from the input stream one after another.
An extension is to take two arguments from the input stream
at a time, with the second argument to look ahead.
\verbatim
\def\fifo#1#2{\process#1\ifx\ofif#2
    \ofif\fi\fifo#2}
\def\ofif#1\ofif{\fi}
\endverbatim
\noindent And what about recursion without parameters?
A nice example of that is
a variant implementation of Knuth's |\iterate| of the |\loop|,
\TeX book, p.219
\verbatim
\def\iterate{\body\else\etareti
    \fi\iterate}
\def\etareti#1\iterate{\fi}
\endverbatim
%
\subhead *Variable number of parameters*
\TeX\ macros can take at most 9 parameters. The above |\fifo| macro can
be seen as a macro which is relieved from that restriction.
Every group, or admissible token,
 in the input stream after |\fifo| up to and including
|\ofif|, will become an argument to the macro.
When the |\ofif| token is reached, the recursion
will be terminated.\ftn{%
  Another way to circumvent the 9 parameters limitation
  is to associate names to the quantities to be used as arguments,
  let us say  via def's,
  and to use these quantities via their names in the macro.
  This is Knuth's parameter mechanism and
  is functionally related to the so-called keyword parameter mechanism of
  command languages, and for example ADA.}
%
\subsubhead*Unknown number of arguments*
Tutelaers (1992), as mentioned by Eijkhout (1991),
faced the problem of inputting a chess position.
The problem is characterized by an unspecified number of
positions of pieces, with for the pawn positions
the identification of the pawn generally omitted.
Let us denote the pieces by  the capital letters
K(ing), Q(ueen), B(ishop), (k)N(ight), R(ook), and P(awn),
with the latter symbol default. The position on the board is indicated by
a letter a, b, c, \dots, or h,
followed by a number, 1, 2, \dots, or 8.
Then, for example,
\verbatim
\position{Ke1, Qd1, Na1, e2, e4}
\endverbatim
\noindent
should entail the invokes
\verbatim
\piece{K}{e1}\piece{Q}{d1}\piece{N}{a1}
\piece{P}{e2}\piece{P}{e4}
\endverbatim
\noindent
This can be done by an appropriate definition
of |\position|, and an adaption of
the |\fifo| template,
\verbatim
\def\position#1{\fifo#1,\ofif,}
\def\fifo#1,{\ifx\ofif#1\ofif
\fi\process#1\relax\fifo}
\def\ofif#1\fifo{\fi}
\def\process#1#2#3{\ifx\relax#3
\piece{P}{#1#2}\else\piece#1{#2#3}\fi}
\endverbatim
\noindent With the following definition (simplified in relation to Tutelaers)
\verbatim
\def\piece#1#2{ #1-#2}
\endverbatim
\noindent we get
{%local scope for this \fifo
\def\position#1{\fifo#1,\ofif,}
\def\fifo#1,{\ifx\ofif#1\ofif
    \fi\process#1\relax\fifo}
\def\ofif#1\fifo{\fi}
\def\process#1#2#3{\ifx\relax#3
\piece{P}{#1#2}\else\piece#1{#2#3}\fi}
\def\piece#1#2{ #1-#2}
\position{Ke1, Qd1, Na1, e2, e4}.
}
\par\noindent For an unknown number of arguments
at two levels see the Nested FIFO section.

\subhead *Length of string*
An alternative to Knuth's macro |\getlength|, \TeX book p.219,
is obtained via the use of |\fifo| with
\verbatim
\newcount\length
\def\process#1{\advance\length1 }
\endverbatim
%
\noindent Then |\fifo aap   noot\ofif| |\number\length|
\newcount\length \def\process#1{\advance\length1 }\fifo aap   noot\ofif
\hfil\break yields the length \ea|\number\length|.\ftn{Insert
{\tt\char92obeyspaces} when the spaces should be counted as well.}
%
\subhead*Number of asterisks*
An alternative to Knuth's |\atest|, \TeX book, p.375, for determining
the number of asterisks, is obtained via |\fifo| with
\verbatim
\def\process#1{\if*#1\advance\acnt by1
\fi}\newcount\acnt
\endverbatim
\noindent {Then |\fifo abc*de*\ofif| |\number\acnt| yields
the number of  asterisks:
\def\process#1{\if*#1\advance\acnt by1 \fi}\newcount\acnt%
\fifo abc*de*\ofif\ea|\number\acnt|.}\ftn{As the reader
should realize, this works correctly when there are
first level asterisks {\it only\/}. For counting at all
levels automatically,
a more general approach is needed, see Knuth's {\tt\char92ctest}, p.376.}
%
\subhead *Vertical printing*
David Salomon treats the problem of vertical printing in his courseware.
Via an appropriate definition of |\process|
and a suitable invoke of |\fifo| it is easily obtained.
\verbatim
\def\process#1{\hbox{#1}}
xy\vbox{\fifo abc\ofif}yx
\endverbatim
yields
\def\process#1{\hbox{#1}}
xy\vbox{\offinterlineskip
        \fifo abc\ofif}yx.
%
\subhead *Delete last character of argument*
Again an example due to David Salomon. It is related to |\deleterightmost|,
\TeX book p.379.
Effective is the following, where a second parameter for |\fifo|
is introduced to look ahead, which is inserted back
when starting the next recursion level
\verbatim
\def\gobblelast#1{\fifo#1\ofif}
\def\fifo#1#2{\ifx\ofif#2\ofif
   \fi#1\fifo#2}
\def\ofif#1\ofif{\fi}
\endverbatim
{%local mods for fifo
\def\gobblelast#1{\fifo#1\ofif}
\def\fifo#1#2{\ifx\ofif#2\ofif
   \fi#1\fifo#2}
\def\ofif#1\ofif{\fi}
\noindent Then |\gobblelast{aap}|
will yield \hbox{\tt\gobblelast{aap}}.
}
%
\subhead*Vowels, voil\`a*
Schwarz (1987) coined the problem to print vowels
in bold face.\ftn{%
His solution mixes up the picking up of list
elements and the process to be applied. Moreover, his nesting of
{\tt\char92if}-s
in order to determine whether a character is a vowel or not, is not elegant.
Fine (1992)'s solution, %to the latter problem
via a switch, is not elegant either.}
The problem can be split into two parts. First, the general part of going
character by character through a string, and second, decide whether the
character at hand is a vowel or not.
\par\noindent
For the first part use |\fifo| (or Knuth's |\dolist|).
For the second part, combine the vowels into a string, |aeiou|,
and the problem can be reduced
to the question $\langle char\rangle\in{}$|aeiou|?
Earlier, I used this approach
in searching a card in a bridge hand, van der Laan (1990,
the macro |\strip|).  That was
well-hidden under several piles of cards, I presume? The following encoding
is related to |\ismember|, \TeX book, p.379
\par\noindent
\verbatim
\newif\iffound
\def\loc#1#2{%locate #1 in #2
\def\locate##1#1##2\end{\ifx\empty##2%
\empty\foundfalse\else\foundtrue\fi}%
\locate#2#1\end}
\endverbatim

\noindent
Then |\fifo Audacious\ofif| yields
\newif\iffound%
\def\loc#1#2{%locate #1 in #2
\def\locate##1#1##2\end{\ifx\empty##2\empty%
\foundfalse\else\foundtrue\fi}%
\locate#2#1\end}%
\def\process#1{\uppercase{\loc#1}{AEIOU}%
\iffound{\bf#1}\else#1\fi}%
\fifo Audacious\ofif,
with
\verbatim
\def\process#1{\uppercase{\loc#1}%
{AEIOU}\iffound{\bf#1}\else#1\fi}
\endverbatim
\noindent
\subsubhead*Variation*
If in the invoke  |\locate#2#1| a free symbol is inserted between
|#2| and |#1|, then |\loc| can be used to locate  substrings.
And because
$\{string_1\in string_2\}\wedge\{string_2\in string_1\} \Rightarrow string_1=
string_2$,
the variant can be used for the equality test for strings.
See also the Multiple FIFO
subsection, for general and more effective alternatives for equality tests
of strings.
%
\subhead*Processing lines*
What about processing lines of text?
In official, juridical, documents it is a habit to fill out lines of text
with dots.\ftn{The problem was posed at Euro\TeX\  91 by Theo Jurriens.}
This can be solved by making the end-of-line character
active, with the function to fill up the line.
A general approach where we can |\process| the line, and not only append to it,
can be based upon |\fifo|.

\noindent One can wonder, whether the purpose can't be better
attained by filling up the last line of paragraphs by dots, because \TeX's
justifies with paragraphs as units.
%
\subhead * Processing words *
What about handling a list of words?
This can be achieved by modifying the |\fifo| template
into a version which picks up words, |\fifow|,
and to give |\processw| an appropriate function.
\verbatim
\def\fifow#1 {\ifx\ofifw#1\ofifw\fi
    \processw{#1}\ \fifow}
\def\ofifw#1\fifow{\fi}
\endverbatim
%
\subsubhead * Underlining words *
In print it is uncommon to emphasize words by underlining.
Generally another font is used, see discussion of exercise 18.26
in the \TeX book.
However, now and then people ask for (poor man's) underlining of words.
The following |\processw| definition underlines
words picked up by  |\fifow|
\verbatim
\def\processw#1{\vtop{\hbox{\strut#1}
               \hrule}}
\endverbatim
\noindent Then
\verbatim
\leavevmode\fifow leentje leerde lotje
lopen langs de lange lindenlaan \ofifw
\unskip.
\endverbatim
\noindent yields
\def\fifow#1 {\ifx\ofifw#1\ofifw\fi
    \processw{#1}\ \fifow}
\def\ofifw#1\fifow{\fi}
\def\processw#1{\vtop{\hbox{\strut#1}\hrule}}
\leavevmode\fifow leentje leerde lotje lopen
langs de lange lindenlaan \ofifw \unskip.
\immediate\write16{Leentje passed}
\par\noindent
%
\head *Nested FIFO*
One can nest the FIFO paradigm. For
processing lines word by word,
or words character by character.
%
\subhead*Words character by character*
Ex11.5,  can be solved by processing words character by character.
A solution, to a slightly simplified version of the exercise, reads
\verbatim
\fifow Though  exercise \ofifw \unskip.
%with
\def\processw#1{\fifo#1\ofif}
\def\process#1{\boxit#1}
\def\boxit#1{\setbox0=\hbox{#1}\hbox
{\lower\dp0\vbox{\offinterlineskip\hrule
\hbox{\vrule\phantom#1\vrule}\hrule}}}
\endverbatim
\noindent yields
%
\def\processw#1{\fifo#1\ofif}
\def\process#1{\boxit#1}
\def\boxit#1{\setbox0=\hbox{#1}\hbox
{\lower\dp0\vbox{\offinterlineskip\hrule
\hbox{\vrule\phantom#1\vrule}\hrule}}}
\fifow Though  exercise \ofifw \unskip.
%
\immediate\write16{Exc11.5 passed}
\smallskip\noindent  In the spirit of |\dolist...|, ex11.5, is
\verbatim
%variant neglecting word structure
\def\fifo{\afterassignment\tap
\let\nxt= }
\def\tap{\ifx\nxt\ofif\ofif
    \fi\process\nxt\fifo}
\def\ofif#1\fifo{\fi}
\def\process#1{\if\space\nxt\
\else\boxit#1\fi}
\fifo Though    exercise\ofif.
\endverbatim
{\noindent  with the same result
\def\fifo{\afterassignment\tap
\let\nxt= }
\def\tap{\ifx\nxt\ofif\ofif
    \fi\process\nxt\fifo}
\def\ofif#1\fifo{\fi}
\def\process#1{\if\space\nxt\
\else\boxit#1\fi}
\fifo Though    exercise\ofif.
}
\subhead* Mark up natural data*
Data for |\h(v)align| needs |&| and |\cr| marks. We can get plain \TeX\
to append a |\cr| at each (natural) input line, \TeX book p.249.
An extension of this is to get plain \TeX\ to insert |\cs|-s,
column separators, and |\rs|-s, row separators, and eventually to add |\lr|,
last row, at the end, in natural data.
For example prior to an invoke of |\halign|, one wants
to get plain \TeX\ to do the transformation   %
%
\let\nx=\noexpand
\def\cs{{\sevenrm{\tt\char92}cs}}
\def\rs{{\sevenrm{\tt\char92}rs}}
\def\lr{{\sevenrm{\tt\char92}lr}}
\def\bdata{\bgroup\obeylines\store}
\def\store#1\edata{\egroup\def\data{#1}}
\def\markup#1{\ea\xdef\ea#1\ea{\ea
              \fifol#1\ofifl}}
{\catcode`\^^M=13
\gdef\fifol#1^^M#2{\fifo#1\ofif%
\ifx\ofifl#2\nx\lr\ofifl
\fi\nx\rs\fifol#2}
}
\def\ofifl#1\ofifl{\fi}
\def\fifo#1#2{#1\ifx\ofif#2\ofif
    \fi\nx\cs\fifo#2}
\def\ofif#1\ofif{\fi}
$$\vcenter{\hbox{P*ON}\kern.5ex
           \hbox{DEK*}}
\,\Rightarrow\,
\bdata P*ON
DEK*
\edata\markup\data
\vcenter{\hbox{\data}}$$

\noindent This can be done via
\verbatim
$$\vcenter{\hbox{P*ON}\kern.5ex
  \hbox{DEK*}} \,\Rightarrow\,
%And now right, mark up part
\bdata P*ON
DEK*
\edata\markup\data
\vcenter{\hbox{\data}}$$
\endverbatim
\noindent with
\verbatim
\def\bdata{\bgroup\obeylines\store}
\def\store#1\edata{\egroup\def\data{#1}}
\def\markup#1{\ea\xdef\ea#1\ea{\ea
              \fifol#1\ofifl}}
\endverbatim
\noindent and auxiliaries
\verbatim
\let\nx=\noexpand
{\catcode`\^^M=13
\gdef\fifol#1^^M#2{\fifo#1\ofif%
   \ifx\ofifl#2\nx\lr\ofifl
   \fi\nx\rs\fifol#2}}
\def\ofifl#1\ofifl{\fi}
\def\fifo#1#2{#1\ifx\ofif#2\ofif
    \fi\nx\cs\fifo#2}
\def\ofif#1\ofif{\fi}
%with for this example
\def\cs{{\sevenrm{\tt\char92}cs}}
\def\rs{{\sevenrm{\tt\char92}rs}}
\def\lr{{\sevenrm{\tt\char92}lr}}
\endverbatim%
\immediate\write16{Natural data passed}%
\noindent
The above came to mind when typesetting crosswords,\ftn{With *,
or {\tt\char32}, given an appropriate function.} van der Laan (1992b), while
striving after the possibility to allow natural
input, independent of |\halign| processing.
%
\head*Multiple FIFO*
What about FIFO for more than one stream?
For example comparing strings, either for
equality or with respect to lexicographic ordering?
Eijkhout (1992, p.137, 138) provided for these applications the macros
\par
\indent
|\ifAllChars...\Are...\TheSame|,  \par\noindent
and   \par\indent
|\ifallchars...\are...\bfore|.        \par\noindent
The encodings are focussed at mouth processing.
The latter contains many |\expandafter|-s.

\noindent
A basic approach is: loop through the strings character by character,
and  compare the characters until either the
assumed condition is no longer true,
or the end of either one of the string, has been reached.
%
\subhead*Equality of strings*
The \TeX-specific encoding, where use has been made of the property of
|\ifx| for control sequences, reads
\verbatim
\def\eq#1#2{\def\st{#1}\def\snd{#2}
\ifx\st\snd\eqtrue\else\eqfalse\fi}
\endverbatim
\noindent As a stepping stone for  lexicographic comparison,
consider the general encoding
\verbatim
\def\eq#1#2{\continuetrue\eqtrue
\loop\ifx#1\empty\continuefalse\fi
     \ifx#2\empty\continuefalse\fi
\ifcontinue \nxt#1\nxtt \nxt#2\nxtu
     \ifx\nxtt\nxtu
     \else\eqfalse\continuefalse\fi
\repeat
\ifx\empty#1\ifx\empty#2
\else\eqfalse\fi\else\eqfalse\fi}
\endverbatim
with auxiliaries
\verbatim
\newif\ifcontinue\newif\ifeq
\def\nxt#1#2{\def\n##1##2\n{%
   \gdef#1{##2}\gdef#2{##1}}\ea\n#1\n}
\endverbatim
\noindent
Then
\verbatim
\def\t{abc}\def\u{ab}
\eq\t\u\ifeq$abc=ab$\else$abc\not=ab$\fi
\endverbatim
\noindent yields
{\newif\ifcontinue\newif\ifeq
\def\nxt#1#2{\def\n##1##2\n{
   \gdef#1{##2}\gdef#2{##1}}\ea\n#1\n}
\def\eq#1#2{\continuetrue\eqtrue%
\loop\ifx#1\empty\continuefalse\fi
     \ifx#2\empty\continuefalse\fi
\ifcontinue\nxt#1\nxtt\nxt#2\nxtu
   \ifx\nxtt\nxtu
   \else\eqfalse\continuefalse\fi
\repeat
\ifx\empty#1\ifx\empty#2
\else\eqfalse\fi\else\eqfalse\fi}
\def\t{abc}\def\u{ab}
\eq\t\u\ifeq$abc=ab$\else$abc\not=ab$\fi.
}
\subhead*Lexicographic comparison*
Assume that we deal with lower case and upper case letters only.
The encoding of |\leq| follows the same flow as the equality test, |\eq|,
but differs in the test, because of \TeX's expansion mechanisms
\verbatim
\def\sleq#1#2{%#1, #2 def's
\global\slttrue {\continuetrue
\loop\ifx#1\empty\continuefalse\fi
     \ifx#2\empty\continuefalse\fi
\ifcontinue\nxte#1\nxtt\nxte#2\nxtu
     \ea\ea\ea\llt\ea\nxtt\nxtu
\repeat}
\ifslt\ifx\empty#2\ifx\empty#1
                  \else\global\sltfalse
                  \fi
       \fi
\fi}
\endverbatim
with auxiliaries
\verbatim
\newif\ifcontinue\global\newif\ifslt
\def\nxte#1#2{\def\pop##1##2\pop{%
\xdef#1{##2}\xdef#2{##1}}\ea\pop#1\pop}
\def\llt#1#2{\uppercase{\ifnum`#1=`#2}
\else\continuefalse
     \uppercase{\ifnum`#1>`#2}{}\global\sltfalse\fi
\fi}
\endverbatim
\noindent For example
\verbatim
\def\t{ABC}\def\u{ab}\leq\t\u
\iflt$ABC<ab$\else$ABC>ab$\fi
\endverbatim
\noindent yields
{
\newif\ifcontinue\global\newif\ifslt
\def\nxte#1#2{\def\pop##1##2\pop{\xdef#1{##2}
   \xdef#2{##1}}\ea\pop#1\pop}
\def\llt#1#2{\uppercase{\ifnum`#1=`#2}
\else\continuefalse
     \uppercase{\ifnum`#1>`#2}{}\global\sltfalse\fi
\fi}
%
\def\sleq#1#2{%#1, #2 def's
\global\slttrue {\continuetrue
\loop\ifx#1\empty\continuefalse\fi
     \ifx#2\empty\continuefalse\fi
\ifcontinue\nxte#1\nxtt\nxte#2\nxtu
     \ea\ea\ea\llt\ea\nxtt\nxtu
\repeat}
\ifslt\ifx\empty#2\ifx\empty#1
                  \else\global\sltfalse
                  \fi
       \fi
\fi}
\def\stra{ABC}\def\strb{ab}
\stra ? \strb:
\sleq\stra\strb
\ifslt $ABC<ab$\else$ABC>ab$\fi.
\break\hfil
\def\stra{noot}\def\strb{aap}
\stra ? \strb:
\sleq\stra\strb
\ifslt $noot<aap$\else$noot>aap$\fi.
}
%\noindent Interesting is to ponder about a version, which
%uses the FIFO template with cooperating processes.
%Another \TeX\ encoding challenge?
%
\head *LIFO*
A modification of the |\fifo|
macro---|\process{#1}| invoked
at the end instead of at the beginning---will yield
the Last-In-First-Out template.
Of course LIFO can be applied to reversion `on the flight,'
without explicitly allocating auxiliary storage.%
\ftn{Johannes Braams drew my attention to Knuth and MacKay (1987),
which contained among others {\tt\char92reflect...\char92tcelfer}.
They compare \#1 with {\tt\char92empty}, which is nice. The invoke
needs an extra token, {\tt\char92empty}\Dash a so-called sentinel,
see Wirth (1976)\Dash
to be included before {\tt\char92tcelfer}, however.
(Knuth and Mackay hide this by another
macro which invokes {\tt\char92reflect...\char92empty\char92tcelfer}).
My approach requires at least one argument,
with the consequence that the empty case must be treated separately,
or a sentinel %\Dash an extra token to be added to the parameter
              %in order to terminate the recursion, see Wirth (1976)\Dash
must be appended after all.
} %end \ftn
\verbatim
\def\lifo#1#2\ofil{\ifx\empty#2
  \empty\ofil\fi\lifo#2\ofil\process#1}
\def\ofil#1\ofil{\fi}
\endverbatim
\noindent With the identity---|\def\process#1{#1}|,
or the invoke |\process#1| replaced by |#1|\ftn{Remember the
stack size limitations.}---the template can
be used for reversion on the flight
\def\lifo#1#2\ofil{\ifx\empty#2\empty\ofil
\fi\lifo#2\ofil#1}
\def\ofil#1\ofil{\fi}
For example |\lifo aap\ofil| yields \ea|\lifo aap\ofil|.
%
\subhead*Change of radix*
In the \TeX book  a LIFO exercise is provided at p.219:
print the digits of a number
in radix 16 representation.
The encoding is based upon the property
$$(N\div r^k) \bmod r=d_k, \quad k=0, 1, \dots, n,$$
with radix r, coefficients $d_k$, %i=0, 1, \dots, n$
and the number representation
$$N=\sum^{n}_{k=0}d_k\,r^k.$$
There are two ways of generating the numbers $d_k$:
starting with $d_n$, or the simpler one starting with $d_0$,
with the disadvantage that the numbers are generated in reverse order
with respect to printing. The latter approach is given in
\TeX book p.219.
Adaption of the LIFO template does not provide a solution much
different from Knuth's, because the numbers, to be typeset, are generated
in the recursion and not available in the input stream.
%
\iffalse
\head * Further reading *
Zalmstra and Rogers (1989), apply the FIFO technique to a list of figures\Dash
or floating bodies\Dash in order to merge the list appropriately with the main
vertical list in the output routine. This is beyond the scope of this paper.
\fi
%
\head * Conclusion *
In looking for a fundamental approach to process elements sequentially---not to
confuse with list processing where the list is also built up, see \TeX book
Appendix D.2,
or with processing of {\it every\/} token in the input stream, see
ex11.5 or p.376---\TeX{} templates for FIFO and LIFO, emerged.
\smallskip\noindent
The templates can be used for processing lines, words or characters.
Also processing of words line by line,
or characters word by word, can be handled
via nested use of the FIFO principle.
\smallskip\noindent
The FIFO principle along with
the look ahead mechanism is applied to molding natural data into
representations required by subsequent \TeX\ processing.
\smallskip\noindent
Courseware might benefit from the FIFO  approach to
unify answers of the exercises of the macro chapter.
\smallskip\noindent
\TeX's |\ifx...| and |\if...| conditionals are non-commutative
with respect to their {\it first level\/} operands,
while the similar mathematical operations are, as are
the  operations in current high-level programming languages.
\smallskip\noindent
Multiple FIFO, by comparing strings lexicographically,  has been touched upon.
%
\head * References *
%
\frenchspacing
\newcount\bcnt
\def\bib{\global\advance\bcnt1 [\the\bcnt]}
\item{\bib} Eijkhout, V (1991): \TeX\ by Topic. Addison-Wesley.
\item{\bib} Fine, J (1992): Some basic control macros for \TeX,
\tubissue{13}(1), 75\dash83.
\item{\bib} Hendrickson, A (priv. comm.)
\item{\bib} Kabelschacht, A (1987):
|\expandafter| vs.\ |\let| and |\def| in conditionals and
            a generalization of plain's |\loop|. \tubissue8(2), 184\dash185.
\item{\bib} Knuth, D.E (1968): The Art of Computer Programming. 1. Fundamental
            Algorithms. Addison-Wesley.
\item{\bib} Knuth, D.E (1984): The \TeX book. Addison-Wesley.
\item{\bib} Knuth, D.E, P. Mackay (1987):
            Mixing right-to-left texts with left-to-right texts.
            \tubissue7(1), 14\dash25.
\item{\bib} Laan, C.G. van der (1990):
Typesetting Bridge via \TeX, \tubissue{11}(2),  91\dash94.
\item{\bib} Laan, C.G. van der (1992a):
Tower of Hanoi, revisited. \tubissue{13}(1), 91\dash94.
\item{\bib} Laan, C.G. van der (1992b):
Typesetting Crosswords via \TeX. Euro\TeX\ 92.
\item{\bib} Laan, C.G. van der (1992c):
Table Diversions.  Euro\TeX\ 92.
\item{\bib} Salomon, D (1992): Advanced \TeX\ course: Insights \& Hindsights,
MAPS 92 Special. 254p.
\item{\bib} Schwarz, N (1987):
{Einf\"uhrung in \TeX}, Addison-Wesley.
\item{\bib} Tutelaers, P (1992): A font and a style for typesetting chess
using \LaTeX\ or \TeX. \tubissue{13}(1), 85\dash90.
\item{\bib} Wirth, N (1976): Algorithms $+$ Data Structures $=$ Programs.
            Prentice-Hall.
\iffalse\item{\bib} Zalmstra, J, D.F. Rogers (1989): A page make-up macro.
            \tubissue{10}(1), 73\dash81.
\fi
\endarticle
\bye