| 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">></span> <span class="mi">0</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">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"><</span> <span class="mi">0</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="n">y</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">y</span> <span class="o"><</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">></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">></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">></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">&</span> <span class="n">y</span> <span class="o"><</span> <span class="mi">10</span><span class="p">,</span> <span class="n">y</span> <span class="o">></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">&</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="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">></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">></span> <span class="mi">0</span><span class="p">,</span> <span class="n">x</span> <span class="o"><</span> <span class="mi">10</span><span class="p">,</span> |
| 244 |
<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">10</span><span class="p">,</span> |
| 245 |
<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">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">></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">></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">></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">></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">></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">>=</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">></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">>=</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">>=</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> |