はじめに
- 本記事全体に関する注意書き
- この記事の問い
- 演算が満たすべき法則とは何か
- １. 反例を探す ── QuickCheck と quickcheck-classes
- ２. 型の等式を表す ── Data.Type.Equality
- ３. 型に「検査済み」の印を付ける ── Ghosts of Departed Proofs
- 実際に書くと、こうなります
- type role は何をしているのか
- だから、検査済みとして扱える
- 何が保証されて、何が保証されないのか
- 論文の記述
- ４. 仕様付きコードを静的に検証する ── LiquidHaskell
- ４つに共通すること
- 演算の性質も『型』として表現できる言語がある
- 予備知識は要りません
この記事のメッセージ
TL;DR
想定読者
この記事を読む価値
この記事の全体像
第１部 ── Haskell には、何があるのか
- 対話に出てきた事実を整理します
第２部 ── 群・環・体とは何か
- 出発点 ── 演算とは何か
- 結合律
- 単位元
- 逆元
- ここまでを組み合わせる
- 具体例で確かめます
- 環 ── 演算が２つある構造
- 可換性
- 分配律
- 環の例
- 非可換 ── 順番を変えると答えが変わる
- 体 ── 割り算ができる環
- 構造の一覧
- ここまでを並べてみる
第３部 ── 障害１コヒーレンス
- 何が問題なのか
- 理由 ── コヒーレンス
- 回避策 ── newtype で包む
- なぜ、これが根本的な解決ではないのか
- 他の言語はどうしているか
- Lean 4
- では、どちらが使われるのか
- 何が起きているのか
- Lean は、どちらが適切かを判断するのか
- Lean 4 は、どう探索しているのか
- 優先度の指定
- 代償
- Mathlib はどうしているか
第４部 ── 障害２法則を検査できない
- Monoid は何を要求しているか
- 検査されない
- 何が起きるか
- 実際にどう対処しているか
- 方法１ ── 等式を型として表現する
- 方法２ ── ファントム型に証明を住まわせる
- 方法３ ── 篩型で検証する
- では、なぜ本記事は「できない」と述べるのか
- これは代数に限った話ではありません
- Idris では、法則を要求できます
- 等式が、型である
- 実際に書いてみる
- 引き算で書こうとすると
- これは標準ライブラリではありません
- なぜ標準にしないのか
- そして、より深い問題があります
- トレードオフ
- ここまでを整理します
- 対話 ── 書かれていないのか、守られていないのか
第５部 ── 障害３階層の設計が一意でない
- なぜ、法則を書けないと階層が難しくなるのか
- 法則がないと、階層はどうなるか
- だから、複数の設計が並立します
- どこで枝分かれさせるか
- 加法と乗法の扱い
- 実際の階層を比べる
- なぜ細かく分けるのか
- 階層の設計は、Lean でも問題だった
次は、外部のライブラリがこれらにどう対処したかを見ます。
第６部 ── 外部ライブラリはどうしたか
- 主なライブラリ
- algebra ── 演算ごとに分ける方式
- numeric-prelude ── 標準を置き換える方式
- algebraic-structures ── マグマから始める方式
- 法則をどう扱っているか
- ライブラリを選ぶときに見る点
- 外部ライブラリでも残る制約
- 対話 ── 関数を、ベクトルとして扱えるか
- 名前と、数学的な定義
- 内積について
- さらに深い問題
- 整理すると
- 他の言語では、どうなのか
- 主な体系での状況
- 実際に証明されているもの
第７部 ── Lean の Mathlib と比べる
- Mathlib の Group
- 主張が、値として要求される
- 対比
- Lean は、第４部の問題をどう避けているか
- なぜ Haskell はそうしなかったのか
- では、Lean のほうが優れているのか
第８部 ── 逆行列を持つことは、型で表せるか
- なぜ、これがさらに難しいのか
第９部 ── 各言語の型システムを比べる
- 比較する軸
- 一覧
- 表から読み取れること
- 法則付きの階層を積み上げられるか
- なぜ、積み上げが難しいのか
- では、なぜ Lean ではこの問題が生じないのか
- Haskell の強み
- 記述が軽い
- インスタンスの選択が一意に決まる
- 型推論が効く
- 実行時の性能が読みやすい
- Haskell の弱み
- 法則が守られる保証がない
- 同じ型に複数の構造を持たせられない
- 依存型がない
- Lean 4 の強みと弱み
- 強み ── 法則が証明として要求される
- 強み ── 演算と法則が同じクラスにある
- 強み ── 大規模なライブラリがある
- 弱み ── 記述の負担が大きい
- 弱み ── インスタンスの解決が複雑
- 弱み ── 汎用のプログラミング言語としての成熟度
- Idris の強みと弱み
- 強み ── 証明を「選べる」
- 強み ── Haskell に近い構文
- 弱み ── 法則の分離が裏目に出る
- 弱み ── 標準ライブラリに法則がない
- Rust の位置
- 共通点
- 違い
- 何を選ぶか
- base に代数構造がない、ということの意味
第１０部 ── 乗り換えれば解決するのか
- 結論を先に
- Haskell以外の言語：各言語の強みと弱み
- Lean 4 の場合
- Rocq の場合
- Agda の場合
- Idris 2 の場合
- OCaml、Standard ML の場合
- 乗り換えの前に考えること
- ユースケース別の選び方
- ケース１ ── 業務アプリケーションを書く
- ケース２ ── 数値計算ライブラリを作る
- ケース３ ── 数学の定理を証明する
- ケース４ ── 暗号やプロトコルを検証する
- ケース５ ── 型システムそのものを研究する
- ケース６ ── 依存型を使いつつ、プログラムも書きたい
- ケース７ ── 既存の Haskell コードがある
- 組み合わせるという選択
- まとめると
まとめ
- 結論
本記事の限界について
出典
- 現行の仕様とドキュメント
- 設計史と研究資料
- 検証されたソフトウェア
- 他の言語
- Haskell で法則を扱う手法
- Lean の型クラス解決
- 型クラスと代数構造