ソフトウェアエンジニアのためのLean証明の解剖
Anatomy of a Lean proof for software engineers (agostbiro.net)
要約
この記事は、ソフトウェアエンジニアが形式的証明システムであるLeanを用いて、計算理論の教科書にある問題を解くプロセスを解説しています。有限オートマトンと正規言語の概念を説明し、特に「x+y=z」という条件を満たすビット列の言語が正規言語であることを証明するために、逆向きに処理するDFA(決定性有限オートマトン)を構築するアプローチを示しています。これにより、形式的証明の考え方とソフトウェア検証への応用可能性を伝えています。
全文翻訳
ソフトウェアエンジニアのためのLean証明の解剖
[目次]
はじめに
最近、計算理論の教科書にある、有限オートマトンを用いて言語の性質を証明する問題を解きました。非形式的な証明は、オートマトンを構築してそれが言語を認識することを示す、構成的な証明です。これはプログラム検証に似ているので、証明を形式化するには何が必要か見てみるのは興味深いと思いました。Leanはこの目的に適しています。なぜなら、そのMathlibには問題のすべての定理が含まれているからです。
形式証明を終えた後、ソフトウェアエンジニアにシステムのプロパティを形式的に証明するために何が必要かについての良い洞察を提供できると思ったので、それを書き出すことにしました。
この投稿を分かりやすくするように努めました。モダンな静的型付けプログラミング言語(TypeScriptやRustなど)、バイナリ算術、基本的な命題論理、帰納的証明に慣れているなら、ついてこれるはずです。
背景:DFAと正規言語
DFAと正規言語に慣れている場合は、次のセクションにスキップしてください。
有限オートマトンは、固定されたメモリを持つ計算の理論的モデルを提供します。理論だけでなく、有限オートマトンは重要な実用的な応用もあります。例えば、有限オートマトンはパーサーや正規表現に関連しており、バグがインターネットの大部分をダウンさせたこともありました。
決定性有限オートマトン(DFA)
決定性有限オートマトン(DFA)は、固定された有限個の状態を持ち、入力記号を左から右へ1つずつ読み取る機械です。各記号に対して、決定的な遷移関数を使用して状態を更新します。最後の記号の後、機械は受理状態にある(入力が受理される)か、そうでない(入力が拒否される)かのどちらかです。
-?[0-9]+ のような単純な正規表現を書いたことがあるなら、DFAを構築したことになります。この正規表現は 12 や -123 のような整数リテラルにマッチし、対応するDFAは以下のようになります(矢印は次の状態につながる記号で注釈されています)。
[図:整数リテラルのためのDFA、デッドステートを含む]
このDFAには4つの状態があります。
- 開始: 最初の文字を処理する前に開始する場所です。開始状態は受理状態ではないため、空文字列は拒否されます。
- 符号: 開始状態から
-文字を検出すると、符号状態に移動します。符号はオプションであるため (-?)、開始状態から直接数字にジャンプして符号状態をスキップできます。文字列の終わりにこの状態にある場合、文字列は拒否されます。 - 数字: 開始状態または符号状態から数字文字 (
[0-9]) を検出すると、数字状態に移動します。この状態にいて再び数字文字を検出した場合、数字状態に留まります。数字状態はこのDFAの唯一の受理状態です。入力文字列を処理した後この状態にある場合、DFAはその文字列を受理します。 - デッド: 数字以外の文字(先頭の負の符号を除く)を検出すると、この状態に入ります。文字列の終わりにこの状態にある場合、DFAはその文字列を拒否します。デッド状態に入ると、そこから抜け出すことはできないため、このDFAのデッド状態はシンクです。
機械の記号の集合はΣ\Sigmaによって定義されます。私たちの正規表現の例では、Σ\Sigma = \left{-, 0, 1, 2, \ldots, 9\right}です。
正規言語
言語は文字列(または単語)の集合であり、あるDFAがその中の文字列だけを受理する場合、その言語は正規と呼ばれます。正規言語を認識することは、メモリ量が入力に依存しない決定問題のクラスです。
正規言語は有用な閉包特性を持ちます。2つの正規言語の和集合と共通部分は正規であり、補集合と(私たちにとって重要な)正規言語の逆転も正規です。
言語が正規であることを証明する標準的な方法は、DFAを構築し、それがその言語だけを受理することを示すことです。
集合内包表記で言語AAを記述できます。
A
{ w∈Σ∗∣P(w) }
A = \bigl{, w \in \Sigma^{*} \bigm| P(w) ,\bigr}
Σ∗\Sigma^{*}はΣ\Sigmaの記号のすべての可能な連結によって作成された文字列の集合を意味し、P(w)P(w)は文字列wwが言語に含まれるために満たさなければならない条件です。
この表記法を正規表現の例 -?[0-9]+ に適用してみましょう。すると、Σ∗\Sigma^{*}には "", "123", "-111", "2-625-" などの文字列が含まれ、P(w)P(w)は「wwは空ではなく、負の符号を含まない。ただし、wwが少なくとも2文字の場合、その最初の文字は負の符号である可能性がある」と定義できます。
問題
これから解く問題は、Michael SipserによるIntroduction to the Theory of Computation(第3版)からのものです。
1.32 次のように定義する。
Σ3
{ [000], [001], [010], …, [111] }
Σ3\left{
\begin{bmatrix}
0
\ 0
\ 0
\end{bmatrix},
\begin{bmatrix}
0
\ 0
\ 1
\end{bmatrix},
\begin{bmatrix}
0
\ 1
\ 0
\end{bmatrix},
\ldots,
\begin{bmatrix}
1
\ 1
\ 1
\end{bmatrix}
\right}.Σ3\Sigma3はすべての高さ3の0と1の列の集合であるため、Σ3\Sigma3上の文字列は3行のビットを決定します。各行を2進数として読むと、次のように定義される。
B
{ w∈Σ3∗∣P(w) }
B\bigl{, w \in \Sigma3^{*} \bigm| P(w) ,\bigr}
ここで、P(w)P(w)は、wwの最下位行が上位2行の合計に等しいという命題です。
BBが正規であることを示してください。(ヒント:BRB^Rで作業する方が簡単です。)
問題は、通常の文字 [a-z] の代わりに、3ビットの列からなるアルファベットを定義しています。したがって、"apple" や "banana" のような文字列で構成される言語ではなく、言語は以下のような2次元ビット文字列で構成されます。
011
001
100
ここで、最初の列が最初の「文字」などとなります。
文字列が言語に含まれるかどうかを決定するルールは、文字列の最初の2行を加算し、それが3番目の行と一致するかどうかを確認することです。
例えば、以下の文字列は言語に含まれます。
011 # x行: 最初の加算項は10進数で3
001 # y行: 2番目の加算項は10進数で1
100 # z行: 合計は4で、3 + 1に等しい
しかし、以下の文字列は言語に含まれません。
01 # x行: 最初の加算項は10進数で1
00 # y行: 2番目の加算項は0
11 # z行: 合計は3で、1 + 0に等しくない
このような言語は最初は奇妙に見えるかもしれませんが、認識するのは実際には簡単です。言語に含まれるかどうかを判断するために、方程式 x+y=z を確認するだけで済みます。課題は、任意に長い文字列に対して固定量のメモリでこれを実行する必要があることです。
解法
秘訣は、手で数字を加算する方法を思い出すことです。つまり、最下位桁から最上位桁に向かって作業します。列から列へ持ち越されるのは桁上がりだけです。
しかし、DFAは左から右へ読み取り、問題は数値を最上位ビットを先に提示します。そのため、BBを直接認識するのではなく、その逆転であるBRB^Rを認識するDFAを構築します。BRB^RはBBの文字列を逆順に並べたもので、機械は最下位桁を最初に目にします。
BRB^Rを認識するDFAを構築できれば、BRB^Rが正規言語であると結論付けることができます。BRB^Rの逆転がBBであるため、正規言語の逆転の閉包特性を使用して、BBも正規であると結論付けることができます。これにより、解法が完了します。
加算器算術
列ごとに算術を実行する場合、加算器方程式を使用して各ステップの合計ビットを計算します。
xi⊕yi⊕cin
zi
x
_i
\oplus y
_i
\oplus c
_\mathrm{in}
z
_i
ここで、xi, yiは加算項のビット、ziは合計ビット、iは現在の列のインデックス、cinは前のステップからの入力桁上がりです。次のステップの出力桁上がり、coutと表記されるものを次のように計算します。
cout
(xi∧yi)∨(cin∧(xi⊕yi))
c
_\mathrm{out}
(x
_i
\wedge y
_i) \vee \left( c
_\mathrm{in}
\wedge (x
_i
\oplus y
_i) \right)
これは、両方の加算項が1であるか、入力桁上がりがあり、加算項のいずれか一方のみが1である場合に桁上がりがあることを意味します。coutを計算する簡単な方法は、xi, yi, cinの少なくとも2つが1であるかどうかを確認することです(Leanの証明でこれを利用します)。
加算器DFA
これを念頭に置いて、BRB^Rを認識するDFAは次のとおりです。
[図:Bの逆転を認識するDFA:状態は保留中の桁上がりであり、デッドステートが追加されています。各遷移は、3ビットの列記号でラベル付けされています。実線矢印は合計ビットが一致する列、破線の赤い矢印は合計ビットが一致しない列です。]
加算器DFAには3つの状態があります。
- 桁上がり0: 次の列を処理する前に桁上がりが0の場合、この状態になります。これは開始状態と受理状態の両方です。なぜなら、最後に桁上がりが残っていると、合計が最下位行を超えたことを意味するからです。
- 桁上がり1: 次の列を処理する前に桁上がりが1の場合、この状態になります。この状態は非受理状態です。なぜなら、単語がここで終了すると桁上がりが残るため、合計がオーバーフローしたことを意味します。しかし、デッド状態とは異なり、[001]の列は保留中の桁上がりを吸収して桁上がり0に戻ることができるため、ここから抜け出すことができます。
- デッド: 合計が一致しない場合、この状態になります。これはシンク状態であり、決して抜け出すことはできません。
矢印は、入力状態から出力状態への遷移を引き起こす列で注釈されています。図が最初は混乱して見える場合、以下の例がおそらくそれをより明確にするでしょう。
例1
問題の最初の例をDFAでトレースしてみましょう。
011 # x行: 10進数で3
001 # y行: 10進数で1
100 # z行: 10進数で4
DFAはBRB^Rを認識するため、列を逆順に読み取ります。実行をアンロールすると、各ステップで1つの状態を持つ直線になります。
[図:受理された単語に対する桁上がりオートマトンの実行をアンロールしたもの。桁上がり0から開始し、機械は列(1,1,0)、(1,0,0)、(0,0,1)を読み取り、桁上がり1、桁上がり1、桁上がり0を通過し、受理状態で終了します。]
実行は桁上がり0(受理状態)で終了するため、逆転した単語はBRB^Rに含まれます。BRB^Rの定義により、元の単語もBBに含まれます。
機械は非受理状態の桁上がり1状態を2回通過することに注意してください。もし単語が最初の2つの列のいずれかで停止していた場合、拒否されていたでしょう。1+1=0(桁上がりなし)と11+01=00(桁上がりなし)は、桁上がりを置く場所がないと両方とも間違っています。
例2
次に、拒否されるべき2番目の例です。
01 # x行: 10進数で1
00 # y行: 10進数で0
11 # z行: 10進数で3
拒否された単語に対する桁上がりオートマトンの実行をアンロールしたもの:桁上がり0から、列(1,0,1)は機械を桁上がり0に保ち、次に列(0,0,1)は合計ビットチェックに失敗し、デッドシンクステートに送ります。
[図:拒否された単語に対する桁上がりオートマトンの実行をアンロールしたもの。桁上がり0から、列(1,0,1)は機械を桁上がり0に保ち、次に列(0,0,1)は合計ビットチェックに失敗し、デッドシンクステートに送ります。]
最初の列はそれ自体では問題ありません(1+0は実際に1です)。そのため、機械はまだ何も間違っていることに気づけません。しかし、2番目の列で失敗します。桁上がりが保留されていない場合、0+0は0を生成しなければなりませんが、最下位行は1を主張しています。実行は受理状態の外で終了するため、2番目の例は拒否されます。
デッド状態はシンク状態であるため、2番目の列の後にさらに有効な列があったとしても、文字列は拒否されることに注意してください。
Leanでの証明
問題の言語BBが正規であることを示すことが目標です。前述のように、言語が正規であることを示すには、DFAを構築し、それが言語を受理することを示す必要があります。
Leanでの証明は3つの部分から構成されます。
- 言語BBの仕様。
- 加算器DFAの実行可能な実装。
- 実装が仕様と一致することを示す証明。
LeanのMathlibは、形式言語とDFAをファーストクラスでサポートしているため、仕様と実装の構造を構築するだけで済みます。
証明については、より多くの作業が必要になりますが、Mathlibも役立ちます。正規言語が逆転に対して閉じているという定理が含まれており、これにより多くの作業が節約されます。証明には見慣れない構文が含まれますが、内部的には単なるプログラムです。実際、証明はプログラムがコンパイルされれば受け入れられます。
以下は、プログラムのコンポーネントをまとめた図です。完全なコードはGitHubで見つけることができます。
[図:Leanコードの3つのファイル。仕様はアルファベットSigma3とそれ上の言語Bを定義します。実装は遷移関数とそれに基づくDFAを定義します。証明ファイルは、機械に関する実行不変条件を述べ、それを仕様と組み合わせて、DFAがBの逆転を受理すること、したがってBの逆転が正規であること、したがってBが正規であることを証明します。]
仕様と実装は証明で結合されます。
仕様
問題のアルファベットは3ビットの列から構成されています。Leanでは、1つの列を3つのブール値のタプルで表すことができます。
abbrev Sigma3 := Bool × Bool × Bool
次に、Mathlib.Computability.Languageを使用してBBを定義します。
def B : Language Sigma3 :=
{ wBE | row3BE wBE = row1BE wBE + row2BE wBE }
Languageは、標準的な操作と関連定理を備えた形式言語の汎用実装です。これをアルファベットSigma3とBBのメンバーシップ述語(言語は文字列の集合であることを思い出してください)を使用して構築します。
wBEは候補となる単語で、ビッグエンディアンで読み取られ、Sigma3値のリスト、つまり2次元のバイナリ値のリストです。rowNBEは、2次元リストのN番目の行を選択し、ビッグエンディアン解釈を使用して自然数に変換する関数です。1したがって、述語は単に
z
x
+
zy
x
+
y
前の例からのものです。
セット内包表記を持つプログラミング言語を使用したことがある場合、構文が familiar に見えるかもしれませんが、ここではコレクションを構築しているわけではありません。Languageは内部的には単なるSetであり、LeanのSetは要素がセットに含まれているかどうかをテストする関数です。2したがって、BBの定義は内部的には関数定義に展開されます。
def B : List Sigma3 → Prop :=
fun wBE =>
row3BE wBE = row1BE wBE + row2BE wBE
この関数はList Sigma3型の引数を1つ持ち、これはSigma3オブジェクトを保持する汎用リストです。これはこれまでのところ非常に標準的ですが、戻り値の型はより興味深いです。典型的なプログラミング言語では、メンバーシップテストはブール値を返すことが期待されます。しかし、ここでは戻り値の型はPropであり、これはLeanのすべての命題の型です(命題は真偽が確定する可能性のあるものです)。
では、メンバーシップテストはどのように機能するのでしょうか?式 wBE ∈ B は関数をwBEに適用し、命題を返します。Leanでは、命題自体が型であり、その値は命題の証明です。したがって、wBE ∈ B を評価してブール値にする代わりに、それを証明します。単語が言語に含まれていることを示すには、命題の型の値を作成します。単語が言語に含まれていないことを示すには、否定命題の値を構築します。このようにして、セットメンバーシップテストは実行時の計算ではなく、型チェックになります。
実装
まず、DFAの状態(桁上がり0、桁上がり1、デッド)を合計型として定義します。
inductive DFAState where
| carry (c : Bool)
| dead
deriving DecidableEq, Fintype
RustのenumやTypeScriptの判別可能なユニオンを使用して同じ型を定義することもできます。Leanのinductive型は、これらの言語の再帰的な合計型よりも少し多くのことを行います。それは、型を証明で簡単に使用できるようにするいくつかの足場も生成します。これについては後で詳しく説明します。
次に、派生に進みます。DecidableEqは、この型が完全な等価性チェックをサポートすることを示しています(RustのEqの派生と同じです)。しかし、Fintypeは証明アシスタントでのみ利用可能なものです。これは、型が有限個の値を持つことを示しており、それらの値のリストとリストが完全であることの証明を作成します。Fintypeを派生させることで、後で言語が定数メモリで認識可能であり、したがって正規であると主張できるようになります。
次に、DFAの遷移関数を定義します。
def dfaStep : DFAState → Sigma3 → DFAState
| .dead, _ => .dead
| .carry c, (x, y, z) ->
if z = (x ^^ y ^^ c) then -- ^^ は XOR
.carry (Bool.atLeastTwo x y c)
else
.dead
この関数は2つの引数、現在の状態と次の記号を取り、次の状態を返します。
前述のように、デッド状態はシンクであるため、常に自身にマッピングされます。桁上がり状態にあり、加算器方程式がチェックアウトする場合、次の状態は桁上がり値を保持する桁上がり状態になります。それ以外の場合は、デッド状態に入ります。
dfaStepは実行可能な通常の関数なので、簡単な健全性チェックを実行してみましょう。
[図:桁上がりオートマトンの1ステップ:桁上がり0から、列(1,1,0)は加算器方程式を満たし、機械を桁上がり1に遷移させます。]
#eval dfaStep (.carry false) (true, true, false)
-- Prints: DFAState.carry true
これが保持されることを確認したい場合は、例にすることができます。
example :
dfaStep (.carry false) (true, true, false) = .carry true := by
decide
Leanのexample : ... := by decide構造は、単体テストのようなものですが、コンパイル時にチェックされる証明です。
証明の仕組み
次のセクションで解法の解法の証明を掘り下げる前に、dfaStep例を使用して証明がどのように機能するかを復習しましょう。
example :
dfaStep (.carry false) (true, true, false) = .carry true := by
decide
byキーワードは、Leanをタクティックモードに切り替えます。これは証明を生成するための命令的な方法です。decideは、型チェッカー内で命題の決定手続きを評価することによって命題を証明するタクティックです3。これは実際にコンパイルされたコードを実行するわけではありませんが、私たちの目的のためには、decideを評価による証明と考えることができます。
decideによって生成された証明は、内部的には次のものと同等です5。
abbrev StepEndsWithCarry : Prop :=
dfaStep (.carry false) (true, true, false) = .carry true
example : StepEndsWithCarry :=
(of_decide_eq_true (Eq.refl true))
今回は:=の後にbyがないことに注意してください。これは、証明を構築して証明を閉じる必要がある項モード証明であることを意味します。
項は型の値です。たとえば、3は自然数の型であるNatの値です。命題の証明はその命題の型を持つ項であり、証明を書くことはその型の値を作成することに似ています。この見方では、命題は型に少なくとも1つの値がある場合に真であり、証明可能に値がない場合に偽です。偽の命題は、Rustの空のenumやTypeScriptのneverのようなものです。型に値がないため、証明として書くことができるものはありません。
上記の例では、命題はStepEndsWithCarryであり、証明として機能する項は次のとおりです。
(of_decide_eq_true (Eq.refl true))
証明を理解するには、この項の型が命題である理由を理解する必要があります。of_decide_eq_trueは標準ライブラリの定理であり、その型は次のとおりです。
decide p = true → p
これは、命題pの決定手続きを評価するとtrueが返される場合、pが成り立つことを示しています。これは、命題を単純に評価することによって証明できる非常に巧妙な定理です(定理の証明はこの投稿の範囲外です)。
矢印は、decide p = true → pが型decide p = trueの1つの引数を持つ関数型であり、戻り値の型がpであることを示しています。したがって、decide StepEndsWithCarry = trueの型の引数をof_decide_eq_trueに渡すことができれば、StepEndsWithCarry命題の値、つまり同じ命題の証明を得ることができます。
しかし、of_decide_eq_trueにdecide StepEndsWithCarry = trueの型の項をどのように構築できるでしょうか?
答えは少し複雑です。of_decide_eq_trueに渡している引数はEq.refl trueであり、その型はtrue = trueです。一見すると、これには私たちの命題とは関係がありません。
Leanがdecide StepEndsWithCarry = trueに対してtrue = trueをチェックするときに魔法が起こります。型チェッカーはdecide StepEndsWithCarryを展開し、dfaStepを評価して結果を.carry trueと比較し、これはtrueに還元されます。
Leanは、2つの型が同じ項に還元される場合、それらを等しいと見なします。したがって、decide StepEndsWithCarry = trueとtrue = trueは同じ型であり、Eq.refl trueは両方の証明として受け入れられます。
そして、私たちの正規なプログラミングに戻りましょう。
証明
前述のように、BB言語が正規であることを証明するには、まず加算器DFAがBRB^Rを受理することを示す必要があります。その後、正規言語の逆転の閉包特性を使用してBBが正規であることを証明できます。これはMathlibで定理として容易に入手できますがMathlibが、加算器DFAがBRB^Rを認識することを示すには、ある程度の作業が必要です。
Mathlibの正規言語の定義は、次のように要約できます6。
def IsRegular (L : Language T) : Prop :=
∃ σ [Fintype σ], ∃ M : DFA T σ, M.accepts = L
(L : Language T)引数は、言語が任意の型のシンボルを持つことができることを意味します。戻り値の型は再びPropです。
∃ σ [Fintype σ]は、状態の有限数があることを示しています。興味深い部分は∃ M : DFA T σ, M.accepts = Lであり、これはLがその状態上のDFAによって正確にLを受理する場合に正規であることを示しています。では、DFAはいつ言語を受理するのでしょうか?
MathlibでDFAが受理する言語は次のように定義されています7。
def accepts : Language T :=
{ word | M.evalFrom M.start word ∈ M.accept }
これは、DFAが受理する言語は、開始状態からDFAを評価すると受理状態に至る単語の集合であることを意味します。
私たちの仕事は、adderDFA.acceptsとB.reverseが同じセットであることを証明することです。これは、証明において次のように形式化されます。
theorem adderDFA_accepts_B_reverse : adderDFA.accepts = B.reverse := by
...
これを証明する方法は、加算器DFAがB.reverseのメンバーシップチェックである同じ方程式を計算することを示すことです。B.reverseは次のように定義されています。
B.reverse = { w | w.reverse ∈ B }
BはrowNBE関数を使用して、最上位ビットを先に読み取ります。逆転した文字列をビッグエンディアンで読み取ることは、元の文字列をリトルエンディアンで読み取ることと同じです。つまり、Bのためにビット文字列をビッグエンディアンで解釈する一方で、B.reverseのためにリトルエンディアンで解釈します。したがって、B.reverseのメンバーシップチェックは次と同等です8。
{ wLE | row1LE wLE + row2LE wLE = row3LE wLE }
adderDFA_accepts_B_reverseを証明する際の課題は、言語定義が単語全体に関する1つの方程式を述べているのに対し、加算器DFAは1列ずつ動作することです。
実行不変条件
DFAは有限個の状態を持ちますが、任意に長い文字列を処理できます。このようなプロセスの性質を証明する自然な方法は、帰納法です。
帰納法で命題を証明するには、すべてのステップで成り立つ帰納的仮説が必要です。帰納的仮説の1つのアイデアは、次の同値性を提案することです。
adderDFA.evalFrom (.carry false) wLE = .carry false ↔
row1LE wLE + row2LE wLE = row3LE wLE
これは次のように読み取れます。
加算器DFAを(リトルエンディアンの)単語ww(コードでは
wLE)に対して桁上がり0から実行すると、次の場合に桁上がり0で終了します。row1(w)+row2(w)=row3(w)
ここで、行はリトルエンディアンの2進数として読み取られます。
これが最終的に必要なものです。常に桁上がり0から開始し、唯一の受理状態も桁上がり0であり、同値の右辺はB.reverseのメンバーシップチェックと一致します。しかし、前述のように、桁上がり1も有効な中間状態になり得るため、このステートメントは帰納的仮説としては弱すぎます。
帰納的仮説を特定の桁上がりの値に制限することはできませんが、桁上がり入力と桁上がり出力の間の接続を確立する必要があります。これを、同値の右辺を桁上がり入力と桁上がり出力の項を含めるように拡張することで達成できます。
row1LE wLE + row2LE wLE + carryIn =
row3LE wLE + carryOut * 2 ^ wLE.length
または、数学的な表記法で、これが単なる2進加算の定義であることが簡単にわかるようにします。
∑
_i
0
n
−
1
x
i
2
i
+
∑
_i
0
n
−
1
y
i
2
i
+
c
i
n
∑
_i
0
n
−
1
z
i
2
i
+
c
_\mathrm{out}
⋅
2
n
\sum
_{i=0}^{n-1} x
_i
2^i + \sum
_{i=0}^{n-1} y
_i
2^i + c
_\mathrm{in}
\sum
_{i=0}^{n-1} z
_i
2^i + c
_\mathrm{out}
\cdot 2^n
完全な同値は次のようになります。
adderDFA.evalFrom (.carry carryIn) wLE = .carry carryOut ↔
row1LE wLE + row2LE wLE + carryIn =
row3LE wLE + carryOut * 2 ^ wLE.length
これは次のように読み取れます。
加算器DFAを(リトルエンディアンの)単語ww(コードでは
wLE)に対して桁上がりcinから実行すると、coutで終了します。row1(w)+row2(w)+cin
row3(w)+cout⋅2∣w∣
\mathrm{row}
_1(w) + \mathrm{row}
_2(w) + c
_\mathrm{in}
=
\mathrm{row}
_3(w) + c
_\mathrm{out}
\cdot 2^{|w|}
ここで、行はリトルエンディアンの2進数として読み取られます。
両方の桁上がりを0に設定すると、これは最初の試みと同等になります。しかし、桁上がり入力と桁上がり出力の両方が非ゼロになる可能性がある中間ステップにも有効です。
実行不変条件の証明
実行不変条件を定理として示します。証明は後で省略します。
def RunEndsWithCarry (carryIn : Bool) (wLE : List Sigma3)
(carryOut : Bool) : Prop :=
adderDFA.evalFrom (.carry carryIn) wLE = .carry carryOut
def WordAddsWithCarry (carryIn : Bool) (wLE : List Sigma3)
(carryOut : Bool) : Prop :=
row1LE wLE + row2LE wLE + carryIn.toNat
= row3LE wLE + carryOut.toNat * 2 ^ wLE.length
lemma run_invariant (wLE : List Sigma3) (carryIn carryOut : Bool) :
RunEndsWithCarry carryIn wLE carryOut ↔
WordAddsWithCarry carryIn wLE carryOut := by
...
同値の両辺はそれぞれ名前を持ち、定理は「carryInからの実行がcarryOutで終了する」⇔「単語がこれらの桁上がりで加算される」と読み取れます。RunEndsWithCarryとWordAddsWithCarryはPropの型を持つ定義であり、値ではなくステートメントです。RunEndsWithCarryは前のセクションの同値の左辺であり、WordAddsWithCarryは右辺です。唯一の違いは.toNatで、これはブール値を0または1に変換して桁上がりを算術に参加できるようにします(簡潔にするために、以下のコードブロックでは.toNatは省略されます)。
定理は関数のように引数を持ちます。実際、定理は本質的に関数です。その引数はステートメントが言及する変数であり、その型は命題であり、その本体は証明です。したがって、パラメータ化された定理があり、その引数のすべての値に対して証明する必要があります。しかし、後でadderDFA_accepts_B_reverseの証明で両方の桁上がりをfalseに設定して使用します。これはB.reverseのメンバーシップチェックに対応します。
run_invariant (carryIn := false) wLE (carryOut := false)
証明は、単語wLE(型はList Sigma3)に関する帰納法によって行われます。リストの帰納法は、空リストのステートメントを証明し、次にそれが一部のリストに対して成り立つ場合、そのリストに要素を1つ追加した場合にも成り立つことを証明する必要があります。すべてのリストは、要素を先頭に追加することによって空リストから構築できるため、これらの2つのステップはすべてのリストをカバーします。
induction wLE generalizing carryIn with
| nil => ...
| cons column columnsLE induction_hypothesis => ...
Leanのタクティックモードは、証明する必要がある目標を作成することによって機能します。目標は、Leanがまだ証明を必要としているステートメントです。各タクティックは、現在の目標を変換または閉じます。
最初の目標は証明しようとしている定理ですが、直接証明することはできません。そのため、inductionタクティックを使用します。これは、リストの各コンストラクタに対して証明する目標を提供します。nilは空リストのコンストラクタであり、consは既存のリストの先頭に要素を追加するコンストラクタです。consケースでは、最初の列、残りの列、および残りの列に対する実行不変条件が真であると仮定された帰納的仮説に名前を付けることができます。
generalizing carryInの部分は重要です。これがないと、帰納的仮説は、見ている実行と同じcarryInで始まる実行のみについて言及します。しかし、帰納的ステップでは、最初の列を剥がします。残りの列に対する実行は、最初の列が生成した桁上がりで始まるため、carryInが持っていた値と同じ値ではありません。generalizingは、帰納的仮説がすべての開始桁上がりに対して成り立つようにします。終了桁上がりは実行全体で同じであるため、carryOutは固定されたままにできます。
ベースケース
空単語に対するDFAの実行について見てみましょう。実行不変条件を思い出してください。
RunEndsWithCarry carryIn wLE carryOut ↔
WordAddsWithCarry carryIn wLE carryOut
まず、同値の左辺で何が起こるかに焦点を当てます。RunEndsWithCarryを展開すると、次のようになります。
adderDFA.evalFrom (.carry carryIn) wLE = .carry carryOut
DFA.evalFromはMathlibで次のように定義されています。
def evalFrom (s : σ) : List T → σ :=
List.foldl M.step s
List.foldlは、入力リストが空の場合、初期値を返します。DFA.evalFromに提供する初期値は.carry carryInなので、ベースケースでは次のようになります。
.carry carryIn = .carry carryOut
同値の左辺。
次に、ベースケースで右辺で何が起こるかを見てみましょう。WordAddsWithCarryを展開すると、方程式が得られます。
row1LE wLE + row2LE wLE + carryIn =
row3LE wLE + carryOut * 2 ^ wLE.length
rowNLEは空リストに対して0を返します。したがって、次のようになります。
0 + 0 + carryIn = 0 + carryOut * 2 ^ 0
または単純に
carryIn = carryOut
したがって、ベースケースでは次のことを証明する必要があります。
.carry carryIn = .carry carryOut ↔
carryIn = carryOut
4つのケースしかないので、網羅的に証明できます。同値は、各行の真理値が同じ場合に成り立ちます。
| carryIn | carryOut | .carry carryIn = .carry carryOut | carryIn = carryOut | ↔ |
|---|---|---|---|---|
| F | F | T | T | T |
| F | T | F | F | T |
| T | F | F | F | T |
| T | T | T | T | T |
Leanでの同じ議論:
lemma run_invariant (wLE : List Sigma3) (carryIn carryOut : Bool) :
RunEndsWithCarry carryIn wLE carryOut ↔
WordAddsWithCarry carryIn wLE carryOut := by
induction wLE generalizing carryIn with
-- base case
| nil =>
unfold RunEndsWithCarry WordAddsWithCarry
revert carryIn carryOut
decide
-- inductive step
| cons column columnsLE induction_hypothesis => ...
decideは、証明の仕組みで単一のdfaStepステップをチェックしたときと同様に、4行の表をチェックします。しかし、最初に2つの設定が必要です。
decideは定義を直接見ることができないため、unfold RunEndsWithCarry WordAddsWithCarryは2つの名前を定義に置き換えます。decideはまた、自由変数を持たない命題を必要としますが、carryInとcarryOutはlemmaの引数です。revert carryIn carryOutはそれらを目標に戻し、目標はすべての桁上がりの値に関するステートメントになります。
∀ carryOut carryIn : Bool,
adderDFA.evalFrom (.carry carryIn) [] = .carry carryOut ↔
row1LE [] + row2LE [] + carryIn =
row3LE [] + carryOut * 2 ^ [].length
有限個のブール値のすべての値に関するステートメントは決定可能なので、decideは同値の両辺を4つの組み合わせそれぞれについて評価し、それらが常に一致するため、目標を閉じます。
帰納的ステップ
帰納的ステップでは、リストに対する不変条件が成り立つ場合、そのリストに要素を1つ追加した場合にも成り立つことを証明する必要があります。
帰納的ステップでは、単語はcolumn :: columnsLEであり、これはcolumnsLEの先頭にcolumnを追加して作成されたリストです。Leanにはリストの先頭に要素を追加するためのinfix演算子::があるため、column :: columnsLEと書くことができます。
帰納的仮説はcolumnsLEに対して仮定されますが、単語全体に対する不変条件を証明する必要があります。これを、最初の列に対するDFAの最初のステップと残りの列に対する実行を中間桁上がりで結合することによって行います。次に、WordAddsWithCarryからの方程式を並べ替えて、算術がチェックアウトすることを示します。
これらは高レベルのステップです。
- DFA側では、実行を最初のステップと残りの列に対する実行に分割し、中間桁上がりで結合します。
- DFAの最初のステップを算術に変換します。これは単一の列の加算器方程式です。
- 帰納的仮説を使用して、残りの列に対する実行を算術に変換します。
- 算術側では、単語全体の方程式が最下位ビットの方程式と残りのビットの方程式に分割されることを示します。
[図:実行の分割、最初のステップ、最初のステップの加算、帰納的仮説、最下位ビットの分割、まとめ。DFA側と算術側は帰納的ステップで結合されます。]
これらのステップの後、同値の2つの辺は同じことを言います。これにより、目標が閉じます。ステップ1、2、4はそれぞれ独自のヘルパーlemmaを取得するため、まずそれらを見てみましょう。
実行の分割
lemma split_run (column : Sigma3) (columnsLE : List Sigma3)
(carryIn carryOut : Bool) :
RunEndsWithCarry carryIn (column :: columnsLE) carryOut ↔
∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
RunEndsWithCarry carryMid columnsLE carryOut := by
...
これは計画のステップ1です。lemmaは、単語に対する実行(column :: columnsLE)がcarryOutで終了する⇔、最初のステップがcarryMidに達し、carryMidからの残りの実行がcarryOutで終了するという2つのプロパティを持つ中間桁上がりcarryMidが存在することを示しています。
RunEndsWithCarryの定義を思い出してください。
def RunEndsWithCarry (carryIn : Bool) (wLE : List Sigma3)
(carryOut : Bool) : Prop :=
adderDFA.evalFrom (.carry carryIn) wLE = .carry carryOut
したがって、RunEndsWithCarryを展開すると、次の目標が残ります。
adderDFA.evalFrom (.carry carryIn) (column :: columnsLE) =
.carry carryOut ↔
∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
これを証明するには、両辺を同じステートメントに書き換えます。まず、左辺を最初の列の単一ステップと、そのステップが着地した状態からのcolumnsLEに対する実行に分割します。
adderDFA.evalFrom (dfaStep (.carry carryIn) column) columnsLE =
.carry carryOut ↔
∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
[図:実行の分割:桁上がり入力から列::columnsLEに対する実行は、列に対する単一ステップ、中間桁上がりへの着地、その桁上がりからのcolumnsLEに対する実行と同じです。]
単語全体の実行は、最初の列に対する単一ステップの後に残りの部分に対する実行が続きます。
次に、dfaStep (.carry carryIn) columnが両辺の同値にあることを示します。次に、最初の列に対する最初のステップが桁上がり状態cで終了すると仮定します。すると、次のようになります。
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut ↔
∃ carryMid,
.carry c = .carry carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
同値の右辺はc = carryMidの場合にのみ真であるため、存在量化子と最初の連言を削除し、次のように書き換えることができます。
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut ↔
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut
これは左辺と正確に一致します。
これまでのところ、dfaStep (.carry carryIn) columnが桁上がり状態cで終了すると仮定しましたが、列のステップはデッド状態に着地することもできます。左辺は、デッド状態が最初のステップで許可される可能性があることを示唆していますが、右辺は最初のステップが桁上がり状態で終了する場合にのみ真です。しかし、デッド状態はシンク(デッド状態から始まる実行はデッド状態で終了する)であることを知っているため、左辺も偽になります。両辺が偽であるため、同値は成り立ち、証明が完了します。
次に、Leanでの証明の外観を見てみましょう。
lemma split_run (column : Sigma3) (columnsLE : List Sigma3)
(carryIn carryOut : Bool) :
RunEndsWithCarry carryIn (column :: columnsLE) carryOut ↔
∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
RunEndsWithCarry carryMid columnsLE carryOut := by
simp only [RunEndsWithCarry, DFA.evalFrom_cons, adderDFA_step]
cases dfaStep (.carry carryIn) column with
| dead =>
rw [dead_state_is_sink]
simp
| carry c =>
simp only [DFAState.carry.injEq, exists_eq_left']
simpはLeanで最も一般的に使用されるタクティックの1つです。これは、簡略化ルールと提供する定義およびlemmaのデータベースを使用して目標を書き換え、目標が自明に真になる場合に目標を閉じます。simp onlyは、simpをリストされたlemmaに制限し、デフォルトのセット全体を使用しないため、目標を予測可能に保ちます。
最初のsimp only行は、lemmaを同値のdfaStepを持つ形式に書き換えます。
adderDFA.evalFrom (dfaStep (.carry carryIn) column) columnsLE =
.carry carryOut ↔
∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
casesタクティックは、型の各コンストラクタに対して1つの目標に目標を分割します。ここでは、cases dfaStep (.carry carryIn) columnは、列への最初のステップがデッド状態に着地する場合と桁上がり状態に着地する場合の2つの新しい目標を導入します。
デッド状態のケースは、ここで省略するヘルパーlemmaで証明されますが、dfaStepの定義から直接導かれます。
桁上がりケースcは、列への最初のステップからの桁上がり値として導入されます。
cases dfaStep (.carry carryIn) column with
| dead => ...
| carry c =>
simp only [DFAState.carry.injEq, exists_eq_left']
これにより、次の目標が残ります。
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut ↔
∃ carryMid,
.carry c = .carry carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
以前は、.carry c = .carry carryMidがc = carryMidを意味すると当然のこととして受け入れていましたが、今では正式な議論が必要です。幸いなことに、DFAState.carryのようなコンストラクタはLeanで単射であるため、同じコンストラクタで構築された2つの値が等しい場合、それらの引数は等しくなります。この有用な事実は、自動生成されたDFAState.carry.injEq定理によって提供され、simpはcとcarryMidを.carryコンストラクタから引き出すために使用します。
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut ↔
∃ carryMid,
c = carryMid ∧
adderDFA.evalFrom (.carry carryMid) columnsLE = .carry carryOut
次に、標準ライブラリの定理exists_eq_left'を使用して目標を閉じます。定理は(∃ a, a' = a ∧ p a) ↔ p a'と述べており、carryMidをcに置き換えて存在量化子と最初の連言を削除できます。
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut ↔
adderDFA.evalFrom (.carry c) columnsLE = .carry carryOut
同値の両辺は同じになったため、simpはこの目標を単独で閉じます。これにより、証明が完了します。
最初のステップの加算
lemma first_step_adds (x y z carryIn carryOut : Bool) :
dfaStep (.carry carryIn) (x, y, z) = .carry carryOut ↔
x + y + carryIn = z + 2 * carryOut := by
...
これは計画のステップ2です。lemmaは、DFAの (x, y, z)列に対する単一ステップが状態carryInから状態carryOutに遷移する⇔次のことを示しています。
x
+
y
+
c
i
n
z
+
2
⋅
c
_\mathrm{out}
x + y + c
_\mathrm{in}
z + 2 \cdot c
_\mathrm{out}
DFAの実行の最初のステップを実行から算術に変換するためにこのlemmaが必要です。5つのブール値のすべての組み合わせをチェックすることにより、定義を展開して証明します。
dfaStepの定義を思い出してください。
def dfaStep : DFAState → Sigma3 → DFAState
| .dead, _ => .dead
| .carry c, (x, y, z) ->
if z = (x ^^ y ^^ c) then -- ^^ は XOR
.carry (Bool.atLeastTwo x y c)
else
.dead
開始状態は桁上がり状態であるため、2番目の分岐が適用され、dfaStepを展開すると次の目標が残ります。
(if z = (x ^^ y ^^ carryIn) then
.carry (Bool.atLeastTwo x y carryIn)
else
.dead) = .carry carryOut ↔
x + y + carryIn = z + 2 * carryOut
同値の左辺は、合計ビットがチェックアウトし、桁上がり出力がtrueになるのは、x、y、carryInの少なくとも2つがtrueの場合であることを示しています。右辺は、自然数での算術を使用して同じことを示しています。
両辺は5つのブール値に対する固定された式であり、32の組み合わせしか生成されないため、ベースケースと同様に網羅的にチェックできます。同値は、各行の真理値が同じ場合に成り立ちます。
両方の辺が真である行と偽である行の2つの例をレビューしましょう。x、y、carryOutがtrueで、zとcarryInがfalseである行を取ります。これは、以前のdfaStep例と同じです。
[図:桁上がりオートマトンの1ステップ:桁上がり0から、列(1,1,0)は加算器方程式を満たし、機械を桁上がり1に遷移させます。]
値を代入すると、次のようになります。
(if false = (true ^^ true ^^ false) then
.carry (Bool.atLeastTwo true true false)
else
.dead) = .carry true ↔
1 + 1 + 0 = 0 + 2 * 1
true ^^ true ^^ falseはfalseに評価されるため、条件は成り立ち、ステップは最初の分岐を取ります。x、y、carryInの2つがtrueであるため、ステップは.carry trueに着地します。
.carry true = .carry true ↔
1 + 1 + 0 = 0 + 2 * 1
両辺は真であるため、この行は成り立ちます。
次に、列が加算されない行を取ります。x、y、z、carryOutはtrueで、carryInはfalseです。
[図:桁上がりオートマトンの1ステップ:桁上がり0から、列(1,1,1)は合計ビットチェックに失敗し、機械をデッドシンクステートに送ります。]
今回は、条件はtrue = (true ^^ true ^^ false)、つまりtrue = falseであり、ステップは2番目の分岐を取り、デッド状態に着地します。
.dead = .carry true ↔
1 + 1 + 0 = 1 + 2 * 1
左辺は.deadと.carry trueが異なる状態であるため偽です。右辺は2が3ではないため偽です。両辺が偽であるため、この行は成り立ちます。
残りの30行も同様です。列が加算される場合は両辺が真であり、加算されない場合は両辺が偽です。これにより、証明が完了します。
次に、Leanでの証明の外観を見てみましょう。
lemma first_step_adds (x y z carryIn carryOut : Bool) :
dfaStep (.carry carryIn) (x, y, z) = .carry carryOut ↔
x + y + carryIn = z + 2 * carryOut := by
revert x y z carryIn carryOut
decide
これはベースケースと同じレシピです。revertは5つのブール引数を目標に戻し、目標は次のようになります。
∀ x y z carryIn carryOut : Bool,
dfaStep (.carry carryIn) (x, y, z) = .carry carryOut ↔
x + y + carryIn = z + 2 * carryOut
decideは、同値の各辺を32の組み合わせそれぞれについて評価します。
最下位ビットの分割
def WholeRunAddition (x y z carryIn : Bool) (a b d k : Nat) : Prop :=
(x + 2 * a) + (y + 2 * b) + carryIn
= (z + 2 * d) + 2 * k
def SplitRunAddition (x y z carryIn : Bool) (a b d k : Nat) : Prop :=
∃ carryMid : Bool,
x + y + carryIn = z + 2 * carryMid ∧
a + b + carryMid = d + k
lemma least_significant_bit_split
(x y z carryIn : Bool) (a b d k : Nat) :
WholeRunAddition x y z carryIn a b d k ↔
SplitRunAddition x y z carryIn a b d k := by
...
これは計画のステップ4です。実行不変条件と同様に、同値の両辺はそれぞれ名前を持ち、読みやすくします。WholeRunAdditionは単語全体の方程式であり、SplitRunAdditionは分割された同じ方程式です。
lemmaは、単語全体の方程式が、中間桁上がりcarryMidが存在し、最下位ビットの方程式が成り立ち、残りのビットの方程式が成り立つ場合にのみ成り立つことを示しています10。このlemmaの形状はsplit_runを反映していますが、算術のみであり、DFAは含まれていません。
DFAを算術に変換する実行不変条件の両辺を接続するためにこのlemmaが必要です。split_run、first_step_adds、および帰納的仮説は、DFAを最初の列の方程式と残りの列の方程式に変換します。このlemmaは、それらが一緒に単語全体の方程式と同じことを言うことを示しています。
このlemmaを、算術を分解しながら数学的表記法を使用して分析します。WholeRunAdditionとSplitRunAdditionを展開すると、次の目標が残ります。
(x
+
2
⋅
a)
+
(y
+
2
⋅
b)
+
c
i
n
(z
+
2
⋅
d)
+
2
⋅
k
⟺
∃
c
_mid
:
x
+
y
+
c
i
n
z
+
2
⋅
c
_mid
∧
∃
c
_mid
:
a
+
b
+
c
_mid
d
+
k
\begin{aligned}
&(\colorbox{#fff2a8}{$\displaystyle x$} + 2 \cdot a) + (\colorbox{#fff2a8}{$\displaystyle y$} + 2 \cdot b) + c
_\mathrm{in}
(\colorbox{#fff2a8}{$\displaystyle z$} + 2 \cdot d) + 2 \cdot k \ &\qquad \iff \ &\qquad \exists, c
_\mathrm{mid}
:; \colorbox{#fff2a8}{$\displaystyle x + y + c
_\mathrm{in}} = \colorbox{#fff2a8}{$\displaystyle z$} + 2 \cdot c
_\mathrm{mid}
;\land \ &\qquad \phantom{\exists, c
_\mathrm{mid}
:;}\ \mathrm{a} + b + c
_\mathrm{mid}
\mathrm{d} + k
\end{aligned}
xx, yy, zzは3行の最下位ビットであり、aa, bb, ddは残りのビットの値、kkは残りのビットの桁上がり項です。
単語全体の方程式は、最下位ビットの方程式と残りのビットの方程式に分割されます。
[図:最下位ビットの分割。x, y, zは最下位ビット、a, b, dは残りのビットの値、cinは最初の列への桁上がり、cmidは最初の列と残りの間の桁上がり、kは桁上がり出力項です。単語全体の方程式は、最下位ビットの方程式と残りのビットの方程式の組み合わせと同じです。]
目標に戻ると、WholeRunAdditionとSplitRunAdditionが同じことを言っていることを示す必要があります。WholeRunAdditionは単純な線形方程式ですが、SplitRunAdditionには存在量化子と連言があります。SplitRunAdditionを線形方程式に変換できれば、2つの線形方程式が等しいことを示して目標を閉じることができます。
例を1つずつ分析します。
まず、xxとyyが1で、zzとcinが0の場合を考えます。これは、1+1=0、cout=1となる列です。
[図:最下位ビットの分割。x=1, y=1, z=0, cin=0の場合。単語全体の方程式は、最下位ビットの方程式と残りのビットの方程式の組み合わせと同じです。]
値を代入すると、次のようになります。
(1
+
2
⋅
a)
+
(1
+
2
⋅
b)
+
0
(0
+
2
⋅
d)
+
2
⋅
k
⟺
∃
c
_mid
:
1
+
1
+
0
0
+
2
⋅
c
_mid
∧
∃
c
_mid
:
a
+
b
+
c
_mid
d
+
k
\begin{aligned}
&(\colorbox{#fff2a8}{$\displaystyle 1$} + 2 \cdot a) + (\colorbox{#fff2a8}{$\displaystyle 1$} + 2 \cdot b) + \colorbox{#fff2a8}{$\displaystyle 0$} = (\colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot d) + 2 \cdot k \ &\qquad \iff \ &\qquad \exists, c
_\mathrm{mid}
:; \colorbox{#fff2a8}{$\displaystyle 1 + 1 + 0$} = \colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot c
_\mathrm{mid}
;\land \ &\qquad \phantom{\exists, c
_\mathrm{mid}
:;}\ \mathrm{a} + b + c
_\mathrm{mid}
\mathrm{d} + k
\end{aligned}
右辺では、最下位ビットの方程式は2 = 2⋅cmid2 = 2 \cdot c
_\mathrm{mid}となり、これを満たすcmidの値は1のみです。したがって、存在量化子を削除し、cmidに1を代入できます。
(1
+
2
⋅
a)
+
(1
+
2
⋅
b)
+
0
(0
+
2
⋅
d)
+
2
⋅
k
⟺
a
+
b
+
1
d
+
k
\begin{aligned}
&(\colorbox{#fff2a8}{$\displaystyle 1$} + 2 \cdot a) + (\colorbox{#fff2a8}{$\displaystyle 1$} + 2 \cdot b) + \colorbox{#fff2a8}{$\displaystyle 0$} = (\colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot d) + 2 \cdot k \ &\qquad \iff \ &\qquad a + b + \colorbox{#fff2a8}{$\displaystyle 1$} = d + k
\end{aligned}
左辺では、すべての項が偶数になります。定数を集めると2+2⋅a+2⋅b
2⋅d+2⋅k2 + 2 \cdot a + 2 \cdot b = 2 \cdot d + 2 \cdot kとなり、両辺を2で割ると次のようになります。
1
+
a
+
b
d
+
k
⟺
a
+
b
+
1
d
+
k
\begin{aligned}
&\colorbox{#fff2a8}{$\displaystyle 1 + a + b = d + k$} \ &\qquad \iff \ &\qquad a + b + 1 = d + k
\end{aligned}
両辺は同じことを言っているので、このケースは成り立ちます。
次に、列が加算されないケースを取ります。xxは1で、yy、zz、cinは0です。
[図:最下位ビットの分割。x=1, y=0, z=0, cin=0の場合。単語全体の方程式は、最下位ビットの方程式と残りのビットの方程式の組み合わせと同じです。中間桁上がりcmidは、1+0+0が奇数であり、0+2*cmidが偶数であるため、最下位ビットの方程式を満たしません。]
値を代入すると、次のようになります。
(1
+
2
⋅
a)
+
(0
+
2
⋅
b)
+
0
(0
+
2
⋅
d)
+
2
⋅
k
⟺
∃
c
_mid
:
1
+
0
+
0
0
+
2
⋅
c
_mid
∧
∃
c
_mid
:
a
+
b
+
c
_mid
d
+
k
\begin{aligned}
&(\colorbox{#fff2a8}{$\displaystyle 1$} + 2 \cdot a) + (\colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot b) + \colorbox{#fff2a8}{$\displaystyle 0$} = (\colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot d) + 2 \cdot k \ &\qquad \iff \ &\qquad \exists, c
_\mathrm{mid}
:; \colorbox{#fff2a8}{$\displaystyle 1 + 0 + 0$} = \colorbox{#fff2a8}{$\displaystyle 0$} + 2 \cdot c
_\mathrm{mid}
;\land \ &\qquad \phantom{\exists, c
_\mathrm{mid}
:;}\ \mathrm{a} + b + c
_\mathrm{mid}
\mathrm{d} + k
\end{aligned}
今回は、最下位ビットの方程式は1 = 2⋅cmid1 = 2 \cdot c
_\mathrm{mid}であり、左辺が奇数で右辺が偶数であるため、cmidのどの値もこれを満たしません。したがって、同値の右辺は偽です。同値の左辺は次のようになります。
1
+
2
⋅
a
+
2
⋅
b
2
⋅
d
+
2
⋅
k
1 + 2 \cdot a + 2 \cdot b = 2 \cdot d + 2 \cdot k
これも片側が奇数で片側が偶数なので偽です。両辺が偽であるため、このケースは成り立ちます。
残りの14ケースも同様です。xx、yy、cinの合計がzzと同じパリティを持つ場合、1つのcmidが最下位ビットの方程式を満たし、残りの方程式は2で割った後に一致します。パリティが異なる場合、両辺は偽です。これにより、証明が完了します。
2番目のケースは、算術側でデッド状態がどのように現れるかです。DFA側では、パリティが間違った列は実行をデッド状態に送るため、桁上がり状態で終了することはありません。算術側では、同じ列は同値の両辺を偽にするため、別のケースは必要ありません。
次に、Leanでの証明の外観を見てみましょう。
lemma least_significant_bit_split
(x y z carryIn : Bool) (a b d k : Nat) :
WholeRunAddition x y z carryIn a b d k ↔
SplitRunAddition x y z carryIn a b d k := by
cases x <;> cases y <;> cases z <;> cases carryIn <;
simp [WholeRunAddition, SplitRunAddition] <;
omega
<;>コンビネータは、左側のタクティックによって生成されたすべての目標に対して右側のタクティックを実行します。したがって、cases x <;> cases yはxで目標を分割し、次に生成された2つの目標それぞれをyで分割します。4つのcasesの連鎖は16の目標を生成します。各目標は4つのビットの組み合わせの1つに対応します。次に、simpが残ったものに対して実行され、omegaがsimpが残したものの後に実行されます。
ここではsimpが実行するステップを詳しく見ていきませんが、以前に見たことがあります。simpは各ケースで1つの目標を残します。これらの各ケースは、分析した2つの例のいずれかの形状を取ります。
carryMidの解が存在する場合、simpは線形方程式の同値性を残します。これは、上記の最初の例の目標です。
1 + 2 * a + (1 + 2 * b) = 2 * d + 2 * k ↔
a + b + 1 = d + k
carryMidの解が存在しない場合、SplitRunAdditionは偽であり、p ↔ Falseは¬pと同じなので、simpはWholeRunAdditionの否定を残します。これは、上記の2番目の例の目標です。
¬ (1 + 2 * a + 2 * b = 2 * d + 2 * k)
simpは、書き換えエンジンであり算術ソルバーではないため、それ以上進むことはできません。一方の式がもう一方の式の2倍であることや、奇数が偶数と等しくなることはないことに気づきません。ここで、自然数と整数上の線形算術の決定手続きであるomegaが登場します。
omegaは矛盾によって目標を証明します。つまり、目標が偽であると仮定し、変数のどの値もそれから導かれる方程式や不等式を満たすことができないことを示します。最初の目標では、最初の方程式は2倍された2番目の方程式であり、したがってa、b、d、kのどの値も一方の辺を真にし、もう一方を偽にすることはできません。2番目の目標では、方程式は片側に奇数、もう片側に偶数があり、したがってどの値もそれを真にすることはできません。omegaは残りの14の目標も同様に閉じ、これによりleast_significant_bit_splitの証明が完了します。
まとめ
lemma run_invariant (wLE : List Sigma3) (carryIn carryOut : Bool) :
RunEndsWithCarry carryIn wLE carryOut ↔
WordAddsWithCarry carryIn wLE carryOut := by
induction wLE generalizing carryIn with
-- base case
| nil => ...
-- inductive step
| cons column columnsLE induction_hypothesis => ...
ヘルパーlemmaが配置されたので、実行不変条件の帰納的ステップに戻ることができます。計画の4つのステップに従って証明します。最初の3つは同値の左辺のDFAを算術に変換し、4つ目は両辺の算術が同じことを言うことを示します。まず非形式的な議論をレビューし、次にLeanでの形式化を見てみましょう。
帰納的ステップでは、単語はcolumn :: columnsLEなので、目標は単語に対する実行不変条件です。
RunEndsWithCarry carryIn (column :: columnsLE) carryOut ↔
WordAddsWithCarry carryIn (column :: columnsLE) carryOut
また、帰納的仮説を使用できます。これは、残りの列に対する実行不変条件です。
∀ carryIn,
RunEndsWithCarry carryIn columnsLE carryOut ↔
WordAddsWithCarry carryIn columnsLE carryOut
carryInの∀はgeneralizing carryInによるものです。これは、帰納的仮説が目標のcarryInだけでなく、すべての開始桁上がりに対して成り立つことを意味します。
ステップ1は実行の分割です。目標の左辺はsplit_runの左辺なので、lemmaの右辺に置き換えることができます。
(∃ carryMid,
dfaStep (.carry carryIn) column = .carry carryMid ∧
RunEndsWithCarry carryMid columnsLE carryOut) ↔
WordAddsWithCarry carryIn (column :: columnsLE) carryOut
ステップ2は、実行の最初のステップを算術に変換することです。columnの3つのビットをx、y、zとします。連言の最初の部分はfirst_step_addsの左辺なので、加算器方程式に置き換えることができます。
(∃ carryMid,
x + y + carryIn = z + 2 * carryMid ∧
RunEndsWithCarry carryMid columnsLE carryOut) ↔
WordAddsWithCarry carryIn (column :: columnsLE) carryOut
ステップ3は、残りの列に対する実行を算術に変換することです。連言の2番目の部分は、carryMidを開始桁上がりとして使用した帰納的仮説の左辺なので、右辺に置き換えることができます。
(∃ carryMid,
x + y + carryIn = z + 2 * carryMid ∧
WordAddsWithCarry carryMid columnsLE carryOut) ↔
WordAddsWithCarry carryIn (column :: columnsLE) carryOut
これがgeneralizing carryInが必要だった理由です。残りの列に対する実行はcarryMidから始まるため、carryInとは異なる場合があります。
DFAは目標から削除され、算術のみが残ります。残っているのは、両辺の算術をleast_significant_bit_splitに一致する形状にすることだけです。
目標は次のようになります。
(∃ carryMid,
x + y + carryIn = z + 2 * carryMid ∧
WordAddsWithCarry carryMid columnsLE carryOut) ↔
WordAddsWithCarry carryIn ((x, y, z) :: columnsLE) carryOut
これは計画のステップ4です。目標は、両辺が逆転したleast_significant_bit_splitの形状になっています。同値は両方向に成り立つため、lemmaは目標を閉じます。これにより、帰納的ステップの証明が完了し、実行不変条件の証明も完了します。
次に、Leanでの帰納的ステップの証明の外観を見てみましょう。
lemma run_invariant (wLE : List Sigma3) (carryIn carryOut : Bool) :
RunEndsWithCarry carryIn wLE carryOut ↔
WordAddsWithCarry carryIn wLE carryOut := by
induction wLE generalizing carryIn with
-- base case
| nil => ...
-- inductive step
| cons column columnsLE induction_hypothesis =>
obtain ⟨x, y, z⟩ := column
rw [split_run]
simp_rw [first_step_adds, induction_hypothesis]
simp only [
WordAddsWithCarry,
row1LE_cons, row2LE_cons, row3LE_cons,
List.length_cons, pow_succ'
]
rw [Nat.mul_left_comm]
exact
Iff.symm
(least_significant_bit_split
x y z carryIn
(row1LE columnsLE)
(row2LE columnsLE)
(row3LE columnsLE)
(carryOut * 2 ^ columnsLE.length))
obtain ⟨x, y, z⟩ := columnは、列を3つのビットに分解します。これは、通常のプログラムでのlet (x, y, z) = columnのようなものです。
rw [split_run]はステップ1です。rwは目標内のlemmaの左辺を探し、右辺に置き換えます。
simp_rw [first_step_adds, induction_hypothesis]はステップ2と3です。simp_rwはrwに似ていますが、rwができない∃の下でも書き換えることができます。
この時点で、DFAは目標から削除され、算術のみが扱われます。残っているのは、方程式をleast_significant_bit_splitに一致する形状にすることだけです。
目標は次のようになります。
(∃ carryMid,
x + y + carryIn = z + 2 * carryMid ∧
WordAddsWithCarry carryMid columnsLE carryOut) ↔
WordAddsWithCarry carryIn ((x, y, z) :: columnsLE) carryOut
simp only行は最初に目標の同値の各辺でWordAddsWithCarryを展開しますが、目標が大きすぎるため、ここでは同値の右辺にのみ焦点を当てます。したがって、simp onlyは最初に書き換えます。
WordAddsWithCarry carryIn ((x, y, z) :: columnsLE) carryOut
次の形式に。
row1LE ((x, y, z) :: columnsLE) +
row2LE ((x, y, z) :: columnsLE) + carryIn =
row3LE ((x, y, z) :: columnsLE) +
carryOut * 2 ^ ((x, y, z) :: columnsLE).length
次に、rowNLE_cons lemmaを使用して、右辺の単語から最初の列を分割します。
x + 2 * row1LE columnsLE + (y + 2 * row2LE columnsLE) + carryIn =
z + 2 * row3LE columnsLE +
carryOut * 2 ^ ((x, y, z) :: columnsLE).length
rowNLE_cons lemmaは、column :: columnsLEの行の値は、列のビットとcolumnsLEの同じ行の値の2倍であると述べています。
最後に、List.length_consとpow_succ'を使用して桁上がり出力項についても同様のことを行います。
x + 2 * row1LE columnsLE + (y + 2 * row2LE columnsLE) + carryIn =
z + 2 * row3LE columnsLE + carryOut * (2 * 2 ^ columnsLE.length)
List.length_consは、column :: columnsLEがcolumnsLEより1つ長いことを示し、pow_succ'は2^{n+1}を2 * 2^nに書き換えます。
ここで、least_significant_bit_splitに一致させるために、修正する必要がある小さなことが1つだけあります。lemmaには2 * kという項があり、ここでkは残りの列の桁上がり出力項を表します。したがって、2 * (carryOut * 2 ^ columnsLE.length)を期待していますが、carryOut * (2 * 2 ^ columnsLE.length)があります。
rw [Nat.mul_left_comm]がこれを修正します。Nat.mul_left_commはa * (b * c) = b * (a * c)と述べているため、これで書き換えると、同値の右辺のcarryOutと2が入れ替わります。
x + 2 * row1LE columnsLE + (y + 2 * row2LE columnsLE) + carryIn =
z + 2 * row3LE columnsLE + 2 * (carryOut * 2 ^ columnsLE.length)
目標は、同値が反転したleast_significant_bit_splitの形状になっています。
証明の最終ステップとして、exactタクティックを使用して項モードに切り替えます。これは、証明を完了するために、目標の型に一致する項を構築する必要があることを意味します。同値の左辺を含む完全な目標は非常に長いため、ここでは完全性のためにのみ示します。
(∃ carryMid,
x + y + carryIn = z + 2 * carryMid ∧
row1LE columnsLE + row2LE columnsLE + carryMid =
row3LE columnsLE + carryOut * 2 ^ columnsLE.length) ↔
x + 2 * row1LE columnsLE + (y + 2 * row2LE columnsLE) + carryIn =
z + 2 * row3LE columnsLE + 2 * (carryOut * 2 ^ columnsLE.length)
列の3つのビット、carryIn、およびcolumnsLEの行の値と桁上がり出力項を呼び出して必要な項を構築し、結果をIff.symmでラップして同値の辺を反転させます。
Iff.symm
(least_significant_bit_split
x y z carryIn
(row1LE columnsLE)
(row2LE columnsLE)
(row3LE columnsLE)
(carryOut * 2 ^ columnsLE.length))
目標の型に一致するこの項を自分で納得させる必要はありません。Leanに任せることができます。
BRB^R は正規である
run_invariant定理を証明したので、BRB^Rが正規であることを証明するために使用できます。これは2つのステップで行います。まず、加算器DFAがBRB^Rを受理することを示し、次にそれがBRB^Rを正規にすることを示します。
加算器DFAはBRB^R を受理する
最初のステップは次の定理です。
theorem adderDFA_accepts_B_reverse : adderDFA.accepts = B.reverse := by
...
前述のように、adderDFA.acceptsとB.reverseは両方ともセットです。2つのセットが等しいということは、それらが同じメンバーを持つことを意味します。したがって、定理の方程式はすべての単語wLEに対して次のことと同等です。
wLE ∈ adderDFA.accepts ↔ wLE ∈ B.reverse
adderDFA.startは.carry falseであり、.carry falseは唯一の受理状態であるため、adderDFA.acceptsのメンバーシップルールは次のようになります。
{ wLE | RunEndsWithCarry (carryIn := false) wLE (carryOut := false) }
したがって、
wLE ∈ adderDFA.accepts ↔
RunEndsWithCarry (carryIn := false) wLE (carryOut := false)
そして、B.reverseのメンバーシップルールは次と同等です8。
{ wLE | WordAddsWithCarry (carryIn := false) wLE (carryOut := false) }
したがって、
wLE ∈ B.reverse ↔
WordAddsWithCarry (carryIn := false) wLE (carryOut := false)
したがって、次のことを証明する必要があります。
RunEndsWithCarry (carryIn := false) wLE (carryOut := false) ↔
WordAddsWithCarry (carryIn := false) wLE (carryOut := false)
しかし、これは両方の桁上がりをfalseにインスタンス化したrun_invariant定理にすぎません。これはすでに証明されています。
run_invariant (carryIn := false) wLE (carryOut := false)
これにより、adderDFA_accepts_B_reverse定理の証明が完了します。
Leanの証明はほぼ同じステップを踏みますが、約12行の長さなので、ここでは詳細には触れません。しかし、コードGitHubをチェックして自分でステップを踏むのは良い考えです。これにより、証明がインタラクティブに展開される様子を確認できます。
受理から正規性へ
adderDFA_accepts_B_reverse定理を手に入れたので、BRB^Rが正規であることを示すことができます。定理は単にB.reverse.IsRegularのステートメントです。
theorem B_reverse_isRegular : B.reverse.IsRegular :=
...
:=の後にbyがないため、これは項モード証明です。つまり、タクティックがそれを構築するのではなく、定理の型を直接記述する必要があります。前述のように、IsRegularは、有限状態型とそれらの状態上のDFAが存在し、言語を受理することを示しています。
def IsRegular (L : Language T) : Prop :=
∃ σ [Fintype σ], ∃ M : DFA T σ, M.accepts = L
したがって、有限状態型、それらの状態上のDFA、およびDFAがB.reverseを受理することを示す必要があります。これは、山括弧の間にリストすることによって行います。
theorem B_reverse_isRegular : B.reverse.IsRegular :=
⟨DFAState, inferInstance, adderDFA, adderDFA_accepts_B_reverse⟩
DFAStateは状態の型であり、adderDFAはDFAです。inferInstanceは、DFAStateのFintypeインスタンスをLeanに検索させます。これは、Fintypeを派生させたときに生成されました。インスタンスは型のすべての値のリストであり、リストが完全であることの証明も含まれています。最後の部分は、DFAがB.reverseを受理することの証明であり、これは証明した定理です。
BB は正規である
BB言語が正規であることを証明するために出発しましたが、ついにその位置に到達しました。必要なのは、正規言語の逆転に対する閉包だけです。MathlibはこれをLanguage.isRegular_reverse_iffとして提供しており、その型は次のとおりです。
L.reverse.IsRegular ↔ L.IsRegular
ここで、Lは汎用Mathlib.Computability.Languageです。
同値は両方向に成り立ち、B.reverse.IsRegularの証明があるので、L.reverse.IsRegular → L.IsRegularという含意を使用してBBが正規であることを証明できます。
Leanでの形式化は次のように記述されます。
theorem B_isRegular : B.IsRegular :=
Language.isRegular_reverse_iff.mp B_reverse_isRegular
mpはmodus ponensの略です。ここではmpフィールドを使用して、型L.reverse.IsRegular ↔ L.IsRegularを持つ定理を、型L.reverse.IsRegular → L.IsRegularを持つ関数に変換します。
この関数にB_reverse_isRegularを渡すと、型B.IsRegularの項が返され、これはBが正規であることの証明です。
結び
BB言語が正規であることを示すために出発しましたが、Leanが受け入れる証明ができました。コードGitHubをチェックしてコンパイルすることで、自分で確認できます。
証明とともに、DFAの形式的に検証された実装も作成しました。実装はLeanで行われ、これはCにコンパイルされるため非常に高速ですが、Rustのような別の言語でDFAを実装し、仕様と証明のみをLeanに保持することもできます11。
見てきたように、形式証明には通常スキップする多くの詳細が必要でした。加算器DFAの場合、比較的簡単でしたが、このような証明を書くのは大変な作業でした。その動作を単純な線形方程式を解くまで算術に変換できました。
実際のシステムの形式証明は、書くのがはるかに困難です。たとえば、分散システムは、時間とともにシステムがどのように変化するかを推論する時相論理を必要とすることが多く、暗号プリミティブは独自の証明スタイルを必要とすることがよくあります12。
幸いなことに、2026年には機械が証明を作成できます。最先端のコーディングエージェントは、私たちのもののようなワンショット証明を行うことができ、より複雑な証明に取り組む能力も急速に向上しています。同時に、Leanは複雑な証明をより効率的に書けるように改善されています13。これらを組み合わせることで、形式検証のコストは急速に低下しています。
コーディングエージェントがあれば、人間は仕様が正しいことを確認するだけでよく、機械生成の実装と証明はブラックボックスとして扱えると考えるのは魅力的です。仕様と証明の間のインターフェースはそれほど明確ではなく、仕様を理解するために証明を見る必要があることが多いため、私はこれに懐疑的です。そして、証明で奇妙なものを見つけた場合、それは何かが間違っている良い兆候です。
私たちの証明にはこの小さな例があります。実行不変条件は、BBの定義では言及されていなかった桁上がり出力項を導入しました。それは仕様のバグではありませんでしたが、隠された要件を表面化しました。つまり、単語の3行すべてが同じ長さであるため、BBはオーバーフローする可能性のある合計を排除します。
私の感覚では、形式的に検証された実装をブラックボックスとして扱い始めることができるかもしれませんが、将来的には機械生成された証明を理解できることが重要です。コーディングエージェントによって生成された証明は複雑になる可能性があるため、これは課題です。
いずれにせよ、形式手法はより高レベルの抽象化で作業することを可能にし、自動化をさらに解き放つことで生産性を向上させるため、ソフトウェアエンジニアリングの未来は非常にエキサイティングだと思います。
- ビットリストの解釈を区別するために
LE/BE規約を使用する代わりに、リトルエンディアンとビッグエンディアンのリストの個別の型を導入して、混同を防ぐことができます。ただし、これにはネイティブリストですでに利用可能な多くの定理を再導出する必要があるため、このスコープのプロジェクトではそれだけの価値はありません。↩︎ - コレクションとしてのセットは、
Std.HashSetおよびStd.TreeSetとして利用可能です。↩︎ - 決定手続きは、命題を評価し、それが成り立つ場合は
true、そうでない場合はfalseを返す関数です。命題が2つのDFAState値間の等式であり、以前にDFAStateのDecidableEqを派生させたため、dfaStep例ではこれが自動的に利用可能になります。↩︎ - 型チェッカーでの評価は終了が保証されています。なぜなら、Leanは終了が証明されない限り関数を拒否するからです(自動的または作成者によって)。定義は明示的にオプトアウトできますが、その場合、型チェッカーはそれを展開できないため、証明で評価できません。↩︎
- 実際の項は
of_decide_eq_true (id (Eq.refl true))です。idは、decideが引数を構築してからof_decide_eq_trueを適用するため、Eq.refl trueがtrue = trueの証明ではなくdecide p = trueの証明として意図されていることを記録する必要があるため、decideが必要とする型アスクリプションです。証明が手書きの場合、期待される型はexampleシグネチャからわかっているので、idは省略できます。↩︎ - Mathlibの定義の簡略化されたバージョン。実際の定義は
Tの宇宙を明示し、有限性を∃ σ : Type, ∃ _ : Fintype σと記述しています。↩︎ - 実際のMathlib定義は少し冗長なので、ここでは引用しません。↩︎
- 単語のリトルエンディアン解釈とその逆転のビッグエンディアン解釈の等価性に関する非形式的な議論(
rowNBE w.reverse = rowNLE w)は、仕様ファイルで形式化されていますが、基本的に単なる事務処理であるため、投稿には含めていません。↩︎ ↩︎ - 前述のように、lemmaステートメントでは簡潔にするためにブール値から
.toNatを削除しました。↩︎ - 省略のために
.toNatを削除しました。↩︎ - 例えば、AeneasはRustプログラムをLeanに翻訳して、その動作を検証できるようにします。↩︎
- 例:ゲームベースまたはシミュレーションベースの証明は形式化が困難です。ゲームベースの証明は、プロトコルへの攻撃を、攻撃者のオッズをわずかにしか変更しない一連の小さなステップとして書き換えます。ShoupのSequences of Gamesを参照してください。シミュレーションベースの証明は、攻撃者が実際のプロトコルから学ぶことができるものは何でも、それなしで生成できたことを示します。LindellのHow to Simulate Itを参照してください。↩︎
- 詳細については、Leonardo de Mouraのブログ投稿Proof Assistants in the Age of AIおよびSignal Shot: The Platform Is Readyを参照してください。↩︎