expl3でFibonacci数列を完全展開可能な形で求める話(1)

🙃「TeX言語🤮でFibonacci数列を完全展開可能な形で求める話」
😵‍💫「そんなのはexpl3でやるべき」
🙃「うえ～ん😭（ネタ獲得失敗）」#TeX #TeX言語 #春のTeX言語キャンペーン🌸
— 某ZR（ざんねん🙃） (@zr_tex8r) 2024年4月6日

某キャンペーン🌸のネタにはならないわけだが、せっかくなのでチョット話してみる。特にexpl3の新機能である“e 引数指定子”について詳しく扱うので「e引数指定子をまだ知らない」というexpl3者にとっては有用な記事になるかもしれない。

※対象読者は「フツーにexpl3できる人」とする🙂

お題

次の2つの完全展開可能な命令を実装したい。

\Fibonacci{<整数n>}：［完全展開可能］フィボナッチ数列の第n項の値（の十進表記）。
\FibonacciSeq{<整数n>}：［完全展開可能］フィボナッチ数列の第n項までをコンマ区切りで並べた文字列。

完全展開可能であるため、展開限定文脈（\typeoutの中など）でも正常に動作する必要がある。

\typeout{F[10] = \Fibonacci{10}}
%==> "F[10] = 55" (端末表示)
\typeout{\FibonacciSeq{10}}
%==> "1, 1, 2, 3, 5, 8, 13, 21, 34, 55" (端末表示)

とにかく実装し始める話

とりあえず「フィボナッチ数列の値を求める部分」以外の“ガワの部分”をさっさと済ませてしまおう。フツーのexpl3者にとっては初歩的なコード実装のはずだが、「完全展開可能にしたいので完全展開可能でない¹ライブラリ関数（\int_step_inline:～等）は使えない」ことに注意する必要がある。

