This blog post is very interesting, using Rust’s compiler optimizer as a theorem prover. This makes me wonder: are there any formal specifications on the complexity of this "optimizer as theorem prover"?<p>Specifically, how does it handle recursion? Consider, for example, the following function, which decrements a number until it reaches zero. At each step, it asserts that the number is nonzero before recursing:<p>fn recursive_countdown(n: u32) -> u32 {
assert!(n > 0, "n should always be positive");
if n == 1 {
return 1;
}
recursive_countdown(n - 1)
}<p>Can the compiler prove that the assertion always holds and possibly optimize it away? Or does the presence of recursion introduce limitations in its ability to reason about the program?