末尾再帰について素朴に考えてみた

この記事は、TeX & LaTeX Advent Calendar 2016 の第 4 日目のために書いたものです。

12/3 のご担当は hak7a3 さんで、12/5 のご担当は aminophen さんです。

いつもながらの言い訳とお詫び

例年は Advent Calendar のエントリの募集が始まってから、何を取り上げるか考えたり、記事を書き始めたりするのですけれど、今年は極めて個人的な事情ながら、11 月から 12 月にかけては、趣味にではなく自分の論文に “ホンキ” にならないと相当マズイだろうということが随分と前から判っていました。

それなら 10 月までにネタを見つけて、記事も完成させておけばよいわけですが、悲しい哉そんな計画性は持ち合わせてないです。また、ネタも時間もないのなら、エントリしなければいいだけなのですが、今年は 5 周年の節目の年なのでなんとか参加したい、というこれまた勝手な思い入れがありました。

で、何もしないまま 10 月が終わろうというときに、たまたま TeX Forum の 「マクロでの繰り返し文について教えて下さい」 という質問に横から口を挟まさせていただく機会がありました。

その際に、お寄せいただいた回答を承けて手元でチョコチョコ試してみたのですが、そのメモを Advent Calendar の記事にしようという安易な考えが浮かびました。

それで、10 月末に急いでまとめたものが、下記の記事になります。

素人がウダウダと考えたことを書き連ねただけのものですので、末尾再帰について正しい知識が必要な方は、ちゃんとした文献にあたってください。 あと、柄にもなく、最後のところで \expandafter についても触れてしまっていますが、何か的はずれなことを書いていましたら、本当にすいません。

I.　事の発端
II.　末尾再帰を実現する典型的な方法
　　　（1） 単純な場合
　　　　　　（a） 直接的なやり方
　　　　　　（b） \let を使うやり方
　　　（2） オプションを取れるようにする場合
　　　　　　（a） 直接的なやり方
　　　　　　（b） \let を使うやり方
III.　オマケ： 条件文の中の \expandafter

Since: December 3, 2016.

I.　事の発端

まず、TeX Forum に投稿したものを再掲しますと ：

Re: マクロでの繰り返し文について教えて下さい
2016年 10月 25日(火曜日) 08:46 - ut 　 の投稿

既に問題は解決済みなので、単純に興味本位でのお尋ねになるのですけれど、質問者の方が当初意図されたようなことって、実現できるのでしょうか？
例えば、すごく素朴に考えてみますと、

