Debian Codegraph @

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

raw
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 &#956;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">&lt;=</span> <span class="n">row</span> <span class="ow">and</span> <span class="n">row</span> <span class="o">&lt;</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">&lt;=</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">&lt;=</span> <span class="n">col</span> <span class="ow">and</span> <span class="n">col</span> <span class="o">&lt;</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">&lt;=</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">-&gt;</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">&lt;</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">&lt;=</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">&lt;=</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">&lt;=</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">&lt;=</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">&lt;</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">&gt;</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">&lt;</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">&lt;</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">&lt;=</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 &lt;= 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 &lt; 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">&lt;</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 &gt; 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">&gt;</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">&lt;=</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">&lt;</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">&lt;</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">&lt;</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">&lt;=</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">&lt;=</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 &gt; 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 &gt;= y</span>
637 <span class="c"># f x y = y if x &lt; 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">&gt;=</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">&lt;</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>