| 1 |
<html> |
| 2 |
<head> |
| 3 |
<title>Z3Py Fixedpoints</title> |
| 4 |
<link rel="StyleSheet" href="style.css" type="text/css"> |
| 5 |
</head> |
| 6 |
<body> |
| 7 |
|
| 8 |
<h1>Fixedpoints</h1> |
| 9 |
|
| 10 |
<p> |
| 11 |
</p> |
| 12 |
|
| 13 |
<p> |
| 14 |
This tutorial illustrates uses of Z3's fixedpoint engine. |
| 15 |
The following papers |
| 16 |
<a href="http://research.microsoft.com/en-us/people/nbjorner/z3fix.pdf"> |
| 17 |
μZ - An Efficient Engine for Fixed-Points with Constraints.</a> |
| 18 |
(CAV 2011) and |
| 19 |
<a href="http://research.microsoft.com/en-us/people/nbjorner/z3pdr.pdf"> |
| 20 |
Generalized Property Directed Reachability</a> (SAT 2012) |
| 21 |
describe some of the main features of the engine. |
| 22 |
</p> |
| 23 |
|
| 24 |
<p> |
| 25 |
Please send feedback, comments and/or corrections to |
| 26 |
<a href="mailto:[email protected]">[email protected]</a>. |
| 27 |
</p> |
| 28 |
|
| 29 |
<h2>Introduction</h2> |
| 30 |
|
| 31 |
|
| 32 |
<p> |
| 33 |
This tutorial covers some of the fixedpoint utilities available with Z3. |
| 34 |
The main features are a basic Datalog engine, an engine with relational |
| 35 |
algebra and an engine based on a generalization of the Property |
| 36 |
Directed Reachability algorithm. |
| 37 |
</p> |
| 38 |
|
| 39 |
|
| 40 |
<h2>Basic Datalog </h2> |
| 41 |
|
| 42 |
<p>The default fixed-point engine is a bottom-up Datalog engine. |
| 43 |
It works with finite relations and uses finite table representations |
| 44 |
as hash tables as the default way to represent finite relations. |
| 45 |
</p> |
| 46 |
|
| 47 |
<h3>Relations, rules and queries</h3> |
| 48 |
|
| 49 |
The first example illustrates how to declare relations, rules and |
| 50 |
how to pose queries. |
| 51 |
|
| 52 |
<example pref="fixedpoint.1"><html><body> |
| 53 |
<div class="highlight"><pre><span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 54 |
|
| 55 |
<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">Bools</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span> |
| 56 |
|
| 57 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">a</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">b</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">c</span><span class="o">.</span><span class="n">decl</span><span class="p">())</span> |
| 58 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">)</span> |
| 59 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">c</span><span class="p">)</span> |
| 60 |
<span class="n">fp</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">engine</span><span class="o">=</span><span class="s">'datalog'</span><span class="p">)</span> |
| 61 |
|
| 62 |
<span class="k">print</span> <span class="s">"current set of rules</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">fp</span> |
| 63 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> |
| 64 |
|
| 65 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> |
| 66 |
<span class="k">print</span> <span class="s">"updated set of rules</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">fp</span> |
| 67 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> |
| 68 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 69 |
</pre></div> |
| 70 |
</body></html></example> |
| 71 |
|
| 72 |
The example illustrates some of the basic constructs. |
| 73 |
<pre> |
| 74 |
fp = Fixedpoint() |
| 75 |
</pre> |
| 76 |
creates a context for fixed-point computation. |
| 77 |
<pre> |
| 78 |
fp.register_relation(a.decl(), b.decl(), c.decl()) |
| 79 |
</pre> |
| 80 |
Register the relations <tt>a, b, c</tt> as recursively defined. |
| 81 |
<pre> |
| 82 |
fp.rule(a,b) |
| 83 |
</pre> |
| 84 |
Create the rule that <tt>a</tt> follows from <tt>b</tt>. |
| 85 |
In general you can create a rule with multiple premises and a name using |
| 86 |
the format |
| 87 |
<pre> |
| 88 |
fp.rule(<em>head</em>,[<em>body1,...,bodyN</em>],<em>name</em>) |
| 89 |
</pre> |
| 90 |
The <em>name</em> is optional. It is used for tracking the rule in derivation proofs. |
| 91 |
|
| 92 |
Continuing with the example, <tt>a</tt> is false unless <tt>b</tt> is established. |
| 93 |
<pre> |
| 94 |
fp.query(a) |
| 95 |
</pre> |
| 96 |
Asks if <tt>a</tt> can be derived. The rules so far say that <tt>a</tt> |
| 97 |
follows if <tt>b</tt> is established and that <tt>b</tt> follows if <tt>c</tt> |
| 98 |
is established. But nothing establishes <tt>c</tt> and <tt>b</tt> is also not |
| 99 |
established, so <tt>a</tt> cannot be derived. |
| 100 |
<pre> |
| 101 |
fp.fact(c) |
| 102 |
</pre> |
| 103 |
Add a fact (shorthand for <tt>fp.rule(c,True)</tt>). |
| 104 |
Now it is the case that <tt>a</tt> can be derived. |
| 105 |
|
| 106 |
<h3>Explanations</h3> |
| 107 |
<p> |
| 108 |
It is also possible to get an explanation for a derived query. |
| 109 |
For the finite Datalog engine, an explanation is a trace that |
| 110 |
provides information of how a fact was derived. The explanation |
| 111 |
is an expression whose function symbols are Horn rules and facts used |
| 112 |
in the derivation. |
| 113 |
</p> |
| 114 |
<example pref="fixedpoint.2"><html><body> |
| 115 |
<div class="highlight"><pre><span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 116 |
|
| 117 |
<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">Bools</span><span class="p">(</span><span class="s">'a b c'</span><span class="p">)</span> |
| 118 |
|
| 119 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">a</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">b</span><span class="o">.</span><span class="n">decl</span><span class="p">(),</span> <span class="n">c</span><span class="o">.</span><span class="n">decl</span><span class="p">())</span> |
| 120 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">)</span> |
| 121 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">c</span><span class="p">)</span> |
| 122 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> |
| 123 |
<span class="n">fp</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">generate_explanations</span><span class="o">=</span><span class="bp">True</span><span class="p">,</span> <span class="n">engine</span><span class="o">=</span><span class="s">'datalog'</span><span class="p">)</span> |
| 124 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> |
| 125 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 126 |
</pre></div> |
| 127 |
</body></html></example> |
| 128 |
|
| 129 |
<h3>Relations with arguments</h3> |
| 130 |
<p> |
| 131 |
Relations can take arguments. We illustrate relations with arguments |
| 132 |
using edges and paths in a graph. |
| 133 |
</p> |
| 134 |
<example pref="fixedpoint.3"><html><body> |
| 135 |
<div class="highlight"><pre><span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 136 |
<span class="n">fp</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">engine</span><span class="o">=</span><span class="s">'datalog'</span><span class="p">)</span> |
| 137 |
|
| 138 |
<span class="n">s</span> <span class="o">=</span> <span class="n">BitVecSort</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> |
| 139 |
<span class="n">edge</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'edge'</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span> |
| 140 |
<span class="n">path</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'path'</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">BoolSort</span><span class="p">())</span> |
| 141 |
<span class="n">a</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'a'</span><span class="p">,</span><span class="n">s</span><span class="p">)</span> |
| 142 |
<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">s</span><span class="p">)</span> |
| 143 |
<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">s</span><span class="p">)</span> |
| 144 |
|
| 145 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">path</span><span class="p">,</span><span class="n">edge</span><span class="p">)</span> |
| 146 |
<span class="n">fp</span><span class="o">.</span><span class="n">declare_var</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="n">c</span><span class="p">)</span> |
| 147 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">path</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="n">edge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">))</span> |
| 148 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">path</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="n">c</span><span class="p">),</span> <span class="p">[</span><span class="n">edge</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="n">path</span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="n">c</span><span class="p">)])</span> |
| 149 |
|
| 150 |
<span class="n">v1</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">s</span><span class="p">)</span> |
| 151 |
<span class="n">v2</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="n">s</span><span class="p">)</span> |
| 152 |
<span class="n">v3</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="n">s</span><span class="p">)</span> |
| 153 |
<span class="n">v4</span> <span class="o">=</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="n">s</span><span class="p">)</span> |
| 154 |
|
| 155 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">edge</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span><span class="n">v2</span><span class="p">))</span> |
| 156 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">edge</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span><span class="n">v3</span><span class="p">))</span> |
| 157 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">edge</span><span class="p">(</span><span class="n">v2</span><span class="p">,</span><span class="n">v4</span><span class="p">))</span> |
| 158 |
|
| 159 |
<span class="k">print</span> <span class="s">"current set of rules"</span><span class="p">,</span> <span class="n">fp</span> |
| 160 |
|
| 161 |
|
| 162 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">path</span><span class="p">(</span><span class="n">v1</span><span class="p">,</span><span class="n">v4</span><span class="p">)),</span> <span class="s">"yes we can reach v4 from v1"</span> |
| 163 |
|
| 164 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">path</span><span class="p">(</span><span class="n">v3</span><span class="p">,</span><span class="n">v4</span><span class="p">)),</span> <span class="s">"no we cannot reach v4 from v3"</span> |
| 165 |
</pre></div> |
| 166 |
</body></html></example> |
| 167 |
|
| 168 |
The example uses the declaration |
| 169 |
<pre> |
| 170 |
fp.declare_var(a,b,c) |
| 171 |
</pre> |
| 172 |
to instrument the fixed-point engine that <tt>a, b, c</tt> |
| 173 |
should be treated as variables |
| 174 |
when they appear in rules. Think of the convention as they way bound variables are |
| 175 |
passed to quantifiers in Z3Py. |
| 176 |
|
| 177 |
<h3>Rush Hour</h3> |
| 178 |
<p> |
| 179 |
A more entertaining example of using the basic fixed point engine |
| 180 |
is to solve the Rush Hour puzzle. The puzzle is about moving |
| 181 |
a red car out of a gridlock. We have encoded a configuration |
| 182 |
and compiled a set of rules that encode the legal moves of the cars |
| 183 |
given the configuration. Other configurations can be tested by |
| 184 |
changing the parameters passed to the constructor for <t>Car</t>. |
| 185 |
We have encoded the configuration from |
| 186 |
<a href="http://www.puzzles.com/products/RushHour/RHfromMarkRiedel/Jam.html?40" target="_top"> |
| 187 |
an online puzzle you can solve manually, or cheat on by asking Z3</a>. |
| 188 |
</p> |
| 189 |
<example pref="fixedpoint.4"><html><body> |
| 190 |
<div class="highlight"><pre><span class="k">class</span> <span class="nc">Car</span><span class="p">():</span> |
| 191 |
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">is_vertical</span><span class="p">,</span> <span class="n">base_pos</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">color</span><span class="p">):</span> |
| 192 |
<span class="bp">self</span><span class="o">.</span><span class="n">is_vertical</span> <span class="o">=</span> <span class="n">is_vertical</span> |
| 193 |
<span class="bp">self</span><span class="o">.</span><span class="n">base</span> <span class="o">=</span> <span class="n">base_pos</span> |
| 194 |
<span class="bp">self</span><span class="o">.</span><span class="n">length</span> <span class="o">=</span> <span class="n">length</span> |
| 195 |
<span class="bp">self</span><span class="o">.</span><span class="n">start</span> <span class="o">=</span> <span class="n">start</span> |
| 196 |
<span class="bp">self</span><span class="o">.</span><span class="n">color</span> <span class="o">=</span> <span class="n">color</span> |
| 197 |
|
| 198 |
<span class="k">def</span> <span class="nf">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> |
| 199 |
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">color</span> <span class="o">==</span> <span class="n">other</span><span class="o">.</span><span class="n">color</span> |
| 200 |
|
| 201 |
<span class="k">def</span> <span class="nf">__ne__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span> |
| 202 |
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">color</span> <span class="o">!=</span> <span class="n">other</span><span class="o">.</span><span class="n">color</span> |
| 203 |
|
| 204 |
<span class="n">dimension</span> <span class="o">=</span> <span class="mi">6</span> |
| 205 |
|
| 206 |
<span class="n">red_car</span> <span class="o">=</span> <span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="s">"red"</span><span class="p">)</span> |
| 207 |
<span class="n">cars</span> <span class="o">=</span> <span class="p">[</span> |
| 208 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="s">'yellow'</span><span class="p">),</span> |
| 209 |
<span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="s">'blue'</span><span class="p">),</span> |
| 210 |
<span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="s">"brown"</span><span class="p">),</span> |
| 211 |
<span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="s">"lgreen"</span><span class="p">),</span> |
| 212 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="s">"light blue"</span><span class="p">),</span> |
| 213 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="s">"pink"</span><span class="p">),</span> |
| 214 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="s">"dark green"</span><span class="p">),</span> |
| 215 |
<span class="n">red_car</span><span class="p">,</span> |
| 216 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="s">"purple"</span><span class="p">),</span> |
| 217 |
<span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="s">"light yellow"</span><span class="p">),</span> |
| 218 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="s">"orange"</span><span class="p">),</span> |
| 219 |
<span class="n">Car</span><span class="p">(</span><span class="bp">False</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="s">"black"</span><span class="p">),</span> |
| 220 |
<span class="n">Car</span><span class="p">(</span><span class="bp">True</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="s">"light purple"</span><span class="p">)</span> |
| 221 |
<span class="p">]</span> |
| 222 |
|
| 223 |
<span class="n">num_cars</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">cars</span><span class="p">)</span> |
| 224 |
<span class="n">B</span> <span class="o">=</span> <span class="n">BoolSort</span><span class="p">()</span> |
| 225 |
<span class="n">bv3</span> <span class="o">=</span> <span class="n">BitVecSort</span><span class="p">(</span><span class="mi">3</span><span class="p">)</span> |
| 226 |
|
| 227 |
|
| 228 |
<span class="n">state</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'state'</span><span class="p">,</span> <span class="p">[</span> <span class="n">bv3</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">cars</span><span class="p">]</span> <span class="o">+</span> <span class="p">[</span><span class="n">B</span><span class="p">])</span> |
| 229 |
|
| 230 |
<span class="k">def</span> <span class="nf">num</span><span class="p">(</span><span class="n">i</span><span class="p">):</span> |
| 231 |
<span class="k">return</span> <span class="n">BitVecVal</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">bv3</span><span class="p">)</span> |
| 232 |
|
| 233 |
<span class="k">def</span> <span class="nf">bound</span><span class="p">(</span><span class="n">i</span><span class="p">):</span> |
| 234 |
<span class="k">return</span> <span class="n">Const</span><span class="p">(</span><span class="n">cars</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">.</span><span class="n">color</span><span class="p">,</span> <span class="n">bv3</span><span class="p">)</span> |
| 235 |
|
| 236 |
<span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 237 |
<span class="n">fp</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">generate_explanations</span><span class="o">=</span><span class="bp">True</span><span class="p">)</span> |
| 238 |
<span class="n">fp</span><span class="o">.</span><span class="n">declare_var</span><span class="p">([</span><span class="n">bound</span><span class="p">(</span><span class="n">i</span><span class="p">)</span> <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">num_cars</span><span class="p">)])</span> |
| 239 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">state</span><span class="p">)</span> |
| 240 |
|
| 241 |
<span class="k">def</span> <span class="nf">mk_state</span><span class="p">(</span><span class="n">car</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span> |
| 242 |
<span class="k">return</span> <span class="n">state</span><span class="p">([</span> <span class="p">(</span><span class="n">num</span><span class="p">(</span><span class="n">value</span><span class="p">)</span> <span class="k">if</span> <span class="p">(</span><span class="n">cars</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">car</span><span class="p">)</span> <span class="k">else</span> <span class="n">bound</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> |
| 243 |
<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">num_cars</span><span class="p">)])</span> |
| 244 |
|
| 245 |
<span class="k">def</span> <span class="nf">mk_transition</span><span class="p">(</span><span class="n">row</span><span class="p">,</span> <span class="n">col</span><span class="p">,</span> <span class="n">i0</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">car0</span><span class="p">):</span> |
| 246 |
<span class="n">body</span> <span class="o">=</span> <span class="p">[</span><span class="n">mk_state</span><span class="p">(</span><span class="n">car0</span><span class="p">,</span> <span class="n">i0</span><span class="p">)]</span> |
| 247 |
<span class="k">for</span> <span class="n">index</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">num_cars</span><span class="p">):</span> |
| 248 |
<span class="n">car</span> <span class="o">=</span> <span class="n">cars</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> |
| 249 |
<span class="k">if</span> <span class="n">car0</span> <span class="o">!=</span> <span class="n">car</span><span class="p">:</span> |
| 250 |
<span class="k">if</span> <span class="n">car</span><span class="o">.</span><span class="n">is_vertical</span> <span class="ow">and</span> <span class="n">car</span><span class="o">.</span><span class="n">base</span> <span class="o">==</span> <span class="n">col</span><span class="p">:</span> |
| 251 |
<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">dimension</span><span class="p">):</span> |
| 252 |
<span class="k">if</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">row</span> <span class="ow">and</span> <span class="n">row</span> <span class="o"><</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="ow">and</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="o"><=</span> <span class="n">dimension</span><span class="p">:</span> |
| 253 |
<span class="n">body</span> <span class="o">+=</span> <span class="p">[</span><span class="n">bound</span><span class="p">(</span><span class="n">index</span><span class="p">)</span> <span class="o">!=</span> <span class="n">num</span><span class="p">(</span><span class="n">i</span><span class="p">)]</span> |
| 254 |
<span class="k">if</span> <span class="n">car</span><span class="o">.</span><span class="n">base</span> <span class="o">==</span> <span class="n">row</span> <span class="ow">and</span> <span class="ow">not</span> <span class="n">car</span><span class="o">.</span><span class="n">is_vertical</span><span class="p">:</span> |
| 255 |
<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">dimension</span><span class="p">):</span> |
| 256 |
<span class="k">if</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">col</span> <span class="ow">and</span> <span class="n">col</span> <span class="o"><</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="ow">and</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="o"><=</span> <span class="n">dimension</span><span class="p">:</span> |
| 257 |
<span class="n">body</span> <span class="o">+=</span> <span class="p">[</span><span class="n">bound</span><span class="p">(</span><span class="n">index</span><span class="p">)</span> <span class="o">!=</span> <span class="n">num</span><span class="p">(</span><span class="n">i</span><span class="p">)]</span> |
| 258 |
|
| 259 |
<span class="n">s</span> <span class="o">=</span> <span class="s">"</span><span class="si">%s</span><span class="s"> </span><span class="si">%d</span><span class="s">-></span><span class="si">%d</span><span class="s">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">car0</span><span class="o">.</span><span class="n">color</span><span class="p">,</span> <span class="n">i0</span><span class="p">,</span> <span class="n">j</span><span class="p">)</span> |
| 260 |
|
| 261 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">mk_state</span><span class="p">(</span><span class="n">car0</span><span class="p">,</span> <span class="n">j</span><span class="p">),</span> <span class="n">body</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span> |
| 262 |
|
| 263 |
|
| 264 |
<span class="k">def</span> <span class="nf">move_down</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">):</span> |
| 265 |
<span class="n">free_row</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> |
| 266 |
<span class="k">if</span> <span class="n">free_row</span> <span class="o"><</span> <span class="n">dimension</span><span class="p">:</span> |
| 267 |
<span class="n">mk_transition</span><span class="p">(</span><span class="n">free_row</span><span class="p">,</span> <span class="n">car</span><span class="o">.</span><span class="n">base</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 268 |
|
| 269 |
|
| 270 |
<span class="k">def</span> <span class="nf">move_up</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">):</span> |
| 271 |
<span class="n">free_row</span> <span class="o">=</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span> |
| 272 |
<span class="k">if</span> <span class="mi">0</span> <span class="o"><=</span> <span class="n">free_row</span> <span class="ow">and</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="o"><=</span> <span class="n">dimension</span><span class="p">:</span> |
| 273 |
<span class="n">mk_transition</span><span class="p">(</span><span class="n">free_row</span><span class="p">,</span> <span class="n">car</span><span class="o">.</span><span class="n">base</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 274 |
|
| 275 |
<span class="k">def</span> <span class="nf">move_left</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">):</span> |
| 276 |
<span class="n">free_col</span> <span class="o">=</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> |
| 277 |
<span class="k">if</span> <span class="mi">0</span> <span class="o"><=</span> <span class="n">free_col</span> <span class="ow">and</span> <span class="n">i</span> <span class="o">+</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="o"><=</span> <span class="n">dimension</span><span class="p">:</span> |
| 278 |
<span class="n">mk_transition</span><span class="p">(</span><span class="n">car</span><span class="o">.</span><span class="n">base</span><span class="p">,</span> <span class="n">free_col</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 279 |
|
| 280 |
|
| 281 |
<span class="k">def</span> <span class="nf">move_right</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">):</span> |
| 282 |
<span class="n">free_col</span> <span class="o">=</span> <span class="n">car</span><span class="o">.</span><span class="n">length</span> <span class="o">+</span> <span class="n">i</span> |
| 283 |
<span class="k">if</span> <span class="n">free_col</span> <span class="o"><</span> <span class="n">dimension</span><span class="p">:</span> |
| 284 |
<span class="n">mk_transition</span><span class="p">(</span><span class="n">car</span><span class="o">.</span><span class="n">base</span><span class="p">,</span> <span class="n">free_col</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 285 |
|
| 286 |
|
| 287 |
<span class="c"># Initial state:</span> |
| 288 |
<span class="n">fp</span><span class="o">.</span><span class="n">fact</span><span class="p">(</span><span class="n">state</span><span class="p">([</span><span class="n">num</span><span class="p">(</span><span class="n">cars</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">.</span><span class="n">start</span><span class="p">)</span> <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">num_cars</span><span class="p">)]))</span> |
| 289 |
|
| 290 |
<span class="c"># Transitions:</span> |
| 291 |
<span class="k">for</span> <span class="n">car</span> <span class="ow">in</span> <span class="n">cars</span><span class="p">:</span> |
| 292 |
<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">dimension</span><span class="p">):</span> |
| 293 |
<span class="k">if</span> <span class="n">car</span><span class="o">.</span><span class="n">is_vertical</span><span class="p">:</span> |
| 294 |
<span class="n">move_down</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 295 |
<span class="n">move_up</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 296 |
<span class="k">else</span><span class="p">:</span> |
| 297 |
<span class="n">move_left</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 298 |
<span class="n">move_right</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">car</span><span class="p">)</span> |
| 299 |
|
| 300 |
|
| 301 |
<span class="k">def</span> <span class="nf">get_instructions</span><span class="p">(</span><span class="n">ans</span><span class="p">):</span> |
| 302 |
<span class="n">lastAnd</span> <span class="o">=</span> <span class="n">ans</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">children</span><span class="p">()[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> |
| 303 |
<span class="n">trace</span> <span class="o">=</span> <span class="n">lastAnd</span><span class="o">.</span><span class="n">children</span><span class="p">()[</span><span class="mi">1</span><span class="p">]</span> |
| 304 |
<span class="k">while</span> <span class="n">trace</span><span class="o">.</span><span class="n">num_args</span><span class="p">()</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span> |
| 305 |
<span class="k">print</span> <span class="n">trace</span><span class="o">.</span><span class="n">decl</span><span class="p">()</span> |
| 306 |
<span class="n">trace</span> <span class="o">=</span> <span class="n">trace</span><span class="o">.</span><span class="n">children</span><span class="p">()[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> |
| 307 |
|
| 308 |
<span class="k">print</span> <span class="n">fp</span> |
| 309 |
|
| 310 |
<span class="n">goal</span> <span class="o">=</span> <span class="n">state</span><span class="p">([</span> <span class="p">(</span><span class="n">num</span><span class="p">(</span><span class="mi">4</span><span class="p">)</span> <span class="k">if</span> <span class="n">cars</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">red_car</span> <span class="k">else</span> <span class="n">bound</span><span class="p">(</span><span class="n">i</span><span class="p">))</span> |
| 311 |
<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">num_cars</span><span class="p">)])</span> |
| 312 |
<span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">goal</span><span class="p">)</span> |
| 313 |
|
| 314 |
<span class="n">get_instructions</span><span class="p">(</span><span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">())</span> |
| 315 |
|
| 316 |
</pre></div> |
| 317 |
</body></html></example> |
| 318 |
|
| 319 |
|
| 320 |
<h2>Abstract Domains</h2> |
| 321 |
The underlying engine uses table operations |
| 322 |
that are based on relational algebra. Representations are |
| 323 |
opaque to the underlying engine. |
| 324 |
Relational algebra operations are well defined for arbitrary relations. |
| 325 |
They don't depend on whether the relations denote a finite or an |
| 326 |
infinite set of values. |
| 327 |
Z3 contains two built-in tables for infinite domains. |
| 328 |
The first is for intervals of integers and reals. |
| 329 |
The second is for bound constraints between two integers or reals. |
| 330 |
A bound constraint is of the form <tt>x or <tt> x . |
| 331 |
When used in conjunction, they form |
| 332 |
an abstract domain that is called the |
| 333 |
<a href="http://www.sciencedirect.com/science/article/pii/S0167642309000719"> |
| 334 |
<em>Pentagon</em></a> abstract |
| 335 |
domain. Z3 implements <em>reduced products</em> |
| 336 |
of abstract domains that enables sharing constraints between |
| 337 |
the interval and bounds domains. |
| 338 |
|
| 339 |
</tt></tt><p> |
| 340 |
Below we give a simple example that illustrates a loop at location <tt>l0</tt>. |
| 341 |
The loop is incremented as long as the loop counter does not exceed an upper |
| 342 |
bound. Using the combination of bound and interval domains |
| 343 |
we can collect derived invariants from the loop and we can also establish |
| 344 |
that the state after the loop does not exceed the bound. |
| 345 |
</p> |
| 346 |
|
| 347 |
|
| 348 |
<example pref="fixedpoint.5"><html><body> |
| 349 |
<div class="highlight"><pre><span class="n">I</span> <span class="o">=</span> <span class="n">IntSort</span><span class="p">()</span> |
| 350 |
<span class="n">B</span> <span class="o">=</span> <span class="n">BoolSort</span><span class="p">()</span> |
| 351 |
<span class="n">l0</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'l0'</span><span class="p">,</span><span class="n">I</span><span class="p">,</span><span class="n">I</span><span class="p">,</span><span class="n">B</span><span class="p">)</span> |
| 352 |
<span class="n">l1</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'l1'</span><span class="p">,</span><span class="n">I</span><span class="p">,</span><span class="n">I</span><span class="p">,</span><span class="n">B</span><span class="p">)</span> |
| 353 |
|
| 354 |
<span class="n">s</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 355 |
<span class="n">s</span><span class="o">.</span><span class="n">set</span><span class="p">(</span><span class="n">engine</span><span class="o">=</span><span class="s">'datalog'</span><span class="p">,</span><span class="n">compile_with_widening</span><span class="o">=</span><span class="bp">True</span><span class="p">,</span> |
| 356 |
<span class="n">unbound_compressor</span><span class="o">=</span><span class="bp">False</span><span class="p">)</span> |
| 357 |
|
| 358 |
<span class="n">s</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">l0</span><span class="p">,</span><span class="n">l1</span><span class="p">)</span> |
| 359 |
<span class="n">s</span><span class="o">.</span><span class="n">set_predicate_representation</span><span class="p">(</span><span class="n">l0</span><span class="p">,</span> <span class="s">'interval_relation'</span><span class="p">,</span> <span class="s">'bound_relation'</span><span class="p">)</span> |
| 360 |
<span class="n">s</span><span class="o">.</span><span class="n">set_predicate_representation</span><span class="p">(</span><span class="n">l1</span><span class="p">,</span> <span class="s">'interval_relation'</span><span class="p">,</span> <span class="s">'bound_relation'</span><span class="p">)</span> |
| 361 |
|
| 362 |
<span class="n">m</span><span class="p">,</span> <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">'m x y'</span><span class="p">)</span> |
| 363 |
|
| 364 |
<span class="n">s</span><span class="o">.</span><span class="n">declare_var</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)</span> |
| 365 |
<span class="n">s</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">l0</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">m</span><span class="p">),</span> <span class="mi">0</span> <span class="o"><</span> <span class="n">m</span><span class="p">)</span> |
| 366 |
<span class="n">s</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">l0</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="n">m</span><span class="p">),</span> <span class="p">[</span><span class="n">l0</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">m</span><span class="p">),</span> <span class="n">x</span> <span class="o"><</span> <span class="n">m</span><span class="p">])</span> |
| 367 |
<span class="n">s</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">l1</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">m</span><span class="p">),</span> <span class="p">[</span><span class="n">l0</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">m</span><span class="p">),</span> <span class="n">m</span> <span class="o"><=</span> <span class="n">x</span><span class="p">])</span> |
| 368 |
|
| 369 |
<span class="k">print</span> <span class="s">"At l0 we learn that x, y are non-negative:"</span> |
| 370 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">l0</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">))</span> |
| 371 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 372 |
|
| 373 |
<span class="k">print</span> <span class="s">"At l1 we learn that x <= y and both x and y are bigger than 0:"</span> |
| 374 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">l1</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">))</span> |
| 375 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 376 |
|
| 377 |
|
| 378 |
<span class="k">print</span> <span class="s">"The state where x < y is not reachable"</span> |
| 379 |
<span class="k">print</span> <span class="n">s</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">l1</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">x</span> <span class="o"><</span> <span class="n">y</span><span class="p">))</span> |
| 380 |
</pre></div> |
| 381 |
</body></html></example> |
| 382 |
|
| 383 |
The example uses the option |
| 384 |
<pre> |
| 385 |
set_option(dl_compile_with_widening=True) |
| 386 |
</pre> |
| 387 |
to instrument Z3 to apply abstract interpretation <em>widening</em> on loop boundaries. |
| 388 |
|
| 389 |
|
| 390 |
<h2>Engine for Property Directed Reachability</h2> |
| 391 |
|
| 392 |
A different underlying engine for fixed-points is based on |
| 393 |
an algorithm for <it>Property Directed Reachability (PDR)</it>. |
| 394 |
The PDR engine is enabled using the instruction |
| 395 |
<pre> |
| 396 |
set_option(dl_engine=1) |
| 397 |
</pre> |
| 398 |
The version in Z3 applies to Horn clauses with arithmetic and |
| 399 |
Boolean domains. When using arithmetic you should enable |
| 400 |
the main abstraction engine used in Z3 for arithmetic in PDR. |
| 401 |
<pre> |
| 402 |
set_option(dl_pdr_use_farkas=True) |
| 403 |
</pre> |
| 404 |
The engine also works with domains using algebraic |
| 405 |
data-types and bit-vectors, although it is currently not |
| 406 |
overly tuned for either. |
| 407 |
The PDR engine is targeted at applications from symbolic model |
| 408 |
checking of software. The systems may be infinite state. |
| 409 |
The following examples also serve a purpose of showing |
| 410 |
how software model checking problems (of safety properties) |
| 411 |
can be embedded into Horn clauses and solved using PDR. |
| 412 |
|
| 413 |
<h3>Procedure Calls</h3> |
| 414 |
<p> |
| 415 |
McCarthy's 91 function illustrates a procedure that calls itself recursively |
| 416 |
twice. The Horn clauses below encode the recursive function: |
| 417 |
|
| 418 |
</p> |
| 419 |
<pre> |
| 420 |
mc(x) = if x > 100 then x - 10 else mc(mc(x+11)) |
| 421 |
</pre> |
| 422 |
|
| 423 |
The general scheme for encoding recursive procedures is by creating a predicate |
| 424 |
for each procedure and adding an additional output variable to the predicate. |
| 425 |
Nested calls to procedures within a body can be encoded as a conjunction |
| 426 |
of relations. |
| 427 |
|
| 428 |
|
| 429 |
<example pref="fixedpoint.8"><html><body> |
| 430 |
<div class="highlight"><pre><span class="n">mc</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'mc'</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">BoolSort</span><span class="p">())</span> |
| 431 |
<span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">p</span> <span class="o">=</span> <span class="n">Ints</span><span class="p">(</span><span class="s">'n m p'</span><span class="p">)</span> |
| 432 |
|
| 433 |
<span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 434 |
|
| 435 |
<span class="n">fp</span><span class="o">.</span><span class="n">declare_var</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">)</span> |
| 436 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">mc</span><span class="p">)</span> |
| 437 |
|
| 438 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="n">m</span><span class="o">-</span><span class="mi">10</span><span class="p">),</span> <span class="n">m</span> <span class="o">></span> <span class="mi">100</span><span class="p">)</span> |
| 439 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="n">n</span><span class="p">),</span> <span class="p">[</span><span class="n">m</span> <span class="o"><=</span> <span class="mi">100</span><span class="p">,</span> <span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="o">+</span><span class="mi">11</span><span class="p">,</span><span class="n">p</span><span class="p">),</span><span class="n">mc</span><span class="p">(</span><span class="n">p</span><span class="p">,</span><span class="n">n</span><span class="p">)])</span> |
| 440 |
|
| 441 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">),</span><span class="n">n</span> <span class="o"><</span> <span class="mi">90</span><span class="p">))</span> |
| 442 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 443 |
|
| 444 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">),</span><span class="n">n</span> <span class="o"><</span> <span class="mi">91</span><span class="p">))</span> |
| 445 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 446 |
|
| 447 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">mc</span><span class="p">(</span><span class="n">m</span><span class="p">,</span><span class="n">n</span><span class="p">),</span><span class="n">n</span> <span class="o"><</span> <span class="mi">92</span><span class="p">))</span> |
| 448 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 449 |
</pre></div> |
| 450 |
</body></html></example> |
| 451 |
|
| 452 |
The first two queries are unsatisfiable. The PDR engine produces the same proof of unsatisfiability. |
| 453 |
The proof is an inductive invariant for each recursive predicate. The PDR engine introduces a |
| 454 |
special query predicate for the query. |
| 455 |
|
| 456 |
<h3>Bakery</h3> |
| 457 |
|
| 458 |
<p> |
| 459 |
We can also prove invariants of reactive systems. It is convenient to encode reactive systems |
| 460 |
as guarded transition systems. It is perhaps for some not as convenient to directly encode |
| 461 |
guarded transitions as recursive Horn clauses. But it is fairly easy to write a translator |
| 462 |
from guarded transition systems to recursive Horn clauses. We illustrate a translator |
| 463 |
and Lamport's two process Bakery algorithm in the next example. |
| 464 |
</p> |
| 465 |
|
| 466 |
<example pref="fixedpoint.9"><html><body> |
| 467 |
<div class="highlight"><pre><span class="n">set_option</span><span class="p">(</span><span class="n">relevancy</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">verbose</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span> |
| 468 |
|
| 469 |
<span class="k">def</span> <span class="nf">flatten</span><span class="p">(</span><span class="n">l</span><span class="p">):</span> |
| 470 |
<span class="k">return</span> <span class="p">[</span><span class="n">s</span> <span class="k">for</span> <span class="n">t</span> <span class="ow">in</span> <span class="n">l</span> <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="n">t</span><span class="p">]</span> |
| 471 |
|
| 472 |
|
| 473 |
<span class="k">class</span> <span class="nc">TransitionSystem</span><span class="p">():</span> |
| 474 |
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">initial</span><span class="p">,</span> <span class="n">transitions</span><span class="p">,</span> <span class="n">vars1</span><span class="p">):</span> |
| 475 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 476 |
<span class="bp">self</span><span class="o">.</span><span class="n">initial</span> <span class="o">=</span> <span class="n">initial</span> |
| 477 |
<span class="bp">self</span><span class="o">.</span><span class="n">transitions</span> <span class="o">=</span> <span class="n">transitions</span> |
| 478 |
<span class="bp">self</span><span class="o">.</span><span class="n">vars1</span> <span class="o">=</span> <span class="n">vars1</span> |
| 479 |
|
| 480 |
<span class="k">def</span> <span class="nf">declare_rels</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 481 |
<span class="n">B</span> <span class="o">=</span> <span class="n">BoolSort</span><span class="p">()</span> |
| 482 |
<span class="n">var_sorts</span> <span class="o">=</span> <span class="p">[</span> <span class="n">v</span><span class="o">.</span><span class="n">sort</span><span class="p">()</span> <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vars1</span> <span class="p">]</span> |
| 483 |
<span class="n">state_sorts</span> <span class="o">=</span> <span class="n">var_sorts</span> |
| 484 |
<span class="bp">self</span><span class="o">.</span><span class="n">state_vals</span> <span class="o">=</span> <span class="p">[</span> <span class="n">v</span> <span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">vars1</span> <span class="p">]</span> |
| 485 |
<span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span> <span class="o">=</span> <span class="n">state_sorts</span> |
| 486 |
<span class="bp">self</span><span class="o">.</span><span class="n">var_sorts</span> <span class="o">=</span> <span class="n">var_sorts</span> |
| 487 |
<span class="bp">self</span><span class="o">.</span><span class="n">state</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'state'</span><span class="p">,</span> <span class="n">state_sorts</span> <span class="o">+</span> <span class="p">[</span> <span class="n">B</span> <span class="p">])</span> |
| 488 |
<span class="bp">self</span><span class="o">.</span><span class="n">step</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'step'</span><span class="p">,</span> <span class="n">state_sorts</span> <span class="o">+</span> <span class="n">state_sorts</span> <span class="o">+</span> <span class="p">[</span> <span class="n">B</span> <span class="p">])</span> |
| 489 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state</span><span class="p">)</span> |
| 490 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">step</span><span class="p">)</span> |
| 491 |
|
| 492 |
<span class="c"># Set of reachable states are transitive closure of step.</span> |
| 493 |
|
| 494 |
<span class="k">def</span> <span class="nf">state0</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 495 |
<span class="n">idx</span> <span class="o">=</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">))</span> |
| 496 |
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">state</span><span class="p">([</span><span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="n">idx</span><span class="p">])</span> |
| 497 |
|
| 498 |
<span class="k">def</span> <span class="nf">state1</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 499 |
<span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">)</span> |
| 500 |
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">state</span><span class="p">([</span><span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <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="p">)])</span> |
| 501 |
|
| 502 |
<span class="k">def</span> <span class="nf">rho</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 503 |
<span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">)</span> |
| 504 |
<span class="n">args1</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <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="p">)</span> <span class="p">]</span> |
| 505 |
<span class="n">args2</span> <span class="o">=</span> <span class="p">[</span> <span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">,</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <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="p">)</span> <span class="p">]</span> |
| 506 |
<span class="n">args</span> <span class="o">=</span> <span class="n">args1</span> <span class="o">+</span> <span class="n">args2</span> |
| 507 |
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">step</span><span class="p">(</span><span class="n">args</span><span class="p">)</span> |
| 508 |
|
| 509 |
<span class="k">def</span> <span class="nf">declare_reachability</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 510 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state1</span><span class="p">(),</span> <span class="p">[</span><span class="bp">self</span><span class="o">.</span><span class="n">state0</span><span class="p">(),</span> <span class="bp">self</span><span class="o">.</span><span class="n">rho</span><span class="p">()])</span> |
| 511 |
|
| 512 |
|
| 513 |
<span class="c"># Define transition relation</span> |
| 514 |
|
| 515 |
<span class="k">def</span> <span class="nf">abstract</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">e</span><span class="p">):</span> |
| 516 |
<span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">)</span> |
| 517 |
<span class="n">sub</span> <span class="o">=</span> <span class="p">[(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_vals</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">]))</span> <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="p">)]</span> |
| 518 |
<span class="k">return</span> <span class="n">substitute</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="n">sub</span><span class="p">)</span> |
| 519 |
|
| 520 |
<span class="k">def</span> <span class="nf">declare_transition</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">tr</span><span class="p">):</span> |
| 521 |
<span class="n">len_s</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">)</span> |
| 522 |
<span class="n">effect</span> <span class="o">=</span> <span class="n">tr</span><span class="p">[</span><span class="s">"effect"</span><span class="p">]</span> |
| 523 |
<span class="n">vars1</span> <span class="o">=</span> <span class="p">[</span><span class="n">Var</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="bp">self</span><span class="o">.</span><span class="n">state_sorts</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <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">len_s</span><span class="p">)]</span> <span class="o">+</span> <span class="n">effect</span> |
| 524 |
<span class="n">rho1</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">abstract</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">step</span><span class="p">(</span><span class="n">vars1</span><span class="p">))</span> |
| 525 |
<span class="n">guard</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">abstract</span><span class="p">(</span><span class="n">tr</span><span class="p">[</span><span class="s">"guard"</span><span class="p">])</span> |
| 526 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">rho1</span><span class="p">,</span> <span class="n">guard</span><span class="p">)</span> |
| 527 |
|
| 528 |
<span class="k">def</span> <span class="nf">declare_transitions</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 529 |
<span class="k">for</span> <span class="n">t</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">transitions</span><span class="p">:</span> |
| 530 |
<span class="bp">self</span><span class="o">.</span><span class="n">declare_transition</span><span class="p">(</span><span class="n">t</span><span class="p">)</span> |
| 531 |
|
| 532 |
<span class="k">def</span> <span class="nf">declare_initial</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> |
| 533 |
<span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state0</span><span class="p">(),[</span><span class="bp">self</span><span class="o">.</span><span class="n">abstract</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">initial</span><span class="p">)])</span> |
| 534 |
|
| 535 |
<span class="k">def</span> <span class="nf">query</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">query</span><span class="p">):</span> |
| 536 |
<span class="bp">self</span><span class="o">.</span><span class="n">declare_rels</span><span class="p">()</span> |
| 537 |
<span class="bp">self</span><span class="o">.</span><span class="n">declare_initial</span><span class="p">()</span> |
| 538 |
<span class="bp">self</span><span class="o">.</span><span class="n">declare_reachability</span><span class="p">()</span> |
| 539 |
<span class="bp">self</span><span class="o">.</span><span class="n">declare_transitions</span><span class="p">()</span> |
| 540 |
<span class="n">query</span> <span class="o">=</span> <span class="n">And</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">state0</span><span class="p">(),</span> <span class="bp">self</span><span class="o">.</span><span class="n">abstract</span><span class="p">(</span><span class="n">query</span><span class="p">))</span> |
| 541 |
<span class="k">print</span> <span class="bp">self</span><span class="o">.</span><span class="n">fp</span> |
| 542 |
<span class="k">print</span> <span class="n">query</span> |
| 543 |
<span class="k">print</span> <span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">query</span><span class="p">)</span> |
| 544 |
<span class="k">print</span> <span class="bp">self</span><span class="o">.</span><span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 545 |
<span class="c"># print self.fp.statistics()</span> |
| 546 |
|
| 547 |
|
| 548 |
<span class="n">L</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'L'</span><span class="p">)</span> |
| 549 |
<span class="n">L</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'L0'</span><span class="p">)</span> |
| 550 |
<span class="n">L</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'L1'</span><span class="p">)</span> |
| 551 |
<span class="n">L</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'L2'</span><span class="p">)</span> |
| 552 |
<span class="n">L</span> <span class="o">=</span> <span class="n">L</span><span class="o">.</span><span class="n">create</span><span class="p">()</span> |
| 553 |
<span class="n">L0</span> <span class="o">=</span> <span class="n">L</span><span class="o">.</span><span class="n">L0</span> |
| 554 |
<span class="n">L1</span> <span class="o">=</span> <span class="n">L</span><span class="o">.</span><span class="n">L1</span> |
| 555 |
<span class="n">L2</span> <span class="o">=</span> <span class="n">L</span><span class="o">.</span><span class="n">L2</span> |
| 556 |
|
| 557 |
|
| 558 |
<span class="n">y0</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'y0'</span><span class="p">)</span> |
| 559 |
<span class="n">y1</span> <span class="o">=</span> <span class="n">Int</span><span class="p">(</span><span class="s">'y1'</span><span class="p">)</span> |
| 560 |
<span class="n">l</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'l'</span><span class="p">,</span> <span class="n">L</span><span class="p">)</span> |
| 561 |
<span class="n">m</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'m'</span><span class="p">,</span> <span class="n">L</span><span class="p">)</span> |
| 562 |
|
| 563 |
|
| 564 |
<span class="n">t1</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">l</span> <span class="o">==</span> <span class="n">L0</span><span class="p">,</span> |
| 565 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">L1</span><span class="p">,</span> <span class="n">y1</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">y1</span> <span class="p">]</span> <span class="p">}</span> |
| 566 |
<span class="n">t2</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">And</span><span class="p">(</span><span class="n">l</span> <span class="o">==</span> <span class="n">L1</span><span class="p">,</span> <span class="n">Or</span><span class="p">([</span><span class="n">y0</span> <span class="o"><=</span> <span class="n">y1</span><span class="p">,</span> <span class="n">y1</span> <span class="o">==</span> <span class="mi">0</span><span class="p">])),</span> |
| 567 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">L2</span><span class="p">,</span> <span class="n">y0</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">y1</span> <span class="p">]</span> <span class="p">}</span> |
| 568 |
<span class="n">t3</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">l</span> <span class="o">==</span> <span class="n">L2</span><span class="p">,</span> |
| 569 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">L0</span><span class="p">,</span> <span class="n">IntVal</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">m</span><span class="p">,</span> <span class="n">y1</span> <span class="p">]}</span> |
| 570 |
<span class="n">s1</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">m</span> <span class="o">==</span> <span class="n">L0</span><span class="p">,</span> |
| 571 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">l</span><span class="p">,</span> <span class="n">y0</span><span class="p">,</span> <span class="n">L1</span><span class="p">,</span> <span class="n">y0</span> <span class="o">+</span> <span class="mi">1</span> <span class="p">]</span> <span class="p">}</span> |
| 572 |
<span class="n">s2</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">And</span><span class="p">(</span><span class="n">m</span> <span class="o">==</span> <span class="n">L1</span><span class="p">,</span> <span class="n">Or</span><span class="p">([</span><span class="n">y1</span> <span class="o"><=</span> <span class="n">y0</span><span class="p">,</span> <span class="n">y0</span> <span class="o">==</span> <span class="mi">0</span><span class="p">])),</span> |
| 573 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">l</span><span class="p">,</span> <span class="n">y0</span><span class="p">,</span> <span class="n">L2</span><span class="p">,</span> <span class="n">y1</span> <span class="p">]</span> <span class="p">}</span> |
| 574 |
<span class="n">s3</span> <span class="o">=</span> <span class="p">{</span> <span class="s">"guard"</span> <span class="p">:</span> <span class="n">m</span> <span class="o">==</span> <span class="n">L2</span><span class="p">,</span> |
| 575 |
<span class="s">"effect"</span> <span class="p">:</span> <span class="p">[</span> <span class="n">l</span><span class="p">,</span> <span class="n">y0</span><span class="p">,</span> <span class="n">L0</span><span class="p">,</span> <span class="n">IntVal</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">]}</span> |
| 576 |
|
| 577 |
|
| 578 |
<span class="n">ptr</span> <span class="o">=</span> <span class="n">TransitionSystem</span><span class="p">(</span> <span class="n">And</span><span class="p">(</span><span class="n">l</span> <span class="o">==</span> <span class="n">L0</span><span class="p">,</span> <span class="n">y0</span> <span class="o">==</span> <span class="mi">0</span><span class="p">,</span> <span class="n">m</span> <span class="o">==</span> <span class="n">L0</span><span class="p">,</span> <span class="n">y1</span> <span class="o">==</span> <span class="mi">0</span><span class="p">),</span> |
| 579 |
<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> <span class="n">s1</span><span class="p">,</span> <span class="n">s2</span><span class="p">,</span> <span class="n">s3</span><span class="p">],</span> |
| 580 |
<span class="p">[</span><span class="n">l</span><span class="p">,</span> <span class="n">y0</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">y1</span><span class="p">])</span> |
| 581 |
|
| 582 |
<span class="n">ptr</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">([</span><span class="n">l</span> <span class="o">==</span> <span class="n">L2</span><span class="p">,</span> <span class="n">m</span> <span class="o">==</span> <span class="n">L2</span> <span class="p">]))</span> |
| 583 |
</pre></div> |
| 584 |
</body></html></example> |
| 585 |
The rather verbose (and in no way minimal) inductive invariants are produced as answers. |
| 586 |
|
| 587 |
<h3>Functional Programs</h3> |
| 588 |
We can also verify some properties of functional programs using Z3's |
| 589 |
generalized PDR. Let us here consider an example from |
| 590 |
<a href="http://www.kb.is.s.u-tokyo.ac.jp/~uhiro/"> |
| 591 |
<em>Predicate Abstraction and CEGAR for Higher-Order Model |
| 592 |
Checking, Kobayashi et.al. PLDI 2011</em></a>. |
| 593 |
We encode functional programs by taking a suitable operational |
| 594 |
semantics and encoding an evaluator that is specialized to |
| 595 |
the program being verified (we don't encode a general purpose |
| 596 |
evaluator, you should partial evaluate it to help verification). |
| 597 |
We use algebraic data-types to encode the current closure that is |
| 598 |
being evaluated. |
| 599 |
|
| 600 |
<example pref="fixedpoint.10"><html><body> |
| 601 |
<div class="highlight"><pre><span class="c"># let max max2 x y z = max2 (max2 x y) z</span> |
| 602 |
<span class="c"># let f x y = if x > y then x else y</span> |
| 603 |
<span class="c"># assert (f (max f x y z) x) = (max f x y z)</span> |
| 604 |
|
| 605 |
|
| 606 |
<span class="n">Expr</span> <span class="o">=</span> <span class="n">Datatype</span><span class="p">(</span><span class="s">'Expr'</span><span class="p">)</span> |
| 607 |
<span class="n">Expr</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'Max'</span><span class="p">)</span> |
| 608 |
<span class="n">Expr</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'f'</span><span class="p">)</span> |
| 609 |
<span class="n">Expr</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'I'</span><span class="p">,</span> <span class="p">(</span><span class="s">'i'</span><span class="p">,</span> <span class="n">IntSort</span><span class="p">()))</span> |
| 610 |
<span class="n">Expr</span><span class="o">.</span><span class="n">declare</span><span class="p">(</span><span class="s">'App'</span><span class="p">,</span> <span class="p">(</span><span class="s">'fn'</span><span class="p">,</span><span class="n">Expr</span><span class="p">),(</span><span class="s">'arg'</span><span class="p">,</span><span class="n">Expr</span><span class="p">))</span> |
| 611 |
<span class="n">Expr</span> <span class="o">=</span> <span class="n">Expr</span><span class="o">.</span><span class="n">create</span><span class="p">()</span> |
| 612 |
<span class="n">Max</span> <span class="o">=</span> <span class="n">Expr</span><span class="o">.</span><span class="n">Max</span> |
| 613 |
<span class="n">I</span> <span class="o">=</span> <span class="n">Expr</span><span class="o">.</span><span class="n">I</span> |
| 614 |
<span class="n">App</span> <span class="o">=</span> <span class="n">Expr</span><span class="o">.</span><span class="n">App</span> |
| 615 |
<span class="n">f</span> <span class="o">=</span> <span class="n">Expr</span><span class="o">.</span><span class="n">f</span> |
| 616 |
<span class="n">Eval</span> <span class="o">=</span> <span class="n">Function</span><span class="p">(</span><span class="s">'Eval'</span><span class="p">,</span><span class="n">Expr</span><span class="p">,</span><span class="n">Expr</span><span class="p">,</span><span class="n">Expr</span><span class="p">,</span><span class="n">BoolSort</span><span class="p">())</span> |
| 617 |
|
| 618 |
<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">Expr</span><span class="p">)</span> |
| 619 |
<span class="n">y</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'y'</span><span class="p">,</span><span class="n">Expr</span><span class="p">)</span> |
| 620 |
<span class="n">z</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'z'</span><span class="p">,</span><span class="n">Expr</span><span class="p">)</span> |
| 621 |
<span class="n">r1</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'r1'</span><span class="p">,</span><span class="n">Expr</span><span class="p">)</span> |
| 622 |
<span class="n">r2</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'r2'</span><span class="p">,</span><span class="n">Expr</span><span class="p">)</span> |
| 623 |
<span class="nb">max</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'max'</span><span class="p">,</span><span class="n">Expr</span><span class="p">)</span> |
| 624 |
<span class="n">xi</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'xi'</span><span class="p">,</span><span class="n">IntSort</span><span class="p">())</span> |
| 625 |
<span class="n">yi</span> <span class="o">=</span> <span class="n">Const</span><span class="p">(</span><span class="s">'yi'</span><span class="p">,</span><span class="n">IntSort</span><span class="p">())</span> |
| 626 |
|
| 627 |
<span class="n">fp</span> <span class="o">=</span> <span class="n">Fixedpoint</span><span class="p">()</span> |
| 628 |
<span class="n">fp</span><span class="o">.</span><span class="n">register_relation</span><span class="p">(</span><span class="n">Eval</span><span class="p">)</span> |
| 629 |
<span class="n">fp</span><span class="o">.</span><span class="n">declare_var</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">r1</span><span class="p">,</span><span class="n">r2</span><span class="p">,</span><span class="nb">max</span><span class="p">,</span><span class="n">xi</span><span class="p">,</span><span class="n">yi</span><span class="p">)</span> |
| 630 |
|
| 631 |
<span class="c"># Max max x y z = max (max x y) z</span> |
| 632 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">Max</span><span class="p">,</span><span class="nb">max</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">r2</span><span class="p">),</span> |
| 633 |
<span class="p">[</span><span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="nb">max</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">r1</span><span class="p">),</span> |
| 634 |
<span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="nb">max</span><span class="p">,</span><span class="n">r1</span><span class="p">),</span><span class="n">z</span><span class="p">,</span><span class="n">r2</span><span class="p">)])</span> |
| 635 |
|
| 636 |
<span class="c"># f x y = x if x >= y</span> |
| 637 |
<span class="c"># f x y = y if x < y</span> |
| 638 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="n">I</span><span class="p">(</span><span class="n">xi</span><span class="p">)),</span><span class="n">I</span><span class="p">(</span><span class="n">yi</span><span class="p">),</span><span class="n">I</span><span class="p">(</span><span class="n">xi</span><span class="p">)),</span><span class="n">xi</span> <span class="o">>=</span> <span class="n">yi</span><span class="p">)</span> |
| 639 |
<span class="n">fp</span><span class="o">.</span><span class="n">rule</span><span class="p">(</span><span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="n">I</span><span class="p">(</span><span class="n">xi</span><span class="p">)),</span><span class="n">I</span><span class="p">(</span><span class="n">yi</span><span class="p">),</span><span class="n">I</span><span class="p">(</span><span class="n">yi</span><span class="p">)),</span><span class="n">xi</span> <span class="o"><</span> <span class="n">yi</span><span class="p">)</span> |
| 640 |
|
| 641 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">And</span><span class="p">(</span><span class="n">Eval</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">App</span><span class="p">(</span><span class="n">Max</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="n">z</span><span class="p">,</span><span class="n">r1</span><span class="p">),</span> |
| 642 |
<span class="n">Eval</span><span class="p">(</span><span class="n">App</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">r1</span><span class="p">,</span><span class="n">r2</span><span class="p">),</span> |
| 643 |
<span class="n">r1</span> <span class="o">!=</span> <span class="n">r2</span><span class="p">))</span> |
| 644 |
|
| 645 |
<span class="k">print</span> <span class="n">fp</span><span class="o">.</span><span class="n">get_answer</span><span class="p">()</span> |
| 646 |
</pre></div> |
| 647 |
</body></html></example> |
| 648 |
|
| 649 |
|
| 650 |
</body> |
| 651 |
</html> |