| 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) |