🙃「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の版で未定義ならば自分で定義する」という方針に従っても前方・後方互換性は保たれる。↩