基本概念と実装

混合コンテキストが、次のレベルで提供される。

  1. ライブラリ
  2. パッケージ
  3. モジュール
  4. 名前空間
  5. セクション
  6. 関数・定理(のボディブロック)
  7. 入れ子ブロック(by, doなど)

これらの組織化機構〈organizing mechanism / feature〉は独立ではないし、一様でもない。構成される混合コンテキストは恣意的に区切られた〈fenced〉テレスコープになる。

コンテキスト/テレスコープの基本は名前の集合で、名前は:

  1. 宣言定数名: 代入〈割り当て〉ができない型付きの名前、axiom で導入。
  2. イミュータブル変数名: 代入〈割り当て〉が一度だけできる型付きの名前 variable で導入。引数リストでも導入される。
  3. 割り当て済み名前: イミュータブル変数名に割り当てを行ったもの。変更はできない。def, let, have で導入。
  4. ミュータブル変数名: 値の変更ができる名前、let mut で導入。

名前〈ラベル〉の型〈プロファイル〉宣言(命題宣言含む)と、型宣言済みの名前への項〈ボディ〉割り当てがテレスコープの中心。他に、定義的等式と項書き換え規則がコンテキストに入る。

関数のコンテキスト〈環境〉と引数、定理のコンテキストと前提の境界は曖昧で、どうとでも移動できる。構文的正規形として、コンテキストを最小化したパック形式〈カリー化形式〉と、コンテキストを最大化したアンパック形式〈アンカリー化形式〉がある。

名前達は、名前空間階層のなかに配置される。名前構造の操作に、open, export, namespace, section が使われる。Cリンケージとの名前のやり取りには、@[extern "名前"]、@[export 名前]。importはモジュールの操作だが、そのモジュールで定義された/取り込まれた名前の操作になる。

特定の機能性を持つ名前(関数名、定理名、型名/命題名)を探すのは困難。この困難が大きな障害になっている。

次は名付けの例:

namespace MyArith

def one_plus_one_equals_two : Prop := 1 + 1 = 2
def one_plus_one_equals_three : Prop := 1 + 1 = 3
def x_plus_y_equals_ten (x y :Nat) : Prop := x + y = 10

end MyArith
#check MyArith.one_plus_one_equals_two
#check MyArith.x_plus_y_equals_ten

関数や定理は、名前で呼び出して使う。呼び出し時に、実引数を渡すかも知れない。関数を呼び出せば、戻り値と戻り型〈return type〉が得られる。得られた戻り値は名前に束縛されるかも知れない〈let, have〉。

宣言定数〈公理〉や関数〈定理〉から作られる項とは別に、コマンドとコマンドスクリプトがある。証明生成コマンドには、FRコマンド〈forward reasoning command〉とBRコマンド〈backward reasoning command〉がある。BRコマンドをタクティクとも呼ぶ。

リーズニングコマンドが相手にするのは、判断と質問〈問題 | ゴール〉が混じった証明状態〈proof state〉。コマンドは証明状態を遷移させる。証明状態の時間的遷移を空間的に描いた図をリーズニング図と呼ぶ。シーケント計算の証明図はリーズニング図である。

リーズニング図は、項を図示したストリング図や横棒図とは別物。しばしば混同される、無理もないが。

証明状態を遷移させるプログラムをリーズニング・コマンドスクリプトと言う。特にBRコマンド=タクティクから作ったスクリプトはタクティク・スクリプト。

判断と質問が混じった証明状態を混合証明状態という。混合証明状態の遷移を記述した図を混合リーズニング図という。混合リーズニング図はツリーとは限らない。

リーズニング図は180度回転する反転〈inversion | conversse〉がある。反転は双対性と関係がある。

項の図示とリーズニングの図示は混同される。その理由のひとつは、項の図はリーズニング図に変換して埋め込めるから。項のスクリプトのノードは、post-composition, pre-composition としてリーズニングコマンドになり、図のリーズニングノードになる。

Socket.leanを作ってみる(失敗)

まず、

$ git clone https://github.com/xubaiw/Socket.lean

$ cd Socket.lean

$ cat lean-toolchain
leanprover/lean4:nightly-2022-06-16

去年だと、「ふるっ!」と思う。

$ git branch
* main

$ git rev-parse main
9fc98bc24ccdb4471b2e38e94dccd18f75d2a293

