Hatena::ブログ(Diary)

マクロツイーター このページをアンテナに追加 RSSフィード Twitter

2011-08-25

TeX での末尾再帰(2)

前回において、「TeX マクロ再帰呼出が末尾再帰になる場合」の展開の様子について考察した。ここから、TeX での「末尾再帰」の定義を導くことができる―すなわち、TeX マクロの置換テキスト(展開した内容)の処理(プリミティブの実行や他のマクロの展開)において、最後に行われるものが当該マクロの展開である場合、それ(マクロの呼出)が「末尾再帰」である。

TeX の末尾再帰に関して注意すべきなのは、普通のプログラミング言語だと末尾再帰になりそうな形が TeX ではならないことがあるということである。

例えば、1 から指定の数まで順に整数を出力する*1という典型的な繰り返し処理を実装してみる。

% \countUpTo{<n>}: 1 から n までの整数を(改段落しながら)出力する
\newcount\num
\newcount\limitNum
\def\countUpTo#1{%
  \num=0 \limitNum=#1\relax
  \countUpToIter
}
\def\countUpToIter{%
  \advance\num1
  \the\num\par          % \num の値を数字で出力して改段落
  \ifnum \num<\limitNum % 指定値に達していないなら
    \countUpToIter      % 末尾再帰(?)を行う
  \fi
}

これで \countUpTo{40} とすると確かに正常に動く。私の環境では \countUpTo{1000} でも大丈夫だった。しかし、\countUpTo{10000} は「容量超過」のエラーになってしまう。前回調べたように、末尾再帰になっていれば何回でも反復できるはずなので、この結果は末尾再帰になっていないことを意味する。

! TeX capacity exceeded, sorry [input stack size=5000].
<inserted text> 4
                 998
\countUpToIter ->\advance \num 1 \the \num
                                           \par \ifnum \num <\limitNum \coun...

\countUpToIter ... \num <\limitNum \countUpToIter
                                                  \fi
\countUpToIter ... \num <\limitNum \countUpToIter
                                                  \fi
\countUpToIter ... \num <\limitNum \countUpToIter
                                                  \fi
\countUpToIter ... \num <\limitNum \countUpToIter
                                                  \fi
...
l.15 \countUpTo{10000}

何故 \countUpToIter 中での自身の呼出は「末尾」でないのか。実は理由は非常に簡単である。

本当に末尾にあるのは \fi であるから。

TeX の if 文はマクロと同様に「展開」することで評価される。その仕組みについては、既に「条件文における「展開」」の記事で説明した。ポイントは、条件部を表す\if... トークンだけでなく、\else\fi も「展開」によって処理されるということである。つまり、今の \countUpToIter の末尾の

\ifnum\num<\limitNum\countUpToIter\fi

の条件成立時の展開結果がもし

↓
\countUpToIter

となる*2のであれば、末尾再帰が成立するのであるが、実際の展開結果は以下のようになる。そして、実行器の「条件分岐状態」が更新される(ネストレベルが増加する)。

↓
\countUpToIter\fi

この深くなったネストレベルから脱出するには \fi を展開する必要があるのだが、実際には次に起こるのは \countUpToIter の展開である。

↓
\advance\num1\the\num\par\ifnum\num<\limitNum\countUpToIter\fi\fi
↓
………
↓
\countUpToIter\fi\fi
↓
………
↓
\countUpToIter\fi\fi\fi

このようにして、終了条件が満たされるまで、後ろにある \fi が延々と増えていってしまう。繰り返し回数が非常に大きくなったら、何かが破綻するということは容易に想像できるだろう。*3再帰呼出はほぼ確実に if が伴うが、*4それを普通に書いたのでは末尾再帰にならないのである。

では if 文がある場合にどうすれば末尾再帰が実現できるか。これには色々な方法がある。原理が判りやすいのは、マクロを介して本当に「末尾」に再帰呼出を置くようにする方法である。

  \ifnum \num<\limitNum   \def\next{\countUpToIter}%
  \else                   \def\next{}%
  \fi
  \next

終了条件が不成立(つまり \ifnum が成立)ならば、末尾にある \next\countUpToIter に展開されるので、「末尾で再帰呼出する」ことが実現できる。終了条件成立ならば、\next は何もしないのでそこで「大本の \countUpTo{<n> の実行が終わる」ことになる。これは現実の TeX プログラミングでよく使われる方法である。*5

今回の場合のように、再帰呼出が単一トークン(マクロ引数がない)である場合は、次の形も使える。

  \ifnum \num<\limitNum
    \expandafter\countUpToIter
  \fi

これだと、\countUpToIter の先に \fi が「展開」される―つまり if 条件を脱出して \fi が無くなる。その後の状態では確かに \countUpToIter が「末尾」にある。この形式は代入を使わないので、完全展開可能が要求される繰り返し処理で使われる。ただし、再帰呼出が単一トークンでない、あるいはそもそも if がネストしている場合には、大量の \expandafter を書く羽目に陥るのであまりやりたくない。完全展開可能なように複数トークンの再帰呼出を行うには、例えば次のような方法がある。

% まずこれを定義する(LaTeX では定義済である)
\def\@gobble#1{}
\def\@firstofone#1{#1}
% 引数付のマクロで末尾再帰したい
\def\foo#1{%
  ......  % 何か処理を行う
  \if<終了条件> \expandafter\@gobble
  \else               \expandafter\@firstofone
  \fi {\foo{...}}%
}

展開過程を辿っていくと、非終了時には \foo{...} が末尾に来ることが判る。

(まだ続く)

*1:ただし、途中でアホになることがないとする。(参考:2011-08-15)また、「出力対象の段落のバッファサイズ」の問題を避けるために、1 つずつ別の段落にする。

*2:先述の記事中で「数学的に綺麗な形」と呼んだもの。

*3:実際の動作では、「字句解析済で処理待ちのトークン列のバッファ」が溢れている。

*4:但し TeX では if トークンを使わずに終了条件でループを脱出する方法は存在する。

*5\def の代わりに \let を用いて、\let\next\countUpToIter\let\next\relax と書いても同じことになる。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/zrbabbler/20110825/1314292788