これは「SATySFi Advent Caleandar 2022」の10日目の記事です。
（9日目は bd_gfngfn さんです。）

気が付けば、SATySFi Advent Calendarも今年で5回目になりました。SATySFiが“Better LaTeX”としての実力を発揮する場面も増えているように見受けられます。

LaTeXを使う目的は様々なものがありますが、その中で特に重要だと思われるのが「10万ページの文書を作成する」というものです_（えっ）

dvipdfmの最大ページ数（TeX Forum）

そこで当然の帰結として_（えっ）、「SATySFiで10万ページの文書を作成することは可能か」について調べてみることになりました

SATySFiで10万ページの文書を作れなそうな話

以下で載せるソースファイルsum*.satyはSATySFiの「テキスト出力モード」を用いて以下のようなコマンドでコンパイルすることが想定されています。
satysfi --text-mode plain -o out.txt sum1.saty
ここでout.txtは出力ファイル名で、記事中で「出力結果」として示されているのはこのファイルの内容です。

10万ページの文書を作れるかを試したい場合、何か「単純なページを出力する作業」を10万回繰り返したくなります。ところがSATySFiでそれを実行する場合に問題になるのがスタックオーバーフローです。

ご存じの通り、SATySFi（のような関数型言語）で繰り返しの処理を実現するには函数の再帰呼出が使われます。例えば、1から100までの整数の総和（つまり1 + 2 + … + 100の値）を求める場合は次のようなプログラムを書くことになります。

sum1.saty

% sum n は"1からnまでの整数の総和".
let-rec sum n =
  if n <= 0 then 0 else n + sum (n - 1)
in
% テキスト出力モードを前提にするので,
% 文字列(string型)を返せばそれが出力になる.
arabic (sum 100)

もちろんこのプログラムは期待通り（テキスト出力モードで）動作します。

出力結果

ここで繰り返しを10万回に変えてみます。

sum2.saty

let-rec sum n =
  if n <= 0 then 0 else n + sum (n - 1)
in
% sumの引数を100000に変更
arabic (sum 100000)

これを実行しようとすると、スタックオーバーフローで異常終了してしまいます。

 ---- ---- ---- ----
  target file: 'out.txt'
  dump file: 'sum2.satysfi-aux' (will be created)
  parsing 'sum2.saty' ...
 ---- ---- ---- ----
……(略)……
  evaluating texts ...
Uncaught exception:

  Stack overflow

Raised by primitive operation at Main__Evaluator.select_pattern in file "src/frontend/evaluator.cppo.ml", line 817, characters 13-44
Called from Main__Evaluator.reduce_beta in file "src/frontend/evaluator.cppo.ml", line 69, characters 13-69
……(略)……

ここで「末尾再帰にすればスタックオーバーフローは防げるのでは？」と思った人もいるかもしれません。しかし、現状のSATySFiでは、次のように末尾再帰の形で書いてもやはりスタックオーバーフローが発生してしまいます。（恐らく末尾呼出最適化の機能がないのでしょう。）

sum3.saty

let sum n =
  % 末尾再帰の函数
  let-rec iter k r =
    if k > n then r else iter (k + 1) (r + k)
  in
  iter 1 0
in
arabic (sum 100000)

SATySFiで10万ページの文書をやっぱり作れる話

とはいっても「10万ページの文書を作る」のに必ずしも「10万回のループを実行する」必要はないはずです。例えば「10ページ分の分量をもつブロックボックスを1万回出力する」でも目的を果たせます。

あるいは、論理的には「10万回のループを実行する」であるとしても、次のように「1回の函数の呼出の中で自身を2回再帰的に呼び出す」形にすれば、再帰呼出の深さを対数のオーダーに減らすことができます。

sum4.saty

let sum n =
  % part s e は"sからeまでの整数の総和".
  let-rec part s e =
    if s >= e then s
    else % 前半と後半に分割する
      let m = s + (e - s) / 2 in
      (part s m) + (part (m + 1) e)
  in
  part 1 n