これが確実なパッケージID。

$ elan toolchain list
leanprover-community/lean:3.23.0
leanprover-community/lean:nightly
leanprover-community/lean:stable
leanprover/lean4:nightly (default)
leanprover/lean4:nightly-2022-07-06
leanprover/lean4:nightly-2022-10-09
leanprover/lean4:nightly-2022-10-20
leanprover/lean4:nightly-2022-11-20
leanprover/lean4:nightly-2022-12-02
leanprover/lean4:nightly-2022-12-16
leanprover/lean4:nightly-2022-12-22
leanprover/lean4:nightly-2022-12-24
leanprover/lean4:nightly-2023-01-10
leanprover/lean4:nightly-2023-01-21
leanprover/lean4:stable
leanprover/lean4:v4.0.0-m5

leanprover/lean4:nightly-2022-06-16 はない。ウーム。とりあえず、手で lean-toolcain を書き換えてやってみるか。

$ mv lean-toolchain lean-toolchain.ORIG

$ echo leanprover/lean4:nightly-2022-07-06 > lean-toolchain

$ cat lean-toolchain
leanprover/lean4:nightly-2022-07-06

$ lake --version
Lake version 3.2.1 (Lean version 4.0.0-nightly-2022-07-06)

$ lean --version
Lean (version 4.0.0-nightly-2022-07-06, commit 38e1f6ba824b, Release)

ひと月弱新しいツールチェーンに無理くり置き換えた。

$ lean-build
error: unknown short option '-v'

ナニッ?! 昔のlakeには -v オプショナルがない。

$ alias lean-build-nov='lake build  |& tee $(date +%Y-%m-%d_%H-%M-%S).lake-build.log'

ビルド失敗。エラーログは:

> c:\Users\m-hiyama\.elan\toolchains\leanprover--lean4---nightly-2022-07-06\bin\leanc.exe -shared -o C:\Windows\System32\ws2_32.dll -Wl,--whole-archive C:\Windows\System32\ws2_32.dll -Wl,--no-whole-archive
> gcc -c -o .\build\native\ffi.o .\native\native.c -I c:\Users\m-hiyama\.elan\toolchains\leanprover--lean4---nightly-2022-07-06\include
error: stderr:
ld.lld: error: cannot open output file C:\Windows\System32\ws2_32.dll: Permission denied
clang: error: unable to remove file: Permission denied
clang: error: linker command failed with exit code 1 (use -v to see invocation)
error: external command c:\Users\m-hiyama\.elan\toolchains\leanprover--lean4---nightly-2022-07-06\bin\leanc.exe exited with status 1

起動コマンドを書くと:

  • leanc.exe -shared -o C:\Windows\System32\ws2_32.dll -Wl,--whole-archive C:\Windows\System32\ws2_32.dll -Wl,--no-whole-archive
  • gcc -c -o .\build\native\ffi.o .\native\native.c -I c:\Users\m-hiyama\.elan\toolchains\leanprover--lean4---nightly-2022-07-06\include
  • エラーメッセージは、ld.lld と clang から出ている。

分かること:

  • gccコマンドは起動可能。Clangがgcc互換モードでインストールされている。cc, gcc, clang のどれでも起動できる。
  • ld.lld.exe はClangではなくて、Leanツールチェーン側かも知れない。
  • lean.cexe は gcc と ld.lld を呼んでいるようだ。gccの実体はclang。
  • -o C:\Windows\System32\ws2_32.dll ここは無理がある。管理者モードで実行か。

しかし、C:\Windows\System32\ws2_32.dll は既存システムファイルだな。書き換えるのはこわい。

代表的Leanパッケージ

