2014年12月06日

Theorem Prover Advent Calendar 6日目:Coqでの前向き証明を始めるまで

タイトルの通り、これはTheorem Prover Advent Calendarの6日目のための記事である。


MizarやIsarをご存じだろうか?
Mizarは数学的な体系について性質を証明し、その証明が正しいことを機械で確認する、というのが目的である。
そのため、比較的証明を自然言語(英語)で書いたものに似せている。
実際の証明は、「こういう仮定がある。これを変形するとこうである。この補題からこういうことが言える。これはゴールと等価であるため、成立することが言える。」のように、仮定から前向きに証明を行うことがよく行われる。
この前向き証明だが、比較的読みやすいのが特徴である。
Isarは、このMizarの書き方をIsabelle上で使えるようにしたシステムである。
どうやら、証明が終わった後に前向き証明に書き換えるということを行われることも多いらしい。


さて、Isabelleに実装されていることをCoqで実装されていないと言うことがあろうか。
いやたくさんあるけど。
しかもかなりほしいものばっかりだけど。
スレッジハンマーとか。
ただし、今回紹介するこの機能に関しては、普通に論文も出て、さらに現在のCoqに実装されている。
マニュアルの11章を見よう。
ここからはそれを見ながらの話になる。


以上、前置き終わり。
ところで、前向きと書いたが、この機能自体は宣言的(declarative)という方が一般的だ。
すまないがタイトル変えるの面倒なので流して欲しい。
そして、マニュアルを書いている人はどうやら数学的証明と呼びたいようだ。
もう何でもいいや。

とりあえずここで書いている「数学的証明言語」とは、本来の証明の記述よりも弱いものらしい(11.1.3)。
記述時に使う自動証明がうまくいかなかった場合に、不完全な(普段で言うadmitで飛ばしたような)証明が書けてしまう。
この方向での証明で、なぜ不完全なものを書けるようにしたのか首を傾げるのだが、著者としては初学者が容易に学べるようにしたい、等の意図があったらしい。
エラーと切り替えられるようにした方が良いと思うのだが(admitにそういう機能が欲しい)。
ちなみに、不完全な証明を書くと、コマンドを打つ度に何度も何度も「これが証明できないよ」と言ってくる。

この機能の、標準的(legacy)Coqとの違いは大体以下の通り(上も含めている)。
  • focusという機能で「今から証明するものを一つに絞る」機能がある。表示範囲が圧迫されない意味では悪くなさそうな機能だ。

  • 証明できないようなものを書いても「後で埋められるようにwarning出すだけにしている」。(上に書いた)

  • 通常のtacticはコマンドの特定の位置に書くか、escapeコマンドで一旦通常モードに戻して使わせる。特定の場所とは、例えばそのときに成り立つ命題を作る際のusingの直後。ちなみに、by 変数かusing tacticで進めるのが主だが、何も書かないとfirst-orderで解くらしい(11.3.14)。これで解けないと「不完全な証明」となる。

  • 変数名などの自動生成は可能だが、必ず_から始まり、次のコマンドの終了後消える(11.2.1)。これは変数名の衝突を避けることと、名前つけるのが面倒なことのバランス取れてるかもしれない。必要なら名前をつけろ、というのも理解できる。


想定環境も書いてあるが、普通にCoqを使う範囲ならば問題なさそうだ。
coqtopやcoqide、Proof-Generalもある。
他にもあるが、今回はちょっと放っておこう。
例えばPCoqが使えないと書いてあるけれど、そもそも今まともに使えるのかわからない(バージョン1.4が2003年2月に出ている。2013年ではない。私が大学に入る直前だ。)。


内容に入ろう。
文法が11.2に載っている。
全体としては証明構造を記述するのが主で、ほとんど対応するのは基本的なtacticだ。
命題などをより具体的に書かせている点が違う。
基本的に命題を具体的に書くが、ゴールだけは何度も書かなくて良いように特殊な名前としてthesisが使えるらしい。
"thesis"はみんなだいすき学位論文・・・という意味もあるが、ここでは主張する命題のこと(辞書を見よう)。

文法は読み慣れていないと分かりづらいので、とりあえず動かすのが定石。
11.3で機能を説明しているので、見ていこう。

まず「証明の始め方と終わり方」が書いてある。
そしていきなりAnormalyを出す。しかも"Please report"が出るヤツだ。(実装のバグの可能性が高いから報告してくれ、と言うメッセージ。実装をいじったりすると出る)

え??

続いて「proofコマンドは残りが一つじゃないと使えないんだ」といって3つのサブゴールがある例を使う。
ここでもAnormalyを出す。

おい。


エラーメッセージ作れよ。

なんでこんなのがマニュアルに載るんだろう。

そんな愚痴を言っても始まらないので、実行してみる。

Welcome to Coq 8.4pl4 (June 2014)

Coq < Goal True.
1 subgoal

  ============================
   True

Unnamed_thm < proof.
1 focused subgoal (unfocused: 0)

  ============================
   True

Unnamed_thm < thus thesis. (* first-orderで解いている *)
No more subgoals.

Unnamed_thm < end proof.
No more subgoals.

Unnamed_thm < Qed.
Anomaly: Cannot print a raw proof_instr. Please report.

Unnamed_thm <

うん。マニュアル通りの動き・・・え??

Unnamed_thm <


証明が終わってない。

たしかQedの直後は「証明に使ったスクリプトを出す」はず。
ちなみに証明項はできていて、Show Proofで見られる。

Unnamed_thm < Show Proof.
((fun _fact : True => _fact) I)

うん、まあ若干不思議なことをやってるけど、別に問題なさそうだ(おそらく特徴の一つの、自動生成された変数の使い切りのために関数抽象になっているのだと思う)。
だがエラーだ。
エラー対策しろよ。マジメに。

考えてみると、この機能で書いた証明、今までの記述と同じ分けがない。
それで証明の出力関数が死んでるわけだ。

そう考えると、Qedの直後の出力を抑制できれば大丈夫なはずだが、マニュアルを見てもそんなコマンドは見つからない。
そして、この機能の説明がある章、よく見ると「どの例もQedまで行ってない」のだ。

ふざけんな。

調べてみたが、唯一見つかったのが、出力をほぼ完全に抑制するSet Silentコマンド。
あとでUnsetすれば大丈夫だろう、と高をくくって実行。こんな感じになった。

Unnamed_thm < Qed.
Anomaly: Cannot print a raw proof_instr. Please report.

Unnamed_thm < Set Silent.

Unnamed_thm < Qed.

Coq < Unset Silent. (* 左側が変わってるのでうまくいったっぽい *)

Coq < Print All.
 >>>>>>> Library Top
Unnamed_thm : True


Coq < (* Goalだから勝手につけられた名前だができている *)



ようやく始められる状態まで来たが、さすがに今回これ以上書こうという気力が湧かない(日をまたぎかねないというのもある)。
なので、この話はここまでと言うことにしておく。
次回をやる気力が湧けば書くかもしれないが、とりあえずこの問題を回避できれば後は書かれている例題を元に少し試してみるだけなので、それぞれで試すこともできるだろう。
まだ紹介するような機能じゃなかった。

腐ってやがる!早すぎたんだ!

なんてね。
posted by chiguri at 22:06| Comment(1) | 雑多