Debian Codegraph @

examples/SMT-LIB2/bounded model checking/bubble_sort.smt2

raw
1 ; File name: bubble_sort.smt2
2 ;
3 ; BUBBLESORT - Copyright (c) March, 2021 - Matteo Nicoli
4 ;
5 ; An example of bounded model checking of the classic bubble sort algorithm.
6 ; we will copy the array values into a list in order to check whether the
7 ; array is ordered or not. That's because:
8 ; - it's easier to walk recursively through a list
9 ; - it gives an example of how list and sequences work in Z3
10 ;
11
12
13 ; size of the array
14 (declare-const dim Int)
15
16 ; arrays declaration
17 (declare-const A0 (Array Int Int))
18 (declare-const A1 (Array Int Int))
19 (declare-const A2 (Array Int Int))
20 (declare-const A3 (Array Int Int))
21
22 ; indexes declaration
23 (declare-const i0 Int)
24 (declare-const i1 Int)
25 (declare-const i2 Int)
26 (declare-const i3 Int)
27
28 (declare-const j0 Int)
29 (declare-const j1 Int)
30 (declare-const j2 Int)
31 (declare-const j3 Int)
32
33 (declare-const tmp0 Int)
34 (declare-const tmp1 Int)
35 (declare-const tmp2 Int)
36
37 ; lists declaration (for post condition)
38 (declare-const l0 (List Int))
39 (declare-const l1 (List Int))
40 (declare-const l2 (List Int))
41 (declare-const l3 (List Int))
42 (declare-const l4 (List Int))
43
44 (define-fun init_indexes ((_i Int) (_j Int)) Bool
45 (and
46 (= _i 0)
47 (= _j 0)
48 )
49 )
50
51 (define-fun inner_loop
52 (
53 (_A0 (Array Int Int))
54 (_A1 (Array Int Int))
55 (tmp Int)
56 (_i0 Int)
57 (_dim Int)
58 ) Bool
59 (ite
60 (> (select _A0 _i0) (select _A0 (+ _i0 1)))
61 (and
62 (= tmp (select _A0 _i0))
63 (= _A1 (store _A0 _i0 (select _A0 (+ _i0 1))))
64 (= _A1 (store _A0 (+ _i0 1) tmp))
65 )
66 (= _A1 _A0)
67 )
68 )
69
70 ; the body of the bubblesort algorithm
71 (define-fun bsort_step
72 (
73 (_A0 (Array Int Int))
74 (_A1 (Array Int Int))
75 (tmp Int)
76 (_i0 Int)
77 (_j0 Int)
78 (_i1 Int)
79 (_j1 Int)
80 (_dim Int)
81 ) Bool
82 (ite
83 (< _j0 (- _dim 1))
84 (and
85 (ite
86 (< _i0 (- _dim 1))
87 (and
88 (inner_loop _A0 _A1 tmp _i0 _dim)
89 (= _i1 (+ _i0 1))
90 )
91 (= _j1 (+ _j0 1))
92 )
93 (= _j1 (+ _j0 1))
94 )
95 (and
96 (= _j1 (+ _j0 1))
97 (= _A1 _A0)
98 )
99 )
100 )
101
102 ; the function by which we check whether the list is ordered
103 (define-fun-rec check ((_l (List Int))) Bool
104 (ite
105 (= _l nil)
106 true
107 (ite
108 (not (= (tail _l) nil))
109 (and
110 (>= (head _l) (head (tail _l)))
111 (check (tail _l))
112 )
113 true
114 )
115 )
116 )
117
118 ; sets the size of the array
119 (assert (= dim 4))
120
121 ; initialization of the counters
122 (assert (init_indexes i0 j0))
123
124 ; the first step of the sorting algorithm
125 (assert (bsort_step A0 A1 tmp0 i0 j0 i1 j1 dim))
126 (assert (bsort_step A1 A2 tmp1 i1 j1 i2 j2 dim))
127 (assert (bsort_step A2 A3 tmp2 i2 j2 i3 j3 dim))
128
129 ; filling the list for test
130 (assert
131 (and
132 (= l0 nil)
133 (= l1 (insert (select A3 0) l0))
134 (= l2 (insert (select A3 1) l1))
135 (= l3 (insert (select A3 2) l2))
136 (= l4 (insert (select A3 3) l3))
137 )
138 )
139
140 (echo "BUBBLE SORT")
141
142 (push)
143
144 ; (negated) post-condition
145 (assert (not (check l4)))
146
147 (echo "Testing the validity of the algorithm; `unsat` expected: ")
148
149 ; `unsat` expected
150 (check-sat)
151
152 (echo "---------------------")
153
154 (pop)
155
156 ; post-condition
157 (assert (check l4))
158
159 (echo "Getting a model; `sat` expected: ")
160
161 ; `sat` expected
162 (check-sat)
163
164 (echo "---------------------")
165
166 (echo "Model: ")
167 (get-value (A3))
168 (exit)