SyGuS: Invariants ¶
examples/api/cpp/sygus-inv.cpp
1 /******************************************************************************
2 * Top contributors (to current version):
3 * Abdalrhman Mohamed, Mathias Preiner, Mudathir Mohamed
4 *
5 * This file is part of the cvc5 project.
6 *
7 * Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
8 * in the top-level source directory and their institutional affiliations.
9 * All rights reserved. See the file COPYING in the top-level source
10 * directory for licensing information.
11 * ****************************************************************************
12 *
13 * A simple demonstration of the Sygus API.
14 *
15 * A simple demonstration of how to use the Sygus API to synthesize a simple
16 * invariant.
17 */
18
19 #include <cvc5/cvc5.h>
20
21 #include <iostream>
22
23 #include "utils.h"
24
25 using namespace cvc5;
26
27 int main()
28 {
29 Solver slv;
30
31 // required options
32 slv.setOption("sygus", "true");
33 slv.setOption("incremental", "false");
34
35 // set the logic
36 slv.setLogic("LIA");
37
38 Sort integer = slv.getIntegerSort();
39 Sort boolean = slv.getBooleanSort();
40
41 Term zero = slv.mkInteger(0);
42 Term one = slv.mkInteger(1);
43 Term ten = slv.mkInteger(10);
44
45 // declare input variables for functions
46 Term x = slv.mkVar(integer, "x");
47 Term xp = slv.mkVar(integer, "xp");
48
49 // (ite (< x 10) (= xp (+ x 1)) (= xp x))
50 Term ite = slv.mkTerm(ITE,
51 {slv.mkTerm(LT, {x, ten}),
52 slv.mkTerm(EQUAL, {xp, slv.mkTerm(ADD, {x, one})}),
53 slv.mkTerm(EQUAL, {xp, x})});
54
55 // define the pre-conditions, transition relations, and post-conditions
56 Term pre_f =
57 slv.defineFun("pre-f", {x}, boolean, slv.mkTerm(EQUAL, {x, zero}));
58 Term trans_f = slv.defineFun("trans-f", {x, xp}, boolean, ite);
59 Term post_f =
60 slv.defineFun("post-f", {x}, boolean, slv.mkTerm(LEQ, {x, ten}));
61
62 // declare the invariant-to-synthesize
63 Term inv_f = slv.synthInv("inv-f", {x});
64
65 slv.addSygusInvConstraint(inv_f, pre_f, trans_f, post_f);
66
67 // print solutions if available
68 if (slv.checkSynth().hasSolution())
69 {
70 // Output should be equivalent to:
71 // (
72 // (define-fun inv-f ((x Int)) Bool (not (>= x 11)))
73 // )
74 std::vector<Term> terms = {inv_f};
75 utils::printSynthSolutions(terms, slv.getSynthSolutions(terms));
76 }
77
78 return 0;
79 }
examples/api/java/SygusInv.java
1 /******************************************************************************
2 * Top contributors (to current version):
3 * Mudathir Mohamed, Andrew Reynolds, Andres Noetzli
4 *
5 * This file is part of the cvc5 project.
6 *
7 * Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
8 * in the top-level source directory and their institutional affiliations.
9 * All rights reserved. See the file COPYING in the top-level source
10 * directory for licensing information.
11 * ****************************************************************************
12 *
13 * A simple demonstration of the Sygus API.
14 *
15 * A simple demonstration of how to use the Sygus API to synthesize a simple
16 * invariant. This is a direct translation of sygus-inv.cpp.
17 */
18
19 import static io.github.cvc5.Kind.*;
20
21 import io.github.cvc5.*;
22
23 public class SygusInv
24 {
25 public static void main(String args[]) throws CVC5ApiException
26 {
27 try (Solver slv = new Solver())
28 {
29 // required options
30 slv.setOption("sygus", "true");
31 slv.setOption("incremental", "false");
32
33 // set the logic
34 slv.setLogic("LIA");
35
36 Sort integer = slv.getIntegerSort();
37 Sort bool = slv.getBooleanSort();
38
39 Term zero = slv.mkInteger(0);
40 Term one = slv.mkInteger(1);
41 Term ten = slv.mkInteger(10);
42
43 // declare input variables for functions
44 Term x = slv.mkVar(integer, "x");
45 Term xp = slv.mkVar(integer, "xp");
46
47 // (ite (< x 10) (= xp (+ x 1)) (= xp x))
48 Term ite = slv.mkTerm(ITE,
49 slv.mkTerm(LT, x, ten),
50 slv.mkTerm(EQUAL, xp, slv.mkTerm(ADD, x, one)),
51 slv.mkTerm(EQUAL, xp, x));
52
53 // define the pre-conditions, transition relations, and post-conditions
54 Term pre_f = slv.defineFun("pre-f", new Term[] {x}, bool, slv.mkTerm(EQUAL, x, zero));
55 Term trans_f = slv.defineFun("trans-f", new Term[] {x, xp}, bool, ite);
56 Term post_f = slv.defineFun("post-f", new Term[] {x}, bool, slv.mkTerm(LEQ, x, ten));
57
58 // declare the invariant-to-synthesize
59 Term inv_f = slv.synthInv("inv-f", new Term[] {x});
60
61 slv.addSygusInvConstraint(inv_f, pre_f, trans_f, post_f);
62
63 // print solutions if available
64 if (slv.checkSynth().hasSolution())
65 {
66 // Output should be equivalent to:
67 // (
68 // (define-fun inv-f ((x Int)) Bool (not (>= x 11)))
69 // )
70 Term[] terms = new Term[] {inv_f};
71 Utils.printSynthSolutions(terms, slv.getSynthSolutions(terms));
72 }
73 }
74 }
75 }
examples/api/python/sygus-inv.py
1 #!/usr/bin/env python
2 ###############################################################################
3 # Top contributors (to current version):
4 # Yoni Zohar, Aina Niemetz, Mudathir Mohamed
5 #
6 # This file is part of the cvc5 project.
7 #
8 # Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
9 # in the top-level source directory and their institutional affiliations.
10 # All rights reserved. See the file COPYING in the top-level source
11 # directory for licensing information.
12 # #############################################################################
13 #
14 # A simple demonstration of the solving capabilities of the cvc5
15 # sygus solver through the Python API. This is a direct
16 # translation of sygus-inv.cpp .
17 ##
18
19 import utils
20 import cvc5
21 from cvc5 import Kind
22
23 if __name__ == "__main__":
24 slv = cvc5.Solver()
25
26 # required options
27 slv.setOption("sygus", "true")
28 slv.setOption("incremental", "false")
29
30 # set the logic
31 slv.setLogic("LIA")
32
33 integer = slv.getIntegerSort()
34 boolean = slv.getBooleanSort()
35
36 zero = slv.mkInteger(0)
37 one = slv.mkInteger(1)
38 ten = slv.mkInteger(10)
39
40 # declare input variables for functions
41 x = slv.mkVar(integer, "x")
42 xp = slv.mkVar(integer, "xp")
43
44 # (ite (< x 10) (= xp (+ x 1)) (= xp x))
45 ite = slv.mkTerm(Kind.ITE,
46 slv.mkTerm(Kind.LT, x, ten),
47 slv.mkTerm(Kind.EQUAL, xp, slv.mkTerm(Kind.ADD, x, one)),
48 slv.mkTerm(Kind.EQUAL, xp, x))
49
50 # define the pre-conditions, transition relations, and post-conditions
51 pre_f = slv.defineFun("pre-f", [x], boolean, slv.mkTerm(Kind.EQUAL, x, zero))
52 trans_f = slv.defineFun("trans-f", [x, xp], boolean, ite)
53 post_f = slv.defineFun("post-f", [x], boolean, slv.mkTerm(Kind.LEQ, x, ten))
54
55 # declare the invariant-to-synthesize
56 inv_f = slv.synthInv("inv-f", {x})
57
58 slv.addSygusInvConstraint(inv_f, pre_f, trans_f, post_f)
59
60 # print solutions if available
61 if slv.checkSynth().hasSolution():
62 # Output should be equivalent to:
63 # (define-fun inv-f ((x Int)) Bool (not (>= x 11)))
64 terms = [inv_f]
65 utils.print_synth_solutions(terms, slv.getSynthSolutions(terms))
66
67
examples/api/smtlib/sygus-inv.sy
1 ; The printed output for this example should be equivalent to:
2 ; (
3 ; (define-fun inv-f ((x Int)) Bool (not (>= x 11)))
4 ; )
5
6 (set-logic LIA)
7 (synth-inv inv-f ((x Int)))
8 (define-fun pre-f ((x Int)) Bool (= x 0))
9 (define-fun trans-f ((x Int) (xp Int)) Bool (ite (< x 10) (= xp (+ x 1)) (= xp x)))
10 (define-fun post-f ((x Int)) Bool (<= x 10))
11 (inv-constraint inv-f pre-f trans-f post-f)
12 (check-synth)
The utility method used for printing the synthesis solutions in the examples
above is defined separately in the
utils
module:
1 /******************************************************************************
2 * Top contributors (to current version):
3 * Abdalrhman Mohamed, Mathias Preiner
4 *
5 * This file is part of the cvc5 project.
6 *
7 * Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
8 * in the top-level source directory and their institutional affiliations.
9 * All rights reserved. See the file COPYING in the top-level source
10 * directory for licensing information.
11 * ****************************************************************************
12 *
13 * Utility methods.
14 */
15
16 #ifndef CVC5__UTILS_H
17 #define CVC5__UTILS_H
18
19 #include <cvc5/cvc5.h>
20
21 namespace utils {
22
23 /**
24 * Print solutions for synthesis conjecture to the standard output stream.
25 * @param terms the terms for which the synthesis solutions were retrieved
26 * @param sols the synthesis solutions of the given terms
27 */
28 void printSynthSolutions(const std::vector<cvc5::Term>& terms,
29 const std::vector<cvc5::Term>& sols);
30
31 } // namespace utils
32
33 #endif // CVC5__UTILS_H
1 /******************************************************************************
2 * Top contributors (to current version):
3 * Abdalrhman Mohamed, Mathias Preiner, Yoni Zohar
4 *
5 * This file is part of the cvc5 project.
6 *
7 * Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
8 * in the top-level source directory and their institutional affiliations.
9 * All rights reserved. See the file COPYING in the top-level source
10 * directory for licensing information.
11 * ****************************************************************************
12 *
13 * Implementations of utility methods.
14 */
15
16 #include "utils.h"
17
18 #include <iostream>
19
20 namespace utils {
21
22 using namespace cvc5;
23
24 /**
25 * Get the string version of define-fun command.
26 * @param f the function to print
27 * @param params the function parameters
28 * @param body the function body
29 * @return a string version of define-fun
30 */
31 std::string defineFunToString(const cvc5::Term& f,
32 const std::vector<cvc5::Term>& params,
33 const cvc5::Term& body)
34 {
35 cvc5::Sort sort = f.getSort();
36 if (sort.isFunction())
37 {
38 sort = sort.getFunctionCodomainSort();
39 }
40 std::stringstream ss;
41 ss << "(define-fun " << f << " (";
42 for (size_t i = 0, n = params.size(); i < n; ++i)
43 {
44 if (i > 0)
45 {
46 ss << ' ';
47 }
48 ss << '(' << params[i] << ' ' << params[i].getSort() << ')';
49 }
50 ss << ") " << sort << ' ' << body << ')';
51 return ss.str();
52 }
53
54 void printSynthSolutions(const std::vector<cvc5::Term>& terms,
55 const std::vector<cvc5::Term>& sols)
56 {
57 std::cout << '(' << std::endl;
58 for (size_t i = 0, n = terms.size(); i < n; ++i)
59 {
60 std::vector<cvc5::Term> params;
61 cvc5::Term body = sols[i];
62 if (sols[i].getKind() == cvc5::LAMBDA)
63 {
64 params.insert(params.end(), sols[i][0].begin(), sols[i][0].end());
65 body = sols[i][1];
66 }
67 std::cout << " " << defineFunToString(terms[i], params, body) << std::endl;
68 }
69 std::cout << ')' << std::endl;
70 }
71
72 } // namespace utils
1 /******************************************************************************
2 * Top contributors (to current version):
3 * Mudathir Mohamed, Abdalrhman Mohamed, Andres Noetzli
4 *
5 * This file is part of the cvc5 project.
6 *
7 * Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
8 * in the top-level source directory and their institutional affiliations.
9 * All rights reserved. See the file COPYING in the top-level source
10 * directory for licensing information.
11 * ****************************************************************************
12 *
13 * Utility methods.
14 */
15
16 import io.github.cvc5.CVC5ApiException;
17 import io.github.cvc5.Kind;
18 import io.github.cvc5.Sort;
19 import io.github.cvc5.Term;
20 import java.util.ArrayList;
21 import java.util.List;
22
23 public class Utils
24 {
25 /**
26 * Get the string version of define-fun command.
27 *
28 * @param f the function to print
29 * @param params the function parameters
30 * @param body the function body
31 * @return a string version of define-fun
32 */
33 private static String defineFunToString(Term f, Term[] params, Term body)
34 {
35 Sort sort = f.getSort();
36 if (sort.isFunction())
37 {
38 sort = sort.getFunctionCodomainSort();
39 }
40 StringBuilder ss = new StringBuilder();
41 ss.append("(define-fun ").append(f).append(" (");
42 for (int i = 0; i < params.length; ++i)
43 {
44 if (i > 0)
45 {
46 ss.append(' ');
47 }
48 ss.append('(').append(params[i]).append(' ').append(params[i].getSort()).append(')');
49 }
50 ss.append(") ").append(sort).append(' ').append(body).append(')');
51 return ss.toString();
52 }
53
54 /**
55 * Print solutions for synthesis conjecture to the standard output stream.
56 *
57 * @param terms the terms for which the synthesis solutions were retrieved
58 * @param sols the synthesis solutions of the given terms
59 */
60 public static void printSynthSolutions(Term[] terms, Term[] sols) throws CVC5ApiException
61 {
62 System.out.println('(');
63 for (int i = 0; i < terms.length; ++i)
64 {
65 List<Term> params = new ArrayList<>();
66 Term body = sols[i];
67 if (sols[i].getKind() == Kind.LAMBDA)
68 {
69 for (Term t : sols[i].getChild(0))
70 {
71 params.add(t);
72 }
73 body = sols[i].getChild(1);
74 }
75 System.out.println(" " + defineFunToString(terms[i], params.toArray(new Term[0]), body));
76 }
77 System.out.println(')');
78 }
79 }
1 #!/usr/bin/env python
2 ###############################################################################
3 # Top contributors (to current version):
4 # Yoni Zohar, Abdalrhman Mohamed, Alex Ozdemir
5 #
6 # This file is part of the cvc5 project.
7 #
8 # Copyright (c) 2009-2022 by the authors listed in the file AUTHORS
9 # in the top-level source directory and their institutional affiliations.
10 # All rights reserved. See the file COPYING in the top-level source
11 # directory for licensing information.
12 # #############################################################################
13 #
14 # Utility Methods, translated from examples/api/utils.h
15 ##
16
17 import cvc5
18 from cvc5 import Kind
19
20 # Get the string version of define-fun command.
21 # @param f the function to print
22 # @param params the function parameters
23 # @param body the function body
24 # @return a string version of define-fun
25
26
27 def define_fun_to_string(f, params, body):
28 sort = f.getSort()
29 if sort.isFunction():
30 sort = f.getSort().getFunctionCodomainSort()
31 result = "(define-fun " + str(f) + " ("
32 for i in range(0, len(params)):
33 if i > 0:
34 result += " "
35 result += "(" + str(params[i]) + " " + str(params[i].getSort()) + ")"
36 result += ") " + str(sort) + " " + str(body) + ")"
37 return result
38
39
40 # Print solutions for synthesis conjecture to the standard output stream.
41 # @param terms the terms for which the synthesis solutions were retrieved
42 # @param sols the synthesis solutions of the given terms
43
44
45 def print_synth_solutions(terms, sols):
46 result = "(\n"
47 for i in range(0, len(terms)):
48 params = []
49 body = sols[i]
50 if sols[i].getKind() == Kind.LAMBDA:
51 params += sols[i][0]
52 body = sols[i][1]
53 result += " " + define_fun_to_string(terms[i], params, body) + "\n"
54 result += ")"
55 print(result)