Search code examples
c++constraintsz3constraint-programminggecode

Gecode vs. Z3 for Constrained Randomization

I'm looking for a C++-based alternative to the SystemVerilog language. While I doubt anything out there can match the simplicity and flexibility of the SystemVerilog constraint language, I have settled on using either Z3 or Gecode for what I'm working on, primarily because they're both under the MIT license.

What I'm looking for is:

  1. Support for variable-sized bit vectors AND bit vector arithmetic logic operations. For example:
bit_vector a<30>;
bit_vector b<30>;
constraint { 
    a == (b << 2);
    a == (b * 2);
    b < a;
}

The problem with Gecode, as far as I can tell, is that it does not provide bit vectors right out of the box. However, its programming model seems a bit simpler, and it does provide a means for one to create their own types of variables. So I could perhaps creates some kind of wrapper around the C++ bitset, similar to how IntVar wraps around 32-bit integers. However, that would lack the ability to perform multiplication-based constrains, since C++ bitsets don't support such operations.

Z3 does provide bit vectors right out of the box, but I'm not sure how it would handle trying to set constraints on, for example, 128-bit vectors. I'm also unsure how I can specify that I want to produce a variety of randomized variables that satisfy a constraint when possible. With Gecode, it's much clearer given how thorough its documentation is.

  1. A simplistic constraint programming model, close or similar to SystemVerilog. For example, a language where I only need to type (x == y + z) instead of something like EQ(x, y + z). As far as I can tell, both APIs provide such a simple programming model.

  2. A means of performing constrained randomization, for the sake of producing random stimulus. As in, I can provide some random seed that, depending on the constraints, result in an answer that may differ from the previous answer. Similar to how SystemVerilog randomize calls may produce new random results. Gecode seems to support the use of random seeds. Z3, it's much less clear.

  3. Support for weighted distribution. Gecode appears to support this via weighted sets. I imagine I can establish a relationship between certain conditions and boolean variables, and then add weights to those variables. Z3 appears to be more flexible in that you can assign weights to expressions, via the optimize class.

At the moment, I'm undecided, because Z3 lacks in documentation what Gecode lacks in out-of-the-box variable types. I'm wondering if anyone has any prior experience using either tool to achieve what SystemVerilog could. I'd like to hear any suggestions for any other API under a flexible license as well.

Solution

  • While z3 (or any SMT solver) can handle all of these, getting a nice sampling of satisfying assignments would be rather difficult to control. SMT solvers are optimized for just giving you a model, and they don't have much in terms of how you want to sample the solution space.

    Incidentally, this is an active research area in SMT solving. Here's a paper that appeared only 6 weeks ago on this very topic: https://ieeexplore.ieee.org/document/8894251

    So, I'd say if support for "good sampling" is your primary motivation, using an SMT solver is probably not the best choice. If your goal is to find satisfying assumptions for bit-vectors expressed conveniently (there are high level APIs in any language you can imagine these days), then z3 would be an extremely fine choice.

    From your description, good sampling sounds like the primary motivation though, and for that SMT solvers are probably not that great. At least not for the time being.