「数学ソフトウェアの作り方」を読んだ

「数学ソフトウェアの作り方」という本が出たので簡単にレビューする。

目次

私の興味は数学とプログラミングの重なる部分にある。数学ソフトウェアを作ることにも関心があり、過去に「複素関数を可視化するWebアプリ」を作ったり、既存のソフトウェアであるwxMaximaにパッチを投げたりしてきた。そんな私としてはこの本は是非読んでおかなければならないと思われたので読んだ。

どういう本なのか

乱暴に一言で言うと、C言語／Unixのツール群を用いて多項式の計算ができるシステムを作る本、となるだろうか。

目次は出版社のページにも書いてあるがここでも章の並びを再掲しておく：

  • 第1章 C言語再論
  • 第2章 多項式の処理と例題システム
  • 第3章 ツール，ビルドシステム，ライブラリ
  • 第4章 Webプラットフォームへの対応

第1章 C言語再論

第1章はC言語……というよりは今日の電子計算機の低レベルな話をC言語を通して概説している。C言語そのものはほかの本である程度勉強済みであることが想定される。

読者は数学に関心があることが期待されるので、「C言語の int 型， unsigned int 型は数学での整数ではなく」決まった大きさを持ち、mod \(2^m\)で計算される、という風な説明がされる。後述するようにこの説明はC言語の符号付き整数に関しては厳密には正しくないが……（符号なし整数なら問題ない）。

数学関係者向けにまとめると， char や int は \(\mathbf{Z}/2^m\mathbf{Z}\) で考えよ！ということになる．

8ページ

1.6ではCで書いた簡単なコード（再帰による階乗計算）の機械語（Intelニーモニック）を読んで関数やローカル変数の実現の仕組みを扱う。「低レベルプログラミング」か？ただし「最新の64bit CPUでの出力はややこしい」のでi386向けのコードでやっている。

1.6の最後の方ではバイナリを書き換えて階乗関数への引数（整数リテラル）を書き換えたり、printf のフォーマット文字列を書き換えたりしている。結構硬派だ。

1.7では「数学における整数」を実現するために簡単な多倍長演算みたいなことをやる。と言っても実装するのは足し算くらいで、掛け算は演習問題になっている。また、「多倍長整数計算の実装のもっとも優れたライブラリ」としてGMPが紹介されている。この本はアルゴリズムについての本ではないので、多倍長演算を真面目に実装したい場合はKnuthの本（TAoCP vol 2）などを読むべきだろう。

【10月27日 追記】GMPの詳しい使い方については「多倍長精度数値計算」という本が出ているので紹介しておく。

メモリ確保に関してはfreeを生真面目に呼ぶかどうかの話をして、GCにも触れている。コード1.5では多倍長整数のメモリ領域はfreeしないことにしたようだ。

1.8ではgnuplotを使って（C言語でgnuplot用のテキストファイルを生成するプログラムを書いて）\((\sin x)/x\) のグラフを描画している。

1.12ではgitの使い方を扱っている。いきなりGitHubでやらずに、リモートのマシンからSSHで取ってくる一般のやり方を説明しているのはいいね（一般人がSSHでアクセスできるリモートのマシンを持っているかは知らないが）。

第2章 多項式の処理と例題システム

第2章では多変数多項式を扱うプログラム（電卓みたいな感じ）を実際にC言語/GMP/yacc/Boehm GCで作る。

係数環としては整数環 \(\mathbf{Z}\), 有理数体 \(\mathbf{Q}\), 有限素体 \(\mathbf{F}_p\) を扱えるようになっている。

私事だが、グレブナー基底の勉強が途中で止まっている。いつかちゃんとグレブナー基底の勉強をしてこの章のプログラムを自分の手で実装したい。

第3章 ツール，ビルドシステム，ライブラリ

第3章はUnix入門である。3.1ではシェルの説明がある。コマンドライン引数やリダイレクトの説明に関しては、C言語やシステムコールへの言及もある。

かなり丁寧に説明されているので、Unix入門には良いのではないか。

3.2ではmakeが説明される。有向グラフ！最後にmakeの方言（gmakeとかpmake）の話がある。

3.3は可搬なMakefileを書くのが難しいという話から、Autotoolsを導入する。

Autotoolsの使い方が日本語で説明される貴重な本ではないだろうか。私が知らないだけの可能性は高いが（わざわざautotoolsの使い方が書かれた本を探そうとは思わないため）。

3.4はyacc (bison)が解説される。

3.5はGMPのインストール方法と簡単な使い方を扱う。mpz_t の変数を参照渡しする際に & を使う必要がない仕組みに触れている。

3.6はBoehm GCについて。インストール方法を扱う。

第4章 Webプラットフォームへの対応

第4章は「Webプラットフォームへの対応」と題して、C言語で書かれたプログラム（第2章で作ったものも含む）をEmscriptenを使用してHTML/JavaScriptから呼び出す。

4.2ではWSL 2のセットアップ方法がスクショ付きで載っている。丁寧だ。

