lean-ja / lean-ja/lean-by-example

`Subtype` として定義された正の数の集合 `Pos` の要素を Nat にばらすタクティクの作例 / unfold_subtype / Lean.mkIdent 使用例

Open
#1,273 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

コード例 メタプログラミング
Dominant language
Lean
Stars
188
Forks
15
Avg merge
9h 8m
Merged PRs (30d)
6

Description

これは自分で書いた。Lean.quoteLean.mkIdent の使い方のいい例になると思った。
Pos 以外の Subtype にも一般化できそうだ。

ただし、これを macro コマンドで定義するのはちょっと微妙かもしれない。
elab コマンドで定義すべきという気もする。なぜなら、ident を作るとか、単なるマクロにとどまらないことをやってしまっているから。

/-- 許されている演算の集合 -/
inductive Op where
  /-- 加法 -/
  | add
  /-- 減法 -/
  | sub
  /-- 乗法 -/
  | mul
  /-- 除法 -/
  | div

private def Op.toString : Op → String
  | Op.add => "+"
  | Op.sub => "-"
  | Op.mul => "*"
  | Op.div => "/"

instance : ToString Op := ⟨Op.toString⟩

/-- 正の自然数。途中の状態として許可されるのは正の自然数のみ。 -/
abbrev Pos := { n : Nat // n > 0 }

private def Pos.ofNat (n : Nat) : Pos :=
  if h : n = 0 then ⟨1, by decide⟩
  else ⟨n, by omega⟩

instance {n : Nat} : OfNat Pos (n + 1) := ⟨Pos.ofNat (n + 1)⟩

instance : ToString Pos := inferInstance

/-- `op` を適用したときに正の整数が生成されるかどうかチェックする

**Note** 本では引数の型は `Int` になっているが、文脈からして型は `Pos` であるべきだと考えられる。
-/
def Op.valid (op : Op) (x y : Pos) : Bool :=
  match op with
  | Op.add => true
  | Op.sub => x.val > y.val
  | Op.mul => true
  | Op.div => x.val % y.val == 0

/-- 有効な演算子の適用を実行する -/
def Op.apply (op : Op) (x y : Pos) : Nat :=
  match op with
  | Op.add => x.val + y.val
  | Op.sub => x.val - y.val
  | Op.mul => x.val * y.val
  | Op.div => x.val / y.val

/-- `x : Pos` をゴールおよび仮定から消してしまって、`x : Nat` と `x.pos : x > 0` にバラす。 -/
macro "unfold_pos" x:ident : tactic => `(tactic| with_reducible
  all_goals
    have $(Lean.mkIdent <| x.getId ++ `pos) : Subtype.val $x > 0 := Subtype.property $x
    generalize hx : Subtype.val $x = $(Lean.mkIdent x.getId)
    simp only [hx] at *
    clear hx
)

/-- `op.valid x y` が成立しているならば、`op.apply x y` は正の数 -/
theorem Op.pos_of_valid (op : Op) (x y : Pos) (h : op.valid x y) : op.apply x y > 0 := by
  dsimp [Op.apply, Op.valid] at *
  cases op <;> dsimp at *

  -- `x y : Pos` を正という情報だけ取り出して展開して、`x y : Nat` にする。
  -- これで `Pos` の項を消すことができる。
  unfold_pos x
  unfold_pos y

  case add => omega
  case mul => apply Nat.mul_pos <;> assumption
  case sub =>
    have : x > y := by simp_all
    omega
  case div =>
    suffices hyp : x / y ≠ 0 from by
      exact Nat.zero_lt_of_ne_zero hyp
    intro hyp
    have : y * (x / y) = x := by
      have : y ∣ x := by
        apply Nat.dvd_of_mod_eq_zero
        simp_all
      simp [Nat.mul_div_cancel' (by assumption)]
    rw [hyp, Nat.mul_zero] at this
    omega

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue provides a complete Lean example centered on the unfold_pos tactic and Lean.mkIdent. Start by locating the repository's existing code-example entry points and conventions; no target file or test is named here. Done would be an accepted example documenting this subtype-unfolding use case.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.