Express properties about Haskell programs and automatically prove them using SMT solvers.
$ ghci ghci> :m Data.SBV ghci> prove $ \x -> x `shiftL` 2 .== 4 * (x::SWord8) Q.E.D. ghci> prove $ \x -> x `shiftL` 2 .== 2 * (x::SWord8) Falsifiable. Counter-example: s0 = 32 :: Word8
prove establishes theorem-hood, while
sat finds any satisfying model. All satisfying models can be computed using
allSat. SBV can also perform static assertion checks, such as absence of division-by-0, and other user given properties. Furthermore, SBV can perform
optimization, minimizing/maximizing arithmetic goals for their optimal values.
SBV also allows for an incremental mode: Users are given a handle to the SMT solver as their programs execute, and they can issue SMTLib commands
programmatically, query values, and direct the interaction using a high-level typed API. The incremental mode also allows for creation of constraints
based on the current model, and access to internals of SMT solvers for advanced users. See the
query commands for details.
SBV library provides support for dealing with symbolic values in Haskell. It introduces the types:
SBool: Symbolic Booleans (bits).
SWord64: Symbolic Words (unsigned).
SInt64: Symbolic Ints (signed).
SInt N, for N > 0: Arbitrary sized unsigned/signed bit-vectors, parameterized by the bitsize. (Using DataKinds extension.)
SInteger: Symbolic unbounded integers (signed).
SReal: Symbolic infinite precision algebraic reals (signed).
SRational: Symbolic rationals, ratio of two symbolic integers. (
SFloat: IEEE-754 single precision floating point number. (
SDouble: IEEE-754 double precision floating point number. (
SFloatingPoint: IEEE-754 floating point number with user specified exponent and significand sizes. (
SChar: Symbolic characters. (Currently Latin-1, but will be unicode in the future.)
SString: Symbolic strings.
SList: Symbolic lists. (Which can be nested, i.e., lists of lists.)
STuple: Symbolic tuples (upto 8-tuples, can be nested)
SEither: Symbolic sums
SMaybe: Symbolic optional values
SSet: Symbolic sets
The user can construct ordinary Haskell programs using these types, which behave like ordinary Haskell values when used concretely. However, when used with symbolic arguments, functions built out of these types can also be:
satfunction with existentials),
The SBV library uses third-party SMT solvers via the standard SMT-Lib interface. The following solvers are supported:
Most functions have two variants: For instance
proveWith. The former uses the default solver, which is currently Z3.
The latter expects you to pass it a configuration that picks the solver. The valid values are
See versions for a listing of the versions of these tools SBV has been tested with. Please report if you see any discrepancies!
Other SMT solvers can be used with SBV as well, with a relatively easy hook-up mechanism. Please do get in touch if you plan to use SBV with any other solver.
SBV also allows for running multiple solvers at the same time, either picking the result of the first to complete, or getting results from all. See
satWithAll functions. The function
sbvAvailableSolvers can be used to query the available solvers at run-time.
The following people made major contributions to SBV, by developing new features and contributing to the design in significant ways: Joel Burget, Brian Huffman, Brian Schroeder, and Jeffrey Young.
The following people reported bugs, provided comments/feedback, or contributed to the development of SBV in various ways: Ara Adkins, Kanishka Azimi, Markus Barenhoff, Reid Barton, Ben Blaxill, Ian Blumenfeld, Guillaume Bouchard, Martin Brain, Ian Calvert, Oliver Charles, Christian Conkle, Matthew Danish, Iavor Diatchki, Alex Dixon, Robert Dockins, Thomas DuBuisson, Trevor Elliott, Gergő Érdi, John Erickson, Adam Foltzer, Joshua Gancher, Remy Goldschmidt, Brad Hardy, Tom Hawkins, Greg Horn, Jan Hrcek, Georges-Axel Jaloyan, Anders Kaseorg, Tom Sydney Kerckhove, Piërre van de Laar, Pablo Lamela, Joe Leslie-Hurd, Brett Letner, Georgy Lukyanov, Martin Lundfall, John Matthews, Curran McConnell, Philipp Meyer, Joshua Moerman, Matt Parker, Jan Path, Matt Peddie, Matthew Pickering, Lee Pike, Gleb Popov, Rohit Ramesh, Geoffrey Ramseyer, Jaro Reinders, Stephan Renatus, Dan Rosén, Ryan Scott, Eric Seidel, Austin Seipp, Andrés Sicard-Ramírez, Don Stewart, Greg Sullivan, Josef Svenningsson, Daniel Wagner, Sean Weaver, Nis Wegmann, and Jared Ziegler.