Something went wrong. Try again.
Coding agent with a memory of all things
Something went wrong. Try again.
12 kB · 376 lines
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377# eukhe: lemmas shared by the proofs of laws/selection.bend## The model's helpers and the spec's agree on every cell: once a cell is# a constructor both compute the same comparison (sl_le, sl_same), so the# order of two cells, a mode's selection and the answers built from them# agree for every argument. Below them: the Nat order facts the proofs# use, and the count of a press that counts on.
import Baseimport ../../bend/selection.bend as Mimport ../../laws/selection.bend as Selection
# Logic# -----
def ls.clash(b: Bool, G: Type) -> Type: match b: case False{}: Unit case True{}: G
# False is not True: anything followsdef ls.absurd(-G: Type, e: {False{} == True{} : Bool}) -> G: %e : ls.clash(_, G) Unit{}
def ls.absurd_t(-G: Type, e: {True{} == False{} : Bool}) -> G: ls.absurd(G, Equal.sym(Bool, True{}, False{}, e))
# Nat order# ---------
def ls.and_tt(a: Bool, -b: Bool, ea: {a == True{} : Bool}, eb: {b == True{} : Bool}) -> {Bool.and(a, b) == True{} : Bool}: match a: case True{}: eb case False{}: ls.absurd({Bool.and(False{}, b) == True{} : Bool}, ea)
def ls.zcl(n: Nat, G: Type) -> Type: match n: case 0n: G case 1n+p: Unit
# 1 + n is not 0: anything followsdef ls.succ_zero(-G: Type, -n: Nat, e: {1n+n == 0n : Nat}) -> G: %e : ls.zcl(_, G) Unit{}
def ls.and_l(a: Bool, -b: Bool, e: {Bool.and(a, b) == True{} : Bool}) -> {a == True{} : Bool}: match a: case True{}: {==} case False{}: ls.absurd({False{} == True{} : Bool}, e)
def ls.and_r(a: Bool, -b: Bool, e: {Bool.and(a, b) == True{} : Bool}) -> {b == True{} : Bool}: match a: case True{}: e case False{}: ls.absurd({b == True{} : Bool}, e)
# a at most b: b is not below adef ls.le_nlt(a: Nat, b: Nat, h: {Nat.is_le(a, b) == True{} : Bool}) -> {Nat.is_lt(b, a) == False{} : Bool}: match a b: case 0n 0n: {==} case 0n 1n+q: {==} case 1n+p 0n: ls.absurd({Nat.is_lt(0n, 1n+p) == False{} : Bool}, h) case 1n+p 1n+q: ls.le_nlt(p, q, h)
def ls.eq_refl(n: Nat) -> {Nat.is_eq(n, n) == True{} : Bool}: match n: case 0n: {==} case 1n+p: ls.eq_refl(p)
def ls.le_zero(n: Nat) -> {Nat.is_le(0n, n) == True{} : Bool}: match n: case 0n: {==} case 1n+p: {==}
def ls.le_refl(n: Nat) -> {Nat.is_le(n, n) == True{} : Bool}: match n: case 0n: {==} case 1n+p: ls.le_refl(p)
def ls.le_succ(n: Nat) -> {Nat.is_le(n, 1n+n) == True{} : Bool}: match n: case 0n: {==} case 1n+p: ls.le_succ(p)
def ls.le_trans(a: Nat, b: Nat, c: Nat, h1: {Nat.is_le(a, b) == True{} : Bool}, h2: {Nat.is_le(b, c) == True{} : Bool}) -> {Nat.is_le(a, c) == True{} : Bool}: match a b c: case 0n _ q: ls.le_zero(q) case 1n+p 0n _: ls.absurd({Nat.is_le(1n+p, c) == True{} : Bool}, h1) case 1n+p 1n+q 0n: ls.absurd({Nat.is_le(1n+p, 0n) == True{} : Bool}, h2) case 1n+p 1n+q 1n+r: ls.le_trans(p, q, r, h1, h2)
# x is at most p + xdef ls.le_add(p: Nat, +x: Nat) -> {Nat.is_le(x, Nat.add(p, x)) == True{} : Bool}: match p: case 0n: ls.le_refl(x) case 1n++q: ls.le_trans(x, Nat.add(q, x), 1n+Nat.add(q, x), ls.le_add(q, x), ls.le_succ(Nat.add(q, x)))
def ls.lt_not_le(a: Nat, b: Nat, h: {Nat.is_lt(a, b) == True{} : Bool}) -> {Nat.is_le(b, a) == False{} : Bool}: match a b: case 0n 0n: ls.absurd({Nat.is_le(0n, 0n) == False{} : Bool}, h) case 0n 1n+q: {==} case 1n+p 0n: ls.absurd({Nat.is_le(0n, 1n+p) == False{} : Bool}, h) case 1n+p 1n+q: ls.lt_not_le(p, q, h)
# x not at most c: c + 1 is at most xdef ls.nle_lt(x: Nat, c: Nat, h: {Nat.is_le(x, c) == False{} : Bool}) -> {Nat.is_le(1n+c, x) == True{} : Bool}: match x c: case 0n q: ls.absurd_t({Nat.is_le(1n+q, 0n) == True{} : Bool}, Equal.trans(Bool, True{}, Nat.is_le(0n, q), False{}, Equal.sym(Bool, Nat.is_le(0n, q), True{}, ls.le_zero(q)), h)) case 1n+p 0n: ls.le_zero(p) case 1n+p 1n+q: ls.nle_lt(p, q, h)
def ls.le_lt_succ(x: Nat, c: Nat, h: {Nat.is_le(x, c) == True{} : Bool}) -> {Nat.is_lt(x, 1n+c) == True{} : Bool}: match x c: case 0n q: {==} case 1n+p 0n: ls.absurd({Nat.is_lt(1n+p, 1n) == True{} : Bool}, h) case 1n+p 1n+q: ls.le_lt_succ(p, q, h)
def ls.lt_le(a: Nat, b: Nat, c: Nat, h1: {Nat.is_lt(a, b) == True{} : Bool}, h2: {Nat.is_le(b, c) == True{} : Bool}) -> {Nat.is_lt(a, c) == True{} : Bool}: match a b c: case 0n 0n _: ls.absurd({Nat.is_lt(0n, c) == True{} : Bool}, h1) case 0n 1n+q 0n: ls.absurd({Nat.is_lt(0n, 0n) == True{} : Bool}, h2) case 0n 1n+q 1n+r: {==} case 1n+p 0n _: ls.absurd({Nat.is_lt(1n+p, c) == True{} : Bool}, h1) case 1n+p 1n+q 0n: ls.absurd({Nat.is_lt(1n+p, 0n) == True{} : Bool}, h2) case 1n+p 1n+q 1n+r: ls.lt_le(p, q, r, h1, h2)
def ls.lt_succ(+x: Nat, +c: Nat, h: {Nat.is_lt(x, c) == True{} : Bool}) -> {Nat.is_lt(x, 1n+c) == True{} : Bool}: ls.lt_le(x, c, 1n+c, h, ls.le_succ(c))
# e + 1 at most x: x is not at most edef ls.succ_le_nle(e: Nat, x: Nat, h: {Nat.is_le(1n+e, x) == True{} : Bool}) -> {Nat.is_le(x, e) == False{} : Bool}: match e x: case 0n 0n: ls.absurd({Nat.is_le(0n, 0n) == False{} : Bool}, h) case 0n 1n+q: {==} case 1n+p 0n: ls.absurd({Nat.is_le(0n, 1n+p) == False{} : Bool}, h) case 1n+p 1n+q: ls.succ_le_nle(p, q, h)
# Nat sums# --------
def ls.add_zero(n: Nat) -> {Nat.add(n, 0n) == n : Nat}: match n: case 0n: {==} case 1n+p: %ls.add_zero(p) : {1n+Nat.add(p, 0n) == 1n+_ : Nat} {==}
def ls.add_succ(a: Nat, -b: Nat) -> {Nat.add(a, 1n+b) == 1n+Nat.add(a, b) : Nat}: match a: case 0n: {==} case 1n+p: %ls.add_succ(p, b) : {1n+Nat.add(p, 1n+b) == 1n+_ : Nat} {==}
def ls.add_assoc(a: Nat, -b: Nat, -c: Nat) -> {Nat.add(Nat.add(a, b), c) == Nat.add(a, Nat.add(b, c)) : Nat}: match a: case 0n: {==} case 1n+p: %ls.add_assoc(p, b, c) : {1n+Nat.add(Nat.add(p, b), c) == 1n+_ : Nat} {==}
def ls.add_comm(a: Nat, +b: Nat) -> {Nat.add(a, b) == Nat.add(b, a) : Nat}: match a: case 0n: Equal.sym(Nat, Nat.add(b, 0n), b, ls.add_zero(b)) case 1n+p: %Equal.sym(Nat, Nat.add(p, b), Nat.add(b, p), ls.add_comm(p, b)) : {1n+_ == Nat.add(b, 1n+p) : Nat} Equal.sym(Nat, Nat.add(b, 1n+p), 1n+Nat.add(b, p), ls.add_succ(b, p))
def ls.lt_irrefl(n: Nat) -> {Nat.is_lt(n, n) == False{} : Bool}: match n: case 0n: {==} case 1n+p: ls.lt_irrefl(p)
def ls.lt_ne(a: Nat, b: Nat, h: {Nat.is_lt(a, b) == True{} : Bool}) -> {Nat.is_eq(a, b) == False{} : Bool}: match a b: case 0n 0n: ls.absurd({Nat.is_eq(0n, 0n) == False{} : Bool}, h) case 0n 1n+q: {==} case 1n+p 0n: {==} case 1n+p 1n+q: ls.lt_ne(p, q, h)
def ls.sub_zero(n: Nat) -> {Nat.sub(n, 0n) == n : Nat}: match n: case 0n: {==} case 1n+p: {==}
def ls.sub_self(n: Nat) -> {Nat.sub(n, n) == 0n : Nat}: match n: case 0n: {==} case 1n+p: ls.sub_self(p)
def ls.sub_le_zero(a: Nat, b: Nat, h: {Nat.is_le(a, b) == True{} : Bool}) -> {Nat.sub(a, b) == 0n : Nat}: match a b: case 0n q: {==} case 1n+p 0n: ls.absurd({Nat.sub(1n+p, 0n) == 0n : Nat}, h) case 1n+p 1n+q: ls.sub_le_zero(p, q, h)
# p - j is one more than p - (j + 1) when j < pdef ls.sub_pos(p: Nat, j: Nat, h: {Nat.is_le(1n+j, p) == True{} : Bool}) -> {Nat.sub(p, j) == 1n+Nat.sub(p, 1n+j) : Nat}: match p j: case 0n q: ls.absurd({Nat.sub(0n, q) == 1n+Nat.sub(0n, 1n+q) : Nat}, h) case 1n+q 0n: %Equal.sym(Nat, Nat.sub(q, 0n), q, ls.sub_zero(q)) : {1n+q == 1n+_ : Nat} {==} case 1n+q 1n+r: ls.sub_pos(q, r, h)
# what M.row_nb answers from index j: 0, or past jdef ls.nbok(n: Nat, +j: Nat) -> Bool: match n: case 0n: True{} case 1n+p: Nat.is_le(j, p)
# the larger of L and N, less L, is 0 when N is at most Ldef ls.hz.k(b: Bool, +L: Nat, +N: Nat, eb: {Nat.is_le(L, N) == b : Bool}, h: {Nat.is_le(N, L) == True{} : Bool}) -> {Nat.sub(M.max.pick(b, L, N), L) == 0n : Nat}: match b: case True{}: ls.sub_le_zero(N, L, h) case False{}: ls.sub_self(L)
def ls.hz(+L: Nat, +N: Nat, h: {Nat.is_le(N, L) == True{} : Bool}) -> {Nat.sub(M.max.pick(Nat.is_le(L, N), L, N), L) == 0n : Nat}: ls.hz.k(Nat.is_le(L, N), L, N, {==}, h)
# Token lists# -----------
def ls.isnil(l: List<&2, Selection.SlTok>, G: Type) -> Type: match l: case Nil{}: G case Con{x, xs}: Unit
def ls.cons_nil(-G: Type, -x: Selection.SlTok, -xs: List<&2, Selection.SlTok>, e: {x <> xs == Nil{} : List<&2, Selection.SlTok>}) -> G: %e : ls.isnil(_, G) Unit{}
def ls.app_nil(xs: List<&2, Selection.SlTok>) -> {List.append(&2, Selection.SlTok, xs, Nil{}) == xs : List<&2, Selection.SlTok>}: match xs: case Nil{}: {==} case Con{x, +rest}: %ls.app_nil(rest) : {x <> List.append(&2, Selection.SlTok, rest, Nil{}) == x <> _ : List<&2, Selection.SlTok>} {==}
def ls.app_assoc(xs: List<&2, Selection.SlTok>, -ys: List<&2, Selection.SlTok>, -zs: List<&2, Selection.SlTok>) -> {List.append(&2, Selection.SlTok, List.append(&2, Selection.SlTok, xs, ys), zs) == List.append(&2, Selection.SlTok, xs, List.append(&2, Selection.SlTok, ys, zs)) : List<&2, Selection.SlTok>}: match xs: case Nil{}: {==} case Con{x, +rest}: %ls.app_assoc(rest, ys, zs) : {x <> List.append(&2, Selection.SlTok, List.append(&2, Selection.SlTok, rest, ys), zs) == x <> _ : List<&2, Selection.SlTok>} {==}
# Cells and answers# -----------------
def ls.le(a: M.Cell, b: M.Cell) -> {M.cell_le(a, b) == Selection.sl_le(a, b) : Bool}: match a: case M.Cell{ar, ac}: match b: case M.Cell{br, bc}: {==}
def ls.same(a: M.Cell, b: M.Cell) -> {M.cell_eq(a, b) == Selection.sl_same(a, b) : Bool}: match a: case M.Cell{ar, ac}: match b: case M.Cell{br, bc}: {==}
def ls.order(a: M.Cell, b: M.Cell) -> {M.order(a, b) == Selection.sl_order(a, b) : M.Rng}: match a: case M.Cell{ar, ac}: match b: case M.Cell{br, bc}: {==}
def ls.sel(m: M.Mode) -> {M.sel(m) == Selection.sl_sel(m) : Maybe<&2, M.Rng>}: match m: case M.Idle{}: {==} case M.Pressed{a}: {==} case M.Selecting{+a, +h}: %Equal.sym(M.Rng, M.order(a, h), Selection.sl_order(a, h), ls.order(a, h)) : {Some{_} == Some{Selection.sl_order(a, h)} : Maybe<&2, M.Rng>} {==} case M.Picked{r}: {==} case M.Shown{r}: {==}
def ls.moved(+m: M.Mode, +p: M.Pan) -> {M.moved(m, p) == Selection.sl_moved(m, p) : M.Res}: %Equal.sym(Maybe<&2, M.Rng>, M.sel(m), Selection.sl_sel(m), ls.sel(m)) : {M.Res{M.St{m, None{}}, M.Out{_, None{}, p, False{}}} == Selection.sl_moved(m, p) : M.Res} {==}
def ls.quiet(+m: M.Mode, +last: Maybe<&2, M.Click>) -> {M.quiet(m, last) == Selection.sl_quiet(m, last) : M.Res}: %Equal.sym(Maybe<&2, M.Rng>, M.sel(m), Selection.sl_sel(m), ls.sel(m)) : {M.Res{M.St{m, last}, M.Out{_, None{}, M.PanNone{}, False{}}} == Selection.sl_quiet(m, last) : M.Res} {==}
# Presses# -------
# a press on the cell of the last press, at most 400 ms later, counts ondef ls.clicks(+r: Nat, +x: Nat, +t1: Nat, +t2: Nat, n: Nat, near: {Bool.and(Nat.is_le(t1, t2), Nat.is_le(Nat.sub(t2, t1), 400n)) == True{} : Bool}) -> {M.clicks(Some{M.Click{M.Cell{r, x}, t1, n}}, M.Cell{r, x}, t2) == M.next(n) : Nat}: %Equal.sym(Bool, Nat.is_eq(r, r), True{}, ls.eq_refl(r)) : {M.near(Bool.and(Bool.and(_, Nat.is_eq(x, x)), Bool.and(Nat.is_le(t1, t2), Nat.is_le(Nat.sub(t2, t1), 400n))), n) == M.next(n) : Nat} %Equal.sym(Bool, Nat.is_eq(x, x), True{}, ls.eq_refl(x)) : {M.near(Bool.and(_, Bool.and(Nat.is_le(t1, t2), Nat.is_le(Nat.sub(t2, t1), 400n))), n) == M.next(n) : Nat} %Equal.sym(Bool, Bool.and(Nat.is_le(t1, t2), Nat.is_le(Nat.sub(t2, t1), 400n)), True{}, near) : {M.near(_, n) == M.next(n) : Nat} {==}