%%<*> \Fibonacci{<整数n>} (完全展開可能)
% フィボナッチ数列の第n項の値.
% ※完全展開可能にしたいので, xparse系のマクロ定義命令を利用するならば
% "Expandable" 版のものを選ぶ必要がある. (\newcommand でもよい.)
\NewExpandableDocumentCommand \Fibonacci { m }
  { \int_to_arabic:n { \__myfib_value:n {#1} } }

%%<*> \FibonacciSeq{<整数n>} (完全展開可能)
% フィボナッチ数列の第n項までをコンマ区切りで並べた文字列.
\NewExpandableDocumentCommand \FibonacciSeq { m }
  % 完全展開可能にしたいので \int_step_inline:～ ではなく
  % \int_step_function:～ を利用する.
  { \int_step_function:nnN { 1 } {#1} \__myfib_seq_iter:n }
% ループの中の処理.
\cs_new:Nn \__myfib_seq_iter:n
  {
    \int_compare:nNnF {#1} =  { 1 } { ,~ } % 先頭以外ではコンマを入れる
    \int_to_arabic:n { \__myfib_value:n {#1} }
  }

%% \__myfib_value:n{<n>}
% フィボナッチ数列の第n項の値.
\cs_new:Nn \__myfib_value:n
  { % TODO:実装する
  }

後は「\__myfib_value:nをいかにして完全展開可能で実装するか」という話になる。

TeX以外で実装してみる話

完全展開可能にするため\int_set:Nn等の「代入操作」は一切使えないことになる。従って再帰を利用した²“関数型プログラミング的なロジック”を組む必要がある。

ここでは「どんな感じのコードを書けばいいか」を示すために関数型組版言語であるSATySFiのコードを掲載することにする。

@require: stdjareport

% 不変条件: a が第(n-k)項, b が第(n-k+1)項に等しい.
let-rec myfib-value-aux k a b =
  if k == 1 then b % 第n項の値
  else myfib-value-aux (k - 1) b (a + b) % 再帰する
let myfib-value n =
  if n < 1 then 0
  else myfib-value-aux n 0 1

% ↓これ以降はSATySFi特有の話なのでexpl3者は気にしなくてよい.
let-inline ctx \Fibonacci n =
  read-inline ctx (embed-string (arabic (myfib-value n)))
in
document (|
  author = {}; title = {}; show-title = false; show-toc = false
|) '<
  +p{${F_{10}} = \Fibonacci(10);}
>

もちろんSATySFiなのでこの記事のお題の\Fibonacciに相当する命令も作れる😃

expl3で一応実装してみた話

「どういう感じのコードを書けばいいか」がわかったので、\__myfib_value:nを実際にexpl3で書いてみよう。

%% \__myfib_value:n{<n>}
% フィボナッチ数列の第n項の値.
\cs_new:Nn \__myfib_value:n
  {
    \int_compare:nNnTF {#1} < { 1 } { 0 } % n<1なら0を返す
      { \__myfib_value_aux:nnn {#1} { 0 } { 1 } }
  }

%% \__myfib_value_aux:nnn{<k>}{<a>}{<b>}
% \__myfib_value:n の下請け.
% 不変条件: a が第(n-k)項, b が第(n-k+1)項に等しい.
\cs_new:Nn \__myfib_value_aux:nnn
  {
    \int_compare:nNnTF {#1} = { 1 } { #3 } % 第n項の値
      {% 単純に再帰呼出してみた
        \__myfib_value_aux:nnn
          { \int_eval:n { #1 - 1 } }
          { #3 }
          { \int_eval:n { #2 + #3 } }
      }
  }

実際に\Fibonacciを\typeoutの中に置いて試してみると、正しく動作しているようにみえる。

\typeout{F[10] = \Fibonacci{10}}
%==> "F[10] = 55" (端末出力)

しかしnの値を少し増やすと爆発してしまう😲

\typeout{F[30] = \Fibonacci{30}}
Runaway argument?
{\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n \
ETC.
! TeX capacity exceeded, sorry [main memory size=5000000].
<argument> ...l:n {\int_eval:n {\int_eval:n {\ETC.

l.3 \typeout{F[30]=\Fibonacci{30}}

※第30項の値は832040だからTeXの扱える整数の範囲にはまだ入っているはず。

\int_eval:nが延々と並んでいるのを見れば察しが付くと思うが、要するに「展開制御が足りていない」のが原因である。

\__myfib_value_aux:nnnの再帰呼出のところを検討してみよう。

\__myfib_value_aux:nnn{2}{0}{1}
↓(展開を続ける)
\__myfib_value_aux:nnn{\int_eval:n{2-1}}{1}{\int_eval:n{0+1}}

ここで期待する動作は「\__myfib_value_aux:nnn{1}{1}{1}」が実行されることであろう。しかしexpl3の“関数”は所詮はTeXのマクロに過ぎないので、何も展開制御をしなければ\int_eval:n{2-1}等のトークン列がそのままマクロに渡されてしまうことになる。これを何度も繰り返すと、引数の式が

{\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n {\int_eval:n ……

のようなオソロシイ形に肥大化するわけである。このトークン列の長さはnに対して指数関数的に増えるので、少し大きいnで“TeX capacity exceeded”になるのも当然である。

結局、行うべき展開制御の内容は「__myfib_value_aux:nnnの再帰呼出の際に第1と第3の引数を完全展開すること」ということになる。

\__myfib_value_aux:nnn{\int_eval:n{2-1}}{1}{\int_eval:n{0+1}}
↓上のコードを下のコードに変えたい
\__myfib_value_aux:nnn{1}{1}{1}

展開制御してみる話

expl3における展開制御は基本的に「展開用の引数指定子(argumente specifier)を指定する」形で行う。今やりたいのは完全展開であるが、expl3に昔からある引数指定子で完全展開の機能をもつものは次の2つである。

x：引数を完全展開³する。ただし、元々n指定の引数を展開制御(\exp_args:N～)によりx指定に転換した場合は完全展開可能性が失われてしまう。
f：引数を先頭完全展開する。（展開制御でf指定に転換した場合には完全展開可能性は失われない。）

\__myfib_value_aux:nnnの展開制御でどちらを使うべきかの答えは明らかである。そもそも完全展開可能な命令を実装しようとしているのだから「完全展開可能性が失われる」性質を持つx指定は選択肢になく、f指定を使うしかない。従って、f指定で目的を果たせるかを検討しよう。

今やりたいのは「\__myfib_value_aux:nnnの2つの引数を完全展開する」ことであるが、この2つの引数はいずれも「\int_eval:n {…}」という形である。\int_eval:nは先頭完全展開可能⁴である（マニュアル（interface3）において★印が付いている）なので、f指定（先頭完全展開を施す）により完全展開されることがわかる。従って引数全体のf指定による展開結果は「整数式の値（を表すトークン列⁵）」となり、結果的にこれは所望のものと一致している。

f指定で目的が果たせることがわかったので実際にコードを改修してみよう。expl3で展開制御を指定する方法には\cs_generate_variant:Nnを使うものと\exp_args:N～を使うものの2種類がある。

\cs_generate_variant:Nn で頑張る話

今欲しいものは「\__myfib_value_aux:nnnの第1と第3の引数にf指定の展開を施したもの」である。これをexpl3の関数の命名規則では\__myfib_value_aux:fnf（引数指定子の第1と第3の文字をfに変える）と呼ぶ。このように「ある関数の引数指定子を変えたもの」のことをその関数の「変種(variant)」と呼ぶ。

そして、所望の変種\__myfib_value_aux:fnfを既存の\__myfib_value_aux:nnnから自動的に生成してくれるのが\cs_generate_variant:Nnというライブラリ関数である。今の場合は「既存の\__myfib_value_aux:nnnからfnf版を生成したい」ので次のようなコードを実行すればよい。

\cs_generate_variant:Nn \__myfib_value_aux:nnn { fnf }

これで\__myfib_value_aux:fnfが定義されるので、\__myfib_value_aux:nnnの定義本体のコードの中の再帰呼出の部分をこのfnf版の呼出に置き換えよう。

\cs_new:Nn \__myfib_value_aux:nnn
  {
    \int_compare:nNnTF {#1} = { 1 } { #3 }
      {% 再帰呼出では引数を展開する
        \__myfib_value_aux:fnf %←※ここで"fnf"版を使っている
          { \int_eval:n { #1 - 1 } }
          { #3 }
          { \int_eval:n { #2 + #3 } }
      }
  }
\cs_generate_variant:Nn \__myfib_value_aux:nnn { fnf }

これでフツーに動く\Fibonacciが完成したことになる。実際に少し大きいnで動作を試してみよう。

\typeout{F[30] = \Fibonacci{30}}
%==> "F[30] = 832040" (端末出力)

うまくいったようだ😊

\exp_args:N～で頑張る話

「\__myfib_value_aux:nnnのfnf版が欲しい」場合に\cs_generate_variant:Nnは実際に\__myfib_value_aux:fnfという関数を定義するのであった。これとは別の方法として、\exp_args:N～という一連のライブラリ関数を利用することもできる。これは「\__myfib_value_aux:nnnにfnf版の動作をさせる」ためのものである。

\exp_args:N～の～の部分には所望の変種の引数指定子を書く。例えば、\__myfib_value_aux:nnnにfnf版の動作をさせたい場合は、\exp_args:Nfnfという関数を前に置けばよい。

\exp_args:Nfnf \__myfib_value_aux:nnn { \int_eval:n { 2 - 1 } } { 1 } { \int_eval:n { 0 + 1 } }

※\__myfib_value_aux:nnn以下のトークン列は「\exp_args:Nfnfの引数」という位置付けになっていて、だからこそNfnfという引数指定子になっている。

これで完成のはずだが、実際には上記のようなコードを実行すると「\exp_args:Nfnfが未定義である」というエラーになる。\exp_args:N～の～の部分のパターンは無数にあり、それら全てを予め定義しておくのは無駄であるから「expl3のカーネルでは一部だけを定義しておく」という方針になっているためである。どのパターンがカーネルで定義されているかはマニュアルに書かれていて、例えば\exp_args:Nfや\exp_args:Nnffは定義されているが\exp_args:Nfnfはされていない。

カーネルで定義されてない\exp_args:N～のパターンを使用するには、予め\exp_args_generate:nという命令を用いて定義する必要がある⁶。

\exp_args_generate:n { fnf }

\exp_args:Nfnfを使って\__myfib_value_aux:nnnを修正した場合のコードは以下のようになる。

% \exp_args:Nfnf を利用可能にする
\exp_args_generate:n { fnf }

\cs_new:Nn \__myfib_value_aux:nnn
  {
    \int_compare:nNnTF {#1} = { 1 } { #3 }
      {% 再帰呼出では引数を展開する
        \exp_args:Nfnf \__myfib_value_aux:nnn
          { \int_eval:n { #1 - 1 } }
          { #3 }
          { \int_eval:n { #2 + #3 } }
      }
  }

（つづけ）

マニュアル（interface3）において星印（★や☆）が付いていない関数は完全展開可能でない。↩
もちろん、「フィボナッチ数列の定義をそのまま書いたコード」は「求めるフィボナッチ数の値に比例した時間（nに対いて指数関数的）」がかかってしまうので、それはやってはいけない🙃↩
この記事での「完全展開」「先頭完全展開」はTeX言語の用法に従う。もしかしたらexpl3では「先頭完全展開」のことを「完全展開(full expansion)」と呼ぶのかもしれないが、今一つ実態をつかめていないので従来の用語を使うことにする。↩
expl3の用語では「先頭完全展開可能」のことを「完全展開可能(fully expandable)」、単なる「完全展開可能」のことを「制限付展開可能(restricted expandable)」と呼ぶ。ここではTeX言語の用法に従う。↩
ちなみに、expl3の仕様としては「整数値を返すライブラリ関数」の実際の展開結果である「整数値を表すトークン列」は必ずしも「十進の数字列」とは限らないようである。\Fibonacciの実装コードでわざわざ\int_to_arabic:nを入れているのはこのためである。↩
なお、既に定義済のパターンについて\exp_args_generate:nを実行しても何も起こらない。今カーネルで定義済のものが将来削除されることもないため、「今のexpl3の版で未定義ならば自分で定義する」という方針に従っても前方・後方互換性は保たれる。↩

マクロツイーター

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

expl3でFibonacci数列を完全展開可能な形で求める話(1)

お題

とにかく実装し始める話

TeX以外で実装してみる話

expl3で一応実装してみた話

展開制御してみる話

\cs_generate_variant:Nn で頑張る話

\exp_args:N～で頑張る話

お題

とにかく実装し始める話

TeX以外で実装してみる話

expl3で一応実装してみた話

展開制御してみる話

\cs_generate_variant:Nn で頑張る話

\exp_args:N～ で頑張る話

\exp_args:N～で頑張る話