Git Product home page Git Product logo

lean-by-example's Introduction

README

repo logo

workflow workflow workflow workflow discord

プログラミング言語であるとともに定理証明支援系でもある Lean 言語と、その主要なライブラリの使い方を豊富なコード例とともに解説した資料です。

Warning

本書は現在開発中であり、各ページのURLが予告なく変更され、リダイレクトも設定されないということがあり得ます。リンク切れを避けるには、個別ページではなくトップページにリンクを張るようにしてください。

CONTRIBUTING

誤りの指摘、編集の提案や寄稿を歓迎いたします。この GitHubリポジトリに issue や Pull Request を開いてください。開発環境が構築済みの Codespace を使用することができます。

codespace badge

CONTRIBUTINGに開発者向けの情報をまとめてあるので、そちらをご確認ください。

Do you want to translate this book?

Thank you for your interest in translating this book! 😄 But please note that we are currently not accepting translations of this book because this book is still under development! No content is stable yet.

Citation

If you use this book for your work, please cite it as follows:

@misc{leanbyexample,
  title = {Lean by {E}xample},
  url = {https://lean-ja.github.io/lean-by-example/}
  author = {The lean-ja community},
  note = {Accessed on Month Day, Year},
}

プライバシーポリシー

当 Web サイトでは、ユーザーのアクセス状況の分析のために Google アナリティクスを使用しています。Google アナリティクスは、 Cookie を利用してユーザーのWebサイト利用情報を収集しますが、これは匿名化されており、個人を特定する情報は収集されません。 当サイトでの Google アナリティクスの利用に関する詳細については、以下の Google の公式ページでご確認いただけます。

スポンサー

このプロジェクトは Proxima Technology 様よりご支援を頂いています。

logo of Proxima Technology

Proxima Technology(プロキシマテクノロジー)は数学の社会実装を目指し、その⼀環としてモデル予測制御の**化を掲げているAIスタートアップ企業です。数理科学の力で社会を変えることを企業の使命としています。

lean-by-example's People

Contributors

aconite-ac avatar actions-user avatar arakur avatar dependabot[bot] avatar github-actions[bot] avatar lumakernel avatar s-taiga avatar seasawher avatar semorrison avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar

lean-by-example's Issues

simp_arith, norm_num, linarith の実行時間の比較

simp_arith, norm_num, linarith はどれも 1 < 2 のようなゴールを閉じることができるタクティクですが,このうち linarith だけ紹介されています.しかし linarith は重めのタクティクです.linarith が必要でない場面では,機能は制限されていてもより軽量なタクティクを使った方が良いように思います.

上記のような注意書きを付け加えるのはいかがでしょうか?

匿名コンストラクタの記述を修正

補足
補題を示すだけでなく,ある特定の形をした主張を分解するのにも have は使うことができます.これは実は have に特有の機能ではありませんが,have と組み合わせて使うことが多いのでここで紹介します.

匿名コンストラクタという名前を出し,TPiL へのリンクを貼る

ワークフローが古い

この部分が古い.lake-packages はもう使わない.

      - name: Cache dependencies
        uses: actions/cache@v3
        with:
          path: |
            ./lake-packages
          key: deps-${{ runner.os }}-${{ hashFiles('lean-toolchain') }}-${{ hashFiles('lake-manifest.json') }}
          restore-keys: |
            deps-${{ runner.os }}-${{ hashFiles('lean-toolchain') }}

Theorem Proving にあるタクティクスのうち載っていないもの

Theorem Proving をちょうど読んでいて,そこで触れられているもので載っていないものを探してみました

  • let
  • intros (introでも特に触れられていない)
  • rename_i
  • revert
  • match
  • simp_arith
  • generalize

コンビネータ寄り?

コンビネータも入れたい?(別 Issue にすべきであればそうします,セクションをそもそも分けたほうがいいかもしれません)

  • ;
  • <;>
  • first| tac| ...

また,以下細かい点

  • (目次に) rwはあるがrewriteはない
  • (目次に) sorryはあるがadmitはない

あくまでも good first issue として役立てばと思い列挙させていただきました,私も取り組めそうなとこから触ってみようかなと思います

calc も紹介する

TPiL は初心者にとっては読みづらい文献.

重要なキーワードである calc 構文の使い方を雑でいいので紹介しておくべきだと思う.

apply? は暗黙に sorryAx を使う

import Mathlib.Tactic

theorem T (x y : Nat) (h: x ≤ y) : 2 ^ x ≤ 2 ^ y := by
  apply?

  -- なぜ subgoal が残ってるのに done が通るのか
  done

#explode T

出力の中に sorryAx がある.勝手に sorry しているし,警告も出ない

exact? を追加する

コード例の案. apply? と少し挙動が異なる

import Mathlib.Tactic

variable (P Q : Prop)

example (hPQ : P → Q) (hQR : Q → R) (hQ : P) : R := by
  -- `Try this: exact hQR (hPQ hQ)` と出力される
  exact?

  -- 証明は `exact?` だけで終わっている!
  done

fun_prop を紹介する

https://leanprover.zulipchat.com/#narrow/stream/113488-general/topic/.60fun_prop.60.20new.20tactic.20for.20Differentiable.2C.20Continuous.2C.20.2E.2E.2E

import Mathlib.Tactic

variable {u v : ℝ → ℝ} (hu : Continuous u) (hv : Continuous v)

/-- 連続関数の積は連続関数 -/
example : Continuous (fun x ↦ u x * v x) := by 
  fun_prop

/-- 有理関数が可測関数であることを示す -/
example : Measurable fun x : ℝ => (x * x - 1) / x + (x - x * x) := by
  fun_prop

unfold を追加する

unfold と rw, dsimp 等がどう違うのかについても,できれば説明したい

all_goals を紹介する

any_goals に比べて使う機会も多そうに思えるので,all_goals 単体でまず紹介する

nth_rewriteの記載追加

rwは書き換え可能な箇所をすべて書き換えるタクティックですが、これに対して式中で書き換え可能な箇所のうちn番目のみ書き換えるnth_rewriteというタクティックがあります。
https://leanprover-community.github.io/mathlib_docs/tactic/nth_rewrite/default.html
例えば以下のように用いることができます。
https://github.com/s-taiga/lean-math-workshop-my-solution/blob/d58278dc98ac95129c3ce7d7627dec70110dc2f4/Tutorial/Advanced/Algebra/Lecture1.lean#L262
個人的には先日の勉強会時にはかなりお世話になったタクティックだったので、言及があると良いのではないかと思います。

CI 追加

コード例がコンパイルできることを、git hub action を用いて確かめる

main へのプッシュと pull request ごとに走らせる

tauto とaesop

tauto は古典論理に依存するものも示せるが、aesopでは示せないようだ。これは偶然ではなさそう

rflの解説について

現在の記述 https://lean-ja.github.io/tactic-cheetsheet/rfl.html ではrflは項のdefinitional equalityを証明するもののように書かれていますが, ドキュメント https://leanprover-community.github.io/mathlib4_docs//Mathlib/Tactic/Relation/Rfl.html によるとこれは refl attributeのついた定理を用いて関係の反射性を示すといったほうが正確ではないかと思います。例えば以下のように順序の反射性を証明することが可能です.

example (n : ℕ) : n ≤ n := by rfl

mdgen を使って構成をやり直す

メリット

  • 今までは md ファイルと lean ファイルの両方を作成していたが,mdgen で一本化できる (既にかなりのタクティクを紹介済みなのでメリットは薄いが…)
  • 一つの大きなコードブロックに説明を書くと,読みづらくなってしまう.今まで特にコマンド紹介欄でそれが顕著だった.(コマンド紹介欄はもう対応済み)

デメリット

  • 作業が大変.残り 55 個のタクティクに対して行わないといけない.

作業内容

  1. Examples/Tactic ディレクトリに lean ファイルを移し,そこからビルドした md ファイルを src ディレクトリに配置するように変更する.
  2. 従来 md ファイルと lean ファイルに分かれている内容を,lean ファイルに一本化する
  3. 1-2 を 55 タクティクに対して繰り返す

dbg_trace を紹介する

デバッグに便利なので紹介する価値はある

タクティクではあるけど、証明と関係がないので紹介しない方が良いかもしれない。「数学に役立つ」リストとしては要らないはず

一つのページにつき1タクティクを紹介するように統一する

現在は racsescases が同じページだったり,simpdsimp が同じページだったりしている.

派生タクティクは,一言説明を考えるのが難しいので同じページにまとめたくなってしまい,このようにしていた.

しかし,紹介するタクティクが多くなってきて,(当初の想定の早見表としてだけでなく)辞書のような使われ方をすることも今後想定される.そうなった場合,一ページあたり一タクティクの方が統一感がある.

存在を示す命題 ∃ x P x を示す際に,前方推論をする方法

普通は ∃ x P x を示すとき,先に x を具体的に渡す.

しかし,P を変形してから x を考えることもできる.

example {c : ℝ} (h : c ≠ 0) : Surjective fun x ↦ c * x := by
  intro y
  use ?term
  simp
  show c * ?term = y

  case term =>
    exact c⁻¹ * y

  case h =>
    rw [mul_inv_cancel_left₀ h y]

contrapose を紹介する

MIL を参考に例を取るとよいかもしれない

example (h : Monotone f) (h' : f a < f b) : a < b := by
  contrapose! h'
  apply h
  assumption

pull request に対して,GitHub Pages のデプロイワークフローが動くようにする

プルリクエストに対してデプロイは行うことができない.しかし,mdbook のビルドが通るかチェックはできるし,生成されたアーティファクトを確認することもできる.

この設定がないと,GitHub Pages の見た目を変えるための PR の結果をテストするのに,main ブランチにいったんマージする必要が生じてしまう.

早見表なのか辞書なのか

当初は「便利なタクティクを集めて,早見表を作る」のが目的でしたが,紹介するタクティクが多くなってきて辞書のようになりつつあります.早見表としての利便性は確保できているのでしょうか…?

個人的には日本語検索が可能になった時点で十分だと感じていましたが,まだ足りないかもしれません.

Lean 初心者の意見を聞きたいところです.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.