This is my windmill tilting project. Pretty raw off the bench kind of stuff, but I'm interested to hear what kinds of things people would use this kind of thing for or ways to make this more understandable to an audience not soaked in formalism.
Some things that I think work well for SMT solvers:
1. Bounded model checking for source code.
2. Finding solutions to constraint problems.
3. Design rule checking for hardware layout and logic gates.
Recently, I built a simple scheduling system using Z3. My wife is a librarian supervisor, and she's been spending hours each week creating schedules by hand. But, with a little Z3, one can enumerate the constraints and let it find a viable example. If the example doesn't work, add more constraints until it does.
Z3 is a marvel. Even if this project is of no interest to a person, Z3 might be. I have intentionally, literally, used z3 data structures to make that transition easier should one find something intriguing here over top of what z3 offers.
Can you give an example of the kinds of constraints that need to get tweaked?
And do you have to tweak them in Z3 each time?
Disclaimer: I know almost nothing about Z3. I'm just picturing you trying to convince her that something like datalog has a learning curve that she'll Totally Be Glad she Powered Through, and she'll Thank you Later for Talking he Into It :)
I wrote a simple DSL that she can use. She knows some HTML and basic scripting, so as long as the rules are easy to express and she has good examples, she can tweak the rules herself.
I just hacked up a little shallow embedding via lex/yacc, using the C API. It's not pretty, but it was put together quickly to solve a problem.
As for typical constraints, there needs to be people on certain desks at certain times. People have to take breaks between N and M hours after starting. People have off-desk time that they use to perform other tasks that must be managed and must be contiguous. People have different numbers of hours they have to work, and a finite amount of time that they are allowed to be on a particular desk on a given day or week.
Sounds like it would be easy to make a set of unsatisfiable constraints. How is that handled in Z3? Can you assign priorities to constraints or something?
You can set soft and hard constraints. Soft constraints can be broken if the system is unsatisfiable otherwise.
For instance, by default, this config sets a soft constraint that two people must be at the desk, and a hard constraint that no more than two people and at least one person must be at the desk. Likewise, there is a soft constraint that desk time must be contiguous, and a hard constraint that desk time must be at least so long to prevent continual splitting.
I have used z3 for a job scheduling problem. I had a piece of equipment which can handle capacity X, jobs come in at known intervals and are available for given durations of varying lengths, some jobs come in multiple times, some jobs must be done above all others. Which jobs should be assigned to the equipment to maximize completed jobs while not missing the high priority entries?
Numbers were such that you could only ever handle a fraction of the possible work. The throughout of a good allocation could be significantly higher than a naive one.
That's a an interesting suggestion! By design, I can swap out or export to nanoCoP-i https://leancop.de/nanocop-i/ , an intuitionistic prover, but I haven't had a good theory the play with. I was considering maybe an intuitionistic set theory, but this seems like a good case too.
Ok so I want to link A Primer of Infinitesimal Analysis https://www.cambridge.org/core/books/primer-of-infinitesimal... this book is so so so good. It begins with nothing and eventually builds enough for Newton-style classical mechanics, made entirely of geometric arguments using infinitesimals, and being fully rigorous. Also has an appendix where it gives the construction using category theory
Anyway so does this mean that Z3 can't be used to prove intuitonistic arguments? That's surprising to me. What exactly makes SMT tied to classical logic?
edit: okay check out this https://dl.acm.org/doi/10.5555/1983702.1983729 the author used an embedding in order to represent intuitionistic formulas inside classical logic, so they could use Z3 anyway
I think embedding intuitionistic logic into z3 is possible in some sense and perhaps even useful. I would a priori expect a prover built from the ground up like nanoCoP-i to deal with intuitionistic logic to be better, even if it is orders of magnitude less complex than z3.
I don't think the concept of SMT is has to be tied to classical logic in some abstract sense, but the SMTlib standard is classical. And in the sense that an SMT solver is SAT solver (kind of as classical as you can get) bolted to theories. But seems reasonable to build some kind of framework bolting domain specific intuitionistic solvers to a intuitionistic fabric.
Nice write-up. If I find the time it would be interesting to dive a bit deeper than a shallow read and compare with how things are done in Rosette, which I have more experience with than the Z3Py-interface.
It is not trying to prove things about python code.
It is building facilities and theory libraries around the pre-existing z3 python interface in a manner that can be reasonably called an interactive theorem prover. Hopefully, eventually, with a lower barrier to entry (and probably lower expressivity ceiling) than pre-existing systems like Lean, Coq, Isabelle.
I am targeting applications close to my heart, like calculus, differential equations, dynamical systems, numerical calculations, software verification. It is a tall order. No promises.
Is there an idea here that you could write out a script and then compile out a Python implementation (for example?), given you have the `Record` code, for example?
I have had a decent number of times where if I was told "write this code in this Python DSL, and then you can do interactive theorem proofs just on that bit", I would be pretty satisfied, even if it meant really cutting down what kind of objects I could use in the process.
I think what you're referring to is code generation or extraction https://coq.inria.fr/doc/V8.11.1/refman/addendum/extraction.... out of knuckledragger? It wouldn't be that difficult to traverse a z3 expression and generate the text of reasonable python code for a subset of possible z3 expressions. It would probably be easiest to extract purely functional code, which would be somewhat non-idiomatic python. I suppose extraction to pytorch, numpy, or pandas could be useful.
If by "Record" you're referring to the Record helper in the blog post, that was nothing clever. Just a helper to define struct-like datatypes (record types).
I did do some experimentation using the python parser to turn python code into z3 expressions but I haven't pushed on that https://www.philipzucker.com/applicative_python/ It is a little annoying to not be able to use the nice native python if-then-else or match syntax.
Bit of a different space, but Amaranth does some fun stuff to copy control flow. It's obviously not "native" `if-then-else` but it's close enough for things that matter IMO.
How do your project and Z3 compare to (1) Logic programming tools like Prolog and (2) optimizers like scipy.optimize?
All of these seem to find solutions to user-provided constraint sets. They must be appropriate for different classes of problems, but it’s not obvious to me how that breaks out.
It’s, uh, been a long time since I last hand-rolled an optimization algorithm…
This is a tough comparison. They are very similar in some respects but also very distinct.
Prolog has some operational flavor to it. You can predict what it'll do. It can be used as "just" a programming language akin to python with fairly little logical/mathemtical content. Declarative Prolog as in constraint logic programming is in the realm of attacking similar logical problems to z3.
scipy.optimize is a grab bag of stuff. Some of it is pretty heuristic. It's all subject to floating point error, which is the devil we live with. The milp and lp solvers are relatives of how z3 handles linear inequality constraints. scipy.optimize doesn't treat logic at all really. It takes in mathematical multivariate functions and finds roots or minima.
Z3 is intended to be mathematically rigorous. It is less operational than prolog. On big combinatorial problems (SAT, bitvector problems), it is probably a superior tool. It does have an optimization interface, I haven't used it much.