4.3では例として、最大公約数を計算するC言語のプログラムをEmscriptenでコンパイルし、HTML/JavaScriptから呼び出している。

4.4では多項式電卓をWebアプリ化する。まずGMPをEmscriptenでビルドする。libgc (Boehm GC) は執筆時点（2021年9月現在）でWebAssembly対応が不完全で動作が不安定なので不使用とする。それから標準入出力の代わりに文字列を受け渡すようにする。

GMPのEmscriptenのビルドは、私の環境（Apple Silicon Mac）ではconfigure時に追加で HOST_CC=/usr/bin/clang を渡す必要があった。

多項式電卓は最終的にMathJaxと連携させて出力を美しく表示することができるようにする。MathJax（あるいはKaTeX）と連携しやすいのはWeb技術の良いところだろう。

4.4.6では「Webアプリ開発日記」として開発時のトラブルの例が紹介されている。整数型周りとGC周りでトラブルがあったようだ。トラブルも赤裸々に、という姿勢は好感が持てる。

4.5は筆者のGUI遍歴となっている。生き残るフレームワークを見繕うのは難しいものだ。

読み終わって

全体を読んでみた感じとしては、大学の講義っぽい。数学科の学生に向けて計算機を基礎から教える。私の出身の東大数学科には「計算数学」という計算機に関する講義（実習）があったが、ああいう雰囲気を感じた。

なお、この本が属するシリーズの続刊テーマとして「紙と計算機による数学入門」「紙と数学による計算機入門」「Proof Checker活用法」「JavaScriptによる数式処理」が予定されているようだ。JavaScriptは型がなくて辛いのでせめてTypeScriptにならんかな……。

細かい指摘

この本を読んで気になった部分をメモしておく。

1.4 2進数，16進数，intの正体

著者は char 型が符号付きであることを仮定しているようだが、C言語的には char は符号付き、符号なしのいずれでも良いことになっている（実装依存）。実際、AArch64 Linuxでは char は符号なしである（AArch64の標準呼び出し規約でそう定められている。一方Appleはそれを上書きして char は符号付きとしている。）。GCCの場合は -fsigned-char, -funsigned-char オプションでその辺を上書きできるようになっているようだ。

なので、符号付きの char に言及したい場合は signed char と書く必要がある。

C言語の固定長整数が（足し算と掛け算について）mod計算されるというのは、符号なし整数に関しては正しいが、符号付き整数に関してはオーバーフローは未定義動作なので、正しくない。

例えば、次のコード

int main()
{
    return 65535 * 65535;
}

を int が32ビットな環境で実行すると未定義動作となる。実際、 clang -fsanitize=undefined overflow-test.c でコンパイルして実行してやると

overflow-test.c:3:18: runtime error: signed integer overflow: 65535 * 65535 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior overflow-test.c:3:18 in

と怒られる（65535の後ろに u をつけて型を符号なし整数にすると怒られなくなる）。

（本当は符号付き整数のオーバーフローがUBなことを利用してコンパイラーがえげつない最適化を行う例を出したかったが、まあそのうち。）

【2023年3月5日 追記】符号付き整数のオーバーフローがUBなことを利用してコンパイラーが最適化を行う例を以下の記事に書いた：

【追記終わり】

C言語での負の整数の表し方について。C17の段階では2の補数表現以外の負の数の表し方（1の補数、符号と絶対値）は切り捨てられていないけどC23では2の補数表現のみになるので、まあいいでしょう。

1.7 整数の計算

macOSでGMPを使うのにHomebrewを使って入れているが、HomebrewはIntel MacとApple Silicon Macでデフォルトのインストール先が異なる。 /opt/homebrew に入るのはApple Silicon Mac上であってIntel Macではデフォルトでは /usr/local にインストールされる。

1.9 構造体とその応用

構造体の最後のメンバーを長さ1の配列にする「ちょっとトリッキーな書き方」が紹介されている：

struct bignum {
  int len;
  int u[1];
};

が、現代のC言語的にはflexible array memberを使うべきだろう：

struct bignum {
  int len;
  int u[];
};

こちらを使えば「malloc時に要素数を1減らす」必要がなくなる。あと長さ1の配列に対する境界外アクセスに対するUBがなくなるらしい。

1.13 例題ーー復習と第2, 3, 4章への準備

最初から UINT64_C なり PRId64 なりを使ってくれ……。

2.1 多項式の計算機上での表現方法

64ページ：「64ビット整数を表す型は，環境により異なるので，以下のように明示的に LONG, ULONG を定義しておく．

#include <stdint.h>

typedef int64_t LONG; // 符号つき64ビット整数
typedef uint64_t ULONG; // 符号なし64ビット整数

」とあるが、typedef せずに直接 (u)int64_t を使うべきでは？こうなった原因は容易に想像できるが……（おそらく最初はC99以前の癖が抜けずに (unsigned) long か (unsigned) long long のtypedefを使っていた）。

3.1 シェル

138ページの脚注7：現代のWindowsではコマンドライン文字列は内部的にはワイド文字列で、マルチバイト文字列は適宜変換されてるだけのはずなので、ここで言及するのは GetCommandLineW の方（〜Aではなく）が良いかと思った。

4.3 CLIからWebプラットフォームへの移植

「モジュール化」のところのコード4.3だが、 fetch("gcd.wasm") した結果を加工した挙句 .then(binary => Module()) で捨ててしまうのは何かおかしい。Emscriptenには詳しくないのでどうするのが正しいのかはよくわからないが、本に載っているコードは絶対におかしい。もちろん著者が動作確認しないコードが載るわけがないので動作はするのだが。

手元で試した感じ、 -s MODULARIZE=1 でビルドしたコードはグローバル変数として Module を生やしており、Module() の呼び出しは Promise を返すようになるようだ。そして、自分で fetch("gcd.wasm") をしなくてもいきなり

Module().then(mod => {
    ...
});

でよさそう。

ブラウザー環境で「複数の .wasm ファイルを混在」させるためには、ビルド時に -s MODULARIZE=1 の他に -s 'EXPORT_NAME="createGCDModule"' という風に個々の EXPORT_NAME を指定してグローバル変数の名前が Module 以外になるようにする必要がありそうだ。Node.jsの場合は EXPORT_NAME を指定しなくても良さそう。

参考：

その他、細かいことだが、<label> を使うなら for 属性を使うか <input> とネストさせるかして <input> と紐づけるべきだろう。

4.4 多項式電卓のWebアプリ化

Cで書いた関数とJavaScriptの間で文字列を受け渡しするのに malloc/free/stringToUTF8/UTF8ToString を手動で呼び出しているが、ccallの型指定で 'number' の代わりに 'string' を指定して済ませることもできる。

コード4.13のJavaScriptコードの改変例：

document.getElementById('run').addEventListener('click', () => {
  var input_text = document.getElementById('input');
  var result = Module.ccall('yyparse_str', 'string', ['string'], [input_text.value + ";"]);
  document.getElementById('result').innerHTML = result;
});

あえて低レベルな方法（基本に則った方法）を使っているというのならそれ以上言うことは何もないが……。

誤植の指摘

6ページの脚注7：unsigend → unsigned

65ページ、 Coef 型（union coef）のメンバー q の型が mpz_ptr となっているが、mpq_ptr が正しいと思われる。

そもそも2022年にC言語を使うのはどうなんだ？

この本はC言語で数学ソフトウェアを作るのであれば非常にためになる本だと思う。では、2022年に数学ソフトウェアを作るにあたって、C言語という選択はそもそも適切と言えるのか？

著者の言い分は「1.2 なぜC言語」にある。短いので全文引用してしまおう：

計算機ソフトウェア全体の中でその基盤となってるシステムはほぼC言語とその派生言語で書かれている．数学ソフトウェアの基盤となっているシステムも同様である．C言語は50年弱使われ続けている古典であり，またさまざまな言語に影響を与えているので，C言語を習得すると他の言語の習得もより容易になるし，過度の抽象化がないので，計算機のアーキテクチャを理解してプログラミングができるようになる．さらにIEEEの人気言語ランキングでも常に上位である．

1.2 なぜC言語

まず、既存のソフトウェアがC言語で書かれているのは仕方ないとしても、新しい数学ソフトウェアは新世代の言語で書かれるべきなのではないかと私は思う。

「さまざまな言語に影響を与えている」言語はC言語以外にも色々ある。最近の言語はLisp, ML, Haskellなどの影響を受けて、洗練されていることが多い。

この本でやっているように計算機の仕組みを扱いたいのであればC言語という選択には理がある。しかし、数学ソフトウェアを作りたい読者が計算機の低レベルな部分をどれだけ知る必要があるのか、私には確信が持てない。計算機の低レベルな部分は「低レベルプログラミング」のような本に任せてもよかったのではないか（それだと本格的すぎるかな）。

C言語を使うことによる具体的なデメリットと言えば、やはりメモリ管理が煩雑になることだろう。この本ではGCを使っているが、それだったら最初からGC付きの言語を使えば良いのでは、と思ってしまう。挙句Web移植時の障害になっているし……。

じゃあどんな言語が良いのか、という話になる。私が数学ソフトウェアを書く上での好みは

  • メモリ安全（例：GC）
  • 強い静的型付け
  • 多倍長整数が組み込まれている
    • GMPを明示的に扱える方が良いんだ、という用途もあるかもしれないので、必須ではない。

を満たす言語だ。例えば、「週刊 代数的実数を作る」はHaskellで実装した。今はLunarMLを開発中なので新しく何か作るとしたらStandard MLを採用するかもしれない。

まあHaskellはモナドが難しいしStandard MLはエコシステムが壊滅的なので万人におすすめできる言語ではない。結局、書く人の好みということになるだろう。そうするとC言語でも仕方がないということに……むむむ。

なお、プログラミング言語処理系の高速なVMを書く場合はC言語は有力な選択肢である。が、この本での用途はそういう感じではない。

Spread the love