マクロツイーター

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

TeX でイオニア式記数法(1)

TeX

先日の「TeX で数式を生成する 〜アッカーマン関数編〜」の記事に関して、ツイッタァーでこんな感想があった。

うーむ、どうやら、TeX 芸のコードは完全展開可能でないといけないようである。仕方がないので、完全展開可能な TeX 芸ネタを作ることにした。お題はまた「SATySFi Advent Calendar 2018」（参加者募集中！）から取ってくることにする。

目標

TeX で以下の要件を満たす完全展開可能なマクロを実装する。

※とりあえず、今回は“結果が単純な文字列で表せる”10000 未満の数に限定する。暇があったら大きな数への対応について考える予定。

方針

  • 先頭完全展開可能にする。
  • 元ネタの記事の中の人が奨励しているように、「汎用的に使い回せる関数」の組み合わせで実装する。
  • （値を返す）関数を普通に「値（を表すトークン列）に展開されるマクロ」として表すと「関数の合成」が困難を極めることになる（参照）ので、ここでは関数を「継続渡し形式のマクロ」で表す。
  • ギリシャ文字の扱いに苦労したくないので XeLaTeX・LuaLaTeX を前提にする。Unicode 文字トークンを扱うこと以外は e-TeX 拡張の範囲に留める。

準備

ユニークトークン

ユニークトークンとは、「それ自身と \let で複写したもの以外の、他のいかなるトークンとも意味((「意味(meaning)」は TeX 言語の用語であることに注意。「意味」が同じであるかを判定するのが \ifx である。))が等価になる（つまり \ifx-等価になる）ことがない」ようなトークン((\def\CSa{\CSb} で定義される \CSa をユニークトークンとして使うには、「制御綴 \CSb の名前を（規約的に）ユニークにする」上にさらに「自分も \CSb を他の場所で使わない」という規約を守る必要がある。もちろん \CSa は他の場所での使用が前提になる。通常は、\CSaが誤って実行されたときにエラーを出すために、\CSb は未定義のままにしておく。))で、TeX 言語プログラミングの重要技巧の一つである。

%% ユニークトークン
% \my@nil : 値がないことを表す.
% ※デバッグの便宜のため保護付にする.
\protected\def\my@nil{\my@nil@}
% \my@mt : \my@if@empty 専用.
\def\my@mt{\my@mt@}
% \my@b : リストの空判定のため.
\def\my@b{\my@b@}
% \my@mk : 展開不能なマーカトークン.
% ※"ユニーク"ではないので, 専らマクロ引数の区切りトークンとして使う.
\let\my@mk\indent
  • \my@nil は SATySFi の ’a option 型の None に相当するものとして使う。（要するに TeX 言語は静的型がないので安易に nil を使う。）((\my@nil を保護付にしているのは、デバッグ用途で \message や \write で端末表示したときに展開されない方が便利だからである。))
  • \my@mk は単に展開不能な適当なプリミティブを充てている。もちろんこれは「外形上ユニーク」なだけで「意味上ユニーク」ではない。
末尾呼出の条件分岐

