Comments (10)
from leon.
Strangely enough the Isabelle solver thinks a
and b
are terminating. Leon claims that b(0)
doesn't terminate but Isabelle evaluates that to false
. (I'm guessing because i == 1
evaluates to false
, so the conclusion is never actually executed.)
from leon.
Ok... Would it be possible to give an error in that case? It is a bit strange to see that this code passes verification :)
from leon.
from leon.
It turns out my assessment was wrong. Here's what Isabelle sees:
fun a :: "int ⇒ int" and b :: "int ⇒ bool" where
"a i = i - 1" |
"b i = (i = 1 ⟶ a i = 0)"
Hence, the function definitions themselves are definitely terminating, because there is no call to b
in a
(the Isabelle backend will – by default – not include the pre- and postconditions in the function definition). If the functions are annotated with @isabelle.fullBody
, then Isabelle sees the call to b
and correctly refuses to define the function. I'm unsure what to make of all this.
from leon.
In essence, the question is: How do you deal with pre- and postconditions introducing complications in the call graph?
from leon.
By the way, the Isabelle backend is supposed to always give sound results even without --termination
switched on. So there is definitely an issue here somewhere.
from leon.
I think that @BLepers is not specifically talking about the Isabelle back end. Termination checker should be on by default and turning it off explicitly should be allowed but known to cause soundness issues if the functions are not terminating. @BLepers , let us know what termination checker reports and if it is too weak in some cases.
from leon.
The termination checker says that a does not finish:
[ Info ] ║ apply ✓ Terminates (Non-recursive)
[ Info ] ║ apply ✓ Terminates (Non-recursive)
[ Info ] ║ a ✗ Non-terminating for call: a(0)
[ Info ] ║ b ✗ Calls non-terminating functions a
So I guess it makes sense that the verification phase is not sound for that example (even though it should probably fail by default as Viktor said because errors like that can easily be made).
What I find a bit confusing in that example is that a() never "really" calls b(). I.e., if you run the applicative code without the "ensuring", there is no infinite loop. (Basically I just tried to separate a bit the proof logic - b() - and the applicative code - a()).
from leon.
The guarantee Leon is giving you when it says "valid" is that if you run the code, every time you encounter a contract, it won't evaluate to false
. In this case, Leon is telling you the contract of a() (namely b()) will never evaluate to false
(which is true since it won't terminate). However, you didn't guarantee that the contract would evaluate to true
, which is typically what you would want when you say something is verified.
Note that with termination (and a few other checks that guarantee the program won't crash), never evaluating to false
is equivalent to always evaluating to true
.
from leon.
Related Issues (20)
- Compilation issue HOT 2
- Termination checker unable to prove termination of mutually recursive functions HOT 1
- TODO exception with Map's and class Invariants
- leon with isabelle, undefined session, documentation HOT 4
- Prover error in operation functions: ERROR "Type unification failed: Clash of types \"<markup>\" and \"<markup>\"\n\nType error in application: incompatible operand type\n\n<markup>\n<markup>\n\n<markup>" HOT 4
- Adding ensuring(rec < ...) in a function prevents other functions from being verified
- Termination checker is unsound in handling streams
- Add doc for @traceInduct
- Problem with preprocessing? HOT 3
- Moving to GPL from BSD HOT 2
- Bug in program evaluation/verification
- Bug in ImperativeCodeElimination
- Bug in RecursionCountInstrumenter(?)
- Z3 exception HOT 3
- Support for generic copy() method
- Can the leon library be published as a maven artifact? HOT 1
- Organization of the leon library
- Web interface appears to be failing HOT 3
- Invalid methods actually compiles
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from leon.