Debian Codegraph @

examples/ml/ml_example.ml

raw
1 (*
2 Copyright (C) 2012 Microsoft Corporation
3 Author: CM Wintersteiger (cwinter) 2012-12-17
4 *)
5
6 open Z3
7 open Z3.Symbol
8 open Z3.Sort
9 open Z3.Expr
10 open Z3.Boolean
11 open Z3.FuncDecl
12 open Z3.Goal
13 open Z3.Tactic
14 open Z3.Tactic.ApplyResult
15 open Z3.Probe
16 open Z3.Solver
17 open Z3.Arithmetic
18 open Z3.Arithmetic.Integer
19 open Z3.Arithmetic.Real
20 open Z3.BitVector
21
22 exception TestFailedException of string
23
24 (**
25 Model Converter test
26 *)
27 let model_converter_test ( ctx : context ) =
28 Printf.printf "ModelConverterTest\n";
29 let xr = (Expr.mk_const ctx (Symbol.mk_string ctx "x") (Real.mk_sort ctx)) in
30 let yr = (Expr.mk_const ctx (Symbol.mk_string ctx "y") (Real.mk_sort ctx)) in
31 let g4 = (mk_goal ctx true false false ) in
32 (Goal.add g4 [ (mk_gt ctx xr (Real.mk_numeral_nd ctx 10 1)) ]) ;
33 (Goal.add g4 [ (mk_eq ctx
34 yr
35 (Arithmetic.mk_add ctx [ xr; (Real.mk_numeral_nd ctx 1 1) ])) ]) ;
36 (Goal.add g4 [ (mk_gt ctx yr (Real.mk_numeral_nd ctx 1 1)) ]) ;
37 (
38 let ar = (Tactic.apply (mk_tactic ctx "simplify") g4 None) in
39 if ((get_num_subgoals ar) == 1 &&
40 ((is_decided_sat (get_subgoal ar 0)) ||
41 (is_decided_unsat (get_subgoal ar 0)))) then
42 raise (TestFailedException "")
43 else
44 Printf.printf "Test passed.\n"
45 );
46 (
47 let ar = (Tactic.apply (and_then ctx (mk_tactic ctx ("simplify")) (mk_tactic ctx "solve-eqs") []) g4 None) in
48 if ((get_num_subgoals ar) == 1 &&
49 ((is_decided_sat (get_subgoal ar 0)) ||
50 (is_decided_unsat (get_subgoal ar 0)))) then
51 raise (TestFailedException "")
52 else
53 Printf.printf "Test passed.\n"
54 ;
55 let solver = (mk_solver ctx None) in
56 let f e = (Solver.add solver [ e ]) in
57 ignore (List.map f (get_formulas (get_subgoal ar 0))) ;
58 let q = (check solver []) in
59 if q != SATISFIABLE then
60 raise (TestFailedException "")
61 else
62 let m = (get_model solver) in
63 match m with
64 | None -> raise (TestFailedException "")
65 | Some (m) ->
66 Printf.printf "Solver says: %s\n" (string_of_status q) ;
67 Printf.printf "Model: \n%s\n" (Model.to_string m)
68 )
69
70 (**
71 Some basic tests.
72 *)
73 let basic_tests ( ctx : context ) =
74 Printf.printf "BasicTests\n" ;
75 let fname = (mk_string ctx "f") in
76 let x = (mk_string ctx "x") in
77 let y = (mk_string ctx "y") in
78 let bs = (Boolean.mk_sort ctx) in
79 let domain = [ bs; bs ] in
80 let f = (FuncDecl.mk_func_decl ctx fname domain bs) in
81 let fapp = (mk_app ctx f
82 [ (Expr.mk_const ctx x bs); (Expr.mk_const ctx y bs) ]) in
83 let fargs2 = [ (mk_fresh_const ctx "cp" bs) ] in
84 let domain2 = [ bs ] in
85 let fapp2 = (mk_app ctx (mk_fresh_func_decl ctx "fp" domain2 bs) fargs2) in
86 let trivial_eq = (mk_eq ctx fapp fapp) in
87 let nontrivial_eq = (mk_eq ctx fapp fapp2) in
88 let g = (mk_goal ctx true false false) in
89 (Goal.add g [ trivial_eq ]) ;
90 (Goal.add g [ nontrivial_eq ]) ;
91 Printf.printf "%s\n" ("Goal: " ^ (Goal.to_string g)) ;
92 (
93 let solver = (mk_solver ctx None) in
94 (List.iter (fun a -> (Solver.add solver [ a ])) (get_formulas g)) ;
95 if (check solver []) != SATISFIABLE then
96 raise (TestFailedException "")
97 else
98 Printf.printf "Test passed.\n"
99 );
100 (
101 let ar = (Tactic.apply (mk_tactic ctx "simplify") g None) in
102 if ((get_num_subgoals ar) == 1 &&
103 ((is_decided_sat (get_subgoal ar 0)) ||
104 (is_decided_unsat (get_subgoal ar 0)))) then
105 raise (TestFailedException "")
106 else
107 Printf.printf "Test passed.\n"
108 );
109 (
110 let ar = (Tactic.apply (mk_tactic ctx "smt") g None) in
111 if ((get_num_subgoals ar) == 1 &&
112 (not (is_decided_sat (get_subgoal ar 0)))) then
113 raise (TestFailedException "")
114 else
115 Printf.printf "Test passed.\n"
116 );
117 (Goal.add g [ (mk_eq ctx
118 (mk_numeral_int ctx 1 (BitVector.mk_sort ctx 32))
119 (mk_numeral_int ctx 2 (BitVector.mk_sort ctx 32))) ] )
120 ;
121 (
122 let ar = (Tactic.apply (mk_tactic ctx "smt") g None) in
123 if ((get_num_subgoals ar) == 1 &&
124 (not (is_decided_unsat (get_subgoal ar 0)))) then
125 raise (TestFailedException "")
126 else
127 Printf.printf "Test passed.\n"
128 );
129 (
130 let g2 = (mk_goal ctx true true false) in
131 let ar = (Tactic.apply (mk_tactic ctx "smt") g2 None) in
132 if ((get_num_subgoals ar) == 1 &&
133 (not (is_decided_sat (get_subgoal ar 0)))) then
134 raise (TestFailedException "")
135 else
136 Printf.printf "Test passed.\n"
137 );
138 (
139 let g2 = (mk_goal ctx true true false) in
140 (Goal.add g2 [ (Boolean.mk_false ctx) ]) ;
141 let ar = (Tactic.apply (mk_tactic ctx "smt") g2 None) in
142 if ((get_num_subgoals ar) == 1 &&
143 (not (is_decided_unsat (get_subgoal ar 0)))) then
144 raise (TestFailedException "")
145 else
146 Printf.printf "Test passed.\n"
147 );
148 (
149 let g3 = (mk_goal ctx true true false) in
150 let xc = (Expr.mk_const ctx (Symbol.mk_string ctx "x") (Integer.mk_sort ctx)) in
151 let yc = (Expr.mk_const ctx (Symbol.mk_string ctx "y") (Integer.mk_sort ctx)) in
152 (Goal.add g3 [ (mk_eq ctx xc (mk_numeral_int ctx 1 (Integer.mk_sort ctx))) ]) ;
153 (Goal.add g3 [ (mk_eq ctx yc (mk_numeral_int ctx 2 (Integer.mk_sort ctx))) ]) ;
154 let constr = (mk_eq ctx xc yc) in
155 (Goal.add g3 [ constr ] ) ;
156 let ar = (Tactic.apply (mk_tactic ctx "smt") g3 None) in
157 if ((get_num_subgoals ar) == 1 &&
158 (not (is_decided_unsat (get_subgoal ar 0)))) then
159 raise (TestFailedException "")
160 else
161 Printf.printf "Test passed.\n"
162 ) ;
163 model_converter_test ctx ;
164 (* Real num/den test. *)
165 let rn = Real.mk_numeral_nd ctx 42 43 in
166 let inum = (get_numerator rn) in
167 let iden = get_denominator rn in
168 Printf.printf "Numerator: %s Denominator: %s\n" (Real.numeral_to_string inum) (Real.numeral_to_string iden) ;
169 if ((Real.numeral_to_string inum) <> "42" || (Real.numeral_to_string iden) <> "43") then
170 raise (TestFailedException "")
171 else
172 Printf.printf "Test passed.\n"
173 ;
174 if ((to_decimal_string rn 3) <> "0.976?") then
175 raise (TestFailedException "")
176 else
177 Printf.printf "Test passed.\n"
178 ;
179 if (to_decimal_string (Real.mk_numeral_s ctx "-1231231232/234234333") 5 <> "-5.25640?") then
180 raise (TestFailedException "")
181 else if (to_decimal_string (Real.mk_numeral_s ctx "-123123234234234234231232/234234333") 5 <> "-525641278361333.28170?") then
182 raise (TestFailedException "")
183 else if (to_decimal_string (Real.mk_numeral_s ctx "-234234333") 5 <> "-234234333") then
184 raise (TestFailedException "")
185 else if (to_decimal_string (Real.mk_numeral_s ctx "234234333/2") 5 <> "117117166.5") then
186 raise (TestFailedException "")
187 ;
188 (* Error handling test. *)
189 try (
190 let i = Integer.mk_numeral_s ctx "1/2" in
191 Printf.printf "%s\n" (Expr.to_string i) ;
192 raise (TestFailedException "check")
193 )
194 with Z3.Error(_) -> (
195 Printf.printf "Exception caught, OK.\n"
196 )
197
198 (**
199 A basic example of how to use quantifiers.
200 **)
201 let quantifier_example1 ( ctx : context ) =
202 Printf.printf "QuantifierExample\n" ;
203 let is = (Integer.mk_sort ctx) in
204 let types = [ is; is; is ] in
205 let names = [ (Symbol.mk_string ctx "x_0");
206 (Symbol.mk_string ctx "x_1");
207 (Symbol.mk_string ctx "x_2") ] in
208 let vars = [ (Quantifier.mk_bound ctx 2 (List.nth types 0));
209 (Quantifier.mk_bound ctx 2 (List.nth types 1));
210 (Quantifier.mk_bound ctx 2 (List.nth types 2)) ] in
211 let xs = [ (Integer.mk_const ctx (List.nth names 0));
212 (Integer.mk_const ctx (List.nth names 1));
213 (Integer.mk_const ctx (List.nth names 2)) ] in
214
215 let body_vars = (Boolean.mk_and ctx
216 [ (mk_eq ctx
217 (Arithmetic.mk_add ctx [ (List.nth vars 0) ; (Integer.mk_numeral_i ctx 1)])
218 (Integer.mk_numeral_i ctx 2)) ;
219 (mk_eq ctx
220 (Arithmetic.mk_add ctx [ (List.nth vars 1); (Integer.mk_numeral_i ctx 2)])
221 (Arithmetic.mk_add ctx [ (List.nth vars 2); (Integer.mk_numeral_i ctx 3)])) ]) in
222 let body_const = (Boolean.mk_and ctx
223 [ (mk_eq ctx
224 (Arithmetic.mk_add ctx [ (List.nth xs 0); (Integer.mk_numeral_i ctx 1)])
225 (Integer.mk_numeral_i ctx 2)) ;
226 (mk_eq ctx
227 (Arithmetic.mk_add ctx [ (List.nth xs 1); (Integer.mk_numeral_i ctx 2)])
228 (Arithmetic.mk_add ctx [ (List.nth xs 2); (Integer.mk_numeral_i ctx 3)])) ]) in
229
230 let x = (Quantifier.mk_forall ctx types names body_vars (Some 1) [] [] (Some (Symbol.mk_string ctx "Q1")) (Some (Symbol.mk_string ctx "skid1"))) in
231 Printf.printf "Quantifier X: %s\n" (Quantifier.to_string x) ;
232 let y = (Quantifier.mk_forall_const ctx xs body_const (Some 1) [] [] (Some (Symbol.mk_string ctx "Q2")) (Some (Symbol.mk_string ctx "skid2"))) in
233 Printf.printf "Quantifier Y: %s\n" (Quantifier.to_string y) ;
234 if (is_true (Quantifier.expr_of_quantifier x)) then
235 raise (TestFailedException "") (* unreachable *)
236 else if (is_false (Quantifier.expr_of_quantifier x)) then
237 raise (TestFailedException "") (* unreachable *)
238 else if (is_const (Quantifier.expr_of_quantifier x)) then
239 raise (TestFailedException "") (* unreachable *)
240
241
242 open Z3.FloatingPoint
243
244 (**
245 A basic example of floating point arithmetic
246 **)
247 let fpa_example ( ctx : context ) =
248 Printf.printf "FPAExample\n" ;
249 (* let str = ref "" in *)
250 (* (read_line ()) ; *)
251 let double_sort = (FloatingPoint.mk_sort_double ctx) in
252 let rm_sort = (FloatingPoint.RoundingMode.mk_sort ctx) in
253
254 (** Show that there are x, y s.t. (x + y) = 42.0 (with rounding mode). *)
255 let s_rm = (mk_string ctx "rm") in
256 let rm = (mk_const ctx s_rm rm_sort) in
257 let s_x = (mk_string ctx "x") in
258 let s_y = (mk_string ctx "y") in
259 let x = (mk_const ctx s_x double_sort) in
260 let y = (mk_const ctx s_y double_sort)in
261 let n = (FloatingPoint.mk_numeral_f ctx 42.0 double_sort) in
262 let s_x_plus_y = (mk_string ctx "x_plus_y") in
263 let x_plus_y = (mk_const ctx s_x_plus_y double_sort) in
264 let c1 = (mk_eq ctx x_plus_y (mk_add ctx rm x y)) in
265 let args = [ c1 ; (mk_eq ctx x_plus_y n) ] in
266 let c2 = (Boolean.mk_and ctx args) in
267 let args2 = [ c2 ; (Boolean.mk_not ctx (Boolean.mk_eq ctx rm (RoundingMode.mk_rtz ctx))) ] in
268 let c3 = (Boolean.mk_and ctx args2) in
269 let and_args = [ (Boolean.mk_not ctx (mk_is_zero ctx y)) ;
270 (Boolean.mk_not ctx (mk_is_nan ctx y)) ;
271 (Boolean.mk_not ctx (mk_is_infinite ctx y)) ] in
272 let args3 = [ c3 ; (Boolean.mk_and ctx and_args) ] in
273 let c4 = (Boolean.mk_and ctx args3) in
274 (Printf.printf "c4: %s\n" (Expr.to_string c4)) ;
275 (
276 let solver = (mk_solver ctx None) in
277 (Solver.add solver [ c4 ]) ;
278 if (check solver []) != SATISFIABLE then
279 raise (TestFailedException "")
280 else
281 Printf.printf "Test passed.\n"
282 );
283
284 (* Show that the following are equal: *)
285 (* (fp #b0 #b10000000001 #xc000000000000) *)
286 (* ((_ to_fp 11 53) #x401c000000000000)) *)
287 (* ((_ to_fp 11 53) RTZ 1.75 2))) *)
288 (* ((_ to_fp 11 53) RTZ 7.0))) *)
289 let c1 = (mk_fp ctx (mk_numeral_string ctx "0" (BitVector.mk_sort ctx 1))
290 (mk_numeral_string ctx "1025" (BitVector.mk_sort ctx 11))
291 (mk_numeral_string ctx "3377699720527872" (BitVector.mk_sort ctx 52))) in
292 let c2 = (mk_to_fp_bv ctx
293 (mk_numeral_string ctx "4619567317775286272" (BitVector.mk_sort ctx 64))
294 (mk_sort ctx 11 53)) in
295 let c3 = (mk_to_fp_int_real ctx
296 (RoundingMode.mk_rtz ctx)
297 (mk_numeral_string ctx "2" (Integer.mk_sort ctx))
298 (mk_numeral_string ctx "1.75" (Real.mk_sort ctx))
299 (FloatingPoint.mk_sort ctx 11 53)) in
300 let c4 = (mk_to_fp_real ctx (RoundingMode.mk_rtz ctx)
301 (mk_numeral_string ctx "7.0" (Real.mk_sort ctx))
302 (FloatingPoint.mk_sort ctx 11 53)) in
303 let args3 = [ (mk_eq ctx c1 c2) ;
304 (mk_eq ctx c1 c3) ;
305 (mk_eq ctx c1 c4) ] in
306 let c5 = (Boolean.mk_and ctx args3) in
307 (Printf.printf "c5: %s\n" (Expr.to_string c5)) ;
308 (
309 let solver = (mk_solver ctx None) in
310 (Solver.add solver [ c5 ]) ;
311 Printf.printf "Memory in use before `check`: %Lu bytes\n" (Statistics.get_estimated_alloc_size());
312 if (check solver []) != SATISFIABLE then
313 raise (TestFailedException "")
314 else
315 Printf.printf "Test passed.\n"
316 )
317
318 (**
319 A basic example of RCF usage
320 **)
321 let rcf_example ( ctx : context ) =
322 Printf.printf "RCFExample\n" ;
323 let pi = RCF.mk_pi ctx in
324 let e = RCF.mk_e ctx in
325 let inf0 = RCF.mk_infinitesimal ctx in
326 let inf1 = RCF.mk_infinitesimal ctx in
327 let r = RCF.mk_rational ctx "42.001" in
328 let pi_div_e = RCF.div ctx pi e in
329 let pi_div_r = RCF.div ctx pi r in
330 (Printf.printf "e: %s, pi: %s, e==pi: %b, e < pi: %b\n"
331 (RCF.num_to_string ctx e true false)
332 (RCF.num_to_string ctx pi true false)
333 (RCF.eq ctx e pi)
334 (RCF.lt ctx e pi)) ;
335 Printf.printf "pi_div_e: %s.\n" (RCF.num_to_string ctx pi_div_e true false);
336 Printf.printf "pi_div_r: %s.\n" (RCF.num_to_string ctx pi_div_r true false);
337 Printf.printf "inf0: %s.\n" (RCF.num_to_string ctx inf0 true false);
338 Printf.printf "(RCF.is_rational ctx pi): %b.\n" (RCF.is_rational ctx pi);
339 Printf.printf "(RCF.is_algebraic ctx pi): %b.\n" (RCF.is_algebraic ctx pi);
340 Printf.printf "(RCF.is_transcendental ctx pi): %b.\n" (RCF.is_transcendental ctx pi);
341 Printf.printf "(RCF.is_rational ctx r): %b.\n" (RCF.is_rational ctx r);
342 Printf.printf "(RCF.is_algebraic ctx r): %b.\n" (RCF.is_algebraic ctx r);
343 Printf.printf "(RCF.is_transcendental ctx r): %b.\n" (RCF.is_transcendental ctx r);
344 Printf.printf "(RCF.is_infinitesimal ctx inf0): %b.\n" (RCF.is_infinitesimal ctx inf0);
345 Printf.printf "(RCF.extension_index ctx inf0): %d.\n" (RCF.extension_index ctx inf0);
346 Printf.printf "(RCF.extension_index ctx inf1): %d.\n" (RCF.extension_index ctx inf1);
347 let poly:RCF.rcf_num list = [ e; pi; inf0 ] in
348 let rs:RCF.root list = RCF.roots ctx poly in
349 let print_root (x:RCF.root) =
350 begin
351 Printf.printf "root: %s\n%!" (RCF.num_to_string ctx x.obj true false);
352 if RCF.is_algebraic ctx x.obj then (
353 (match x.interval with
354 | Some ivl -> Printf.printf " interval: (%b, %b, %s, %b, %b, %s)\n"
355 ivl.lower_is_inf
356 ivl.lower_is_open
357 (RCF.num_to_string ctx ivl.lower true false)
358 ivl.upper_is_inf
359 ivl.upper_is_open
360 (RCF.num_to_string ctx ivl.upper true false);
361 | None -> ());
362 Printf.printf " polynomial coefficients:";
363 List.iter (fun c -> Printf.printf " %s" (RCF.num_to_string ctx c false false)) x.polynomial;
364 Printf.printf "\n";
365 Printf.printf " sign conditions:";
366 List.iter
367 (fun (poly, sign) ->
368 List.iter (fun p -> Printf.printf " %s" (RCF.num_to_string ctx p true false)) poly;
369 Printf.printf " %s" (if sign > 0 then "> 0" else if sign < 0 then "< 0" else "= 0"))
370 x.sign_conditions;
371 Printf.printf "\n")
372 end
373 in
374 List.iter print_root rs;
375 RCF.del_roots ctx rs;
376 RCF.del_list ctx [pi; e; inf0; inf1; r; pi_div_e; pi_div_r];
377 Printf.printf "Test passed.\n"
378
379 let _ =
380 try (
381 if not (Log.open_ "z3.log") then
382 raise (TestFailedException "Log couldn't be opened.")
383 else
384 (
385 Printf.printf "Running Z3 version %s\n" Version.to_string ;
386 Printf.printf "Z3 full version string: %s\n" Version.full_version ;
387 let cfg = [("model", "true"); ("proof", "false")] in
388 let ctx = (mk_context cfg) in
389 let is = (Symbol.mk_int ctx 42) in
390 let ss = (Symbol.mk_string ctx "mySymbol") in
391 let bs = (Boolean.mk_sort ctx) in
392 let ints = (Integer.mk_sort ctx) in
393 let rs = (Real.mk_sort ctx) in
394 let v = (Arithmetic.Integer.mk_numeral_i ctx 8000000000) in
395 Printf.printf "int symbol: %s\n" (Symbol.to_string is);
396 Printf.printf "string symbol: %s\n" (Symbol.to_string ss);
397 Printf.printf "bool sort: %s\n" (Sort.to_string bs);
398 Printf.printf "int sort: %s\n" (Sort.to_string ints);
399 Printf.printf "real sort: %s\n" (Sort.to_string rs);
400 Printf.printf "integer: %s\n" (Expr.to_string v);
401 basic_tests ctx ;
402 quantifier_example1 ctx ;
403 fpa_example ctx ;
404 rcf_example ctx ;
405 Printf.printf "Disposing...\n";
406 Gc.full_major ()
407 );
408 Printf.printf "Exiting.\n" ;
409 exit 0
410 ) with Error(msg) -> (
411 Printf.printf "Z3 EXCEPTION: %s\n" msg ;
412 exit 1
413 )
414 ;;
415