I am nonetheless studying about FM, however I believe I can provide some coarse instance.
To start with, “Formal Strategies” will be many issues, however let’s deal with one thing like what you talked about.
There certainly are circumstances the place you would write 2 occasions the identical algorithm in numerous methods (completely different languages or not), and make sure that they’re constant. For instance: the Fibonacci sequence is definitely outlined with a mathematical recursive operate. In C:
int fib(int i){
return fib(i-1) + fib(i-2);
}
You possibly can deal with that operate as a specification that’s straightforward to jot down, perceive and confirm; however for those who attempt to use that operate to calculate an extended sequence of the sequence, it is terribly costly / gradual.
Now, you would write an optimized model of that very same operate utilizing any variety of methods to make it a lot sooner. Your compiler would possibly even apply some methods mechanically! However then, how will you ensure that your new optimized operate is admittedly calculating the identical factor because the specification (the unique operate)? Possibly there’s new nook circumstances that did not exist within the specification? Even, perhaps your compiler has a bug that can make the optimized model fail with large numbers?
As you mentioned, testing will solely present that some circumstances are appropriate (i.e., the outcomes of each capabilities are the identical in a finite variety of circumstances).
In distinction, formal verification would help you:
- make sure that the specification is “ok” and self-consistent.
- make sure that the optimized model is at all times equal to the specification.
How is (1) potential? Effectively, as an alternative of C, we might use some language that may assist you to pin down what you’re verifying, after which really confirm it. For instance, is i allowed to be unfavourable? What occurs when i == 0? What if i is large and the sum of outcomes is just too large to slot in the sort int?
And so it might be that you just develop a specification in a single language (e.g. Isabelle/HOL), after which generate code from it; or confirm that the specification corresponds to code presumably written in a distinct language (e.g. C).
