Debian Codegraph @

examples/python/tutorial/html/strategies-examples.htm

raw
1 <html>
2 <head>
3 <title>Z3Py Strategies</title>
4 <link rel="StyleSheet" href="style.css" type="text/css">
5 </head>
6 <body>
7
8 <h1>Strategies</h1>
9
10 <p>
11 High-performance solvers, such as Z3, contain many tightly integrated, handcrafted heuristic
12 combinations of algorithmic proof methods. While these heuristic
13 combinations tend to be highly tuned for known classes of problems,
14 they may easily perform very badly on new classes of problems.
15 This issue is becoming increasingly pressing
16 as solvers begin to gain the attention of practitioners in diverse areas of science and engineering.
17 In many cases, changes to the solver heuristics can make a
18 tremendous difference.
19 </p>
20
21 <p>
22 In this tutorial we show how to create custom strategies using the basic building blocks
23 available in Z3. Z3Py and Z3 4.0 implement the ideas proposed in this <a target="_blank" href="http://research.microsoft.com/en-us/um/people/leonardo/strategy.pdf">article</a>.
24 </p>
25
26 <p>
27 Please send feedback, comments and/or corrections to <a href="mailto:[email protected]">[email protected]</a>.
28 Your comments are very valuable.
29 </p>
30
31 <h2>Introduction</h2>
32
33 <p>
34 Z3 implements a methodology for orchestrating reasoning
35 engines where "big" symbolic reasoning steps are represented as
36 functions known as <b>tactics</b>, and tactics are composed using
37 combinators known as <b>tacticals</b>. Tactics process sets of
38 formulas called <b>Goals</b>.
39 </p>
40
41 <p>
42 When a tactic is applied to some goal <tt>G</tt>, four different outcomes
43 are possible. The tactic succeeds in showing <tt>G</tt> to be satisfiable (i.e., feasible);
44 succeeds in showing <tt>G</tt> to be unsatisfiable (i.e., infeasible); produces a sequence of subgoals; or fails.
45 When reducing a goal <tt>G</tt> to a sequence of subgoals <tt>G1</tt>, ...,
46 <tt>Gn</tt>, we face the problem of model conversion.
47 A <b>model converter</b> construct a model for <tt>G</tt>
48 using a model for some subgoal <tt>Gi</tt>.
49 </p>
50
51 <p>In the following example, we create a goal <tt>g</tt> consisting of three formulas, and a tactic <tt>t</tt>
52 composed of two built-in tactics: <tt>simplify</tt> and <tt>solve-eqs</tt>. The tactic <tt>simplify</tt>
53 apply transformations equivalent to the ones found in the command <tt>simplify</tt>. The tactic <tt>solver-eqs</tt>
54 eliminate variables using Gaussian elimination. Actually, <tt>solve-eqs</tt> is not restricted only to linear arithmetic.
55 It can also eliminate arbitrary variables. Then, combinator <tt>Then</tt> applies <tt>simplify</tt> to the input goal
56 and <tt>solve-eqs</tt> to each subgoal produced by <tt>simplify</tt>. In this example, only one subgoal is produced.
57 </p>
58
59 <example pref="tactic.1"><html><body>
60 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
61 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
62 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">==</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="p">)</span>
63 <span class="k">print</span> <span class="n">g</span>
64
65 <span class="n">t1</span> <span class="o">=</span> <span class="n">Tactic</span><span class="p">(</span><span class="s">'simplify'</span><span class="p">)</span>
66 <span class="n">t2</span> <span class="o">=</span> <span class="n">Tactic</span><span class="p">(</span><span class="s">'solve-eqs'</span><span class="p">)</span>
67 <span class="n">t</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">)</span>
68 <span class="k">print</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
69 </pre></div>
70 </body></html></example>
71
72 <p>In the example above, variable <tt>x</tt> is eliminated, and is not present the resultant goal.
73 </p>
74
75 <p>In Z3, we say a <b>clause</b> is any constraint of the form <tt>Or(f_1, ..., f_n)</tt>.
76 The tactic <tt>split-clause</tt> will select a clause <tt>Or(f_1, ..., f_n)</tt> in the input goal, and split it
77 <tt>n</tt> subgoals. One for each subformula <tt>f_i</tt>.
78 </p>
79
80 <example pref="tactic.2"><html><body>
81 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
82 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
83 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">),</span> <span class="n">x</span> <span class="o">==</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span>
84
85 <span class="n">t</span> <span class="o">=</span> <span class="n">Tactic</span><span class="p">(</span><span class="s">'split-clause'</span><span class="p">)</span>
86 <span class="n">r</span> <span class="o">=</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
87 <span class="k">for</span> <span class="n">g</span> <span class="ow">in</span> <span class="n">r</span><span class="p">:</span>
88 <span class="k">print</span> <span class="n">g</span>
89 </pre></div>
90 </body></html></example>
91
92 <h2>Tactics</h2>
93
94 <p>Z3 comes equipped with many built-in tactics.
95 The command <tt>describe_tactics()</tt> provides a short description of all built-in tactics.
96 </p>
97
98 <example pref="tactic.3"><html><body>
99 <div class="highlight"><pre><span class="n">describe_tactics</span><span class="p">()</span>
100 </pre></div>
101 </body></html></example>
102
103 <p>Z3Py comes equipped with the following tactic combinators (aka tacticals):
104 </p>
105
106 <ul>
107 <li> <tt>Then(t, s)</tt>
108 applies <tt>t</tt> to the input goal and <tt>s</tt>
109 to every subgoal produced by <tt>t</tt>.
110 </li>
111 <li> <tt>OrElse(t, s)</tt>
112 first applies <tt>t</tt> to the given goal,
113 if it fails then returns the result of <tt>s</tt> applied to the given goal.
114 </li>
115 <li> <tt>Repeat(t)</tt> Keep applying the given tactic until no subgoal is modified by it.
116 </li>
117 <li> <tt>Repeat(t, n)</tt> Keep applying the given tactic until no subgoal is modified by it, or
118 the number of iterations is greater than <tt>n</tt>.
119 </li>
120 <li> <tt>TryFor(t, ms)</tt> Apply tactic <tt>t</tt> to the input goal, if it does not return in
121 <tt>ms</tt> milliseconds, it fails.
122 </li>
123 <li> <tt>With(t, params)</tt> Apply the given tactic using the given parameters.
124 </li>
125 </ul>
126
127 <p>The following example demonstrate how to use these combinators.</p>
128
129 <example pref="tactic.4"><html><body>
130 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
131 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
132 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
133 <span class="n">Or</span><span class="p">(</span><span class="n">y</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
134 <span class="n">Or</span><span class="p">(</span><span class="n">z</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">z</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
135 <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">2</span><span class="p">)</span>
136
137 <span class="c"># Split all clauses"</span>
138 <span class="n">split_all</span> <span class="o">=</span> <span class="n">Repeat</span><span class="p">(</span><span class="n">OrElse</span><span class="p">(</span><span class="n">Tactic</span><span class="p">(</span><span class="s">'split-clause'</span><span class="p">),</span>
139 <span class="n">Tactic</span><span class="p">(</span><span class="s">'skip'</span><span class="p">)))</span>
140 <span class="k">print</span> <span class="n">split_all</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
141
142 <span class="n">split_at_most_2</span> <span class="o">=</span> <span class="n">Repeat</span><span class="p">(</span><span class="n">OrElse</span><span class="p">(</span><span class="n">Tactic</span><span class="p">(</span><span class="s">'split-clause'</span><span class="p">),</span>
143 <span class="n">Tactic</span><span class="p">(</span><span class="s">'skip'</span><span class="p">)),</span>
144 <span class="mi">1</span><span class="p">)</span>
145 <span class="k">print</span> <span class="n">split_at_most_2</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
146
147 <span class="c"># Split all clauses and solve equations</span>
148 <span class="n">split_solve</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="n">Repeat</span><span class="p">(</span><span class="n">OrElse</span><span class="p">(</span><span class="n">Tactic</span><span class="p">(</span><span class="s">'split-clause'</span><span class="p">),</span>
149 <span class="n">Tactic</span><span class="p">(</span><span class="s">'skip'</span><span class="p">))),</span>
150 <span class="n">Tactic</span><span class="p">(</span><span class="s">'solve-eqs'</span><span class="p">))</span>
151
152 <span class="k">print</span> <span class="n">split_solve</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
153 </pre></div>
154 </body></html></example>
155
156 <p>In the tactic <tt>split_solver</tt>, the tactic <tt>solve-eqs</tt> discharges all but one goal.
157 Note that, this tactic generates one goal: the empty goal which is trivially satisfiable (i.e., feasible) </p>
158
159 <p>The list of subgoals can be easily traversed using the Python <tt>for</tt> statement.</p>
160
161 <example pref="tactic.5"><html><body>
162 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
163 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
164 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
165 <span class="n">Or</span><span class="p">(</span><span class="n">y</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
166 <span class="n">Or</span><span class="p">(</span><span class="n">z</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">z</span> <span class="o">==</span> <span class="mi">1</span><span class="p">),</span>
167 <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">2</span><span class="p">)</span>
168
169 <span class="c"># Split all clauses"</span>
170 <span class="n">split_all</span> <span class="o">=</span> <span class="n">Repeat</span><span class="p">(</span><span class="n">OrElse</span><span class="p">(</span><span class="n">Tactic</span><span class="p">(</span><span class="s">'split-clause'</span><span class="p">),</span>
171 <span class="n">Tactic</span><span class="p">(</span><span class="s">'skip'</span><span class="p">)))</span>
172 <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="n">split_all</span><span class="p">(</span><span class="n">g</span><span class="p">):</span>
173 <span class="k">print</span> <span class="n">s</span>
174 </pre></div>
175 </body></html></example>
176
177 <p>A tactic can be converted into a solver object using the method <tt>solver()</tt>.
178 If the tactic produces the empty goal, then the associated solver returns <tt>sat</tt>.
179 If the tactic produces a single goal containing <tt>False</tt>, then the solver returns <tt>unsat</tt>.
180 Otherwise, it returns <tt>unknown</tt>.
181 </p>
182
183 <example pref="tactic.6"><html><body>
184 <div class="highlight"><pre><span class="n">bv_solver</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="s">'simplify'</span><span class="p">,</span>
185 <span class="s">'solve-eqs'</span><span class="p">,</span>
186 <span class="s">'bit-blast'</span><span class="p">,</span>
187 <span class="s">'sat'</span><span class="p">)</span><span class="o">.</span><span class="n">solver</span><span class="p">()</span>
188
189 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">BitVecs</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
190 <span class="n">solve_using</span><span class="p">(</span><span class="n">bv_solver</span><span class="p">,</span> <span class="n">x</span> <span class="o">|</span> <span class="n">y</span> <span class="o">==</span> <span class="mi">13</span><span class="p">,</span> <span class="n">x</span> <span class="o">&gt;</span> <span class="n">y</span><span class="p">)</span>
191 </pre></div>
192 </body></html></example>
193
194 <p>In the example above, the tactic <tt>bv_solver</tt> implements a basic bit-vector solver using equation solving,
195 bit-blasting, and a propositional SAT solver. Note that, the command <tt>Tactic</tt> is suppressed.
196 All Z3Py combinators automatically invoke <tt>Tactic</tt> command if the argument is a string.
197 Finally, the command <tt>solve_using</tt> is a variant of the <tt>solve</tt> command where the first
198 argument specifies the solver to be used.
199 </p>
200
201 <p>In the following example, we use the solver API directly instead of the command <tt>solve_using</tt>.
202 We use the combinator <tt>With</tt> to configure our little solver. We also include the tactic <tt>aig</tt>
203 which tries to compress Boolean formulas using And-Inverted Graphs.
204 </p>
205
206 <example pref="tactic.7"><html><body>
207 <div class="highlight"><pre><span class="n">bv_solver</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="n">With</span><span class="p">(</span><span class="s">'simplify'</span><span class="p">,</span> <span class="n">mul2concat</span><span class="o">=</span><span class="bp">True</span><span class="p">),</span>
208 <span class="s">'solve-eqs'</span><span class="p">,</span>
209 <span class="s">'bit-blast'</span><span class="p">,</span>
210 <span class="s">'aig'</span><span class="p">,</span>
211 <span class="s">'sat'</span><span class="p">)</span><span class="o">.</span><span class="n">solver</span><span class="p">()</span>
212 <span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">BitVecs</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="mi">16</span><span class="p">)</span>
213 <span class="n">bv_solver</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span><span class="o">*</span><span class="mi">32</span> <span class="o">+</span> <span class="n">y</span> <span class="o">==</span> <span class="mi">13</span><span class="p">,</span> <span class="n">x</span> <span class="o">&amp;</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">,</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="o">-</span><span class="mi">100</span><span class="p">)</span>
214 <span class="k">print</span> <span class="n">bv_solver</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
215 <span class="n">m</span> <span class="o">=</span> <span class="n">bv_solver</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
216 <span class="k">print</span> <span class="n">m</span>
217 <span class="k">print</span> <span class="n">x</span><span class="o">*</span><span class="mi">32</span> <span class="o">+</span> <span class="n">y</span><span class="p">,</span> <span class="s">"=="</span><span class="p">,</span> <span class="n">m</span><span class="o">.</span><span class="n">evaluate</span><span class="p">(</span><span class="n">x</span><span class="o">*</span><span class="mi">32</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span>
218 <span class="k">print</span> <span class="n">x</span> <span class="o">&amp;</span> <span class="n">y</span><span class="p">,</span> <span class="s">"=="</span><span class="p">,</span> <span class="n">m</span><span class="o">.</span><span class="n">evaluate</span><span class="p">(</span><span class="n">x</span> <span class="o">&amp;</span> <span class="n">y</span><span class="p">)</span>
219 </pre></div>
220 </body></html></example>
221
222 <p>The tactic <tt>smt</tt> wraps the main solver in Z3 as a tactic.</p>
223
224 <example pref="tactic.8"><html><body>
225 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y'</span><span class="p">)</span>
226 <span class="n">s</span> <span class="o">=</span> <span class="n">Tactic</span><span class="p">(</span><span class="s">'smt'</span><span class="p">)</span><span class="o">.</span><span class="n">solver</span><span class="p">()</span>
227 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">y</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
228 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
229 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
230 </pre></div>
231 </body></html></example>
232
233 <p>Now, we show how to implement a solver for integer arithmetic using SAT. The solver is complete
234 only for problems where every variable has a lower and upper bound.
235 </p>
236
237 <example pref="tactic.9"><html><body>
238 <div class="highlight"><pre><span class="n">s</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="n">With</span><span class="p">(</span><span class="s">'simplify'</span><span class="p">,</span> <span class="n">arith_lhs</span><span class="o">=</span><span class="bp">True</span><span class="p">,</span> <span class="n">som</span><span class="o">=</span><span class="bp">True</span><span class="p">),</span>
239 <span class="s">'normalize-bounds'</span><span class="p">,</span> <span class="s">'lia2pb'</span><span class="p">,</span> <span class="s">'pb2bv'</span><span class="p">,</span>
240 <span class="s">'bit-blast'</span><span class="p">,</span> <span class="s">'sat'</span><span class="p">)</span><span class="o">.</span><span class="n">solver</span><span class="p">()</span>
241 <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
242 <span class="n">solve_using</span><span class="p">(</span><span class="n">s</span><span class="p">,</span>
243 <span class="n">x</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">,</span>
244 <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">y</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">,</span>
245 <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">,</span> <span class="n">z</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">,</span>
246 <span class="mi">3</span><span class="o">*</span><span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span> <span class="o">==</span> <span class="n">z</span><span class="p">)</span>
247 <span class="c"># It fails on the next example (it is unbounded)</span>
248 <span class="n">s</span><span class="o">.</span><span class="n">reset</span><span class="p">()</span>
249 <span class="n">solve_using</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="mi">3</span><span class="o">*</span><span class="n">y</span> <span class="o">+</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span> <span class="o">==</span> <span class="n">z</span><span class="p">)</span>
250 </pre></div>
251 </body></html></example>
252
253 <p>
254 Tactics can be combined with solvers. For example, we can apply a tactic to a goal, produced a set of subgoals,
255 then select one of the subgoals and solve it using a solver. The next example demonstrates how to do that, and how to
256 use model converters to convert a model for a subgoal into a model for the original goal.
257 </p>
258
259 <example pref="tactic.10"><html><body>
260 <div class="highlight"><pre><span class="n">t</span> <span class="o">=</span> <span class="n">Then</span><span class="p">(</span><span class="s">'simplify'</span><span class="p">,</span>
261 <span class="s">'normalize-bounds'</span><span class="p">,</span>
262 <span class="s">'solve-eqs'</span><span class="p">)</span>
263
264 <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
265 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
266 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">10</span><span class="p">,</span> <span class="n">y</span> <span class="o">==</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">3</span><span class="p">,</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="n">y</span><span class="p">)</span>
267
268 <span class="n">r</span> <span class="o">=</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
269 <span class="c"># r contains only one subgoal</span>
270 <span class="k">print</span> <span class="n">r</span>
271
272 <span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span>
273 <span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">r</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
274 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span>
275 <span class="c"># Model for the subgoal</span>
276 <span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span>
277 <span class="c"># Model for the original goal</span>
278 <span class="k">print</span> <span class="n">r</span><span class="o">.</span><span class="n">convert_model</span><span class="p">(</span><span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">())</span>
279 </pre></div>
280 </body></html></example>
281
282 <h2>Probes</h2>
283
284 <p>
285 <b>Probes</b> (aka formula measures) are evaluated over goals.
286 Boolean expressions over them can be built using relational operators and Boolean connectives.
287 The tactic <tt>FailIf(cond)</tt> fails if the given goal does not satisfy the condition <tt>cond</tt>.
288 Many numeric and Boolean measures are available in Z3Py. The command <tt>describe_probes()</tt> provides the list of
289 all built-in probes.
290 </p>
291
292 <example pref="probe.1"><html><body>
293 <div class="highlight"><pre><span class="n">describe_probes</span><span class="p">()</span>
294 </pre></div>
295 </body></html></example>
296
297 <p>In the following example, we build a simple tactic using <tt>FailIf</tt>. It also shows that a probe can be applied directly
298 to a goal.</p>
299
300 <example pref="probe.2"><html><body>
301 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
302 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
303 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="n">z</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
304
305 <span class="n">p</span> <span class="o">=</span> <span class="n">Probe</span><span class="p">(</span><span class="s">'num-consts'</span><span class="p">)</span>
306 <span class="k">print</span> <span class="s">"num-consts:"</span><span class="p">,</span> <span class="n">p</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
307
308 <span class="n">t</span> <span class="o">=</span> <span class="n">FailIf</span><span class="p">(</span><span class="n">p</span> <span class="o">&gt;</span> <span class="mi">2</span><span class="p">)</span>
309 <span class="k">try</span><span class="p">:</span>
310 <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
311 <span class="k">except</span> <span class="n">Z3Exception</span><span class="p">:</span>
312 <span class="k">print</span> <span class="s">"tactic failed"</span>
313
314 <span class="k">print</span> <span class="s">"trying again..."</span>
315 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
316 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
317 <span class="k">print</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
318 </pre></div>
319 </body></html></example>
320
321 <p>Z3Py also provides the combinator (tactical) <tt>If(p, t1, t2)</tt> which is a shorthand for:</p>
322
323 <pre>OrElse(Then(FailIf(Not(p)), t1), t2)</pre>
324
325 <p>The combinator <tt>When(p, t)</tt> is a shorthand for:</p>
326
327 <pre>If(p, t, 'skip')</pre>
328
329 <p>The tactic <tt>skip</tt> just returns the input goal.
330 The following example demonstrates how to use the <tt>If</tt> combinator.</p>
331
332 <example pref="probe.3"><html><body>
333 <div class="highlight"><pre><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">Reals</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">)</span>
334 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
335 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">-</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span>
336
337 <span class="n">p</span> <span class="o">=</span> <span class="n">Probe</span><span class="p">(</span><span class="s">'num-consts'</span><span class="p">)</span>
338 <span class="n">t</span> <span class="o">=</span> <span class="n">If</span><span class="p">(</span><span class="n">p</span> <span class="o">&gt;</span> <span class="mi">2</span><span class="p">,</span> <span class="s">'simplify'</span><span class="p">,</span> <span class="s">'factor'</span><span class="p">)</span>
339
340 <span class="k">print</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
341
342 <span class="n">g</span> <span class="o">=</span> <span class="n">Goal</span><span class="p">()</span>
343 <span class="n">g</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> <span class="o">+</span> <span class="n">z</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">-</span> <span class="n">y</span><span class="o">**</span><span class="mi">2</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span>
344
345 <span class="k">print</span> <span class="n">t</span><span class="p">(</span><span class="n">g</span><span class="p">)</span>
346 </pre></div>
347 </body></html></example>
348
349 </body>
350 </html>