🙃「TeX言語🤮でFibonacci数列を完全展開可能な形で求める話」
— 某ZR（ざんねん🙃） (@zr_tex8r) 2024年4月6日
😵💫「そんなのはexpl3でやるべき」
🙃「うえ～ん😭（ネタ獲得失敗）」#TeX #TeX言語 #春のTeX言語キャンペーン🌸
某キャンペーン🌸のネタにはならないわけだが、せっかくなのでチョット話してみる。特に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者にとっては初歩的なコード実装のはずだが、「完全展開可能にしたいので完全展開可能でない1ライブラリ関数（\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等の「代入操作」は一切使えないことになる。従って再帰を利用した2“関数型プログラミング的なロジック”を組む必要がある。
ここでは「どんな感じのコードを書けばいいか」を示すために関数型組版言語である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： 引数を完全展開3する。ただし、元々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は先頭完全展開可能4である（マニュアル（interface3）において★印が付いている）なので、f指定（先頭完全展開を施す）により完全展開されることがわかる。従って引数全体のf指定による展開結果は「整数式の値（を表すトークン列5）」となり、結果的にこれは所望のものと一致している。
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という命令を用いて定義する必要がある6。
\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の版で未定義ならば自分で定義する」という方針に従っても前方・後方互換性は保たれる。↩