\newcounter{MyNum}
\newcommand{\cmdA}[1][foo]{%
   \setcounter{MyNum}{0}
   \loop \ifnum \value{MyNum} < 3\relax
   \stepcounter{MyNum}
   \cmdB{#1}
   \repeat
 }
\newcommand{\cmdB}[4]{%
   (#1)(#2)(#3)(#4)%
 }

みたいに定義したら、

\cmdA{a}{b}{c}{d}{e}{f}{g}{h}{i}
　　↓
\cmdB{foo}{a}{b}{c}\cmdB{foo}{d}{e}{f}\cmdB{foo}{g}{h}{i}

とか、

\cmdA[bar]{a}{b}{c}{d}{e}{f}{g}{h}{i}
　　↓
\cmdB{bar}{a}{b}{c}\cmdB{bar}{d}{e}{f}\cmdB{bar}{g}{h}{i}

という風になることを期待されてたんじゃないかなと思うのですけれど、実際には、これではうまくいきませんよね…。

\loop 〜 \repeat の部分の書き方がちょっとおかしいとか、あと、\setcounter や \stepcounter の後の “%” を忘れているとかいうのにはひとまず目をつぶっていただくとしても、この場合、“\loop 〜 \repeat” を使うのでは、期待通りにはいかなかったわけですが、これに対しては、アセトアミノフェンさん と Z. R. さん とから、「末尾再帰 （tail recursion）」 を使えばよいと教えていただきました （他にもご意見をお寄せくださったみなさま、ありがとうございます）。

以下では、このときに末尾再帰について少し考えてみたことを、メモ程度にまとめておきます。

II.　末尾再帰を実現する典型的な方法

（1）　単純な場合

簡単な例を考えることにします。とりあえず、実現したいことは ：

\cmdA{a}{b}{c}{d}{e}{f}

のように、冒頭に一回だけ \cmdA を置いたら、\cmdA が順番に 2 個ずつ引数を食べていってくれて、それで、e と f まで行ったら、そこでちゃんと処理が終わる、というものにしましょう。2 つの引数に対する操作は何でもいいのですけれど、ここでは、それらを （ ） の中に入れることにします。つまり ：

\cmdA{a}{b}{c}{d}{e}{f}
　　↓
(a,b)\cmdA{c}{d}{e}{f}
　　↓
(a,b)(c,d)\cmdA{e}{f}
　　↓
(a,b)(c,d)(e,f)

という風になってほしいということです。

このような動作を実現する方法は、典型的には、二つ考えられます。

（a）　直接的なやり方

まず、一つ目の考え方としては、\cmdA{a}{b} の置換テキストが “(a,b)” ではなくて、“(a,b)\cmdA” であれば、うまくいきそうです。つまりは、末尾再帰ですね。

しかし、最後の \cmdA{e}{f} の置換テキストが “(e,f)\cmdA” となるのでは、\cmdA が無限に展開することになってしまいますので、\cmdA{e}{f} のときには、その置換テキストは “(e,f)” でないと困ります。

今の場合のように、\cmdA を実行する回数が予め分かっているときには、カウンタで回数を数えて、処理を分岐させればよさそうです。そこで ：

\newcounter{cntA}

\newcommand{\cmdA}[2]{%
   \stepcounter{cntA}%
   \ifnum \value{cntA} < 3\relax
      (#1,#2)\expandafter\cmdA
   \else
      (#1,#2)%
      \setcounter{cntA}{0}%
   \fi
}

のように定義しますと、

\cmdA{a}{b}{c}{d}{e}{f}
　　↓
　　↓ cntA=1
　　↓ \cmdA{a}{b} --> (a,b)\cmdA
　　↓ 
(a,b)\cmdA{c}{d}{e}{f}
　　↓
　　↓ cntA=2
　　↓ \cmdA{c}{d} --> (c,d)\cmdA
　　↓ 
(a,b)(c,d)\cmdA{e}{f}
　　↓
　　↓ cntA=3
　　↓ \cmdA{e}{f} --> (e,f)
　　↓ 
(a,b)(c,d)(e,f)% cntA=0

となります。

【補足】
本記事では、単純さを優先して、\cmdA の動作の実体部分を \cmdA （乃至 \cmdB） の定義内部に直書きしていますが、普通は、\cmdA の本体部分は別に定義しておいたほうが、後々 \cmdA の動作を変更したりするのが楽になります。つまり ：

\newcounter{cntA}

\newcommand{\cmdA}[2]{%
   \stepcounter{cntA}%
   \ifnum \value{cntA} < 3\relax
      \cmdAbody{#1}{#2}\expandafter\cmdA
   \else
      \cmdAbody{#1}{#2}%
      \setcounter{cntA}{0}%
   \fi
}

\newcommand{\cmdAbody}[2]{%
   (#1,#2)%
}

みたいにするのが普通かと思います。

（b）　\let を使うやり方

次に、二つ目としては、\cmdA{a}{b} の置換テキストが “(a,b)\cmdA” ではなくて、“(a,b)\cmdNext” になると考えて、それで、場合に分けて、\cmdNext の意味を \cmdA に \let したり \relax その他に \let したりする、という方法があります。例えば ：

\newcounter{cntA}

\newcommand{\cmdA}[2]{%
   \stepcounter{cntA}%
   (#1,#2)%
   \ifnum \value{cntA} < 3\relax
      \let\cmdNext\cmdA
   \else
      \let\cmdNext\relax
      \setcounter{cntA}{0}%
   \fi
   \cmdNext
}

のように定義しますと、

\cmdA{a}{b}{c}{d}{e}{f}
　　↓
　　↓ cntA=1
　　↓ \cmdNext=\cmdA
　　↓ \cmdA{a}{b} --> (a,b)\cmdNext
　　↓ 
(a,b)\cmdNext{c}{d}{e}{f}
　　↓
　　↓ cntA=2
　　↓ \cmdNext=\cmdA
　　↓ \cmdNext{c}{d} --> (c,d)\cmdNext
　　↓ 
(a,b)(c,d)\cmdNext{e}{f}
　　↓
　　↓ cntA=3
　　↓ \cmdNext=\relax
　　↓ \cmdNext{e}{f} --> (e,f)\cmdNext
　　↓ 
(a,b)(c,d)(e,f)\cmdNext% cntA=0

という風になります。

（2）　オプションを取れるようにする場合

TeX Forum での例では、\cmdA がオプション引数を取れるようになっていましたので、ここでも、そうしてみましょう。

（a）　直接的なやり方

例えば、こんな感じでしょうか ：

\newcounter{cntA}

\newcommand{\cmdA}[1][foo]{%
   \setcounter{cntA}{0}%
   \def\cmdBwithArg{\cmdB{#1}}%
   \cmdBwithArg
}

\newcommand{\cmdB}[3]{%
   \stepcounter{cntA}%
   \ifnum \value{cntA} < 3\relax
      (#1,#2,#3)\expandafter\cmdBwithArg
   \else
      (#1,#2,#3)%
   \fi
}

（b）　\let を使うやり方

こちらも同様にして ：

\newcounter{cntA}

\newcommand{\cmdA}[1][foo]{%
   \setcounter{cntA}{0}%
   \def\cmdBwithArg{\cmdB{#1}}%
   \cmdBwithArg
}

\newcommand{\cmdB}[3]{%
   (#1,#2,#3)%
   \stepcounter{cntA}%
   \ifnum \value{cntA} < 3\relax
      \let\cmdNext\cmdBwithArg
   \else
      \let\cmdNext\relax
   \fi
   \cmdNext
}

（あんまりちゃんと考えてないので、本当はもっといい方法があるのかも知れません…）

III.　オマケ： 条件文の中の \expandafter

上で見た II. （1）（a） と II. （2）（a） には私のような初級の人間には鬼門の “\expandafter” が出てきましたけれど、この件についても簡単にメモ。

条件判断文は、一般に、

\ifsomecondition <true text> \else <false text> \fi

という形をとりますが、ここで、“\ifsomecondition” が true のときは、“<true text> \else” の部分が左から順番に展開されていって、\else に行き当たると、そこで条件文は終わって、“<false text> \fi” の部分は一瞬にして読み飛ばされます。

他方、“\ifsomecondition” が false のときは、“<true text> \else” の部分が読み飛ばされて、“<false text> \fi” の部分が左から順番に展開されていって、\fi に行き当たると、そこで条件文は終わりとなります。

実際、例えば ：

\def\cmdA{A} \def\cmdB{B} \def\cmdC{C}

と定義してあるときに、

\ifsomecondition \cmdA \else \cmdB \fi \cmdC

の動きについて、\tracingcommands と \tracingmacros で追ってみますと、\ifsomecondition が true のときには ：

{vertical mode: \ifsomecondition}
{true}
\cmdA ->A
{the letter A}
{horizontal mode: the letter A}
{\else}
\cmdC ->C

となっていて、\cmdA と \else を順番に展開後、\cmdB と \fi は読み飛ばされて、\cmdC が展開されていることが分かります。

逆に、false のときには ：

{vertical mode: \ifsomecondition}
{false}
\cmdB ->B
{the letter B}
{horizontal mode: the letter B}
{\fi}
\cmdC ->C

となってて、今度は、\cmdA と \else が読み飛ばされて、\cmdB と \fi が順に展開された後に、\cmdC が展開されていることが確認できます。

今の例では、\cmdA や \cmdB が引数を取らないマクロでしたが、ここでもしも、“<true text>” や “<false text>” の最後 （または “<true text>” や “<false text>” の展開結果の最後） が、引数をとるマクロだったとしたら、どうなるでしょうか。

その場合には、\else や \fi が、マクロの引数として一旦呑み込まれて （！）、それから、当該マクロの置換テキストの “#n” の場所に移動してしまうことになります。

【補足】
つまり、\else や \fi が、マクロの一つ目の引数として呑み込まれると、 そのマクロの置換テキストの “#1” の場所に移動し、二つ目の引数として呑み込まれると、 “#2” の場所に移動する…〔以下略〕、ということです。

そのため、前出の II. （1）（a） で、“<true text>\else” の部分を

　　(#1,#2)\cmdA\else

としてしまうと、\else は \cmdA の一つ目の引数として呑み込まれることになり、同様に、前出の II. （2）（a） で、“<true text>\else” の部分を

　　(#1,#2,#3)\cmdBwithArg\else

としてしまうと、\else は \cmdB の二つ目の引数として呑み込まれることになります。

具体例を考えてみますと、例えば ：

\def\cmdX#1#2{(#1,#2)} \def\cmdY#1#2{[#1,#2]}

と定義した上で、

\ifsomecondition \cmdX \else \cmdY \fi {a}{b}

と書いたら、\ifsomecondition が

• true のときには \cmdX{a}{b} --> (a,b)
• false のときには \cmdY{a}{b} --> [a,b]

となるかな、と思ったら、残念ながらそうはならないということです。

実際には、\ifsomecondition が true の場合には ：

\ifsomecondition \cmdX \else \cmdY \fi {a}{b}
　　↓
　　↓ \cmdX は引数を 2 個とるので \else と \cmdY が呑み込まれる
　　↓
\cmdX \else \cmdY \fi {a}{b}
　　↓
　　↓ \cmdX の定義に \else と \cmdY が入る
　　↓
(\else,\cmdY) \fi {a}{b}
　　↓
　　↓ つまり、“(\else” と “,\cmdY) \fi”
　　↓
(\else,\cmdY) \fi {a}{b}
　　↓
　　↓ \else の展開で条件文は終わり、“,\cmdY) \fi” は読み飛ばされ、最終的な出力は、
　　↓
(ab

となり、他方、\ifsomecondition が false の場合には ：

\ifsomecondition \cmdX \else \cmdY \fi {a}{b}
　　↓
　　↓ まず、\cmdX と \else が読み飛ばされる
　　↓
\cmdX \else \cmdY \fi {a}{b}
　　↓
　　↓ \cmdY は引数を 2 個とるので \fi と {a} が呑み込まれる
　　↓
\cmdY \fi {a}{b}
　　↓
　　↓ \cmdY の定義に \fi と a が入る
　　↓
[\fi,a]{b}
　　↓
　　↓ つまり、“[\fi” と “,a]{b}”
　　↓
[\fi,a]{b}
　　↓
　　↓ \fi の展開で条件文は終わり、最終的な出力は、
　　↓
[,a]b

となるからです。

期待したようにはいかない理由は、TeX が、\else や \fi を見つける前に、\cmdX や \cmdY を展開してしまうからですよね。そこで、\expandafter を \cmdX や \cmdY に 前置して ：

\ifsomecondition \expandafter \cmdX \else \expandafter \cmdY \fi {a}{b}

という風にすれば、無事 TeX は \cmdX や \cmdY を展開する前に \else や \fi を見つけることができるようになるわけです。

\ifsomecondition \let\cmdNext\cmdX \else \let\cmdNext\cmdY \fi \cmdNext{a}{b}

例年内容は薄いのですけれど、今年は分量も少なくて、以上で終わりです。

ではでは、Merry TeXmas & Happy TeXing!

Last modified: Nov. 13, 2016.