%Paradigm: Loops. Aug 1995, revised Feb 1996 
%C.G. van der laan, cgl@rc.service.rig.nl
\input blue.tex \loadtocmacros %\tolerance500\hbadness=499\hfuzz=5pt
\everyverbatim{\emc}

\bluetitle Paradigms: Loops

\blueissue \maps{96}2

\bluepictures\flowchartlooppic\pythpic

%And to test van der Goot's variant it is supplied here
\def\loop#1\repeat{\def\body{#1}\doloop}
\def\doloop{\body\else\poolod\fi\doloop}
\def\poolod#1\doloop{\fi}
\beginscript

\bluehead BLUe's Design VII

Hi folks.
When you like plain's \cs{loop}-s so much as I do then this is for you. 
Hang on!
\DeK's loop implements  the flow, \TB{} \on219{}

\begindemo
\def\loop#1\repeat{%
  \def\body{#1}\iterate}
\def\iterate{\body
   \let\next\iterate
   \else\let\next\relax
   \fi\next}
!yields
\flowchartlooppic
\enddemo 

with as pseudosyntax for the tags

\cs{loop}$\langle pretst\rangle$\cs{if...}%
$\langle posttst\rangle$\cs{repeat}.

Special cases result when either
$\langle pretst\rangle$, or
$\langle posttst\rangle$ is empty. 
The former is equivalent to for example
PASCAL's {\bf while} \dots {\bf do} \dots, and the latter to
{\bf repeat}\dots {\bf until}.
From this I conclude that all those \cs{while} casu quo \cs{repeat} flavors 
are not needed.
Syntactic sugar? Yes, IMHO, with all respect.

In practice we all need repetitions either via a loop or
via tail recursion, which by the way are equivalent.
The loop notation is simpler to use than tail recursion, I guess.

\bluehead Van der Goot's loop

Van der Goot implemented the loop construction as a straight tail recursion. 
An eye-opener! I have simplified it into the following.\ftn{The unusual in the coding
   is the infinite loop. I have to unlearn much. In the old days of ALGOL \on60{}
   I was taught to avoid side-effects and infinite loops of course.
   With the expression language ALGOL \on68{} all storing was a side-effect.
   Now with the interpretive languages it is beneficial to think in infinite loops.} 

\beginverbatim
\def\Loop#1\Pool{#1\Loop#1\Pool}
\def\Break#1\Pool{}
%a trivial example of use
\count0=10
\Loop a \advance\count0 by-1
   \ifnum\count0=0 \expandafter\Break\fi
\Pool
\end
!endverbatim 

For more details see his  Midnight suite, |loop.doc| and |loop.tex|.\ftn{Available
   on the \TeX-Alive TUG CD.} 

Remark. Either \cs{expandafter} is needed or the \cs{Break} should take
\cs{fi} as replacement text. 
The above with \cs{expandafter} is convenient  with nesting of loops.

\bluehead Loops in markup

I used a loop in the markup for turtle graphics, especially for the 
stochastic Sierpi\'nski carpets\Dash  to throw the dice repeatedly\Dash 
and for a spiral. In the markup for the spiral below
\cs{E}, \dots \cs{N} mean draw in the directions east, \dots north.

\blueexample Spiral

$$\vbox to3cm{\vss
 \hsize0pt \offinterlineskip
 \unitlength.5ex \y0pt \x0pt
 \loop\N{\the\k}\advance\k+1
      \W{\the\k}\advance\k+1
      \S{\the\k}\advance\k+1
      \E{\the\k}\advance\k+1
 \ifnum\k<30 \repeat
\vss}$$

\thisverbatim{\unmc}
\beginverbatim
$$\vbox to3cm{\vss
 \hsize0pt \offinterlineskip
 \unitlength.5ex \y0pt \x0pt
 \loop\N{\the\k}\advance\k+1
      \W{\the\k}\advance\k+1
      \S{\the\k}\advance\k+1
      \E{\the\k}\advance\k+1
 \ifnum\k<30 \repeat
\vss}$$
!endverbatim

Remark. One can also start at a corner. However, for reuse of these kinds of pictures
I consider it more convenient to start at the center of symmetry.

Most of the time I use the tail recursion via my FIFO or (binary)
tree macros. 
My favorite FIFO example is the outline exercise 
\TB{} ex{\oldstyle11}.{\oldstyle5}.
I solved this via nested FIFO
   processing
\item{-} words via \cs{fifow}, and 
\item{-} characters via \cs{fifo}.
\smallbreak

\blueexample Outlines

\beginverbatim
\fifow Tough  exercise \wofif \unskip.
%with
\def\fifow#1 {\ifx\wofif#1\wofif\fi
   \processw{#1}\fifow}
\def\processw#1{\fifo#1 \ofif\ }
\def\process#1{\boxit#1}
\def\boxit#1{\setbox0=\hbox{#1}%
  \hbox{\lower\dp0\vbox{\hrule
   \hbox{\vrule\phantom#1\vrule}%
   \hrule}}}
!endverbatim
\def\fifow#1 {\ifx\wofif#1\wofif\fi
   \processw{#1}\fifow}
\def\processw#1{\fifo#1\ofif\ }
\def\process#1{\boxit#1}
\def\boxit#1{\setbox0=\hbox{#1}%
  \hbox{\lower\dp0\vbox{\hrule
   \hbox{\vrule\phantom#1\vrule}%
   \hrule}}}
\qquad\qquad\qquad
\fifow Tough exercise \wofif \unskip.

Another nice example is writing lines verbatim to a file, that is manmac's
\cs{copytoblankline} recast in FIFO terms.\ftn{See FIFO and LIFO sing the BLUes.}

\blueexample Sorting citation lists

Suppose, we have
\beginverbatim
\def\lst{\\\ia\\\ib\\\ic}
\def\ia{314}\def\ib{27}\def\ic{1}
!endverbatim 
{%scope for \\
\newif\ifnoe
\def\ia{314}\def\ib{27}\def\ic{1}
\def\lst{\\\ia\\\ib\\\ic}
\def\\{ }  \immediate\write16{Numbers unsorted \lst}
%
\def\dblbsl#1{\ifnum#1<\min\let\min=#1\fi}
%
then sorting \cs{lst} yields
\loop\ifx\empty\lst\noefalse
   \else\noetrue\fi
\ifnoe\def\\{\let\\=\dblbsl\let\min=}
   \lst%find true minimum
   \min%typeset minimum 
   {\def\\##1{\ifx\min##1\else
    \noexpand\\\noexpand##1\fi}%
   \xdef\lst{\lst}}%delete minimum
\repeat.
}%end scope for \\

The above is obtained as follows.

\thisverbatim{\unmc}
\beginverbatim
\def\dblbsl#1{\ifnum#1<\min\let\min=#1\fi}
%
\Loop\ifx\empty\lst\expandafter\break\fi
   \def\\{\let\\=\dblbsl\let\min=} %space
   \lst%find minimum   
   \min%typeset minimum
   {\def\\#1{\ifx#1\min \else\nx\\%
    \nx#1\fi}\xdef\lst{\lst}}%
\Pool
%with auxiliaries
\def\Loop#1\Pool{#1\Loop#1\Pool}
\def\break#1\Pool{}
!endverbatim

The coding implements the looping of the basic steps
\item- find minimum (via \cs{lst},
       and suitable definition of \DeK's active list separator |\\|)
\item- typeset minimum (via \cs{min})
\item- delete minimum from the list (via another appropriate
       definition of the list element tag).
\smallbreak

Remarks. 
\cs{dblbsl} is mnemonics for double backslash.
The deletion of elements from the list works with \cs{ifx}. 
The variant with \cs{ifnum} does not work as such (!) 
because a \cs{relax} is inserted by \TeX.\ftn
{The \cs{relax} can be suppressed by inserting an unexpandable token 
 like \cs{noexpand} \cs{empty}. Courtesy Bernd Raichle.}

The problem occurred in sorting citation lists of bibliography references 
which are specified by their symbolic names.\ftn
{In BLUe's bibliography I have explained how to circumvent
 the sorting of citation lists of references.}

\blueexample Reading a file line by line 

\beginverbatim
\Loop\ifeof\readfile\Break\fi
  \read\readfile to\inputline
  <process \inputline>
\Pool
%with auxiliary
\def\Break#1\Pool{\fi}
!endverbatim

This use occurred in the Convertor Assistant BLUe-2-\LaTeX,
well \dots it is the main loop.

\bluesubhead Relevancy

From my experience as exemplified above, 
I conclude that loops are mainly of interest for macro writers and 
not so much for the casual \AllTeX{} user.

\bluehead Macro writers attention

Knuth's loop does not allow for the use of \cs{else} in the exit code
because it is already part of the macro \cs{loop}.
Kabelschacht \on1987\Dash and Spivak \on1989\Dash needed the use of \cs{else}.

\blueexample Kabelschacht's loop

Kabelschacht removed the \cs{else} from the loop code as follows.

\beginverbatim
\def\loop#1\repeat{\def\iterate{#1\ea
   \iterate\fi}\iterate}
%a trivial example of use
\count0=10
\loop\advance\count0 by-1
   \ifnum\count0=0 
   \else do what has to be done 
\repeat
!endverbatim

Remarks. 
The exit is via the then-branche in contrast with Knuth's loop.
Suppressed are some efficiency aspects with respect to storage.
Kabelschacht's  claim that his
loop is a {\em generalization\/} of plain's loop must be seen
in the light of not being restricted to quit a loop via the else-branch.

The reason, I can think of,
for introducing another loop macro, while the most
general form has been implemented already,
is the existence of commands like \cs{ifvoid}, and \cs{ifeof}, and 
the absence of their negatives \cs{ifnonvoid}, respectively \cs{ifnoneof}.
In those cases we like to continue the loop via the \cs{else} branch.
For the latter case this means to continue
the loop when the file is {\em not\/} ended.
This can be obtained via modifying the loop \`a la Kabelschacht or more elegantly
via van der Goot's macro.

Another approach is to use  a \cs{newif} parameter,
better known as `boolean' or `logical' in other programming languages,
together with Knuth's loop.
A \cs{newif} parameter, \cs{ifneof}, 
can be used  to test for an end of file or  casu quo, an end of a list.

\beginverbatim
\ifx\lst\empty\neofalse\else\noetrue\fi\ifneo
!endverbatim

\blueexample Reading a list via Knuth's loop

\beginverbatim
\newif\ifneo
\def\lst{a b c}\neotrue
\loop\ifx\lst\empty\neofalse\fi
   \ifneo \def\lst{}
\repeat
!endverbatim

Related to the above coding of the logical $\neg$, are the codings
of the logical and, $\wedge$, and or, $\vee$, via

$$\vbox{\offinterlineskip\halign{#\enspace\hfil\vrule&\enspace#\hfil\strut\cr
\strut Functional code&\TeX\ coding\cr
\noalign{\hrule}
$\neg$|\if...|
   &|\if...\notfalse\else|\cr
   &|\nottrue\fi\ifnot|\cr
|\if...|$\wedge$|\if...|
   &|\andtrue\if...\if...| \cr
   &|\else\andfalse| \cr
   &|\else\andfalse\fi\fi| \cr
   &|\ifand| \cr
|\if...|$\vee$|\if...|
   &|\ortrue| \cr
   &|\if...\else\if...\else| \cr
   &|\orfalse\fi\fi   \ifor| \cr
   &|%alternative| \cr
   &|\orfalse| \cr
   &|\if...\ortrue\fi| \cr
   &|\if...\ortrue\fi| \cr
   &|\ifor| \cr
}}$$
with the \cs{newif}-s: \cs{ifnot}, \cs{ifand}, and \cs{ifor}.\ftn
{By the way, now I have you on the line  about Booleans, 
 did you ever understand the macro \cs{newif}?
 If not let me tell you that \cs{global} |\<name>true| and its false 
 counterpart make sense, but \cs{global} \cs{newif} |\if<name>| does not.
 \TeX{} {\em does not\/} complain but the `allocation' remains non-global.
 A bit inconsistent with the global allocations of other data like 
 counters\smiley.}


\bluehead Nesting of loops

My favorite example of nesting of loops is the bubble sort.\ftn{\cs{cmp} 
    stands for comparison. \cs{xch} stands for exchange. 
    For a pseudocode see Paradigms: Sorting.}

\thisverbatim{\unmc}
\beginverbatim
\def\bubblesort{%Data in defs \1, \2,...\<n>.
{\loop\ifnum1<\n{\k\n
  \loop\ifnum1<\k \advance\k-1 
     \cmp{\deref\k}{\deref\n}% 
   \ifnum1=\status\xch\k\n\fi
  \repeat}\advance\n-1
 \repeat}}%end \bubblesort
%with auxiliary
\def\deref#1{\csname\the#1\endcsname}
\let\cmp\cmpn %from blue.tex or provide
%\def\cmp#1#2{%Yields 
% status=0, 1, 2 for =, >, <
%{...}
!endverbatim

\bluesubhead Inconsistency pitfall
 
I experience the non-expansion of a counter variable\Dash 
   or the non-dereference of it as you wish\Dash
within a \cs{csname} counter-intuitive.
The counter must be preceded by \cs{the}, see \cs{deref}. 
I understand the difference with the situation 
that a value might be assigned but in this constructs this is out of order.

Another nesting of `loops' is in the earlier mentioned linear sorting fo citation lists,
where the inner loop is the \cs{xdef}.

\bluesubhead Braces around inner loops are mandatory

Pittman argued that there is a need for other loop codings.
\beginquote
`Recently, I encountered an application that required a set of nested loops
and local-only assignments and definitions. 
\TeX's \cs{loop} \dots \cs{repeat} con\-struc\-tion proved to be 
inadequate because of the requirement
that the inner loop be grouped.'
\endquote
In `Syntactic Sugar' I have shown that his problem can be solved 
from a table point of view.\ftn{It is also in the tables chapter of PWT.}

However, Pittman was definitely right with respect to bracing the inner loop,
because of the parameter separator \cs{repeat}. 
If braces are omitted, the first \cs{repeat} is mistaken for the outer one, 
with the result that the text of the outer loop will 
{\em not\/} become the first \cs{body}.
The good way is, to make the inner \cs{repeat} invisible for the
outer loop level, by enclosing the inner loop in braces.

With non-explicit nesting\Dash for example the inner loop is the
replacement text of a macro\Dash we still need scope braces, 
because otherwise the \cs{body} of the outer loop 
will be silently redefined by the body of the inner loop.

\bluesubhead Dialogue with \TeX

Nestings of loops occur when in dialogue with \TeX{} only certain answers
are allowed. 

\blueexample Checking user input

\beginverbatim
%Insist on allowed answers only
\def\iw{\immediate\write0}
\def\readyesornotoanswer{{%
   \def\yes{yes}\def\no{no}
   \Loop\iw{Please provide yes or no:}
      \read-1 to\answer
      \ifx\answer\yes\ea\Break\fi
      \ifx\answer\no \ea\Break\fi
    \Pool\xdef\answer{\answer}}}
%
\let\yes\Break\let\no\relax
\endlinechar-1 %TB20.18
\Loop\message{Are you happy? }
   \readyesornotoanswer
   \ea\csname\answer\endcsname
   \iw{Too bad, I insist...} 
\Pool
\bye
!endverbatim
Remarks. The \cs{xdef} makes the answer globally available.
En-passant a little `switch functionality in \TeX' is realized  via \cs{csname}. 

\bluehead Hidden counter

I like a hidden counter very much.\ftn{As in ALGOL \on68{}, METAFONT/MetaPost, or PostScript.}
In \TeX{} we don't have a garbage collector and therefore
there is no gains in storage. However, to alleviate
the user from the details of the allocation of 
storage of the counter I provided the following.\ftn{Bernd Raichle has implemented local
   storage allocation macros. Although I can see the benefits of his robust approach especially
   together with push-the-button packages like \LaTeX, I refrained from it, because
   for my applications I know that the bounds\Dash  only {\oldstyle 256} locations are
   available\Dash are not severe. Moreover, intelligibility is hampered, and I like to add 
   just a little to \TeX, as little as possible.}
\beginverbatim
\def\preloop{%To create loopcnt, a
             %local loopcounter
   \bgroup \advance\count10 by 1
   \countdef\loopcnt=\count10
            %Symbolic name
   \loopcnt=1 %(default)
 }%end \preloop
\def\postloop{\loopcnt=0 %Restore
   \egroup}%end \postloop
!endverbatim

I used the above in the coding of the Tower of Hanoi game.
The paradigm in there is that it is used together with \cs{aftergroup}\Dash shortcut \cs{ag}\Dash
to create {\em  dynamically\/} a data structure, i.e.\ the tower of which the size is specified 
by the user.
\thisverbatim{\unmc}
\beginverbatim
%   \def\I{\disksep\i\disksep\ii
%        \disksep\iii...\disksep\`n'}
%next to the defs for \i,\ii,...\`n'.
\preloop\ag\def\ag\I\ag{%
  \loop
    \ea\xdef\csname\romannumeral\loopcnt
            \endcsname{\the\loopcnt}
       \ag\disksep\ea\ag\csname
         \romannumeral\loopcnt\endcsname
    \ifnum\loopcnt<\n
    \advance\loopcnt by1
  \repeat   \ag} 
\postloop
!endverbatim
Note that \cs{disksep} is \DeK's active list separator, which I use abundantly in macro writing.
I call it the list element tag, because it is also needed before the first element.\ftn{I use 
   them also with more than one argument, 
   especially in selective loading of entries from a database.
   The above construction of a list is also used in my test example for sorting random
   words. Each character is obtained randomly and placed after the loop to form words of
   random length. Neat.}

\bluehead Flip-flop traversal 

In programming it occurs that loops are traversed with the first
traversal different from the others. In practice I needed\Dash 
   well, it was more elegant\Dash
in a play to handle only one player in each traversal but toggle the players:
player, opponent, player, opponent, etc. 
\def\data{+\cs o\cs+\rs \cs o\cs+\rs o\cs \cs +}
$$\ruled\btable\data$$
The play at hand was tic-tac-toe, and the prototype implementation
which demonstrates the toggling reads as follows.
\beginverbatim
\def\play{\initialize 
\loop\showboard
   \ifx\mark\markplayer\let\mark\markopponent
   \else\let\mark\markplayer
   \fi\iw{Supply index for \mark:}
      \read0to\index         
   \ea\xdef\csname\index\endcsname{\mark}
\ifnum\index>0 
\repeat}
\def\markplayer{+}\def\markopponent{o}
\endlinechar-1 %TB20.18
\play \bye   
%with auxiliaries 
%(\iw is shortcut for \immediate\write0)
\def\showboard{\iw{\1\2\3}...\iw{\7\8\9}}
\def\initialize{\def\1{-}...\def\9{-}}
!endverbatim

In a general sense I need often in a repetitive situation to do something different
at the beginning or at the end. Examples are my implementation of 
\item-\cs{nitem}\Dash
numbered item and ilks
\item-to suppress the first headline of a chapter, and 
\item-the |\\| in the linear sorting at the beginning.

\bluehead Trees

Another intriguing repetitive or tail-recursive situation occurs when 
coding trees in \TeX.\ftn{Well also in METAFONT and PostScript.} 
For fun\Dash though the undertone is serious\Dash 
I have added a tree from the Pythagorean family, borrowed from |pic.dat|. 

$$\thispicture{\level6 \ydim{70}}\pythpic$$

The essence of the implementation in \TeX{} of the repetition is shown below. 
For the full coding consult |pic.dat|.
\beginverbatim
\let\drawsq\ldrawsq %left drawing square
\def\pyth{\ifnum\level=1 \htyp\fi
    \drawsq\advance\level-1 
    \multiply\kk18\divide\kk25
    {\turn7\x\leftx  \y\lefty 
     \let\drawsq\ldrawsq\pyth}%
     \turn1\x\rightx \y\righty
     \let\drawsq\rdrawsq\pyth}
\def\htyp##1\pyth{\fi}
!endverbatim
\cs{turn} turns over a multiple of {\oldstyle45}$^\circ$.
(\cs{leftx}, \cs{lefty}) and (\cs{rightx}, \cs{righty})
contain the coordinates to start drawing a left square and 
a right square, respectively. 

\bluehead Conclusion

Many slightly different codings for a loop are around.
This contributes to the reasons why  understanding macro collections is so hard.
It is so easy to come up with a variant, inhibiting intelligibility and trustworthyness.

I consider van der Goot's loop the simplest and most general, 
though Knuth's loop is usually sufficient for me.

\bluehead Looking back

It is fun to flashback at for example Child's \TeX{} Selftest, \on1989,
and to conclude that much of the perceived important \TeX ing nitty-gritties 
is not needed\Dash not to mention all those essential issues which are lacking\Dash
when developing something like BLUe's format system.

This is precisely the reason why I pay so much attention to flashbacks, 
to summarize the paradigms, to bring to light what is needed in practical work, 
in such a way that the essence can be  reused easily.
Towards a discipline of \TeX ing. 
My case rest.
\medbreak
Have fun, and all the best 
\makesignature
\pasteuptoc
\endscript