マクロツイーター

はてダから移行した記事の表示が崩れてますが、そのうちに直せればいいのに(えっ)

TeX の末尾再帰(3)

TeX で再帰する件」の続き。再帰関数型プログラミングで常用される技術である。従って、SchemeHaskell 等の関数型プログラミング言語を習得しているなら、その知識は TeX でのプログラミングでも役に立つことは確かである。ただ、TeX は「関数がない言語」という「関数型言語」の対極にある性質も備えている。だから関数型言語におけるコーディング手法をそのまま持ち込むのは不適切な場合もあることに注意すべきである。

再び「1 から n までの整数を順に出力する」を例にとる。Scheme で末尾再帰形式で書くと次のようになるだろう。

(define (count-up-to n)
  (define (count-up-to-iter m n)
    (display m) (newline)
    (if (< m n)
      (count-up-to-iter (+ m 1) n)))
  (count-up-to-iter 1 n))

このコードの書き方をそのまま TeX に直すと以下のようになる。

\newcount\countM
\newcount\countN
\def\countUpToIter#1#2{%
  \countM=#1\relax \countN=#2\relax
  \the\countM\par
  \ifnum\countM<\countN
    \advance\countM 1
    \def\next{\countUpToIter{\countM}{\countN}}%
  \else \let\next\relax
  \fi
  \next
}
\def\countUpTo#1{%
  \countN=#1\relax
  \countUpToIter{1}{#1}%
}

このプログラムは全く正常に動作する。しかし、このような「引数を使った末尾再帰」を TeX で行うのは少し危険なところがある。前の Scheme と比べた場合、この TeX のコードは以下の点が決定的に異なる。

  • Scheme のコードで、count-up-to-iter の変数 mn はこの関数内でローカルである。対して、TeX のコードでの \countM\countN はグローバルである。TeX において「マクロ(の各々の呼出)内でローカル」なものはパラメタ(#1#2)だけである。
  • Scheme の関数の引数は「値渡し(call-by-value)」で評価される―つまり、再帰呼出した関数に渡されるのは mn の値である。対して、TeX のマクロの引数の取扱は、動作としては「参照渡し(call-by-reference)」での評価に近い。*1

上記の TeX のプログラムとこれらの 2 点についてほぼ等価な動作を C++ で書くと次のようになる。(取り敢えず「型名に & の付いた引数は参照渡しになる」と理解しておけば良い。*2

#include <iostream>
int m, n; // グローバル変数
void count_up_to_iter(int& m_, int& n_) { // 引数は参照渡し
    m = m_; n = n_;
    std::cout << m << std::endl; // m を出力する
    if (m < n) {
        m += 1; count_up_to_iter(m, n);
    }
}
void count_up_to(int n_) {
    m = 1; n = n_;
    count_up_to_iter(m, n);
}
int main() {
  count_up_to(40);
  return 0;
}

参照渡しのある言語に慣れている人なら、かなり不可解なことをしていることが解ると思う。あるいは、もっと直接的に、\countUpToIter{\countM}{\countN} の呼出(展開)をした後のコードを考えてもよい。

(#1->\countM#2->\countN\countUpToIter を展開)
  \countM=\countM\relax \countN=\countN\relax
  \the\countM\par
  \ifnum\countM<\countN

この先頭の代入は全く冗長である。この場合、冗長であるだけで特に害はない(だから結果的に正常動作する)のであるが、何となく「同じ書き方をしていると失敗する場合がある」可能性を感じるであろう。以下では「失敗する場合」を挙げることにする。

(define (gcd x y)
  (if (= y 0) x
    (gcd y (mod x y))))

Scheme 屋にはお馴染みの、最大公約数(GCD)の互除法による再帰的定義である。これを「同じように」TeX に書き直したとしよう。*3

\newcount\countResult
\newcount\countX
\newcount\countY
\newcount\countZ
% \doGcd{<x>}{<y>}: x と y のGCDを \countResult に代入する
\def\doGcd#1#2{%
  \countX=#1\relax \countY=#2\relax
  % countX := countX mod countY
  \countZ=\countX \divide\countZ\countY
  \multiply\countZ\countY \advance\countX-\countZ
  \ifnum\countX=0
    \def\next{\countResult=\countY}%
  \else
    \def\next{\doGcd{\countY}{\countX}}%
  \fi
  \next
}
% テスト: 91 と 42 の GCD を端末に表示する
\doGcd{91}{42}
\immediate\write16{Answer = \the\countResult}
% --> Answer = 42 (間違い)

これまでの説明を理解したなら、この理由は容易に解るであろう。再帰呼出の \doGcd{\countY}{\countX} を展開したコードの冒頭は、

  \countX=\countY\relax \countY=\countX\relax

になってしまう。これでは \countX\countY が同じ値になってしまって、上手くいく筈がない。

(次回へ続く)

*1:ただし、Scheme(や C 等の大多数の言語)と TeX の評価戦略の違いは「値渡し vs 参照渡し」ではなく、ラムダ計算における「適用順序(applicative order) vs 正規順序(normal order)」の違いに寧ろ近い。

*2:Scheme で書くのは諦めた ;-)

*3:「関数はない」ので、戻り値のある関数を表現しようとすると、「ある決まった変数に代入する」か「引数で指定された変数に代入する」等の方式を採ることになる。