arithcc | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

eb3595ed

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

08b081ea

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -296,7 +296,7 @@ theorem write_eq_implies_stateEq {t : Register} {v : Word} {ζ₁ ζ₂ : State}
   intro r hr
   cases' h with _ h
   specialize h r (lt_trans hr (register.lt_succ_self _))
-  rwa [if_neg (ne_of_lt hr)] at h 
+  rwa [if_neg (ne_of_lt hr)] at h
 #align arithcc.write_eq_implies_state_eq Arithcc.write_eq_implies_stateEq
 
 /-- The main **compiler correctness theorem**.
@@ -352,7 +352,7 @@ theorem compiler_correctness :
       intros
       calc
         read (loc x map) ζ₂ = read (loc x map) (write t ν₁ η) := hζ₂ _ (ht' _)
-        _ = read (loc x map) η := by simp only [loc] at ht ; simp [(ht _).Ne]
+        _ = read (loc x map) η := by simp only [loc] at ht; simp [(ht _).Ne]
         _ = ξ x := hmap x
     have hζ₃ : ζ₃ ≃[t + 1] { write t ν₁ η with ac := ν₂ }
     calc

08b081ea

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2020 Xi Wang. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
 -/
-import Mathbin.Order.Basic
-import Mathbin.Tactic.Basic
+import Order.Basic
+import Tactic.Basic
 
 #align_import arithcc from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"

08b081ea

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2020 Xi Wang. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
-
-! This file was ported from Lean 3 source module arithcc
-! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Order.Basic
 import Mathbin.Tactic.Basic
 
+#align_import arithcc from "leanprover-community/mathlib"@"08b081ea92d80e3a41f899eea36ef6d56e0f1db0"
+
 /-!
 # A compiler for arithmetic expressions

08b081ea

bump to nightly-2023-07-17-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/bf2428c9486c407ca38b5b3fb10b87dad0bc99fa

a159b65f

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
 
 ! This file was ported from Lean 3 source module arithcc
-! leanprover-community/mathlib commit eb3595ed8610db8107b75b75ab64ab6390684155
+! leanprover-community/mathlib commit 08b081ea92d80e3a41f899eea36ef6d56e0f1db0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Tactic.Basic
 /-!
 # A compiler for arithmetic expressions
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 A formalization of the correctness of a compiler from arithmetic expressions to machine language
 described by McCarthy and Painter, which is considered the first proof of compiler correctness.

eb3595ed

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -208,7 +208,6 @@ def StateEqRs (t : Register) (ζ₁ ζ₂ : State) : Prop :=
   ∀ r : Register, r < t → ζ₁.rs r = ζ₂.rs r
 #align arithcc.state_eq_rs Arithcc.StateEqRs
 
--- mathport name: «expr ≃[ ]/ac »
 notation:50 ζ₁ " ≃[" t "]/ac " ζ₂:50 => StateEqRs t ζ₁ ζ₂
 
 @[refl]
@@ -230,7 +229,6 @@ def StateEq (t : Register) (ζ₁ ζ₂ : State) : Prop :=
   ζ₁.ac = ζ₂.ac ∧ StateEqRs t ζ₁ ζ₂
 #align arithcc.state_eq Arithcc.StateEq
 
--- mathport name: «expr ≃[ ] »
 notation:50 ζ₁ " ≃[" t "] " ζ₂:50 => StateEq t ζ₁ ζ₂
 
 @[refl]

eb3595ed

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

Diff

@@ -331,7 +331,6 @@ theorem compiler_correctness :
     calc
       ζ₁ = outcome (compile map e_s₁ t) η := by cc
       _ ≃[t] { η with ac := ν₁ } := by apply e_ih_s₁ <;> assumption
-      
     have hζ₁_ν₁ : ζ₁.ac = ν₁ := by finish [state_eq]
     have hζ₂ : ζ₂ ≃[t + 1]/ac write t ν₁ η
     calc
@@ -343,7 +342,6 @@ theorem compiler_correctness :
         by
         apply state_eq_rs_implies_write_eq_rs
         simp [state_eq_rs]
-      
     have hζ₂_ν₂ : read t ζ₂ = ν₁ := by
       simp [state_eq_rs] at hζ₂ ⊢
       specialize hζ₂ t (register.lt_succ_self _)
@@ -358,13 +356,11 @@ theorem compiler_correctness :
         read (loc x map) ζ₂ = read (loc x map) (write t ν₁ η) := hζ₂ _ (ht' _)
         _ = read (loc x map) η := by simp only [loc] at ht ; simp [(ht _).Ne]
         _ = ξ x := hmap x
-        
     have hζ₃ : ζ₃ ≃[t + 1] { write t ν₁ η with ac := ν₂ }
     calc
       ζ₃ = outcome (compile map e_s₂ (t + 1)) ζ₂ := by cc
       _ ≃[t + 1] { ζ₂ with ac := ν₂ } := by apply e_ih_s₂ <;> assumption
       _ ≃[t + 1] { write t ν₁ η with ac := ν₂ } := by simp [state_eq]; apply hζ₂
-      
     have hζ₃_ν₂ : ζ₃.ac = ν₂ := by finish [state_eq]
     have hζ₃_ν₁ : read t ζ₃ = ν₁ :=
       by
@@ -380,7 +376,6 @@ theorem compiler_correctness :
       _ ≃[t + 1] { { write t ν₁ η with ac := ν₂ } with ac := ν } := by simp [state_eq] at hζ₃ ⊢;
         cases hζ₃; assumption
       _ ≃[t + 1] { write t ν₁ η with ac := ν } := by simp
-      
     apply write_eq_implies_state_eq <;> assumption
 #align arithcc.compiler_correctness Arithcc.compiler_correctness

eb3595ed

bump to nightly-2023-06-07-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/a3209ddf94136d36e5e5c624b10b2a347cc9d090

176da745

Changes in mathlib4

mathlib3

mathlib4

eb3595ed

style: add nonterminal simp checker (#7496)

Adds a linter that detects calls to simp where the next line is at the same indentation level.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

8426743e

Diff

@@ -319,7 +319,8 @@ theorem compiler_correctness
   -- 5.III
   | sum =>
     rename_i e_s₁ e_s₂ e_ih_s₁ e_ih_s₂
-    simp
+    simp only [compile, List.append_assoc, List.singleton_append, List.cons_append, outcome_append,
+      outcome, value]
     generalize value e_s₁ ξ = ν₁ at e_ih_s₁ ⊢
     generalize value e_s₂ ξ = ν₂ at e_ih_s₂ ⊢
     generalize dν : ν₁ + ν₂ = ν

eb3595ed

chore: classify added instance porting notes (#10755)

Classifies by adding issue number (#10754) to porting notes claiming added instance.

283cf08e

Diff

@@ -249,7 +249,7 @@ protected theorem StateEq.trans {t : Register} (ζ₁ ζ₂ ζ₃ : State) :
   · trans ζ₂ <;> assumption
 #align arithcc.state_eq.trans Arithcc.StateEq.trans
 
--- Porting note: added
+-- Porting note (#10754): added instance
 instance (t : Register) : Trans (StateEq (t + 1)) (StateEq (t + 1)) (StateEq (t + 1)) :=
   ⟨@StateEq.trans _⟩
 
@@ -261,7 +261,7 @@ protected theorem StateEqStateEqRs.trans (t : Register) (ζ₁ ζ₂ ζ₃ : Sta
   trans ζ₂ <;> assumption
 #align arithcc.state_eq_state_eq_rs.trans Arithcc.StateEqStateEqRs.trans
 
--- Porting note: added
+-- Porting note (#10754): added instance
 instance (t : Register) : Trans (StateEq (t + 1)) (StateEqRs (t + 1)) (StateEqRs (t + 1)) :=
   ⟨@StateEqStateEqRs.trans _⟩

eb3595ed

chore: remove stream-of-consciousness uses of have, replace and suffices (#10640)

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

a13e8040

Diff

@@ -327,13 +327,11 @@ theorem compiler_correctness
     generalize dζ₂ : step (Instruction.sto t) ζ₁ = ζ₂
     generalize dζ₃ : outcome (compile _ e_s₂ (t + 1)) ζ₂ = ζ₃
     generalize dζ₄ : step (Instruction.add t) ζ₃ = ζ₄
-    have hζ₁ : ζ₁ ≃[t] { η with ac := ν₁ }
-    calc
+    have hζ₁ : ζ₁ ≃[t] { η with ac := ν₁ } := calc
       ζ₁ = outcome (compile map e_s₁ t) η := by simp_all
       _ ≃[t] { η with ac := ν₁ } := by apply e_ih_s₁ <;> assumption
     have hζ₁_ν₁ : ζ₁.ac = ν₁ := by simp_all [StateEq]
-    have hζ₂ : ζ₂ ≃[t + 1]/ac write t ν₁ η
-    calc
+    have hζ₂ : ζ₂ ≃[t + 1]/ac write t ν₁ η := calc
       ζ₂ = step (Instruction.sto t) ζ₁ := by simp_all
       _ = write t ζ₁.ac ζ₁ := by simp [step]
       _ = write t ν₁ ζ₁ := by simp_all
@@ -350,8 +348,7 @@ theorem compiler_correctness
         read (loc x map) ζ₂ = read (loc x map) (write t ν₁ η) := hζ₂ _ (ht' _)
         _ = read (loc x map) η := by simp only [loc] at ht; simp [(ht _).ne]
         _ = ξ x := hmap x
-    have hζ₃ : ζ₃ ≃[t + 1] { write t ν₁ η with ac := ν₂ }
-    calc
+    have hζ₃ : ζ₃ ≃[t + 1] { write t ν₁ η with ac := ν₂ } := calc
       ζ₃ = outcome (compile map e_s₂ (t + 1)) ζ₂ := by simp_all
       _ ≃[t + 1] { ζ₂ with ac := ν₂ } := by apply e_ih_s₂ <;> assumption
       _ ≃[t + 1] { write t ν₁ η with ac := ν₂ } := by simp [StateEq]; apply hζ₂
@@ -361,14 +358,13 @@ theorem compiler_correctness
       cases' hζ₃ with _ hζ₃
       specialize hζ₃ t (Register.lt_succ_self _)
       simp_all
-    have hζ₄ : ζ₄ ≃[t + 1] { write t ν₁ η with ac := ν }
-    calc
+    have hζ₄ : ζ₄ ≃[t + 1] { write t ν₁ η with ac := ν } := calc
       ζ₄ = step (Instruction.add t) ζ₃ := by simp_all
-      _ = { ζ₃ with ac := read t ζ₃ + ζ₃.ac } := by simp [step]
-      _ = { ζ₃ with ac := ν } := by simp_all
-      _ ≃[t + 1] { { write t ν₁ η with ac := ν₂ } with ac := ν } := by
+      _  = { ζ₃ with ac := read t ζ₃ + ζ₃.ac } := by simp [step]
+      _  = { ζ₃ with ac := ν } := by simp_all
+      _  ≃[t + 1] { { write t ν₁ η with ac := ν₂ } with ac := ν } := by
         simp [StateEq] at hζ₃ ⊢; cases hζ₃; assumption
-      _ ≃[t + 1] { write t ν₁ η with ac := ν } := by simp_all; rfl
+      _  ≃[t + 1] { write t ν₁ η with ac := ν } := by simp_all; rfl
     apply write_eq_implies_stateEq <;> assumption
 #align arithcc.compiler_correctness Arithcc.compiler_correctness

eb3595ed

refactor: Split off basic Nat file (#9551)

Data.Nat.Basic is currently made of two things:

Basic lemmas that continue the theory in Std (and could belong there, really)
Basic algebraic order instances

I need the first ones earlier in the algebraic order hierarchy, hence the split.

Part of #9411. Similar to #9443

497ed074

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2020 Xi Wang. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
 -/
+import Mathlib.Init.Data.Nat.Lemmas
 import Mathlib.Order.Basic
-import Mathlib.Data.Nat.Basic
 import Mathlib.Tactic.Common
 
 #align_import arithcc from "leanprover-community/mathlib"@"eb3595ed8610db8107b75b75ab64ab6390684155"

eb3595ed

style: use cases x with | ... instead of cases x; case => ... (#9321)

This converts usages of the pattern

cases h
case inl h' => ...
case inr h' => ...

which derive from mathported code, to the "structured cases" syntax:

cases h with
| inl h' => ...
| inr h' => ...

The case where the subgoals are handled with · instead of case is more contentious (and much more numerous) so I left those alone. This pattern also appears with cases', induction, induction', and rcases. Furthermore, there is a similar transformation for by_cases:

by_cases h : cond
case pos => ...
case neg => ...

is replaced by:

if h : cond then
  ...
else
  ...

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

e04a464d

Diff

@@ -303,23 +303,21 @@ theorem write_eq_implies_stateEq {t : Register} {v : Word} {ζ₁ ζ₂ : State}
 
 Unlike Theorem 1 in the paper, both `map` and the assumption on `t` are explicit.
 -/
-theorem compiler_correctness :
-    ∀ (map : Identifier → Register) (e : Expr) (ξ : Identifier → Word) (η : State) (t : Register),
-      (∀ x, read (loc x map) η = ξ x) →
-        (∀ x, loc x map < t) → outcome (compile map e t) η ≃[t] { η with ac := value e ξ } := by
-  intro map e ξ η t hmap ht
-  revert η t
-  induction e <;> intro η t hmap ht
+theorem compiler_correctness
+    (map : Identifier → Register) (e : Expr) (ξ : Identifier → Word) (η : State) (t : Register)
+    (hmap : ∀ x, read (loc x map) η = ξ x) (ht : ∀ x, loc x map < t) :
+    outcome (compile map e t) η ≃[t] { η with ac := value e ξ } := by
+  induction e generalizing η t with
   -- 5.I
-  case const => simp [StateEq, step]; rfl
+  | const => simp [StateEq, step]; rfl
   -- 5.II
-  case var =>
+  | var =>
     simp [hmap, StateEq, step] -- Porting note: was `finish [hmap, StateEq, step]`
     constructor
     · simp_all only [read, loc]
     · rfl
   -- 5.III
-  case sum =>
+  | sum =>
     rename_i e_s₁ e_s₂ e_ih_s₁ e_ih_s₂
     simp
     generalize value e_s₁ ξ = ν₁ at e_ih_s₁ ⊢

eb3595ed

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -272,7 +272,7 @@ theorem stateEq_implies_write_eq {t : Register} {ζ₁ ζ₂ : State} (h : ζ₁
   constructor; · exact h.1
   intro r hr
   have hr : r ≤ t := Register.le_of_lt_succ hr
-  cases' lt_or_eq_of_le hr with hr hr
+  rcases lt_or_eq_of_le hr with hr | hr
   · cases' h with _ h
     specialize h r hr
     simp_all

eb3595ed

chore: cleanup in Mathlib.Init (#6977)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

8f46576d

Diff

@@ -4,7 +4,8 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
 -/
 import Mathlib.Order.Basic
-import Mathlib.Tactic.Basic
+import Mathlib.Data.Nat.Basic
+import Mathlib.Tactic.Common
 
 #align_import arithcc from "leanprover-community/mathlib"@"eb3595ed8610db8107b75b75ab64ab6390684155"

eb3595ed

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2020 Xi Wang. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Xi Wang
-
-! This file was ported from Lean 3 source module arithcc
-! leanprover-community/mathlib commit eb3595ed8610db8107b75b75ab64ab6390684155
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Order.Basic
 import Mathlib.Tactic.Basic
 
+#align_import arithcc from "leanprover-community/mathlib"@"eb3595ed8610db8107b75b75ab64ab6390684155"
+
 /-!
 # A compiler for arithmetic expressions

eb3595ed

chore: remove occurrences of semicolon after space (#5713)

This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.

In most cases this 2-character substring has a space after it, so the following command was run first:

find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;

The remaining cases were few enough in number that they were done manually.

c795bd35

Diff

@@ -352,7 +352,7 @@ theorem compiler_correctness :
       intro x
       calc
         read (loc x map) ζ₂ = read (loc x map) (write t ν₁ η) := hζ₂ _ (ht' _)
-        _ = read (loc x map) η := by simp only [loc] at ht ; simp [(ht _).ne]
+        _ = read (loc x map) η := by simp only [loc] at ht; simp [(ht _).ne]
         _ = ξ x := hmap x
     have hζ₃ : ζ₃ ≃[t + 1] { write t ν₁ η with ac := ν₂ }
     calc

eb3595ed

fix: bug fixes to rw? (#5563)

As reported on zulip

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

3ec9bf62

`arithcc` ⟷ `Archive.Arithcc`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3

arithcc ⟷ Archive.Arithcc

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3

`arithcc` ⟷ `Archive.Arithcc`