Zulip Chat Archive

Stream: lean4

Topic: Delightful typo in a nontrivial routine


Geoffrey Irving (Jan 06 2024 at 20:34):

Here's a case-analysis intensive routine from what I'm currently working on, which is a fun example of programming alongside theorem proving:

/-- Multiply, changing `s` -/
def Interval.mul (x : Interval s) (y : Interval t) (u : Int64) : Interval u :=
  bif x == 0 || y == 0 then 0
  else bif x.lo == nan || x.hi == nan || y.lo == nan || y.hi == nan then nan,nan
  else bif x.lo.n.isNeg != x.hi.n.isNeg && y.lo.n.isNeg != x.hi.n.isNeg then  -- x,y have mixed sign
    min (x.lo.mul y.hi u false) (x.hi.mul y.lo u false),
     max (x.lo.mul y.lo u true) (x.hi.mul y.hi u true)⟩
  else -- At least one of x,y has constant sign, so we can save multiplications
    let (a,b,c,d) := match (x.lo.n.isNeg, x.hi.n.isNeg, y.lo.n.isNeg, y.hi.n.isNeg) with
      | (false, _, false, _)    => (x.lo, x.hi, y.lo, y.hi)  -- 0 ≤ x, 0 ≤ y
      | (false, _, true, false) => (x.hi, x.hi, y.lo, y.hi)  -- 0 ≤ x, 0 ∈ y
      | (false, _, _, true)     => (x.hi, x.lo, y.lo, y.hi)  -- 0 ≤ x, y ≤ 0
      | (true, false, false, _) => (x.lo, x.hi, y.hi, y.hi)  -- 0 ∈ x, 0 ≤ y
      | (true, false, _, _)     => (x.hi, x.lo, y.lo, y.lo)  -- 0 ∈ x, y ≤ 0 (0 ∈ y is impossible)
      | (_, true, false, _)     => (x.lo, x.hi, y.hi, y.lo)  -- x ≤ 0, 0 ≤ y
      | (_, true, true, false)  => (x.lo, x.lo, y.hi, y.lo)  -- x ≤ 0, 0 ∈ y
      | (_, true, _, true)      => (x.hi, x.lo, y.hi, y.lo)  -- x ≤ 0, y ≤ 0
    a.mul c u false, b.mul d u true

I proved this code correct: it is a conservative approximation of real multiplication. However, it also has a typo: the first line in the following should be the second:

  else bif x.lo.n.isNeg != x.hi.n.isNeg && y.lo.n.isNeg != x.hi.n.isNeg then  -- wrong: last x should be a y
  else bif x.lo.n.isNeg != x.hi.n.isNeg && y.lo.n.isNeg != y.hi.n.isNeg then  -- correct

But it doesn't matter! The two comparisons y.lo.n.isNeg != x.hi.n.isNeg and y.lo.n.isNeg != y.hi.n.isNeg are equal when it matters, since if x has mixed sign then x.hi must be positive. And indeed my split-and-simplify proof didn't notice this typo, since the relevant case simplified to the same thing. :)

Mario Carneiro (Jan 09 2024 at 02:50):

if it's still correct, is it really a typo?


Last updated: May 02 2025 at 03:31 UTC