コントロール+クリック

  1. "Cli" : https://github.com/mhuisi/lean4-cli 非依存
  2. "leancolls" : https://github.com/jamesgallicchio/leancolls mathlib依存、ビルド失敗
  3. "advent" : https://github.com/odomontois/advent2022-lean mathlib依存、ビルド成功
  4. "CMark" : https://github.com/xubaiw/cmark.lean 非依存、Cソースあり、ビルド成功
  5. "Qq" : https://github.com/gebner/quote4 非依存、依存パッケージとしてビルド成功
  6. "mathlib" : https://github.com/leanprover-community/mathlib4.git std, Qq, aesop に依存、依存パッケージとしてビルド成功
  7. "aesop" : https://github.com/jlimperg/aesop stdに依存、依存パッケージとしてビルド成功
  8. "doc-gen4" : https://github.com/leanprover/doc-gen4 CMar, Unicode, Cli, lake, leanInk に依存
  9. "leanInk" : https://github.com/hargonix/leanink 非依存
  10. "Unicode" : https://github.com/xubaiw/unicode.lean 非依存
  11. "std" : https://github.com/leanprover/std4 非依存
  12. "LSpec" : https://github.com/yatima-inc/lspec 非依存
  13. "socket" : https://github.com/xubaiw/socket.lean 非依存、Cソースあり

Lakeマニフェストファイル

npmのpackage-lock.json相当が、Lakeマニフェストファイル。lean_packages/manifes.json と lake-manifest.json がある。注意すべきはマニフェストファイル自体のバージョンで、JSONファイルのトップレベルフィールドとしてバージョン番号が記入されている。

{
  "version": 4,
  "packagesDir": "./lake-packages",
  "packages": [...]
}

最近は、lake-manifest.json と lake-packages/ だろう。

lakefile.lean の require と重複情報になっている。どう処理するかが気になる。

コンテキストと拡張、いろいろ

我々は、様々なレベルのコンテキスト(ライブラリ、モジュール/セクション)を行為〈activity〉により拡張していくのだが、拡張のための行為は二種類しかない。

  1. 関数定義 (λΠ計算ベース)
  2. 帰納的型定義 (CICベース)

関数定義は def で、帰納的型定義は inductive 、これだけ。他のキーワード(例: theorem, structure)はシンタックスシュガー。

関数定義〈定理記述〉は、宇宙単相と宇宙多相がある。宇宙とカリー/ハワード対応は意識する。混合コンテキストには次が入る。

  1. 関数定義
    1. 計算項の型判断
    2. 関数名への計算項割り当て
    3. 定義的等式〈definitional equality〉
    4. 定義展開〈unfold〉書き換え規則
  2. 帰納的型定義
    1. 型名
    2. 型名名前空間
    3. コンストラクタ疑似関数(1つ以上、複数可能、0個なら空型)
    4. リカーサー

定理は証明ボディに名前を付けたもの。推論規則は定理なので、引数型=前提命題と戻り型=結論命題を持つ。推論規則の引数は、多くの場合命題ではなくて、証明/証拠である。証明項/証拠ラベル/定理名〈計算項/要素ラベル/関数名〉は交換可能である。

命題コネクティブ〈型演算子〉と証明コンビネータ〈計算コンビネータ〉は区别すべし。だが、命題型宇宙だと、Trueからの命題への証明が証明無関係〈proof irrelevance〉原理により本質的に1つしかないので、証明と命題の区别は困難である。

様々な引数形式

  • 名前付き引数〈named arguments〉と引数省略時値〈default value〉の指定
def mySub (left right :Nat) : Nat := left - right
#check mySub
#eval mySub (right := 3) (left := 5) --> 2

def mySub' (left :Nat) (right:Nat := 1) : Nat := left - right
#check mySub'
#eval mySub' (right := 3) (left := 5) --> 2
#eval mySub' (left := 5) --> 4
  • 暗黙引数: パターンマッチ/型推論で埋める引数
  • 型インスタンスパラメータ: 型クラスのインスタンス解決によって埋める引数。引数名省略可能。例: [ToString]
  • Two-dots「..」で残余明示引数〈missing explicit arguments〉。以下が例:
inductive Term where
  | var    (name : String)
  | num    (val : Nat)
  | add    (fn : Term) (arg : Term)
  | lambda (name : String) (type : Term) (body : Term)

def getBinderName : Term → Option String
  | Term.lambda (name := n) .. => some n
  | _ => none

def getBinderType : Term → Option Term
  | Term.lambda (type := t) .. => some t
  | _ => none
structure Point where
  x : Nat
  y : Nat

def Point.addX : Point → Point → Nat :=
  fun { x := a, .. } { x := b, .. } => a + b
  • 変数引数〈varible argument〉: variable宣言された変数は、その後の関数の引数として組み込まれる。セクションでスコーピングできる。
  • 構造体を引数とすると、名前付き引数としても使うことができる。ブレイス括弧が使えて、入れ子も出来る。