in
arabic (sum 100000)

実際、このプログラムであれば、現状のSATySFiで無事に実行することができました

出力結果

5000050000

つまり「SATySFiプログラム実行における深い再帰によるスタックオーバーフロー」は実装の工夫により回避できるわけです。

SATySFiで10万ページの文書を作る話

スタックオーバーフローが回避可能だとすると、後に残る問題は「10万ページ分のデータをメモリに保持できるか」になりそうです。10万ページの文書の作成が可能だったとしてその際の処理時間も気になるところです。

そこで実際に「極めて単純な内容をもつ10万ページの文書」を作って調べてみることにします。以下のような文書を作ってみます。

用紙サイズは100pt×100pt。
nページ目の内容は「紙の中央にnの値を大きな文字（フォントサイズ24pt）で書いたもの」とする。

例えば42ページ目の内容は以下のようになるはずです。

これ以降は「テキスト出力モード」ではなく通常の「PDF出力モード」のソースコードを扱います。

まずは各ページの内容（ブロックボックス）を作成する函数を実装してみます。

% text-box-board: length -> length -> inline-boxes
% w×hの矩形の中央にibを配置したボックス.
let text-box-board w h ib =
  let (tw, th, _) = get-natural-metrics ib in
  let gtxt = draw-text ((w -' tw) *' 0.5, (h -' th) *' 0.5) ib in
  inline-graphics w h 0pt (fun p -> [shift-graphics p gtxt])

% text-board: context -> length -> length -> string -> length -> string -> inline-boxes
% w×hの矩形の中央に, フォント名fnameとサイズfsizeを指定して文字列strを書いたボックス.
let text-board ctx w h fname fsize str =
  let ctx = ctx |> (set-font-size fsize)
    |> (set-font Latin (fname, 1., 0.)) in
  let ib = read-inline ctx (embed-string str) in
  text-box-board w h ib

% number-board: context -> int -> block-boxes
% 整数nを書いたページを表すブロックボックス.
let number-board ctx n =
  let ib = text-board ctx 100pt 100pt `Junicode` 24pt (arabic n) in
  line-break true true ctx (ib ++ inline-fil)

これで例えば、number-board 42は先の画像に示したような100pt×100ptのブロックボックスになります。

次に、“文書データを作る函数”（つまりdocument値を返す函数）を実装します。用紙サイズが100pt×100ptなので、以下のようになります。

数式（math値）は全く使わないので、get-initial-contextの引数に渡す“数式ハンドラ”の命令はダミー実装にしています。

% \dummy-math: [math] inline-cmd
% ダミーの数式ハンドラ.
let-inline ctx \dummy-math _ = inline-nil

% make-document: (ctx -> inline-boxes) -> document
% 文書本体の内容bodyから文書を作る.
let make-document body =
  let ctx = get-initial-context 100pt (command \dummy-math) in
  page-break (UserDefinedPaper (100pt, 100pt))
    (fun _ -> (| 
      text-origin = (0pt, 0pt); text-height = 100pt;
    |))
    (fun _ -> (| 
      header-origin = (0pt, 0pt); header-content = block-nil;
      footer-origin = (0pt, 0pt); footer-content = block-nil;
    |))
    (body ctx)

残っている作業はこの2つの実装を“つなぐ”ことです。make-documeuntには“文書の内容全体”のブロックボックス列（正確には context → block-boxes の函数）を渡す必要がありますが、この「10万ページの内容のブロックボックス列」はどうすれば得られるでしょうか？

各ページの内容のボックスがnumber-board函数で生成され、かつそのボックスの前後で改ページ可能にしている（line-breakの最初の2引数にtrueを指定している）ため、結局、10万個のボックスを+++で単純に連結したものを“文書の内容全体”とすればよいことがわかります。具体的に式で書くと以下の通りです。

number-board ctx 1 +++ number-board ctx 2 +++ …… +++ number-board ctx 100000

この式は記事の最初に挙げた「1からnまでの整数の総和」（1 + 2 + … + n）と同じ形をもっています。なので、そこで説明した「再帰の深さを減らす」テクニックを適用することができて、それによりスタックオーバーフローを起こすことなく処理ができます。

% make-body: context -> int -> block-boxes
% ページ数がnのときの"文書全体の内容".
let make-body ctx n =
  let-rec part s e =
    % 単なるsでなくnumber-boardを適用する
    if s >= e then number-board ctx s
    else
      let m = s + (e - s) / 2 in
      % 演算子は'+++'
      (part s m) +++ (part (m + 1) e)
  in
  part 1 n

make-documentに渡すのは context → block-boxes 型の値なので、10万ページの文書を作りたい場合はfun ctx -> (make-body ctx 100000)を渡せばいいことになります。

in
% 文書を表すdocument値
make-document (fun ctx -> (make-body ctx 100000))

これで「10万ページの文書を出力するプログラム」は完成です。全体のプログラム（文書ソースファイル）をGistに置きました。

count100k.saty（Gist／zr-tex8r）

このファイルを実際にSATySFiでコンパイルすると……。

>satyra count100k.saty
 ---- ---- ---- ----
  target file: 'count100k.pdf'
  dump file: 'count100k.satysfi-aux' (will be created)
  parsing 'count100k.saty' ...
 ---- ---- ---- ----
  type checking 'count100k.saty' ...
  type check passed. (document)
  preprocessing 'count100k.saty' ...
 ---- ---- ---- ----
  evaluating texts ...
  evaluation done.
 ---- ---- ---- ----
  breaking contents into pages ...
  all cross references were solved.
 ---- ---- ---- ----
  embedding fonts ...
 ---- ---- ---- ----
  writing pages ...
 ---- ---- ---- ----
  output written on 'count100k.pdf'.

このように正常に終了し、約33MBのPDFファイルcount100k.pdfが出力されました。（ちなみに手許のマシンでの処理時間は約25秒でした。）

（↑画像は82828ページ目）

ちゃんと10万ページありますね！

SATySFiで10万ページの文書をもっと作る話

首尾よく10万ページの文書を作ることに成功したので、今度は、大昔に作ったLaTeXネタをSATySFiに“移植”してみました。

例の10万ページのアレ（マクロツイーター）

この記事で紹介しているbxhanoiというLaTeXパッケージは「『ハノイの塔』のパズルを解く手順について、1ステップごとに1ページを使って状況を出力する」という機能をもちます。

The Tower of Hanoi with graphics, in LaTeX（Gist／zr-tex8r）

「ハノイの塔」の最短の手数は円盤がn枚のときに 2ⁿ − 1 手となります。初期状態（0手目）が最初のページに出力されるため、与えられたnに対してちょうど 2ⁿ ページの文書が出力されます。

今回はこのbxhanoiをSATySFiに移植しました。

The Tower of Hanoi with graphics, in SATySFi（Gist／zr-tex8r）

hanoiパッケージ（文書クラス）を読み込むと、以下の函数が利用できます。

Hanoi.document: int → document
Hanoi.document n は円盤がn枚のときの「ハノイの塔」を解く手順を1ステップごとに1ページを使って出力した文書。

このhanoiパッケージを使って、円盤が17枚の「ハノイの塔」の手順を出力してみます。2¹⁷ = 131072 なので、131072ページからなる文書が出力されるはずです。

hanoi17.saty

@import: hanoi
Hanoi.document 17

実際にコンパイルすると、以下のような文書が得られました。ファイルサイズは約119MB、手許のマシンでの実行時間は約2分30秒でした。

（↑画像は100000ページ目、つまり99999手目）

まとめ

SATySFiで10万ページの文書は作れます！皆さんもドンドン10万ページの文書を作っていきましょう！いや、別に10万ページ未満の文書でもいいので、皆さんもっとサティスファイしましょう！