本文へスキップ
hdknr blog

Quint

TLA+ と同じ論理に、型付きでプログラマ向けの構文を載せた形式仕様記述言語。型検査・REPL・テストで書きながら間違いを潰し、ランダムシミュレータ・Apalache(記号的・有界)・TLC(明示的・全探索)を同じ仕様に使い分けられる

概要

Quint は、分散システムや並行プロトコルの設計を書いて検査する形式仕様記述言語。Informal Systems が開発を始め、GitHub のリポジトリは現在 quint-co/quint にある。論理の土台は TLA+ と同じで、構文は TypeScript や Rust に近く、型検査・REPL・テストが最初から付いてくる。「TLA+ の考え方はそのままに、プログラマが書きやすい形にしたもの」と捉えるとわかりやすい。

TLC が TLA+ の検査器であるのに対し、Quint は言語とツール群の名前で、検査器としてランダムシミュレータ・Apalache・TLC を使い分ける。

詳細

インストール

npm で配布されている(パッケージ名 @informalsystems/quint)。

npm install -g @informalsystems/quint

型検査・テスト・quint run は Node.js だけで動く。quint verify(Apalache)と --backend=tlc(Apalache と TLC)は Java の実行環境が必要で、本体は初回実行時に自動でダウンロードされる。Apalache はカレントディレクトリに _apalache-out/ を作るので、リポジトリ内で使うなら .gitignore に入れる。

TLA+ との書き方の対応

TLA+Quint意味
/\ A /\ Ball { A, B }すべて成り立つ
\/ A \/ Bany { A, B }どれか 1 つが起きる
\E b \in Buyers : ...nondet b = oneOf(BUYERS) ...非決定的に 1 つ選ぶ
[pc EXCEPT ![b] = "done"]pc.set(b, Done)写像の 1 か所を書き換える
pc[b]pc.get(b)写像の値を引く
UNCHANGED varsstock' = stock, pc' = pc変数を変えない
.cfg の CONSTANTSimport stock(BUYERS = ...)定数に値を与える

プライム付きで次の状態を書く点は TLA+ と同じ。状態を type Phase = Check | Buy | Done のような直和型で定義できるので、"chek" のような綴り間違いは型検査で弾かれる。検査条件は .cfg の別ファイルではなく、定数を与えたモジュール(module main { import stock(...).* })として同じファイルに書ける。

書きながらのフィードバック

3 つの検査方法

コマンド検査器方式「違反なし」の意味
quint runランダムシミュレータ--max-samples 回、最大 --max-steps 手の実行を試す試した範囲では見つからなかった(網羅ではない)
quint verifyApalache(既定)「N 手以内に破れる実行はあるか」を論理式にし SMT ソルバ Z3 に解かせる記号的な有界モデル検査--max-steps 以内には 1 つもない
quint verify --backend=tlcTLC仕様を TLA+ に変換(変換には Apalache を使う)し、到達状態を全列挙上限なしの全探索で違反なし

在庫 1 個を 2 人が同時に買う例では、3 つの検査器すべてが 4 ステップで在庫が -1 になる反例を返し、TLC は TLA+ 版と同じ 10 状態を探索した。確認と減算をアトミックにした版では、TLC が 4 状態を全探索して違反なしと報告した。

TLA+ / TLC との比較

項目Quint(Apalache / シミュレータ)TLA+ と TLC
構文TypeScript / Rust 風、静的型付き数学記号を ASCII で表す。型なし
検査方式記号的(Z3)+ランダムシミュレーション到達状態を 1 つずつ列挙
大きな値記号のまま扱えるので値の範囲が広くても列挙せずに済む状態空間を小さく絞る必要がある
実行の長さApalache は指定ステップ数まで(有界)状態空間が有限なら上限なしに網羅
活性Apalache の時相性質の対応は部分的(Quint のドキュメント)公平性つきの活性まで検査できる
実績比較的新しい。Cosmos などブロックチェーン・分散プロトコル1999 年以来の長い実績。AWS・Azure の事例

どう使い分けるか

どの検査器でも「違反なし」は、何を網羅したか(ランダム試行か、ステップ上限までか、全状態か)と、何を検査しなかったか(TLC 経由ではデッドロックを見ない、など)とセットで読む。

関連ページ

ソース記事