Exercise in computation with macros: expansion not working as expected

Question

I'm studying macros and, as an exercise, I wanted to compute the successor of a number, represented as text, in binary, little endian (lsb first). After big effort I devised this:

\def\finish#1\relax{#1}
\def\go#1{\toks0={}%
  \ifx#1\relax\toks0={1}\fi%
  \if0#1\toks0={1\finish}\fi%
  \if1#1\toks0={0\go}\fi%
  \the\toks0}

The idea is to scan the number from the left and apply the obvious transformations, recurring when needed and copying the rest of the number otherwise. I use \relax as a marker for the end of the string: I was using \end, taking inspiration from the TeXbook, but it didn't work here.

It works correctly in the first cases: \go\relax and \go0\relax produce 1 as the successor of 0, \go1\relax produces 01.

Anyway, I can't understand why \go01\relax yields an empty output. Manually following the expansion and even substituting its fragments in place give the correct 11. What am I missing?

Answer 1

I guess your numbers are big endian, because they finish (in the sense of writing) with the most significant bit.

Let's see what happens with \go01\relax. The argument to \go is 0, so we get

\toks0={}\ifx0\relax\toks0={1}\fi\if00\toks0={1\finish}\fi\if10\toks0={0\go}\fi\the\toks01\relax

Now try

\def\finish#1\relax{#1}
\def\go#1{\toks0={}%
  \ifx#1\relax\toks0={1}\fi
  \if0#1\toks0={1\finish}\fi
  \if1#1\toks0={0\go}\fi
  \the\toks0%
}

\toks1={Oops!}

\go01\relax

\bye

and check that TeX prints “Oops!”.

Do you see what's the problem? This is a (curable) case of the missing space syndrome, which is a bit nastier than its companion spurious space syndrome. Here's the cure: Always put a blank space after a numeric constant (The TeXbook, page 208).

\def\finish#1\relax{#1}
\def\go#1{\toks0={}%
  \ifx#1\relax\toks0={1}\fi
  \if0#1\toks0={1\finish}\fi
  \if1#1\toks0={0\go}\fi
  \the\toks0
}

0: \go0\relax

1: \go1\relax

01: \go01\relax

11: \go11\relax

011: \go011\relax

111: \go111\relax

\bye

You may enjoy looking at this fully expandable version.

\long\def\firstoftwo#1#2{#1}
\long\def\secondoftwo#1#2{#2}

\def\finish#1\relax{#1}
\def\go#1{%
  \ifx#1\relax
    \expandafter\firstoftwo
  \else
    \expandafter\secondoftwo
  \fi
  {1}{\digit#1}%
}
\def\digit#1{%
  \if0#1%
    \expandafter\firstoftwo
  \else
    \expandafter\secondoftwo
  \fi
  {1\finish}{0\go}%
}

0: \go0\relax

1: \go1\relax

01: \go01\relax

11: \go11\relax

011: \go011\relax

111: \go111\relax

\edef\test{\go10011101\relax}

{\tt\meaning\test}

\bye

Answer 2

Here is another implementation of your task which is more simple and fully expandable because there is no setting to the toks register.

If you did it that way the first time, you wouldn't have any problems with the \toks01 register.

\def\go#1{%
   \ifx#1\relax 1\expandafter\goF \fi
   \ifx#101\expandafter\goC
   \else  0\expandafter\go  % 1 converted to 0, do recursive \go
   \fi
}
\def\goF #1\go\fi{}   % \go Final, \relax scanned, 1 added, do nothing
\def\goC #1\relax{#1} % \go Copy, 0 converted to 1, copy rest

0: \go0\relax

1: \go1\relax

01: \go01\relax

11: \go11\relax

011: \go011\relax

111:  \go111\relax

11100:  \go11100\relax

1100110011:  \go1100110011\relax

000:  \go000\relax

\bye

We can combine the \go macro with the \revers macro and create the \addone macro which reads and prints binary numbers as we are used to:

\def\afterfi#1#2\fi{\fi#1}
\def\revers#1#2\relax{\ifx\relax#2\relax\else\afterfi{\revers#2\relax}\fi#1}

\def\go#1{%
   \ifx#1\relax 1\expandafter\goF \fi
   \ifx#101\expandafter\goC
   \else  0\expandafter\go  % 1 converted to 0, do recursive \go
   \fi
}
\def\goF #1\go\fi{}   % \go Final, \relax scanned, do nothing
\def\goC #1\relax{#1} % \go Copy, 0 converted to 1, copy rest.

\def\addone#1{%
   \expandafter\revers \expanded{%
       \expandafter\go\expanded{\revers#1\relax}\relax}%
   \relax
}

0: \addone{0}    % prints 1

1: \addone{1}    % prints 10

10: \addone{10}  % prints 11

11: \addone{11}  % prints 100

\bye

Answer 3

As egreg already pointed out, with the directive \the\toks0 TeX needs to know the number of the \toks-register denoted and therefore gathers (and hereby expands expandable) tokens that form a TeX ⟨number⟩-quantity. Thus after encountering the digit 0 TeX does not spit out the content of the register \toks0 but keeps gathering more digits belonging to the number denoting the \toks-register, hereby consuming tokens that belong to the argument of \go.
You can prevent this via \the\toks0 , i.e., via \the\toks0⟨space⟩.

Here is another fully expandable variant of Big-Endian-Incrementing of binary numbers which does without \if..-forking—instead forking is done by means of delimiter-matching of delimited arguments:

\def\go{\innergo{1}{0}{1}}
\def\innergo#1#2#3#4{%
    % #1 replacement for bit 0 
    % #2 replacement for bit 1
    % #3 digit to append when \relax is reached.
    % #4 current bit or \relax
  \ForkBit
  !#4!1!\relax!{#1\innergo{0}{1}{}}%      <- #4 (current bit) is 0
  !0!#4!\relax!{#2\innergo{#1}{#2}{#3}}%  <- #4 (current bit) is 1
  !0!1!#4!{#3}%                           <- #4 (current bit) is \relax
  !!!%
}%
\def\ForkBit#1!0!1!\relax!#2#3!!!{#2}%

101:  \go101\relax

001:  \go001\relax

111:  \go111\relax

11100:  \go11100\relax

1100110011:  \go1100110011\relax

00110011001100:  \go00110011001100\relax

000:  \go000\relax

\bye

If you wish trailing (significant) zeros to be removed from your Big-Endian-Number, you can probably try s.th. like this:

\def\go{\innergo{1}{0}{}{}}
\def\innergo#1#2#3#4#5{%
    % #1 replacement for bit 0 / digit to append when \relax is reached.
    % #2 replacement for bit 1
    % #3 symbol to gather when encountering bit 0
    % #4 replacements for bit 0 gathered so far
    % #5 current bit or \relax
  \ForkBit
  !#5!1!\relax!{#1\innergo{}{1}{0}{#4#3}}%    <- #5 (current bit) is 0
  !0!#5!\relax!{#4#2\innergo{#1}{#2}{#3}{}}%  <- #5 (current bit) is 1
  !0!1!#5!{#1}%                               <- #5 (current bit) is \relax
  !!!%
}%
\def\ForkBit#1!0!1!\relax!#2#3!!!{#2}%

101:  \go101\relax

001:  \go001\relax

111:  \go111\relax

11100:  \go11100\relax

1100110011:  \go1100110011\relax

00110011001100:  \go00110011001100\relax

000:  \go000\relax

\bye