Git Product home page Git Product logo

schmitty's Introduction

Schmitty the Solver

{-# OPTIONS --allow-exec #-}
{-# OPTIONS --guardedness #-}

open import Data.Integer
open import Data.List
open import Data.Product
open import Function
open import Relation.Binary.PropositionalEquality
open import SMT.Theories.Ints as Ints
open import SMT.Backend.Z3 Ints.theory

If you wanna solve some problems, you’re in luck! Schmitty is an Agda library which gives you bindings to SMT solvers! I know, cool right?!

verycool :  (x y : ℤ)  x ≤ y  y ≤ x  x ≡ y
verycool = solveZ3

So, basically, what Schmitty offers you is a well-typed embedding of some of the SMT-LIB language in Agda. That means you can't just shout “solve” at your problems, you can also write SMT queries yourself!

blegh : Script [] (INT ∷ INT ∷ []) (SAT ∷ [])
blegh = `declare-const "x" INT
      $ `declare-const "y" INT
      $ `assert (`app₂ leq (# 0) (# 1))
      $ `assert (`app₂ leq (# 1) (# 0))
      $ `assert (`app₁ not (`app₂ eq (# 0) (# 1)))
      $ `check-sat
      $ []

Ohh, that's almost the script that our call to solveZ3 above generates! What a lucky coincidence! You see, top-level constants are existentially quantified, so that script asks Z3 to see if ∃[ x ] ∃[ y ] (x ≤ y → y ≤ x → x ≢ y) is satisfiable… and if it is, then, well, there must be a counter-example to our original goal!

_ : z3 blegh ≡ unsat ∷ []
_ = refl

Lucky us! It's very unsatisfiable… Wait, how did that work?! Did you just call Z3 while type checking?! Yes, dear reader, I did. You might’ve seen that I recently extended Agda with the execTC primitive, which allows you to make arbitrary system calls during type checking… well, within reason at least. Schmitty lets you take the script above, print it as an SMT-LIB term, and pass it to Z3!

Did you pick up on that unsat there? Schmitty doesn’t just give you back the solver’s output… she’s kind enough to actually parse the output for you! In fact, when Schmitty prints the term, she also builds you an output parser, which parses the expected solver output, including models! Let’s make sure our next query is satisfiable!

yesss : Script [] (INT ∷ INT ∷ []) (MODEL (INT ∷ INT ∷ []) ∷ [])
yesss = `declare-const "x" INT
      $ `declare-const "y" INT
      $ `assert (`app₂ leq (`app₂ sub (# 0) (# 1)) (`app₂ add (# 0) (# 1)))
      $ `assert (`app₁ not (`app₂ eq (# 0) (# 1)))
      $ `get-model
      $ []

If we call get-model instead of check-sat, Schmitty will give us back a valid model!

_ : z3 yesss ≡ ((sat , + 1 ∷ + 0 ∷ []) ∷ [])
_ = refl

Okay, I know that wasn’t a particularly hard problem, but I was in a rush. Send me a pull-request if you’ve got more interesting questions for Schmitty!

Wait, we can get models? Cool! We could use that to get counter-examples, if you try to prove something that isn't true! We, uh… We do:

woops :  (x y : ℤ)  x - y ≤ x + y  x ≡ y
woops = solveZ3

-- > Found counter-example:
--     x = + 1
--     y = + 0
--   refuting (z : + 1 ≤ + 1) → + 1 ≡ + 0
--   when checking that the expression unquote solveZ3 has type
--   (x y : ℤ) → x - y ≤ x + y → x ≡ y

Right now, Schmitty supports three theories—Core, Ints, and Reals—and two backends—Z3, and CVC4. If you’re missing your favourite theory or solver, your contribution is more than welcome!

Installation

Note that the path to z3 must be added to the list of trusted executables in Agda. See manual.

Roadmap

  • Issue: move theorems proved via SMT solvers into Prop or the Classical monad (moderate);
  • Issue: only normalise closed subterms in error messages (moderate);
  • Add error reporting to the parser (easy);
  • Add backends for other SMT-LIB compliant solvers: (verit, bitwuzla, yices2, etc)
  • Add theory of real arithmetic linked to Agda rational numbers (easy);
  • Add theory of floating-point numbers linked to Agda floats (easy);
  • Add theory of strings linked to Agda strings (easy);
  • Add theory of sequences linked to Agda lists (moderate);
  • Add theory of uninterpreted functions and constants linked to Agda names (moderate);
  • Add theory of regular expressions linked to gallais/aGdaREP (moderate);
  • Add theory of algebraic datatypes linked to Agda datatypes (moderate);
  • Add theory of arrays linked to an axiomatisation of Haskell arrays (moderate);
  • Add support for combined theories (moderate);
  • Add support for logic declarations (moderate);
  • Add proof reconstruction for SAT using Kanso.Boolean.SatSolver (moderate);
  • Add proof reconstruction for Z3 proofs (cf. Proof Reconstruction for Z3 in Isabelle/HOL) (hard).

schmitty's People

Contributors

cyberglot avatar gallais avatar gshen42 avatar lysxia avatar matthewdaggitt avatar pre-commit-ci[bot] avatar priyasiddharth avatar ulfnorell avatar wenkokke avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

schmitty's Issues

Better heuristic to guess declare-const vs assert

Right now unused variables are treated as assertions, e.g., this fails:

_ : (x y : ℤ) → x ≤ x  -- Unrecognized identifier Agda.Builtin.Int.Int in script "(assert Agda.Builtin.Int.Int)"

Maybe a better heuristic is to try decoding every element both as a sort and as a term and pick whichever succeeds. It would also be useful to just drop uninterpretable assumptions, so that you can use solveZ3 deep in a term with a lot of junk in the context.

It doesn't seem straightforward to do this at the moment because of the current architecture that produces a RawScript at a stage where the theory-specific decoding functions aren't available.

seeking a working combination of schmitty, agda, agda-stdlib and agdarsec

I tried to install the lower bounds of the suggestions in the README:
Agda (>= 2.6.2-60564a4)
agda-stdlib (>= experimental-d66a21f)
agdarsec (>= master-b26230)

But I get this error:

agda-stdlib/src/Data/List/Membership/Propositional/Properties.agda:17,1-52
Failed to solve the following constraints:
Check definition of to∘from : {P.A.a : Level} {P.A : Set P.A.a}
{P.p : Level} {P = P₁ : Pred P.A P.p} {Q.A.a : Level}
{Q.A : Set Q.A.a} {Q.p : Level} {Q = Q₁ : Pred Q.A Q.p}
{xs = xs₁ : List P.A} {ys = ys₁ : List Q.A}
(pq
: Any (λ x → Any (λ y → Prod.Σ (P₁ x) (λ x₁ → Q₁ y)) ys₁) xs₁) →
Any-×⁺ (Any-×⁻ pq) ≡ pq
stuck because
agda-stdlib/src/Data/List/Relation/Unary/Any/Properties.agda:266,3-34
I'm not sure if there should be a case for the constructor refl,
because I get stuck when trying to solve the following unification
problems (inferred index ≟ expected index):
lhs ≟ Any.map
(λ x →
Any.map (λ q → P.subst P x p , q)
(Any.map
(λ x₁ →
P.subst Q x₁
(_5428 (x = x₂) (pq′ = pq′) (y = y) (y∈ys = y∈ys) (p = p) (q = q)
(lem₂ = lem₂) (pq = pq) (x∈xs = x∈xs) (lem₁ = lem₁)
(p = (P.subst P x p))))
y∈ys))
x∈xs
when checking that the pattern refl has type
lhs ≡
Any.map
(λ x →
Any.map (λ q → P.subst P x p , q)
(Any.map
(λ x₁ →
P.subst Q x₁
(_5428 (x = x₂) (pq′ = pq′) (y = y) (y∈ys = y∈ys) (p = p) (q = q)
(lem₂ = lem₂) (pq = pq) (x∈xs = x∈xs) (lem₁ = lem₁)
(p = (P.subst P x p))))
y∈ys))
x∈xs
(blocked on _P.p_475)
when scope checking the declaration
open import Data.List.Relation.Unary.Any.Properties
agda-stdlib/src/Data/List/Membership/Propositional/Properties.agda:17,1-52
Unsolved metas at the following locations:
agda-stdlib/src/Data/List/Relation/Unary/Any/Properties.agda:100,17-18
agda-stdlib/src/Data/List/Relation/Unary/Any/Properties.agda:105,16-17
agda-stdlib/src/Data/List/Relation/Unary/Any/Properties.agda:105,28-29
when scope checking the declaration
open import Data.List.Relation.Unary.Any.Properties

I also tried the upper bounds - i.e., the latest versions

I get this error:

schmitty/src/Text/Parser/String.agda:53,17-31
Not in scope:
Parser.Success
at schmitty/src/Text/Parser/String.agda:53,17-31
(did you mean 'Success'?)
when scope checking Parser.Success

Multiple definitions of xs⊆xs++ys.

agda/agda-stdlib@c49854d#diff-e0f22a07a1e767e68cb3581868064af185b9557ffbf50917c8668c9ad61b1f14 leads to the error

~/work/schmitty-master/src/Data/List/Relation/Binary/Subset/Propositional/ExtraProperties.agda:22,1-10
Multiple definitions of xs⊆xs++ys. Previous definition at
~/work/agda-stdlib-experimental/src/Data/List/Relation/Binary/Subset/Propositional/Properties.agda:139,1-10
when scope checking the declaration
 xs⊆xs++ys : xs ⊆ xs ++ ys

at least on the current state of the experimental standard library.

Also, schmitty's readme says the standard library should be at least agda/agda-stdlib@da286d0 but the link agda/agda-stdlib@9c56155 is for an earlier pull request. In both cases, I get the error

~/work/agda-stdlib/src/Reflection/Term.agda:392,20-26
Too few arguments to constructor absurd, expected 1 more explicit
argument
when checking that the pattern absurd has type Pattern

I am not sure how to proceed in trying to get the tests to run. I appreciate any advice!

Make robust model tests

The tests which return a model are not robust. For instance:

script : Script [] (REAL ∷ REAL ∷ []) (MODEL (REAL ∷ REAL ∷ []) ∷ [])
script = declare-const "x" REAL
       ∷ declare-const "y" REAL
       ∷ assert (app₂ eq (# 0) (app₂ div (# 1) (lit (nat 2))))
       ∷ assert (app₂ gt (# 0) (lit (nat 1)))
       ∷ assert (app₂ gt (# 1) (lit (nat 1)))
       ∷ get-model
       ∷ []

_ : z3 script ≡ ((sat , 1.5 ∷ 3.0 ∷ []) ∷ [])
_ = refl

These tests are currently written on a by-solver basis, under the assumption that the returned models may differ between solvers, but are deterministic for a single solver. Unfortunately, this is not the case. Therefore, these tests have to be migrated to tests which check the asserted properties, i.e., for the test case above, we should check that z3 script ≡ ((sat , x ∷ y ∷ []) ∷ []) where x ≡ y / 2.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.