-
Notifications
You must be signed in to change notification settings - Fork 0
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Inclusion/Lattice of Logics #27
Comments
Hi Guillaume, |
It depends on what exactly you mean by "using an Int constant where a Real is expected will not be allowed anymore": there are currently two different situations that I think may fit that description/formulation, and depending on which of these two is not allowed anymore (maybe both ?) the problem may persist or not. The two situations are as follows:
In practice, this is point 2 that is problematic I think (at least for this issue). That being said, point 2 does not allow to "use an Int constant where a Real is expected" (that formulation is closer to the point 1 above), but rather it is that "an Int constant" is actually either an So the question, is whether it is 1, 2 (or both, or another solution ?) that are not to be allowed anymore in SMT-LIB 3 ? |
In SMT-LIB 3, + is overloaded with types (-> Real Real Real) and (-> Int Int Int). (+ 1 2.5) is not well-typed, but (+1 2) and (1. 2.5) are. There is no silent conversion from an Int constant to a Real. |
So, if I understand correctly, this means that both points 1 and 2 from my above post will no longer be allowed in SMT-LIB 3. In that case, this issue will indeed disappear in SMT-LIB 3. Side note: you say that |
Indeed
Sorry, I was not rigorous. Only lexically valid decimal numbers will be allowed, so "1.0", not "1." |
Thanks for all the clarifications ! I guess the specific issue I raised will be resolved in SMT-LIB 3. That being said, about the most general question I was also wondering: is the inclusion of logics (e.g. following the graph of the SMT-LIB website, and the inclusion of any logic in the |
The very concept of logic somehow disappears in SMT-LIB3. A new concept of module stands for both theories and logics. It is easy to simulate an old logic, with a module that includes modules standing for theories in the combination. Artificial limitations or strange particularities of logic are more complicated to exactly reproduce in SMT-LIB 3, so this will have a "cleaning" side effect. And this gives a more flexible framework. It is not clear to me yet how categorization of benchmarks, etc... will evolve within this new context. |
In a nutshell: there are SMT-LIB problems that can be typechecked in a given logic, but may not be typechecked in the
ALL
logic.Context and problematic example
More precisely, the webpage for logic in the SMT-LIB website (cf https://smt-lib.org/logics.shtml ), presents a graph of logics "ordered by inclusion". What is meant exactly by "inclusion" is a bit unclear though, but I'd naively expect that if a logic
A
is included in another logicB
, then any valid problem forA
is also a valid problem forB
. However, there are (at least) two logics that are linked in the graph on the webpage, thus suggesting there should be some inclusion, but that do not respect the 'naive' criterion I wrote just above.Consider the following example:
This is a valid (as in, typecheckable and conformant to the SMT-LIB specification) file for the given
UFLRA
logic. However, if you change the logic toUFLIRA
(or theAUFLIRA
logic, which the webpage suggests should include theUFLRA
logic), then it is not valid/compliant anymore. Similarly this file would not be valid/compliant in theALL
logic, assuming that the solver/tool supports/includesLIRA
/NIRA
inALL
(and that is the current behavior implemented indolmen
).That is a problem in practice, as it did make the model validation part of the SMT-COMP harder (cc @bobot ) : indeed due to that fact, even if a file is valid/compliant, it may not be valid/compliant if you force the logic to be
ALL
(which was sometimes necessary to use during SMT-COMP because some problems of the SMT-LIB library are misclassified and do not respect the restrictions of their declared logic). In any case, i'd argue that it is a very surprising behavior for users that going from a logic to a "larger" logic may break the typechecking of some problems.Explanation and solutions
The root problem of these behaviors is the following: in real-only arithmetic, integer literals, such as
42
are interpreted as real constants, however, with both integer and real arithmetic, integer literals are interpreted as integer constants, which means that the type of42
effectively changes fromReal
toInt
when going from a real-only logic to a integer-and-real logic.One may object that the arithmetic theories (and therefore also the corresponding logics) have a mechanism to automatically cast an integer expression into a real one when needed by introducing a
to_real
application, however, that is only specified to apply for arithmetic operators (i.e.+
,-
, ...), and therefore does not apply to a user-defined function as in the example above.I would strongly object to making that syntactic sugar apply to all function symbols, because it means that the
Reals
theory would effectively change the typing rules of other theories and of the general first-order application globally. Even if that was restricted to literals, that still means that type-checking would not be "local" anymore, and instead become dependent on the context (and not just the names in scope): while that may work currently (and even then, that is a "may"), in a context with polymorphism and type inference, this would become extremely complex to implement and reason about.One solution would be to never interpret integer literals as real constants, but that would likely break some problems. That being said, the export/printing functionality of dolmen makes sure to generate problems that always use the non-ambiguous literal form (i.e. it inserts
.0
to make sure a real literal will always be parsed as a real and not an integer).Conclusion
I haven't yet found other (better) solutions to this problem, but I'm interested in feedback from the maintainers on the severity of this issue: should logics have a notion of inclusion (as I understand it) ? if so should be try and fix the spec ?
The text was updated successfully, but these errors were encountered: