summaryrefslogtreecommitdiff
path: root/macros/generic/laan/fifo.art
blob: 680b5d281ac2f3f0a52bb962b27124829d5370cb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
%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