| 1 |
<html> |
| 2 |
<head> |
| 3 |
<title>Z3Py Advanced</title> |
| 4 |
<link rel="StyleSheet" href="style.css" type="text/css"> |
| 5 |
</head> |
| 6 |
<body> |
| 7 |
|
| 8 |
<h1>Advanced Topics</h1> |
| 9 |
|
| 10 |
<p> |
| 11 |
Please send feedback, comments and/or corrections to <a href="mailto:[email protected]">[email protected]</a>. |
| 12 |
Your comments are very valuable. |
| 13 |
</p> |
| 14 |
|
| 15 |
<h2>Expressions, Sorts and Declarations</h2> |
| 16 |
|
| 17 |
<p>In Z3, expressions, sorts and declarations are called <i>ASTs</i>. |
| 18 |
ASTs are directed acyclic graphs. Every expression has a sort (aka type). |
| 19 |
The method <tt>sort()</tt> retrieves the sort of an expression. |
| 20 |
</p> |
| 21 |
|
| 22 |
<example pref="expr.1"><html><body> |
| 23 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 24 |
<span class="n">y</span> <span class="o">=</span> <span class="n">Real</span><span class="p">(</span><span class="s">'y'</span><span class="p">)</span> |
| 25 |
<span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span> |
| 26 |
<span class="k">print</span> <span class="p">(</span><span class="n">y</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span> |
| 27 |
<span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">>=</span> <span class="mi">2</span><span class="p">)</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span> |
| 28 |
</pre></div> |
| 29 |
</body></html></example> |
| 30 |
|
| 31 |
<p>The function <tt>eq(n1, n2)</tt> returns <tt>True</tt> if <tt>n1</tt> |
| 32 |
and <tt>n2</tt> are the same AST. This is a structural test. |
| 33 |
</p> |
| 34 |
|
| 35 |
<example pref="expr.2"><html><body> |
| 36 |
<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> |
| 37 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span> |
| 38 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">,</span> <span class="n">y</span> <span class="o">+</span> <span class="n">x</span><span class="p">)</span> |
| 39 |
<span class="n">n</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span> |
| 40 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span> |
| 41 |
<span class="c"># x2 is eq to x</span> |
| 42 |
<span class="n">x2</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 43 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x2</span><span class="p">)</span> |
| 44 |
<span class="c"># the integer variable x is not equal to </span> |
| 45 |
<span class="c"># the real variable x</span> |
| 46 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">),</span> <span class="n">Real</span><span class="p">(</span><span class="s">'x'</span><span class="p">))</span> |
| 47 |
</pre></div> |
| 48 |
</body></html></example> |
| 49 |
|
| 50 |
<p>The method <tt>hash()</tt> returns a hashcode for an AST node. |
| 51 |
If <tt>eq(n1, n2)</tt> returns <tt>True</tt>, then <tt>n1.hash()</tt> |
| 52 |
is equal to <tt>n2.hash()</tt>. |
| 53 |
</p> |
| 54 |
|
| 55 |
<example pref="expr.3"><html><body> |
| 56 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 57 |
<span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span> |
| 58 |
<span class="k">print</span> <span class="p">(</span><span class="mi">1</span> <span class="o">+</span> <span class="n">x</span><span class="p">)</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span> |
| 59 |
<span class="k">print</span> <span class="n">x</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span><span class="o">.</span><span class="n">hash</span><span class="p">()</span> |
| 60 |
</pre></div> |
| 61 |
</body></html></example> |
| 62 |
|
| 63 |
<p>Z3 expressions can be divided in three basic groups: <b>applications</b>, |
| 64 |
<b>quantifiers</b> and <b>bounded/free variables</b>. |
| 65 |
Applications are all you need if your problems do not contain |
| 66 |
universal/existential quantifiers. Although we say <tt>Int('x')</tt> is an |
| 67 |
integer "variable", it is technically an integer constant, and internally |
| 68 |
is represented as a function application with <tt>0</tt> arguments. |
| 69 |
Every application is associated with a <b>declaration</b> and contains |
| 70 |
<tt>0</tt> or more arguments. The method <tt>decl()</tt> returns |
| 71 |
the declaration associated with an application. The method <tt>num_args()</tt> |
| 72 |
returns the number of arguments of an application, and <tt>arg(i)</tt> one of the arguments. |
| 73 |
The function <tt>is_expr(n)</tt> returns <tt>True</tt> |
| 74 |
if <tt>n</tt> is an expression. Similarly <tt>is_app(n)</tt> (<tt>is_func_decl(n)</tt>) |
| 75 |
returns <tt>True</tt> if <tt>n</tt> is an application (declaration). |
| 76 |
</p> |
| 77 |
|
| 78 |
<example pref="expr.4"><html><body> |
| 79 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 80 |
<span class="k">print</span> <span class="s">"is expression: "</span><span class="p">,</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> |
| 81 |
<span class="n">n</span> <span class="o">=</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">1</span> |
| 82 |
<span class="k">print</span> <span class="s">"is application:"</span><span class="p">,</span> <span class="n">is_app</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> |
| 83 |
<span class="k">print</span> <span class="s">"decl: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span> |
| 84 |
<span class="k">print</span> <span class="s">"num args: "</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">num_args</span><span class="p">()</span> |
| 85 |
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="o">.</span><span class="n">num_args</span><span class="p">()):</span> |
| 86 |
<span class="k">print</span> <span class="s">"arg("</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="s">") ->"</span><span class="p">,</span> <span class="n">n</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> |
| 87 |
</pre></div> |
| 88 |
</body></html></example> |
| 89 |
|
| 90 |
<p>Declarations have names, they are retrieved using the method <tt>name()</tt>. |
| 91 |
A (function) declaration has an arity, a domain and range sorts. |
| 92 |
</p> |
| 93 |
|
| 94 |
<example pref="expr.5"><html><body> |
| 95 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 96 |
<span class="n">x_d</span> <span class="o">=</span> <span class="n">x</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span> |
| 97 |
<span class="k">print</span> <span class="s">"is_expr(x_d): "</span><span class="p">,</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">x_d</span><span class="p">)</span> |
| 98 |
<span class="k">print</span> <span class="s">"is_func_decl(x_d):"</span><span class="p">,</span> <span class="n">is_func_decl</span><span class="p">(</span><span class="n">x_d</span><span class="p">)</span> |
| 99 |
<span class="k">print</span> <span class="s">"x_d.name(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">name</span><span class="p">()</span> |
| 100 |
<span class="k">print</span> <span class="s">"x_d.range(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">range</span><span class="p">()</span> |
| 101 |
<span class="k">print</span> <span class="s">"x_d.arity(): "</span><span class="p">,</span> <span class="n">x_d</span><span class="o">.</span><span class="n">arity</span><span class="p">()</span> |
| 102 |
<span class="c"># x_d() creates an application with 0 arguments using x_d.</span> |
| 103 |
<span class="k">print</span> <span class="s">"eq(x_d(), x): "</span><span class="p">,</span> <span class="n">eq</span><span class="p">(</span><span class="n">x_d</span><span class="p">(),</span> <span class="n">x</span><span class="p">)</span> |
| 104 |
<span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span> |
| 105 |
<span class="c"># f is a function from (Int, Real) to Bool</span> |
| 106 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">RealSort</span><span class="p">(),</span> <span class="n">BoolSort</span><span class="p">())</span> |
| 107 |
<span class="k">print</span> <span class="s">"f.name(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">name</span><span class="p">()</span> |
| 108 |
<span class="k">print</span> <span class="s">"f.range(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">range</span><span class="p">()</span> |
| 109 |
<span class="k">print</span> <span class="s">"f.arity(): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">arity</span><span class="p">()</span> |
| 110 |
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">f</span><span class="o">.</span><span class="n">arity</span><span class="p">()):</span> |
| 111 |
<span class="k">print</span> <span class="s">"domain("</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="s">"): "</span><span class="p">,</span> <span class="n">f</span><span class="o">.</span><span class="n">domain</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> |
| 112 |
<span class="c"># f(x, x) creates an application with 2 arguments using f.</span> |
| 113 |
<span class="k">print</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> |
| 114 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">f</span><span class="p">)</span> |
| 115 |
</pre></div> |
| 116 |
</body></html></example> |
| 117 |
|
| 118 |
<p> |
| 119 |
The built-in declarations are identified using their <b>kind</b>. The kind |
| 120 |
is retrieved using the method <tt>kind()</tt>. The complete list of built-in declarations |
| 121 |
can be found in the file <tt>z3consts.py</tt> (<tt>z3_api.h</tt>) in the Z3 distribution. |
| 122 |
</p> |
| 123 |
|
| 124 |
<example pref="expr.6"><html><body> |
| 125 |
<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> |
| 126 |
<span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span><span class="o">.</span><span class="n">kind</span><span class="p">()</span> <span class="o">==</span> <span class="n">Z3_OP_ADD</span> |
| 127 |
<span class="k">print</span> <span class="p">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="p">)</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span><span class="o">.</span><span class="n">kind</span><span class="p">()</span> <span class="o">==</span> <span class="n">Z3_OP_SUB</span> |
| 128 |
</pre></div> |
| 129 |
</body></html></example> |
| 130 |
|
| 131 |
<p> |
| 132 |
The following example demonstrates how to substitute sub-expressions in Z3 expressions. |
| 133 |
</p> |
| 134 |
|
| 135 |
<example pref="expr.7"><html><body> |
| 136 |
<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> |
| 137 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 138 |
<span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 139 |
<span class="n">n</span> <span class="o">=</span> <span class="n">f</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))),</span> <span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">y</span><span class="p">)))</span> |
| 140 |
<span class="k">print</span> <span class="n">n</span> |
| 141 |
<span class="c"># substitute g(g(x)) with y and g(y) with x + 1</span> |
| 142 |
<span class="k">print</span> <span class="n">substitute</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">)),</span> <span class="n">y</span><span class="p">),</span> <span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">x</span> <span class="o">+</span> <span class="mi">1</span><span class="p">))</span> |
| 143 |
</pre></div> |
| 144 |
</body></html></example> |
| 145 |
|
| 146 |
<p> |
| 147 |
The function <tt>Const(name, sort)</tt> declares a constant (aka variable) of the given sort. |
| 148 |
For example, the functions <tt>Int(name)</tt> and <tt>Real(name)</tt> are shorthands for |
| 149 |
<tt>Const(name, IntSort())</tt> and <tt>Const(name, RealSort())</tt>. |
| 150 |
</p> |
| 151 |
|
| 152 |
<example pref="expr.8"><html><body> |
| 153 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">())</span> |
| 154 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">))</span> |
| 155 |
|
| 156 |
<span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a b'</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span> |
| 157 |
<span class="k">print</span> <span class="n">And</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span> |
| 158 |
</pre></div> |
| 159 |
</body></html></example> |
| 160 |
|
| 161 |
<h2>Arrays</h2> |
| 162 |
|
| 163 |
<p>As part of formulating a programme of a mathematical theory of computation |
| 164 |
McCarthy proposed a <i>basic</i> theory of arrays as characterized by |
| 165 |
the select-store axioms. The expression <tt>Select(a, i)</tt> returns |
| 166 |
the value stored at position <tt>i</tt> of the array <tt>a</tt>; |
| 167 |
and <tt>Store(a, i, v)</tt> returns a new array identical to <tt>a</tt>, |
| 168 |
but on position <tt>i</tt> it contains the value <tt>v</tt>. |
| 169 |
In Z3Py, we can also write <tt>Select(a, i)</tt> as <tt>a[i]</tt>. |
| 170 |
</p> |
| 171 |
|
| 172 |
<example pref="array.1"><html><body> |
| 173 |
<div class="highlight"><pre><span class="c"># Use I as an alias for IntSort()</span> |
| 174 |
<span class="n">I</span> <span class="o">=</span> <span class="n">IntSort</span><span class="p">()</span> |
| 175 |
<span class="c"># A is an array from integer to integer</span> |
| 176 |
<span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">I</span><span class="p">)</span> |
| 177 |
<span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 178 |
<span class="k">print</span> <span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> |
| 179 |
<span class="k">print</span> <span class="n">Select</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> |
| 180 |
<span class="k">print</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="mi">10</span><span class="p">)</span> |
| 181 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Select</span><span class="p">(</span><span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="n">x</span><span class="o">+</span><span class="mi">1</span><span class="p">),</span> <span class="mi">2</span><span class="p">))</span> |
| 182 |
</pre></div> |
| 183 |
</body></html></example> |
| 184 |
|
| 185 |
<p> |
| 186 |
By default, Z3 assumes that arrays are extensional over select. |
| 187 |
In other words, Z3 also enforces that if two arrays agree on all positions, |
| 188 |
then the arrays are equal. |
| 189 |
</p> |
| 190 |
|
| 191 |
<p> |
| 192 |
Z3 also contains various extensions |
| 193 |
for operations on arrays that remain decidable and amenable |
| 194 |
to efficient saturation procedures (here efficient means, |
| 195 |
with an NP-complete satisfiability complexity). |
| 196 |
We describe these extensions in the following using a collection of examples. |
| 197 |
Additional background on these extensions is available in the |
| 198 |
paper <a href="http://research.microsoft.com/en-us/um/people/leonardo/fmcad09.pdf" target="_blank">Generalized and Efficient Array Decision Procedures</a>. |
| 199 |
</p> |
| 200 |
|
| 201 |
<p> |
| 202 |
Arrays in Z3 are used to model unbounded or very large arrays. |
| 203 |
Arrays should not be used to model small finite collections of values. |
| 204 |
It is usually much more efficient to create different variables using list comprehensions. |
| 205 |
</p> |
| 206 |
|
| 207 |
<example pref="array.2"><html><body> |
| 208 |
<div class="highlight"><pre><span class="c"># We want an array with 3 elements.</span> |
| 209 |
<span class="c"># 1. Bad solution</span> |
| 210 |
<span class="n">X</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 211 |
<span class="c"># Example using the array</span> |
| 212 |
<span class="k">print</span> <span class="n">X</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">>=</span><span class="mi">0</span> |
| 213 |
|
| 214 |
<span class="c"># 2. More efficient solution</span> |
| 215 |
<span class="n">X</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span> |
| 216 |
<span class="k">print</span> <span class="n">X</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">X</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">>=</span> <span class="mi">0</span> |
| 217 |
<span class="k">print</span> <span class="n">Sum</span><span class="p">(</span><span class="n">X</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span> |
| 218 |
</pre></div> |
| 219 |
</body></html></example> |
| 220 |
|
| 221 |
<h3>Select and Store</h3> |
| 222 |
|
| 223 |
|
| 224 |
<p>Let us first check a basic property of arrays. |
| 225 |
Suppose <tt>A</tt> is an array of integers, then the constraints |
| 226 |
<tt>A[x] == x, Store(A, x, y) == A</tt> |
| 227 |
are satisfiable for an array that contains an index <tt>x</tt> that maps to <tt>x</tt>, |
| 228 |
and when <tt>x == y</tt>. |
| 229 |
We can solve these constraints. |
| 230 |
</p> |
| 231 |
|
| 232 |
<example pref="array.3"><html><body> |
| 233 |
<div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 234 |
<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> |
| 235 |
<span class="n">solve</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="n">A</span><span class="p">)</span> |
| 236 |
</pre></div> |
| 237 |
</body></html></example> |
| 238 |
|
| 239 |
<p>The interpretation/solution for array variables is very similar to the one used for functions.</p> |
| 240 |
|
| 241 |
<p>The problem becomes unsatisfiable/infeasible if we add the constraint <tt>x != y</tt>. |
| 242 |
|
| 243 |
</p> |
| 244 |
<example pref="array.4"><html><body> |
| 245 |
<div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">Array</span><span class="p">(</span><span class="s">'A'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 246 |
<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> |
| 247 |
<span class="n">solve</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">Store</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="n">A</span><span class="p">,</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">y</span><span class="p">)</span> |
| 248 |
</pre></div> |
| 249 |
</body></html></example> |
| 250 |
|
| 251 |
<h3>Constant arrays</h3> |
| 252 |
|
| 253 |
<p> |
| 254 |
The array that maps all indices to some fixed value can be specified in Z3Py using the |
| 255 |
<tt>K(s, v)</tt> construct where <tt>s</tt> is a sort/type and <tt>v</tt> is an expression. |
| 256 |
<tt>K(s, v)</tt> returns a array that maps any value of <tt>s</tt> into <tt>v</tt>. |
| 257 |
The following example defines a constant array containing only ones. |
| 258 |
</p> |
| 259 |
|
| 260 |
<example pref="array.5"><html><body> |
| 261 |
<div class="highlight"><pre><span class="n">AllOne</span> <span class="o">=</span> <span class="n">K</span><span class="p">(</span><span class="n">IntSort</span><span class="p">(),</span> <span class="mi">1</span><span class="p">)</span> |
| 262 |
<span class="n">a</span><span class="p">,</span> <span class="n">i</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a i'</span><span class="p">)</span> |
| 263 |
<span class="n">solve</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">AllOne</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> |
| 264 |
<span class="c"># The following constraints do not have a solution</span> |
| 265 |
<span class="n">solve</span><span class="p">(</span><span class="n">a</span> <span class="o">==</span> <span class="n">AllOne</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">)</span> |
| 266 |
</pre></div> |
| 267 |
</body></html></example> |
| 268 |
|
| 269 |
<h2>Datatypes</h2> |
| 270 |
|
| 271 |
<p>Algebraic datatypes, known from programming languages such as ML, |
| 272 |
offer a convenient way for specifying common data structures. Records |
| 273 |
and tuples are special cases of algebraic datatypes, and so are |
| 274 |
scalars (enumeration types). But algebraic datatypes are more |
| 275 |
general. They can be used to specify finite lists, trees and other |
| 276 |
recursive structures.</p> |
| 277 |
|
| 278 |
<p> |
| 279 |
The following example demonstrates how to declare a List in Z3Py. It is |
| 280 |
more verbose than using the SMT 2.0 front-end, but much simpler than using |
| 281 |
the Z3 C API. It consists of two phases. |
| 282 |
First, we have to declare the new datatype, its constructors and accessors. |
| 283 |
The function <tt>Datatype('List')</tt> declares a "placeholder" that will |
| 284 |
contain the constructors and accessors declarations. The method |
| 285 |
<tt>declare(cname, (aname, sort)+)</tt> declares a constructor named |
| 286 |
<tt>cname</tt> with the given accessors. Each accessor has an associated <tt>sort</tt> |
| 287 |
or a reference to the datatypes being declared. |
| 288 |
For example, <tt>declare('cons', ('car', IntSort()), ('cdr', List))</tt> |
| 289 |
declares the constructor named <tt>cons</tt> that builds a new <tt>List</tt> |
| 290 |
using an integer and a <tt>List</tt>. It also declares the accessors <tt>car</tt> and |
| 291 |
<tt>cdr</tt>. The accessor <tt>car</tt> extracts the integer of a <tt>cons</tt> |
| 292 |
cell, and <tt>cdr</tt> the list of a <tt>cons</tt> cell. |
| 293 |
After all constructors were declared, we use the method <tt>create()</tt> to |
| 294 |
create the actual datatype in Z3. Z3Py makes the new Z3 declarations and constants |
| 295 |
available as slots of the new object. |
| 296 |
</p> |
| 297 |
|
| 298 |
<example pref="datatype.1"><html><body> |
| 299 |
<div class="highlight"><pre><span class="c"># Declare a List of integers</span> |
| 300 |
<span class="n">List</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'List'</span><span class="p">)</span> |
| 301 |
<span class="c"># Constructor cons: (Int, List) -> List</span> |
| 302 |
<span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">List</span><span class="p">))</span> |
| 303 |
<span class="c"># Constructor nil: List</span> |
| 304 |
<span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span> |
| 305 |
<span class="c"># Create the datatype</span> |
| 306 |
<span class="n">List</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">create</span><span class="p">()</span> |
| 307 |
<span class="k">print</span> <span class="n">is_sort</span><span class="p">(</span><span class="n">List</span><span class="p">)</span> |
| 308 |
<span class="n">cons</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">cons</span> |
| 309 |
<span class="n">car</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">car</span> |
| 310 |
<span class="n">cdr</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">cdr</span> |
| 311 |
<span class="n">nil</span> <span class="o">=</span> <span class="n">List</span><span class="o">.</span><span class="n">nil</span> |
| 312 |
<span class="c"># cons, car and cdr are function declarations, and nil a constant</span> |
| 313 |
<span class="k">print</span> <span class="n">is_func_decl</span><span class="p">(</span><span class="n">cons</span><span class="p">)</span> |
| 314 |
<span class="k">print</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">nil</span><span class="p">)</span> |
| 315 |
|
| 316 |
<span class="n">l1</span> <span class="o">=</span> <span class="n">cons</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="n">cons</span><span class="p">(</span><span class="mi">20</span><span class="p">,</span> <span class="n">nil</span><span class="p">))</span> |
| 317 |
<span class="k">print</span> <span class="n">l1</span> |
| 318 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">cdr</span><span class="p">(</span><span class="n">l1</span><span class="p">))</span> |
| 319 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">car</span><span class="p">(</span><span class="n">l1</span><span class="p">))</span> |
| 320 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">l1</span> <span class="o">==</span> <span class="n">nil</span><span class="p">)</span> |
| 321 |
</pre></div> |
| 322 |
</body></html></example> |
| 323 |
|
| 324 |
<p> |
| 325 |
The following example demonstrates how to define a Python function that |
| 326 |
given a sort creates a list of the given sort. |
| 327 |
</p> |
| 328 |
|
| 329 |
<example pref="datatype.2"><html><body> |
| 330 |
<div class="highlight"><pre><span class="k">def</span> <span class="nf">DeclareList</span><span class="p">(</span><span class="n">sort</span><span class="p">):</span> |
| 331 |
<span class="n">List</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'List_of_</span><span class="si">%s</span><span class="s">'</span> <span class="o">%</span> <span class="n">sort</span><span class="o">.</span><span class="n">name</span><span class="p">())</span> |
| 332 |
<span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">sort</span><span class="p">),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">List</span><span class="p">))</span> |
| 333 |
<span class="n">List</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span> |
| 334 |
<span class="k">return</span> <span class="n">List</span><span class="o">.</span><span class="n">create</span><span class="p">()</span> |
| 335 |
|
| 336 |
<span class="n">IntList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">IntSort</span><span class="p">())</span> |
| 337 |
<span class="n">RealList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">RealSort</span><span class="p">())</span> |
| 338 |
<span class="n">IntListList</span> <span class="o">=</span> <span class="n">DeclareList</span><span class="p">(</span><span class="n">IntList</span><span class="p">)</span> |
| 339 |
|
| 340 |
<span class="n">l1</span> <span class="o">=</span> <span class="n">IntList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="mi">10</span><span class="p">,</span> <span class="n">IntList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span> |
| 341 |
<span class="k">print</span> <span class="n">l1</span> |
| 342 |
<span class="k">print</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">l1</span><span class="p">,</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">l1</span><span class="p">,</span> <span class="n">IntListList</span><span class="o">.</span><span class="n">nil</span><span class="p">))</span> |
| 343 |
<span class="k">print</span> <span class="n">RealList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="s">"1/3"</span><span class="p">,</span> <span class="n">RealList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span> |
| 344 |
|
| 345 |
<span class="k">print</span> <span class="n">l1</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span> |
| 346 |
</pre></div> |
| 347 |
</body></html></example> |
| 348 |
|
| 349 |
<p>The example above demonstrates that Z3 supports operator overloading. |
| 350 |
There are several functions named <tt>cons</tt>, but they are different since they receive and/or |
| 351 |
return values of different sorts. |
| 352 |
Note that it is not necessary to use a different sort name for each instance of the sort |
| 353 |
list. That is, the expression <tt>'List_of_%s' % sort.name()</tt> is not necessary, we |
| 354 |
use it just to provide more meaningful names. |
| 355 |
</p> |
| 356 |
|
| 357 |
<p> |
| 358 |
As described above enumeration types are a special case of algebraic datatypes. |
| 359 |
The following example declares an enumeration type consisting of three values: |
| 360 |
<tt>red</tt>, <tt>green</tt> and <tt>blue</tt>. |
| 361 |
</p> |
| 362 |
|
| 363 |
<example pref="datatype.3"><html><body> |
| 364 |
<div class="highlight"><pre><span class="n">Color</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'Color'</span><span class="p">)</span> |
| 365 |
<span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'red'</span><span class="p">)</span> |
| 366 |
<span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'green'</span><span class="p">)</span> |
| 367 |
<span class="n">Color</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'blue'</span><span class="p">)</span> |
| 368 |
<span class="n">Color</span> <span class="o">=</span> <span class="n">Color</span><span class="o">.</span><span class="n">create</span><span class="p">()</span> |
| 369 |
|
| 370 |
<span class="k">print</span> <span class="n">is_expr</span><span class="p">(</span><span class="n">Color</span><span class="o">.</span><span class="n">green</span><span class="p">)</span> |
| 371 |
<span class="k">print</span> <span class="n">Color</span><span class="o">.</span><span class="n">green</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span> |
| 372 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Color</span><span class="o">.</span><span class="n">green</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span><span class="p">)</span> |
| 373 |
|
| 374 |
<span class="c"># Let c be a constant of sort Color</span> |
| 375 |
<span class="n">c</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'c'</span><span class="p">,</span> <span class="n">Color</span><span class="p">)</span> |
| 376 |
<span class="c"># Then, c must be red, green or blue</span> |
| 377 |
<span class="n">prove</span><span class="p">(</span><span class="n">Or</span><span class="p">(</span><span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">green</span><span class="p">,</span> |
| 378 |
<span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">blue</span><span class="p">,</span> |
| 379 |
<span class="n">c</span> <span class="o">==</span> <span class="n">Color</span><span class="o">.</span><span class="n">red</span><span class="p">))</span> |
| 380 |
</pre></div> |
| 381 |
</body></html></example> |
| 382 |
|
| 383 |
<p> |
| 384 |
Z3Py also provides the following shorthand for declaring enumeration sorts. |
| 385 |
</p> |
| 386 |
|
| 387 |
<example pref="datatype.4"><html><body> |
| 388 |
<div class="highlight"><pre><span class="n">Color</span><span class="p">,</span> <span class="p">(</span><span class="n">red</span><span class="p">,</span> <span class="n">green</span><span class="p">,</span> <span class="n">blue</span><span class="p">)</span> <span class="o">=</span> <span class="n">EnumSort</span><span class="p">(</span><span class="s">'Color'</span><span class="p">,</span> <span class="p">(</span><span class="s">'red'</span><span class="p">,</span> <span class="s">'green'</span><span class="p">,</span> <span class="s">'blue'</span><span class="p">))</span> |
| 389 |
|
| 390 |
<span class="k">print</span> <span class="n">green</span> <span class="o">==</span> <span class="n">blue</span> |
| 391 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">green</span> <span class="o">==</span> <span class="n">blue</span><span class="p">)</span> |
| 392 |
|
| 393 |
<span class="n">c</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'c'</span><span class="p">,</span> <span class="n">Color</span><span class="p">)</span> |
| 394 |
<span class="n">solve</span><span class="p">(</span><span class="n">c</span> <span class="o">!=</span> <span class="n">green</span><span class="p">,</span> <span class="n">c</span> <span class="o">!=</span> <span class="n">blue</span><span class="p">)</span> |
| 395 |
</pre></div> |
| 396 |
</body></html></example> |
| 397 |
|
| 398 |
<p> |
| 399 |
Mutually recursive datatypes can also be declared. The only difference is that we use |
| 400 |
the function <tt>CreateDatatypes</tt> instead of the method <tt>create()</tt> to create |
| 401 |
the mutually recursive datatypes. |
| 402 |
</p> |
| 403 |
|
| 404 |
<example pref="datatype.5"><html><body> |
| 405 |
<div class="highlight"><pre><span class="n">TreeList</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'TreeList'</span><span class="p">)</span> |
| 406 |
<span class="n">Tree</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'Tree'</span><span class="p">)</span> |
| 407 |
<span class="n">Tree</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'leaf'</span><span class="p">,</span> <span class="p">(</span><span class="s">'val'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()))</span> |
| 408 |
<span class="n">Tree</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'node'</span><span class="p">,</span> <span class="p">(</span><span class="s">'left'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">),</span> <span class="p">(</span><span class="s">'right'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">))</span> |
| 409 |
<span class="n">TreeList</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'nil'</span><span class="p">)</span> |
| 410 |
<span class="n">TreeList</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'cons'</span><span class="p">,</span> <span class="p">(</span><span class="s">'car'</span><span class="p">,</span> <span class="n">Tree</span><span class="p">),</span> <span class="p">(</span><span class="s">'cdr'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">))</span> |
| 411 |
|
| 412 |
<span class="n">Tree</span><span class="p">,</span> <span class="n">TreeList</span> <span class="o">=</span> <span class="n">CreateDatatypes</span><span class="p">(</span><span class="n">Tree</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">)</span> |
| 413 |
|
| 414 |
<span class="n">t1</span> <span class="o">=</span> <span class="n">Tree</span><span class="o">.</span><span class="n">leaf</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span> |
| 415 |
<span class="n">tl1</span> <span class="o">=</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">cons</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span> |
| 416 |
<span class="n">t2</span> <span class="o">=</span> <span class="n">Tree</span><span class="o">.</span><span class="n">node</span><span class="p">(</span><span class="n">tl1</span><span class="p">,</span> <span class="n">TreeList</span><span class="o">.</span><span class="n">nil</span><span class="p">)</span> |
| 417 |
<span class="k">print</span> <span class="n">t2</span> |
| 418 |
<span class="k">print</span> <span class="n">simplify</span><span class="p">(</span><span class="n">Tree</span><span class="o">.</span><span class="n">val</span><span class="p">(</span><span class="n">t1</span><span class="p">))</span> |
| 419 |
|
| 420 |
<span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">,</span> <span class="n">t3</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'t1 t2 t3'</span><span class="p">,</span> <span class="n">TreeList</span><span class="p">)</span> |
| 421 |
|
| 422 |
<span class="n">solve</span><span class="p">(</span><span class="n">Distinct</span><span class="p">(</span><span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">,</span> <span class="n">t3</span><span class="p">))</span> |
| 423 |
</pre></div> |
| 424 |
</body></html></example> |
| 425 |
|
| 426 |
<h2>Uninterpreted Sorts</h2> |
| 427 |
|
| 428 |
<p> |
| 429 |
Function and constant symbols in pure first-order logic are uninterpreted or free, |
| 430 |
which means that no a priori interpretation is attached. |
| 431 |
This is in contrast to arithmetic operators such as <tt>+</tt> and <tt>-</tt> |
| 432 |
that have a fixed standard interpretation. |
| 433 |
Uninterpreted functions and constants are maximally flexible; |
| 434 |
they allow any interpretation that is consistent with the constraints over the function or constant. |
| 435 |
</p> |
| 436 |
|
| 437 |
<p> |
| 438 |
To illustrate uninterpreted functions and constants let us introduce an (uninterpreted) sort <tt>A</tt>, |
| 439 |
and the constants <tt>x</tt>, <tt>y</tt> ranging over <tt>A</tt>. |
| 440 |
Finally let <tt>f</tt> be an uninterpreted function that takes one |
| 441 |
argument of sort <tt>A</tt> and results in a value of sort <tt>A</tt>. |
| 442 |
The example illustrates how one can force an interpretation where <tt>f</tt> applied twice to <tt>x</tt> results in <tt>x</tt> again, |
| 443 |
but <tt>f</tt> applied once to <tt>x</tt> is different from <tt>x</tt>. |
| 444 |
</p> |
| 445 |
|
| 446 |
<example pref="uninterp.1"><html><body> |
| 447 |
<div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span> |
| 448 |
<span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 449 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 450 |
|
| 451 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 452 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="n">y</span><span class="p">,</span> <span class="n">x</span> <span class="o">!=</span> <span class="n">y</span><span class="p">)</span> |
| 453 |
|
| 454 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 455 |
<span class="n">m</span> <span class="o">=</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span> |
| 456 |
<span class="k">print</span> <span class="n">m</span> |
| 457 |
<span class="k">print</span> <span class="s">"interpretation assigned to A:"</span> |
| 458 |
<span class="k">print</span> <span class="n">m</span><span class="p">[</span><span class="n">A</span><span class="p">]</span> |
| 459 |
</pre></div> |
| 460 |
</body></html></example> |
| 461 |
|
| 462 |
<p> |
| 463 |
The resulting model introduces abstract values for the elements in <tt>A</tt>, |
| 464 |
because the sort <tt>A</tt> is uninterpreted. The interpretation for <tt>f</tt> in the |
| 465 |
model toggles between the two values for <tt>x</tt> and <tt>y</tt>, which are different. |
| 466 |
The expression <tt>m[A]</tt> returns the interpretation (universe) for the uninterpreted sort <tt>A</tt> |
| 467 |
in the model <tt>m</tt>. |
| 468 |
</p> |
| 469 |
|
| 470 |
<h2>Quantifiers</h2> |
| 471 |
|
| 472 |
<p> |
| 473 |
Z3 is can solve quantifier-free problems containing arithmetic, bit-vector, Booleans, |
| 474 |
arrays, functions and datatypes. Z3 also accepts and can work with formulas |
| 475 |
that use quantifiers. It is no longer a decision procedure for |
| 476 |
such formulas in general (and for good reasons, as there can be |
| 477 |
no decision procedure for first-order logic). |
| 478 |
</p> |
| 479 |
|
| 480 |
<example pref="quant.1"><html><body> |
| 481 |
<div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 482 |
<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> |
| 483 |
<span class="k">print</span> <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> |
| 484 |
<span class="k">print</span> <span class="n">Exists</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">)</span> |
| 485 |
|
| 486 |
<span class="n">a</span><span class="p">,</span> <span class="n">b</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b'</span><span class="p">)</span> |
| 487 |
<span class="n">solve</span><span class="p">(</span><span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">),</span> <span class="n">f</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> |
| 488 |
</pre></div> |
| 489 |
</body></html></example> |
| 490 |
|
| 491 |
<p> |
| 492 |
Nevertheless, Z3 is often able to handle formulas involving |
| 493 |
quantifiers. It uses several approaches to handle quantifiers. |
| 494 |
The most prolific approach is using <i>pattern-based</i> quantifier |
| 495 |
instantiation. This approach allows instantiating quantified formulas |
| 496 |
with ground terms that appear in the current search context based |
| 497 |
on <i>pattern annotations</i> on quantifiers. |
| 498 |
Z3 also contains a model-based quantifier instantiation |
| 499 |
component that uses a model construction to find good terms to instantiate |
| 500 |
quantifiers with; and Z3 also handles many decidable fragments. |
| 501 |
</p> |
| 502 |
|
| 503 |
<p>Note that in the previous example the constants <tt>x</tt> |
| 504 |
and <tt>y</tt> were used to create quantified formulas. |
| 505 |
This is a "trick" for simplifying the construction of quantified |
| 506 |
formulas in Z3Py. Internally, these constants are replaced by |
| 507 |
bounded variables. The next example demonstrates that. The method |
| 508 |
<tt>body()</tt> retrieves the quantified expression. |
| 509 |
In the resultant formula the bounded variables are free. |
| 510 |
The function <tt>Var(index, sort)</tt> creates a bounded/free variable |
| 511 |
with the given index and sort. |
| 512 |
</p> |
| 513 |
|
| 514 |
<example pref="quant.2"><html><body> |
| 515 |
<div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 516 |
<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> |
| 517 |
<span class="n">f</span> <span class="o">=</span> <span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> |
| 518 |
<span class="k">print</span> <span class="n">f</span><span class="o">.</span><span class="n">body</span><span class="p">()</span> |
| 519 |
<span class="n">v1</span> <span class="o">=</span> <span class="n">f</span><span class="o">.</span><span class="n">body</span><span class="p">()</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span><span class="o">.</span><span class="n">arg</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> |
| 520 |
<span class="k">print</span> <span class="n">v1</span> |
| 521 |
<span class="k">print</span> <span class="n">eq</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span> <span class="n">Var</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()))</span> |
| 522 |
</pre></div> |
| 523 |
</body></html></example> |
| 524 |
|
| 525 |
<h3>Modeling with Quantifiers</h3> |
| 526 |
|
| 527 |
<p> |
| 528 |
Suppose we want to model an object oriented type system with single inheritance. |
| 529 |
We would need a predicate for sub-typing. Sub-typing should be a partial order, |
| 530 |
and respect single inheritance. For some built-in type constructors, |
| 531 |
such as for <tt>array_of</tt>, sub-typing should be monotone. |
| 532 |
</p> |
| 533 |
|
| 534 |
<example pref="quant.3"><html><body> |
| 535 |
<div class="highlight"><pre><span class="n">Type</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'Type'</span><span class="p">)</span> |
| 536 |
<span class="n">subtype</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'subtype'</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span> |
| 537 |
<span class="n">array_of</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'array_of'</span><span class="p">,</span> <span class="n">Type</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span> |
| 538 |
<span class="n">root</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'root'</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span> |
| 539 |
|
| 540 |
<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">Consts</span><span class="p">(</span><span class="s">'x y z'</span><span class="p">,</span> <span class="n">Type</span><span class="p">)</span> |
| 541 |
|
| 542 |
<span class="n">axioms</span> <span class="o">=</span> <span class="p">[</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">x</span><span class="p">)),</span> |
| 543 |
<span class="n">ForAll</span><span class="p">([</span><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="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">)),</span> |
| 544 |
<span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">z</span><span class="p">))),</span> |
| 545 |
<span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">x</span><span class="p">)),</span> |
| 546 |
<span class="n">x</span> <span class="o">==</span> <span class="n">y</span><span class="p">)),</span> |
| 547 |
<span class="n">ForAll</span><span class="p">([</span><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="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">z</span><span class="p">)),</span> |
| 548 |
<span class="n">Or</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">),</span> <span class="n">subtype</span><span class="p">(</span><span class="n">z</span><span class="p">,</span> <span class="n">y</span><span class="p">)))),</span> |
| 549 |
<span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">subtype</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">),</span> |
| 550 |
<span class="n">subtype</span><span class="p">(</span><span class="n">array_of</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">array_of</span><span class="p">(</span><span class="n">y</span><span class="p">)))),</span> |
| 551 |
|
| 552 |
<span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">subtype</span><span class="p">(</span><span class="n">root</span><span class="p">,</span> <span class="n">x</span><span class="p">))</span> |
| 553 |
<span class="p">]</span> |
| 554 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 555 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">axioms</span><span class="p">)</span> |
| 556 |
<span class="k">print</span> <span class="n">s</span> |
| 557 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 558 |
<span class="k">print</span> <span class="s">"Interpretation for Type:"</span> |
| 559 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()[</span><span class="n">Type</span><span class="p">]</span> |
| 560 |
<span class="k">print</span> <span class="s">"Model:"</span> |
| 561 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span> |
| 562 |
</pre></div> |
| 563 |
</body></html></example> |
| 564 |
|
| 565 |
<h3>Patterns</h3> |
| 566 |
|
| 567 |
<p> |
| 568 |
The Stanford Pascal verifier and the subsequent Simplify theorem prover pioneered |
| 569 |
the use of pattern-based quantifier instantiation. |
| 570 |
The basic idea behind pattern-based quantifier instantiation is in a sense straight-forward: |
| 571 |
Annotate a quantified formula using a pattern that contains all the bound variables. |
| 572 |
So a pattern is an expression (that does not contain binding operations, such as quantifiers) |
| 573 |
that contains variables bound by a quantifier. Then instantiate the quantifier whenever a term |
| 574 |
that matches the pattern is created during search. This is a conceptually easy starting point, |
| 575 |
but there are several subtleties that are important. |
| 576 |
</p> |
| 577 |
|
| 578 |
<p> |
| 579 |
In the following example, the first two options make sure that Model-based quantifier instantiation engine is disabled. |
| 580 |
We also annotate the quantified formula with the pattern <tt>f(g(x))</tt>. |
| 581 |
Since there is no ground instance of this pattern, the quantifier is not instantiated, and |
| 582 |
Z3 fails to show that the formula is unsatisfiable. |
| 583 |
</p> |
| 584 |
|
| 585 |
<example pref="quant.4"><html><body> |
| 586 |
<div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 587 |
<span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 588 |
<span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span> |
| 589 |
<span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 590 |
|
| 591 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 592 |
<span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span> |
| 593 |
|
| 594 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))]),</span> |
| 595 |
<span class="n">g</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span> |
| 596 |
<span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span> |
| 597 |
<span class="n">a</span> <span class="o">!=</span> <span class="n">b</span> <span class="p">)</span> |
| 598 |
|
| 599 |
<span class="c"># Display solver state using internal format</span> |
| 600 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span> |
| 601 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 602 |
</pre></div> |
| 603 |
</body></html></example> |
| 604 |
|
| 605 |
<p>When the more permissive pattern <tt>g(x)</tt> is used. Z3 proves the formula |
| 606 |
to be unsatisfiable. More restrictive patterns minimize the number of |
| 607 |
instantiations (and potentially improve performance), but they may |
| 608 |
also make Z3 "less complete". |
| 609 |
</p> |
| 610 |
|
| 611 |
<example pref="quant.5"><html><body> |
| 612 |
<div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 613 |
<span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 614 |
<span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span> |
| 615 |
<span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 616 |
|
| 617 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 618 |
<span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span> |
| 619 |
|
| 620 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">)]),</span> |
| 621 |
<span class="n">g</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span> |
| 622 |
<span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span> |
| 623 |
<span class="n">a</span> <span class="o">!=</span> <span class="n">b</span> <span class="p">)</span> |
| 624 |
|
| 625 |
<span class="c"># Display solver state using internal format</span> |
| 626 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">sexpr</span><span class="p">()</span> |
| 627 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 628 |
</pre></div> |
| 629 |
</body></html></example> |
| 630 |
|
| 631 |
<p> |
| 632 |
Some patterns may also create long instantiation chains. Consider the following assertion. |
| 633 |
</p> |
| 634 |
|
| 635 |
<pre> |
| 636 |
ForAll([x, y], Implies(subtype(x, y), |
| 637 |
subtype(array_of(x), array_of(y))), |
| 638 |
patterns=[subtype(x, y)]) |
| 639 |
</pre> |
| 640 |
|
| 641 |
<p> |
| 642 |
The axiom gets instantiated whenever there is some ground term of the |
| 643 |
form <tt>subtype(s, t)</tt>. The instantiation causes a fresh ground term |
| 644 |
<tt>subtype(array_of(s), array_of(t))</tt>, which enables a new |
| 645 |
instantiation. This undesirable situation is called a matching |
| 646 |
loop. Z3 uses many heuristics to break matching loops. |
| 647 |
</p> |
| 648 |
|
| 649 |
<p> |
| 650 |
Before elaborating on the subtleties, we should address an important |
| 651 |
first question. What defines the terms that are created during search? |
| 652 |
In the context of most SMT solvers, and of the Simplify theorem |
| 653 |
prover, terms exist as part of the input formula, they are of course |
| 654 |
also created by instantiating quantifiers, but terms are also |
| 655 |
implicitly created when equalities are asserted. The last point means |
| 656 |
that terms are considered up to congruence and pattern matching takes |
| 657 |
place modulo ground equalities. We call the matching problem |
| 658 |
<b>E-matching</b>. For example, if we have the following equalities: |
| 659 |
</p> |
| 660 |
|
| 661 |
<example pref="quant.6"><html><body> |
| 662 |
<div class="highlight"><pre><span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 663 |
<span class="n">g</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'g'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">(),</span> <span class="n">IntSort</span><span class="p">())</span> |
| 664 |
<span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span> |
| 665 |
<span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 666 |
|
| 667 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 668 |
<span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">auto_config</span><span class="o">=</span><span class="bp">False</span><span class="p">,</span> <span class="n">mbqi</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span> |
| 669 |
|
| 670 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span> <span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">,</span> <span class="n">patterns</span> <span class="o">=</span> <span class="p">[</span><span class="n">f</span><span class="p">(</span><span class="n">g</span><span class="p">(</span><span class="n">x</span><span class="p">))]),</span> |
| 671 |
<span class="n">a</span> <span class="o">==</span> <span class="n">g</span><span class="p">(</span><span class="n">b</span><span class="p">),</span> |
| 672 |
<span class="n">b</span> <span class="o">==</span> <span class="n">c</span><span class="p">,</span> |
| 673 |
<span class="n">f</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">!=</span> <span class="n">c</span> <span class="p">)</span> |
| 674 |
|
| 675 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 676 |
</pre></div> |
| 677 |
</body></html></example> |
| 678 |
|
| 679 |
<p> |
| 680 |
The terms <tt>f(a)</tt> and <tt>f(g(b))</tt> are equal modulo the |
| 681 |
equalities. The pattern <tt>f(g(x))</tt> can be matched and <tt>x</tt> bound to <tt>b</tt> |
| 682 |
and the equality <tt>f(g(b)) == b</tt> is deduced. |
| 683 |
</p> |
| 684 |
|
| 685 |
<p> |
| 686 |
While E-matching is an NP-complete problem, the main sources of overhead in larger verification |
| 687 |
problems comes from matching thousands of patterns in the context of an evolving set of terms and |
| 688 |
equalities. Z3 integrates an efficient E-matching engine using term indexing techniques. |
| 689 |
</p> |
| 690 |
|
| 691 |
<h3>Multi-patterns</h3> |
| 692 |
|
| 693 |
<p> |
| 694 |
In some cases, there is no pattern that contains all bound variables |
| 695 |
and does not contain interpreted symbols. In these cases, we use |
| 696 |
multi-patterns. In the following example, the quantified formula |
| 697 |
states that <tt>f</tt> is injective. This quantified formula is annotated with |
| 698 |
the multi-pattern <tt>MultiPattern(f(x), f(y))</tt>. |
| 699 |
</p> |
| 700 |
|
| 701 |
<example pref="quant.7"><html><body> |
| 702 |
<div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span> |
| 703 |
<span class="n">B</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'B'</span><span class="p">)</span> |
| 704 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> |
| 705 |
<span class="n">a1</span><span class="p">,</span> <span class="n">a2</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a1 a2'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 706 |
<span class="n">b</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> |
| 707 |
<span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 708 |
|
| 709 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 710 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">a1</span> <span class="o">!=</span> <span class="n">a2</span><span class="p">,</span> |
| 711 |
<span class="n">f</span><span class="p">(</span><span class="n">a1</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span> |
| 712 |
<span class="n">f</span><span class="p">(</span><span class="n">a2</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span> |
| 713 |
<span class="n">ForAll</span><span class="p">([</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">],</span> <span class="n">Implies</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="n">f</span><span class="p">(</span><span class="n">y</span><span class="p">),</span> <span class="n">x</span> <span class="o">==</span> <span class="n">y</span><span class="p">),</span> |
| 714 |
<span class="n">patterns</span><span class="o">=</span><span class="p">[</span><span class="n">MultiPattern</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">),</span> <span class="n">f</span><span class="p">(</span><span class="n">y</span><span class="p">))])</span> |
| 715 |
<span class="p">)</span> |
| 716 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 717 |
</pre></div> |
| 718 |
</body></html></example> |
| 719 |
|
| 720 |
<p> |
| 721 |
The quantified formula is instantiated for every pair of occurrences |
| 722 |
of <tt>f</tt>. A simple trick allows formulating injectivity of <tt>f</tt> in such a way |
| 723 |
that only a linear number of instantiations is required. The trick is |
| 724 |
to realize that <tt>f</tt> is injective if and only if it has a partial |
| 725 |
inverse. |
| 726 |
</p> |
| 727 |
|
| 728 |
<example pref="quant.8"><html><body> |
| 729 |
<div class="highlight"><pre><span class="n">A</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'A'</span><span class="p">)</span> |
| 730 |
<span class="n">B</span> <span class="o">=</span> <span class="n">DeclareSort</span><span class="p">(</span><span class="s">'B'</span><span class="p">)</span> |
| 731 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'f'</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> |
| 732 |
<span class="n">finv</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'finv'</span><span class="p">,</span> <span class="n">B</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 733 |
<span class="n">a1</span><span class="p">,</span> <span class="n">a2</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'a1 a2'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 734 |
<span class="n">b</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'b'</span><span class="p">,</span> <span class="n">B</span><span class="p">)</span> |
| 735 |
<span class="n">x</span><span class="p">,</span> <span class="n">y</span> <span class="o">=</span> <span class="n">Consts</span><span class="p">(</span><span class="s">'x y'</span><span class="p">,</span> <span class="n">A</span><span class="p">)</span> |
| 736 |
|
| 737 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 738 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">a1</span> <span class="o">!=</span> <span class="n">a2</span><span class="p">,</span> |
| 739 |
<span class="n">f</span><span class="p">(</span><span class="n">a1</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span> |
| 740 |
<span class="n">f</span><span class="p">(</span><span class="n">a2</span><span class="p">)</span> <span class="o">==</span> <span class="n">b</span><span class="p">,</span> |
| 741 |
<span class="n">ForAll</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">finv</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">x</span><span class="p">))</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span> |
| 742 |
<span class="p">)</span> |
| 743 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">()</span> |
| 744 |
</pre></div> |
| 745 |
</body></html></example> |
| 746 |
|
| 747 |
<h3>Other attributes</h3> |
| 748 |
|
| 749 |
<p> |
| 750 |
In Z3Py, the following additional attributes are supported: <b>qid</b> (quantifier identifier |
| 751 |
for debugging), <b>weight</b> (hint to the quantifier instantiation module: "more weight equals less instances"), |
| 752 |
<b>no_patterns</b> (expressions that should not be used as patterns, <b>skid</b> (identifier |
| 753 |
prefix used to create skolem constants/functions. |
| 754 |
</p> |
| 755 |
|
| 756 |
<h2>Multiple Solvers</h2> |
| 757 |
|
| 758 |
<p>In Z3Py and Z3 4.0 multiple solvers can be simultaneously used. |
| 759 |
It is also very easy to copy assertions/formulas from one solver to another. |
| 760 |
</p> |
| 761 |
|
| 762 |
<example pref="msolver.1"><html><body> |
| 763 |
<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> |
| 764 |
<span class="n">s1</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 765 |
<span class="n">s1</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="mi">10</span><span class="p">)</span> |
| 766 |
<span class="n">s2</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 767 |
<span class="c"># solver s2 is empty</span> |
| 768 |
<span class="k">print</span> <span class="n">s2</span> |
| 769 |
<span class="c"># copy assertions from s1 to s2</span> |
| 770 |
<span class="n">s2</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">s1</span><span class="o">.</span><span class="n">assertions</span><span class="p">())</span> |
| 771 |
<span class="k">print</span> <span class="n">s2</span> |
| 772 |
</pre></div> |
| 773 |
</body></html></example> |
| 774 |
|
| 775 |
<h2>Unsat Cores and Soft Constraints</h2> |
| 776 |
|
| 777 |
<p>Z3Py also supports <i>unsat core extraction</i>. The basic idea is to use |
| 778 |
<i>assumptions</i>, that is, auxiliary propositional variables that we want to track. |
| 779 |
Assumptions are also available in the Z3 SMT 2.0 frontend, and in other Z3 front-ends. |
| 780 |
They are used to extract unsatisfiable cores. They may be also used to "retract" |
| 781 |
constraints. Note that, assumptions are not really <i>soft constraints</i>, but they can be used to implement them. |
| 782 |
</p> |
| 783 |
|
| 784 |
<example pref="unsatcore.1"><html><body> |
| 785 |
<div class="highlight"><pre><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">,</span> <span class="n">p3</span> <span class="o">=</span> <span class="n">Bools</span><span class="p">(</span><span class="s">'p1 p2 p3'</span><span class="p">)</span> |
| 786 |
<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> |
| 787 |
<span class="c"># We assert Implies(p, C) to track constraint C using p</span> |
| 788 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Solver</span><span class="p">()</span> |
| 789 |
<span class="n">s</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">Implies</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">x</span> <span class="o">></span> <span class="mi">10</span><span class="p">),</span> |
| 790 |
<span class="n">Implies</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">y</span> <span class="o">></span> <span class="n">x</span><span class="p">),</span> |
| 791 |
<span class="n">Implies</span><span class="p">(</span><span class="n">p2</span><span class="p">,</span> <span class="n">y</span> <span class="o"><</span> <span class="mi">5</span><span class="p">),</span> |
| 792 |
<span class="n">Implies</span><span class="p">(</span><span class="n">p3</span><span class="p">,</span> <span class="n">y</span> <span class="o">></span> <span class="mi">0</span><span class="p">))</span> |
| 793 |
<span class="k">print</span> <span class="n">s</span> |
| 794 |
<span class="c"># Check satisfiability assuming p1, p2, p3 are true</span> |
| 795 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p2</span><span class="p">,</span> <span class="n">p3</span><span class="p">)</span> |
| 796 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">unsat_core</span><span class="p">()</span> |
| 797 |
|
| 798 |
<span class="c"># Try again retracting p2</span> |
| 799 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">check</span><span class="p">(</span><span class="n">p1</span><span class="p">,</span> <span class="n">p3</span><span class="p">)</span> |
| 800 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">model</span><span class="p">()</span> |
| 801 |
</pre></div> |
| 802 |
</body></html></example> |
| 803 |
|
| 804 |
<p>The example above also shows that a Boolean variable (<tt>p1</tt>) can be used to track |
| 805 |
more than one constraint. Note that Z3 does not guarantee that the unsat cores are minimal. |
| 806 |
</p> |
| 807 |
|
| 808 |
<h2>Formatter</h2> |
| 809 |
|
| 810 |
<p> |
| 811 |
Z3Py uses a formatter (aka pretty printer) for displaying formulas, expressions, solvers, and other |
| 812 |
Z3 objects. The formatter supports many configuration options. |
| 813 |
The command <tt>set_option(html_mode=False)</tt> makes all formulas and expressions to be |
| 814 |
displayed in Z3Py notation. |
| 815 |
</p> |
| 816 |
|
| 817 |
<example pref="printer"><html><body> |
| 818 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'x'</span><span class="p">)</span> |
| 819 |
<span class="n">y</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'y'</span><span class="p">)</span> |
| 820 |
<span class="k">print</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">1</span> |
| 821 |
<span class="n">set_option</span><span class="p">(</span><span class="n">html_mode</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span> |
| 822 |
<span class="k">print</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">1</span> |
| 823 |
</pre></div> |
| 824 |
</body></html></example> |
| 825 |
|
| 826 |
<p>By default, Z3Py will truncate the output if the object being displayed is too big. |
| 827 |
Z3Py uses … to denote the output is truncated. |
| 828 |
The following configuration options can be set to control the behavior of Z3Py's formatter: |
| 829 |
</p> |
| 830 |
|
| 831 |
<ul> |
| 832 |
<li> <tt>max_depth</tt> Maximal expression depth. Deep expressions are replaced with …. </li> |
| 833 |
<li> <tt>max_args</tt> Maximal number of arguments to display per node. </li> |
| 834 |
<li> <tt>rational_to_decimal</tt> Display rationals as decimals if True. </li> |
| 835 |
<li> <tt>precision</tt> Maximal number of decimal places for numbers being displayed in decimal notation. </li> |
| 836 |
<li> <tt>max_lines</tt> Maximal number of lines to be displayed. </li> |
| 837 |
<li> <tt>max_width</tt> Maximal line width (this is a suggestion to Z3Py). </li> |
| 838 |
<li> <tt>max_indent</tt> Maximal indentation.</li> |
| 839 |
</ul> |
| 840 |
|
| 841 |
<example pref="format"><html><body> |
| 842 |
<div class="highlight"><pre><span class="n">x</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'x'</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> |
| 843 |
<span class="n">y</span> <span class="o">=</span> <span class="n">IntVector</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span> <span class="mi">20</span><span class="p">)</span> |
| 844 |
<span class="n">f</span> <span class="o">=</span> <span class="n">And</span><span class="p">(</span><span class="n">Sum</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">Sum</span><span class="p">(</span><span class="n">y</span><span class="p">)</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">)</span> |
| 845 |
|
| 846 |
<span class="n">set_option</span><span class="p">(</span><span class="n">max_args</span><span class="o">=</span><span class="mi">5</span><span class="p">)</span> |
| 847 |
<span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 1:"</span> |
| 848 |
<span class="k">print</span> <span class="n">f</span> |
| 849 |
|
| 850 |
<span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 2:"</span> |
| 851 |
<span class="n">set_option</span><span class="p">(</span><span class="n">max_args</span><span class="o">=</span><span class="mi">100</span><span class="p">,</span> <span class="n">max_lines</span><span class="o">=</span><span class="mi">10</span><span class="p">)</span> |
| 852 |
<span class="k">print</span> <span class="n">f</span> |
| 853 |
|
| 854 |
<span class="k">print</span> <span class="s">"</span><span class="se">\n</span><span class="s">test 3:"</span> |
| 855 |
<span class="n">set_option</span><span class="p">(</span><span class="n">max_width</span><span class="o">=</span><span class="mi">300</span><span class="p">)</span> |
| 856 |
<span class="k">print</span> <span class="n">f</span> |
| 857 |
</pre></div> |
| 858 |
</body></html></example> |
| 859 |
|
| 860 |
</body> |
| 861 |
</html> |