引数は、リストともレコード〈構造体〉とも、コンテキストデータとも受け取れる、面白い

タクティクの使い方

  1. apply は backward apply〈deapply | reverse apply〉の意味。だいぶ困る。
  2. 複数のゴールは左〈上〉から順に攻撃する。ツリー辿りは深さ優先再帰かな。
  3. ゴールの固有名はないが、left, right のcaseラベルは付く。並びの順番でも参照できる。
  4. ツリーが構成されると、各ゴール〈ノード〉に付くラベルはツリーパスになる。ただし、ツリーの全貌は表示されない。時間方向にツリーが展開される。ツリーがビジュアルではないので認知負荷が大きい。
  5. ドットの使いみちが、モジュールパス、名前空間パス、そして、バックワード・リーズニング・ツリーパス。あと、箇条書き記法のブレット。
  6. バックワードリーズニングのツリーは、タブローツリーと同じで、タクティクはタブローコマンドと同じ。
  7. #print 定理名 で、格納形式〈パックド形式〉の証明項=定理ボディが表示される。これは役立つ。
  8. [Ctrl]+[Shift]+[Enter] で InfoView の表示/非表示がトグルする。(知らんかった。)InfoViewが出てないときに便利。
  9. exactの代わりにapplyでもよい。applyに「それで終わり」の意味を付け加えたのがexact。exactly apply で、その意味は exactly deapply。
  10. applyに推論規則〈定理〉だけでなく、(推論規則 証拠) の形が使える。これも意味はdeappyだからややこしい。
  11. ゴールのラベル(ゴール名)をタグとも呼ぶ。タグは推論規則(例: And.intro)の引数名から取られる。推論規則は定理であり、定理は証明に名前を付けたもので、定理ヘッドに仮引数リストがあり、仮引数リストに引数名が付けられている。
  12. タクティクのシーケンスだと、複数ゴールのどれにタクティクが適用されるかが非常に分かりににくい。ゴールのタグ〈ラベル〉を利用して、ツリー構造を反映したタクティクコーディングが出来る。case タグ => タクティクコード と書く。
  13. caseの入れ子を使わないと、ツリー構造が平坦化されたコードになる。極めて分かりにくい。case構造は、タクティクコードの構造化構文として有用。
  14. リスト・ツリーが、推論規則の引数名でラベルされた、ラベル付き木になる。ラベルを使わないと、ラベル無し順序木となる。ツリーのノードが逆推論規則で、子ノードへのラベルが引数名。
  15. タグ=ラベルを書くのが面倒なら、入れ子箇条書き記法が使える。箇条書きの各箇条の頭にはブレット。
  16. introは「仮説を導入する」と書いてあるが、全然ダメ! intro の正体はカリー化の逆で、つまりは反カリー化操作。導入するのは、シークエントのコンテキスで使う証拠ラベル。シークエントのコンテキスを前提とも呼ぶので、前提に新たな証拠ラベルを導入する、とは言える。
  17. introは反カリー化だが、コンテキスがラベル付きを要求しているので、ラベルだけは人間が指定する必要がある。「ラベル必須」の影響は色々とある。依存パイ型の記述でもラベルが要求される。が、ラベルはアルファ変換可能。
  18. example, theorem, by は通常の関数定義にも使える。theorem myIdFunc (α : Type) : α → α := by intro x; exact x

mainが決まるとき。ステージングでもオブジェクトは作られる。

git init 直後HEADの内容:

ref: refs/heads/main

mainという名前はここで決定されて、その後も使われる。初期化しただけでは ./.git/refs/heads/ は空で、HEADの参照先である ./.git/refs/heads/main は存在しない。

git add README.md しても見た目上の「リポジトリが空状態」は変わらないが、blobオブジェクトが1個作成される。index〈ステージ | キャッシュ〉を見ると:

> git ls-files --stage
100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0       README.md

このblogオブジェクトは消えない/消せない -- git rm --cached README.md でインデックスのエントリーを削除はできるけど。ステージング状態のオブジェクトや参照困難になったオブジェクトの確認は、git ls-files --stage と git fsck --dangling

自然演繹証明図のエンコード

証明図から証明項に引き写すのは手作業。支援系とかいいながら、ソフトウェアは何も支援してくれない

/-! example_1.lean -/