完全展開可能なマクロの実装において頻繁に使うやつ。((\my@cond の #1 の区切りを \fi にしているのは、\my@cond をつかった文を外形的に \if-均衡にするため。\def の前に（何もしないはずの）\@gobbletwo\if\if があるのは \my@cond の定義文を \if-均衡にするため。))

%% \my@cond\ifXXX...\fi{<真>}{<偽>}
% \ifXXX... の判定結果により<真>と<偽>の何れかに展開される.
% TeXのif-トークンを末尾呼出で使うための機構.
\@gobbletwo\if\if \def\my@cond#1\fi{%
  #1\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi}

例えば次の 2 つは等価になる。

\ifnum\my@foo=42 \my@good \else \my@bad \fi {54}
⇕
\my@cond\ifnum\my@foo=42\fi{\my@good}{\my@nad}{54}

しかしここで後ろの {54} を \my@good と \my@bad の引数として扱いたい場合、TeX の \if 文のままだと、\else や \fi を先に処分するための展開制御が必要になって非常に厄介である。\xx@cond を使うと \my@good や \my@bad が「末尾呼出」される形になるので展開制御が不要になる。（TeX での末尾呼出の扱いについては過去の記事を参照されたい。）

%% \my@if@empty{<入力>}{<真>}{<偽>}
% 入力が空であるかを判定する.
\def\my@if@empty#1{%
  \my@cond\ifx\my@mt#1\my@mt\fi}

カスタムの条件分岐を定義するのも、末尾呼出形式を前提にすると簡単である。((TeX の \if 文のままではカスタムの条件分岐を作りにくい、というのはよく知られた話である。))

その他
%% \my@iexpanded{<トークン列>}
% edef中で一回展開の結果を置く.
\def\my@iexpanded#1{%
  \unexpanded\expandafter{#1}}

先日の記事でも出てきた、「edef 中でマクロを一回だけ展開させたい」を実現するもの。((無論、展開不能である edef は \greeknumber の展開中に使うのではなく、それを定義するためのコードの途中で利用する。))

継続渡しの機構

継続渡し形式とはなにか

※この小節に出てくるコード（名前空間を“xx@”にした）は \greeknumber の実装コードの一部ではない。以降の “xx@”名前空間のコードも同様。

「継続渡し」というのは、本来は「関数」という概念をもたない TeX 言語において「関数」を表現する方法の一つである。

完全展開可能を前提とした TeX プログラミングで「関数」を表現する場合、通常は「値（のトークン列*1）に先頭完全展開されるマクロ」を用いる。例えば、整数式を（e-TeX の \numexpr を利用して）評価する「関数」は次のように表される。

% \xx@num@eval{<整数式>}
% 整数式の値（の十進表現）に展開される.
\def\xx@num@eval#1{%
  \the\numexpr#1\relax}

これで例えば「\xx@num@eval{1+5*8+1}」を 2 回展開すると「42」が得られる。しかしここで問題なのは「2 回展開する必要がある」ということである。もし「42」を他の「関数」の引数に渡そうとする((この \xx@num@eval の場合は評価せずに元のトークン列のまま別の「関数」に渡しても多くの場合は通用するだろうが、何れにしてもそれは普通の「関数」という概念からは外れる。))と、その途端に山ほどの \expandafter を書く羽目に陥る。多くの「関数」を組み合わせてプログラミングをしようとする*2場合はこの性質は致命的になる。

この欠点を避けるための「関数」の別の表現方法が「継続渡し形式」*3である。この方式では、「関数」を表現するマクロの末尾に引数（「継続」と呼ぶ）を追加する。

\xx@num@eval{<整数式>}{<継続>}

この「継続」は「関数の値を受け取るコード」を表していて、普通は((「継続」には複数トークンからなるトークン列を指定してもよい。「\xx@num@eval{1+5*8+1}{\xx@modulo{100}}」のように別の引数を伴う形もよく使われ、この場合「\xx@modulo{100}{42}」に展開されることになる。))次のようにマクロの制御綴を指定する。

\xx@num@eval{1+5*8+1}{\xx@foo}

そしてこれを展開すると、\xx@num@eval を評価した値である「42」を引数にして \xx@foo が呼び出された形である「\xx@foo{42}」に到達する、というのが「継続渡し形式の関数」の規約である。

継続渡し形式の利点は、「関数」の呼出側での展開制御が不要になることである。実際、先に挙げた例は \xx@num@eval の値を別のマクロ \xx@foo に渡す例とみることもできる。\xx@foo は値そのものの「42」を受け取るので、展開制御をする必要がなくなる。

継続渡し形式するための諸々

以下のマクロは継続渡し形式における恒等関数の実装である。「\my@return{foo}{\xx@cont}」を展開すると「\xx@cont{foo}」となるので確かに継続渡し形式の規約を満たしている。

%% \my@return{<値v>}{<継続>}
% 継続渡しの恒等写像関数.
% ※関数の中で値を返すのに用いる.
\def\my@return#1#2{#2{#1}}

このマクロは継続渡し形式のマクロを実装する際に値を“返す*4”時に利用できる。例えば、今回のプログラムでの \my@num@eval の実装コードは次のようになっている。

%% \my@num@eval{<整数式>}{<継続>}
% 整数式の評価結果を返す.
\def\my@num@eval#1{%
  \expandafter\my@num@eval@a\the\numexpr#1\my@mk}
\def\my@num@eval@a#1\my@mk{\my@return{#1}}

値を“返す”のに専ら \my@return を使うようにすると、当該のマクロのコード中では継続（第 2 引数）を全く扱わなくてよい。

もう一つの例として、「引数のトークン列を一回展開する」という「関数」を継続渡し形式で書くと次のようになる。

%% \my@expand{<トークン列>}{<継続>}
% 一回展開する.
\def\my@expand#1{%
  \expandafter\my@return\expandafter{#1}}

これで継続渡し形式について大体理解できたと思う。ここで一つ問題がある。継続渡し形式の「関数」を呼ぶには必ず「継続」を渡す必要がある。もし \my@num@eval{1+5*8+1} の値の「42」を単に“その場に吐き出す”ようにしたい場合、言い換えると、「完全展開方式の \xx@num@eval の動作が欲しい」場合はどうすればよいか。そういう場合は「完全展開方式の恒等関数」を利用すればよい。((一見すると、「継続」部分を空トークン列にすればよいような気もするが、これだと展開結果は「{42}」と余計な括弧がついてしまう。))

%% \my@get{<値v>}
% 恒等写像のマクロ.
% ※継続渡しの一連の計算の結果を取得するのに用いる.
\def\my@get#1{#1}

例えば、「\my@num@eval{1+5*8+1}{\my@get}」を先頭完全展開すると「42」になる。

※これ以降は、「継続渡し形式に従って『関数』を表すマクロ」のことを単に「関数」と呼ぶことにする。

関数の合成

以下のような関数を次々と適用していく状況を考える。

funD (funC (funB (funA val)))

% SATySFi では次のようにも書ける
funA val |> funB |> funC |> funD

継続渡し形式の TeX コードでは次のように書くことができる。

\xx@funA{val}{\xx@funB}{\xx@funC}{\xx@funD}{<継続>}

もし、「val |> funA |> funB |> funC |> funD」みたいに書きたいのであれば、最初を \my@return（恒等関数）をすればよい。

\my@return{val}{\xx@funA}{\xx@funB}{\xx@funC}{\xx@funD}{<継続>}

そこで次のようなマクロを用意した。

%% \my@compose{<継続のリスト>}{<値>}{<継続>}
% 継続の"合成"みたいなやつ.
\def\my@compose#1#2{\my@return{#2}#1}

この \my@compose を利用すると、先のコードを次のように書ける。

\my@compose{{\xx@funA}{\xx@funB}{\xx@funC}{\xx@funD}}{val}{<継続>}

つまり、「\my@compose{{\xx@funA}{\xx@funB}{\xx@funC}{\xx@funD}}」というトークン列が 4 つの関数を合成した関数として扱える。（引数と継続が後に続くという規約に従っているため。）

補助関数

\greeknumber の実装にあたって、ネタ元のコードと無関係に自分が用意したもの。

%% \my@pack@two{<値x>}{<値y>}{<継続>}
% xとyからなるリストを返す.
\def\my@pack@two#1#2{\my@return{{#1}{#2}}}

%% \my@unpack{<リスト>}{<継続>}
% リストの要素を順に返す多値関数.
\def\my@unpack#1#2{#2#1}
  • ここでは [1; 2; 34; 567] のようなリスト値は {1}{2}{34}{567} のようなトークン列で表すことにする。
  • \my@pack@two{foo}{bar} は {foo}{bar} というリストを返す。*5これは多引数関数の例である。
  • \my@unpack は多値の関数で、リストの要素をそのまま値として返す。（つまり、リストの長さが n なら n 個の返り値をもつ。）((Lua の table.unpack() に相当するもの。これは多値であるだけでなく値の個数が可変になっている。同様に、引数の個数が可変な関数も作ることができる。しかし引数や値が可変な関数は、その個数を知る方法がないので使いにくい。))
値の表現

SATySFi における値を次のようなトークン列で表すことにする。*6

  • 文字列(string)は文字トークン列で表す： `foo` → foo
  • 整数(int)は十進表現の文字トークン列で表す： 42 → 42
    • TeX の実装は内部値で与えられる場合も考慮するが、基本的には、真っ先に \my@num@eval を適用して数字列に転換する。
  • リスト(α list)は「各要素を括弧で囲んで並べたもの」で表す： [2; 8] → {2}{8}
    • ただし（入力については）「単一トークンの要素は囲んでなくてもよい」ことにする。例えば、foo は [`f`;`o`;`o`] という string list 値の表現でもある。
  • タプル(α * β)もリストと同じ方法で表す： (42,`x`) → {42}{x}
  • α option 型は、Some x は x と同一の表現とし、None は \my@nil で表す。
List モジュールの関数

SATySFi 標準の List モジュールの関数のうち \greeknumber の実装に必要なものを実装する。map、mapi、nth、reverse が該当する。

%% \my@map{<関数f>}{<リストxs>}{<継続>}
\def\my@map#1#2{%
  \my@map@a{#1}{}#2\my@b\my@mk}
\def\my@map@a#1#2#3#4\my@mk{%
  \my@cond\ifx\my@b#3\fi{\my@return{#2}}{%else
    #1{#3}{\my@map@b{#1}{#2}{#4}}}}
\def\my@map@b#1#2#3#4{%
  \my@map@a{#1}{#2{#4}}#3\my@mk}

%% \my@mapi{<関数f>}{<リストxs>}{<継続>}
\def\my@mapi#1#2{%
  \my@mapi@a{#1}{}{0}#2\my@b\my@mk}
\def\my@mapi@a#1#2#3#4#5\my@mk{%
  \my@cond\ifx\my@b#4\fi{\my@return{#2}}{%else
    #1{#3}{#4}{\my@num@eval{#3+1}{\my@mapi@b{#1}{#2}{#5}}}}}
\def\my@mapi@b#1#2#3#4#5{%
  \my@mapi@a{#1}{#2{#5}}{#4}#3\my@mk}

%% \my@nth{<整数n>}{<リストxs>}{<継続>}
\def\my@nth#1{%
  \my@num@eval{#1}{\my@nth@a}}
\def\my@nth@a#1#2{%
  \my@nth@b{#1}#2\my@b\my@mk}
\def\my@nth@b#1#2#3\my@mk{%
  \my@cond\ifx\my@b#2\fi{\my@return{\my@nil}}{%else
  \my@cond\ifnum#1=\z@\fi{\my@return{#2}}{%else
    \my@num@eval{#1-1}{\my@nth@c{#3}}}}}
\def\my@nth@c#1#2{%
  \my@nth@b{#2}#1\my@mk}

%% \my@reverse{<リストxs>}{<継続>}
\def\my@reverse#1{%
  \my@reverse@a{}#1\my@b\my@mk}
\def\my@reverse@a#1#2#3\my@mk{%
  \my@cond\ifx\my@b#2\fi{\my@return{#1}}{%else
    \my@reverse@a{{#2}#1}#3\my@mk}}

入口と出口の部分を「継続渡し形式」の規約に合わせればよく、途中の処理については、普通の完全展開可能マクロと同じ要領で実装することになる。

ユーティリティー関数

以上でようやく準備が整ったので、ここからは元ネタの記事の方針に従って、\greeknumber を実装することになる。

まずは元記事の「ユーティリティー関数」の節にある関数。自明に対応がつくように、名前も引数の順番もそのままにしている。

%% \my@apply@non@empty{<関数f>}{<値s>}{<継続>}
\def\my@apply@non@empty#1#2{%
  \my@if@empty{#2}{\my@return{}}{#1{#2}}}

%% \my@zip{<リストxs>}{<リストys>}{<継続>}
\def\my@zip#1#2{%
  \my@zip@a#1\my@b\my@mk#2\my@b\my@mk{}}
\def\my@zip@a#1#2\my@mk#3#4\my@mk#5{%
  \my@cond\ifx\my@b#1\fi{\my@return{#5}}{%else
  \my@cond\ifx\my@b#3\fi{\my@return{#5}}{%else
    \my@zip@a#2\my@mk#4\my@mk{#5{{#1}{#3}}}}}}

%% \my@split@by{<整数n>}{<リストys>}{<継続>}
\def\my@split@by#1{%
  \my@num@eval{#1}{\my@split@by@a}}
\def\my@split@by@a#1#2{%
  \my@split@by@b{#1}{}{}{#1}#2\my@b\my@mk}
\def\my@split@by@b#1#2#3#4#5#6\my@mk{%
  \my@cond\ifx\my@b#5\fi{\my@return{#2{#3}}}{%else
  \my@cond\ifnum#4=\z@\fi{\my@split@by@b{#1}{#2{#3}}{}{#1}{#5}#6\my@mk}{%
    \my@num@eval{#4-1}{\my@split@by@c{#1}{#2}{#3}{#5}{#6}}}}}
\def\my@split@by@c#1#2#3#4#5#6{%
  \my@split@by@b{#1}{#2}{#3{#4}}{#6}#5\my@mk}

%% \my@repeat{<整数n>}{<リストxs>}{<継続>}
\def\my@repeat#1{%
  \my@num@eval{#1}{\my@repeat@a}}
\def\my@repeat@a#1#2{%
  \my@repeat@b{#1}{#2}{}}
\def\my@repeat@b#1#2#3{%
  \my@cond\ifnum#1=\z@\fi{\my@return{#3}}{%else
    \my@num@eval{#1-1}{\my@repeat@c{#2}{#3}}}}
\def\my@repeat@c#1#2#3{%
  \my@repeat@b{#3}{#1}{#2#1}}

%% \my@concat@maybe{<リストxs>}{<継続>}
\def\my@concat@maybe#1{%
  \my@concat@maybe@a{}#1\my@b\my@mk}
\def\my@concat@maybe@a#1#2#3\my@mk{%
  \my@cond\ifx\my@b#2\fi{\my@return{#1}}{%else
  \my@cond\ifx\my@nil#2\fi{\my@concat@maybe@a{#1}#3\my@mk}{%else
    \my@concat@maybe@a{#1{#2}}#3\my@mk}}}

%% \my@intersparse{<値c>}{<リストxs>}{<継続>}
\def\my@intersparse#1#2{%
  \my@if@empty{#2}{\my@return{}}{%else
    \my@intersparse@a{#1}#2\my@b\my@mk}}
\def\my@intersparse@a#1#2{%
  \my@intersparse@b{#1}{{#2}}}
\def\my@intersparse@b#1#2#3#4\my@mk{%
  \my@cond\ifx\my@b#3\fi{\my@return{#2}}{%else
    \my@intersparse@b{#1}{#2{#1}{#3}}#4\my@mk}}
  • 先述の値の表現の規約に従うと、explode-into-digits は恒等関数になるので省いた。
  • max-length は今回の \greeknumber の範囲では不要で、また完全に実装する場合でも不要になる可能性があるので取りあえず保留。

文字列に関する扱いの差異を吸収するため、以下の関数を用意する。例えば「\my@implode{{f}{o}{o}}」は「foo」を返す.

%% \my@implode{<リストxs>}{<継続>}
% リストの各々の文字列を連接した文字列.
\def\my@implode#1{%
  \my@implode@a{}#1\my@b\my@mk}
\def\my@implode@a#1#2#3\my@mk{%
  \my@cond\ifx\my@b#2\fi{\my@return{#1}}{%else
    \my@implode@a{#1#2}#3\my@mk}}

1,0000 未満の表記

続いて「1,0000 未満の表記」節にある定義。

文字の定義。

%% 定数
\def\my@s@gnls{͵}
\def\my@ones{{}{α}{β}{γ}{δ}{ε}{ϛ}{ζ}{η}{θ}}
\def\my@tens{{}{ι}{κ}{λ}{μ}{ν}{ξ}{ο}{π}{ϟ}}
\def\my@hundreds{{}{ρ}{σ}{τ}{υ}{φ}{χ}{ψ}{ω}{ϡ}}

%% \my@thousands
\def\my@tmpa#1{\my@expand{\my@s@gnls#1}}
\my@expand{\my@ones}{\my@map{\my@apply@non@empty{\my@tmpa}}}{%
  \def\my@thousands}

%% \my@number@symbols
\edef\my@number@symbols{%
  {\my@iexpanded{\my@ones}}{\my@iexpanded{\my@tens}}%
  {\my@iexpanded{\my@hundreds}}{\my@iexpanded{\my@thousands}}}
  • \my@thousands と \my@number@symbols の定義には多少の処理を行うことになるが、ここは完全展開可能である必要はない。
  • \my@thousands の定義では最後の継続を \def\my@thousands にしている。この値に {<結果の値>} を付けて呼び出されるから、これで所望の動作になっている。
  • \my@number@symbols の定義は普通の TeX コード;-)

1,0000 未満の数を変換。

%% \my@simple@digits{<リストxs>}{<継続>}
\def\my@simple@digits#1{%
  \my@expand{\my@number@symbols}{\my@zip{#1}}{\my@reverse}{%
    \my@map{\my@compose{{\my@unpack}{\my@nth}}}}{\my@implode}}
  • 元のコードの「fun (d, ss) -> List.nth d ss` |> Option.from `!`」にあたる関数は my@compose{{\my@unpack}{\my@nth} としている。タプルはリストと同じく {<d>}{<ss>} で表されているので、\my@unpack で 2 つの値に分解して、それを \my@nth の引数に渡している。ここで実際に nth の値が \my@nil(None) になることはないので、option の処理は省略した。

\greeknumber の実装

元記事ではこの後に万以上の数に対応するためのコードが続くが、本記事ではそこは対象外になる。

元記事の「1,0000 未満の表記」まで読んだ段階を考えると、本記事の \greeknumber に相当する SATySFi のコマンドは、次のコードで実装できる。((元記事でも「比較」という節にそれに相当する話があるのだけど、そこで挙げられている \greeknumber の実装は色々とアレである。))

let s-keraia = `ʹ`

let-inline \greeknumber n =
  let s = n |> explode-into-digits |> List.reverse |> simple-digits
  in embed-string (s ^ s-keraia)

これに相当する TeX 言語での実装は以下のようになる。

\def\my@s@keraia{ʹ}

%%<*> \greeknumber{<整数n>}
\newcommand*{\greeknumber}[1]{%
  \my@num@eval{#1}{\my@reverse}{\my@simple@digits}{%
    \my@greeknumber@a}{\my@get}}
\def\my@greeknumber@a#1{%
  \my@expand{\my@s@keraia}{\my@pack@two{#1}}{\my@implode}}
  • \my@greeknumber@a は後ろに \my@s@keraia を付ける関数。
  • \greeknumber は結果の値のトークン列に展開される必要があるため、最後の継続に\my@get を指定している。

無事に実装が完了したので、テスト用のコードを書いてみる。

% (文書本体中で)
\newcommand*{\Test}[1]{%
  #1 = \greeknumber{#1}}
\begin{itemize}
\item\Test{1}
\item\Test{2}
\item\Test{3}
\item\Test{5}
\item\Test{8}
\item\Test{13}
\item\Test{21}
\item\Test{34}
\item\Test{55}
\item\Test{89}
\item\Test{144}
\item\Test{233}
\item\Test{377}
\item\Test{610}
\item\Test{987}
\item\Test{1597}
\item\Test{2584}
\item\Test{4181}
\item\Test{6765}
\end{itemize}

完璧！

※完全なソースを以下の場所に置きました。

まとめ

やっぱり TeX 言語は超絶アレなので、関数型プログラミングをしたい人は是非とも SATySFi を使いましょう！

（続けばいいね）

*1:完全展開可能を前提とする場合、基本的にデータ型は「トークン列」しかないことに注意。全ての「値」は何らかのトークン列として表現する必要がある。

*2:もしかして：関数型プログラミング

*3:ここでいう「継続渡し」が、一般の言語における「継続渡し（continuation passing）」と対応する概念に本当になっているのかは、深く考えてはいけない;-)

*4:だから“return”という名前である。

*5:単体ではほとんど存在意義がないようにみえるが、他の「継続渡し形式の関数」と組み合わせると有用になる場合がある。

*6:TeX 言語に静的型なんて存在しない！