namespace Imp
def elim_right {A B: Prop} (f:A → B) (a:A) : B :=
   f a
def elim_left {A B: Prop} (a:A) (f:A → B) : B :=
   f a
end Imp

variable (A B C D: Prop)

def example_1 (p1: A) (p2: A→B) (p3: B→C)  :  C∧(A∨D) :=
 /-(1)-/ have a: A := p1
 /-(2)-/ have a_imp_b := p2
 /-(3)-/ have b: B := Imp.elim_left a a_imp_b
 /-(4)-/ have c_imp_b := p3
 /-(5)-/ have c: C := Imp.elim_right c_imp_b b
 
 /-(6) = (1) -/ -- 重複記述はできない
 /-(7)-/ have a_or_d: A∨D := Or.intro_left D a

 /-(8)-/ show C∧(A∨D) from And.intro c a_or_d
#check example_1

def example_1' (p1: A) (p2: A→B) (p3: B→C)  :  C∧(A∨D) :=
 /-(1)-/ have b: B := p2 p1
 /-(2)-/ have c: C := p3 b
 /-(3)-/ have a_or_d: A∨D := Or.intro_left D p1
 /-(4)-/ show C∧(A∨D) from And.intro c a_or_d
#check example_1'

証明ソフトウェアが出来ないこと

  1. 証明図〈横棒図〉やストリング図を扱うこと、解釈すること。
  2. 順行リーズニング
  3. 柔軟な参照(固有名、固有ラベル以外の参照方法)
    1. 直示
    2. 位置による参照
    3. 曖昧参照
  4. リーズニングの中断保留(未完成のままに保存)
  5. 順行リーズニングと逆行リーズニングを混ぜたリーズニング
  6. 参照先がない(ダングリングな)コンテキストの許容

真偽判定の三段階

  • 命題の真偽判定: 白黒つける、決着をつける。どうやって?
  • 証明項の正当性検証: 構文を決めれば機械的に決定出来るか、または無限走行
  • 証明項の生成工程〈リーズニングプロセス〉の正当性検証: 構文を決めれば機械的に決定出来るか、または無限走行

証明項の正当性検証が型チェックエンジンがやること。証明項の生成工程の正当性検証が対話的支援系やスクリプトチェッカーがやること。

絵図とテキスト形式

問題は、絵図で自明なことをどうやってテキストエンコードするか?

  • 論理絵図=横棒図〈バー図〉
  • 圏論絵図=ストリング図
テキスト 論理絵図 圏論絵図
命題 命題 ワイヤー・ラベル
証拠ラベル バー・ラベル ノード・ラベル
証明項 横棒図 ストリング図
公理 上段空白横棒 入力ワイヤー無しノード

順行リーズニング:

テキスト 論理絵図 圏論絵図
結合や適用 カット ワイヤー接続
ラムダ抽象 含意導入 ワイヤー曲げ
デカルトペア 連言導入 コピーと接続
variables A B : Prop
variable h : A ∧ ¬ B

#check And.intro (And.right h) (And.left h)

ここで、

And.intro (And.right h) (And.left h) ≡ (And.intro ◁ (And.right h)) ◁ (And.left h)

だが、意味的に、

And.intro∪( (And.right∪(h)),  (And.left∪(h))

と解釈してから、次の絵を描く。

テキスト 横棒図 ストリング図
And.intro∪ 上段2項目バー 2入力ワイヤー・ノード
And.right∪ 上段1項目バー 1入力ワイヤー・ノード
And.left∪ 上段1項目バー 1入力ワイヤー・ノード
() 横棒図のスタック ストリング図の接続
( , ) 横棒図の横並べとスタック ストリング図の横並べと接続

絵から先に見ると:

  1. 絵から素直なテキスト化、結合には括弧を使う
  2. フルカリー化して、結合の代わりに適用だけを使う。
  3. Lean記法に直す。

圏論的な図、古典的な関数記法、フルカリー化と適用への変換、構文変換というけっこう長い道のりがある。

道のりは長いが、https://leanprover.github.io/logic_and_proof/propositional_logic_in_lean.html の説明法はいいと思う。例えば:

-- 素材の準備
variable (A B : Prop)
variable (h : A ∧ ¬ B)

-- 項として組み立てる
#check And.left h
#check And.right h
#check And.intro (And.right h) (And.left h)