Common — library smtlib-low-level-theory.theory — module DSeq
57
module DSeq

The theory tries to define only the minimum number of functions, and use for each of them a simple semantic:

(1) https://easychair.org/publications/paper/qdvJ

70
use int.Int
71
use int.MinMax
72
73
type
seq
'a

The length is always greater than or equal to 0, there is only one empty sequence for each default value.

76
function
length
(x:seq 'a) : int No proof
77
axiom
length_nonneg
: forall x: seq 'a. length x >= 0

A sequence s is totaly defined because its value outside its bound is defined by default s.

81
function
default
(x:seq 'a) : 'a

0 length —========— ^ ^ default default

We tried to define the theory by adding a default parameter to get. However in that case the user need to define a polymorphic constant for using get in polymorphic axioms

Outside 0..length-1 the function get always returns the default value

94
function
get
(x:seq 'a) (i:int) : 'a No proof
95
axiom
prop_get
: forall x:seq 'a.
96
forall i. not (0 <= i < length x) -> get x i = default x

Extensionnality need to look at the default value

    No proof
99
axiom
ext
: forall x y: seq 'a.
100
(length x = length y) ->
101
(default x = default y) ->
102
(forall i. 0 <= i < length x -> get x i = get y i) ->
103
x = y

Create a constante sequence, the default is x

106
function
const
(len:int) (x:'a) : seq 'a
107
No proof
108
axiom
length_const
: forall x:'a. forall len. length (const len x) = max 0 len No proof
109
axiom
default_const
: forall x:'a. forall len. default (const len x) = x No proof
110
axiom
get_const
: forall x:'a. forall len. forall i. get (const len x) i = x

Modification outside the bound of the sequence keep the original sequence

113
function
set
(x:seq 'a) (i:int) (a:'a) : seq 'a No proof
114
axiom
length_set
: forall x:seq 'a. forall i a. length (set x i a) = length x No proof
115
axiom
default_set
: forall x:seq 'a. forall i a. default (set x i a) = default x No proof
116
axiom
get_set
[@rewrite]: forall x:seq 'a. forall i a j.
117
get (set x i a) j = if 0 <= i = j < length x then a else get x j

extract extract a sequence of the given length at the given position. Edge cases are filled with the default value.

0 length orig: —========— extract —========— ^ | ^ default | orig

The default value is the one of orig. So the only value that are changed are the one in the bounds of orig that are not extracted.

133
function
extract
(x:seq 'a) (pos len:int) : seq 'a No proof
134
axiom
length_extract
: forall x: seq 'a. forall pos len. length (extract x pos len) = max 0 len No proof
135
axiom
default_extract
: forall x: seq 'a. forall pos len. default (extract x pos len) = (default x) No proof
136
axiom
get_extract
: forall x: seq 'a. forall pos len j.
137
0 <= j < len -> get (extract x pos len) j = get x (pos+j)

The value of dst are kept except at the intersection of its bound and pos..pos+len-1

142
function
update
(dst:seq 'a) (pos len:int) (src:seq 'a) : seq 'a No proof
143
axiom
length_update
: forall dst src: seq 'a. forall pos len. length (update dst pos len src) = length dst No proof
144
axiom
default_update
: forall dst src: seq 'a. forall pos len. default (update dst pos len src) = (default dst) No proof
145
axiom
get_update
: forall dst src: seq 'a. forall pos len j.
146
0 <= j < length dst -> get (update dst pos len src) j = if pos <= j < pos+len then get src (j-pos) else get dst j
147
No proof
148
lemma
extract_update
: forall dst src: seq 'a.
149
forall pos len. 0 <= pos <= pos+len <= length dst ->
150
default src = default dst ->
151
extract (update dst pos len src) pos len = extract src 0 len
152
No proof
153
lemma
extract_length
: forall s: seq 'a.
154
extract s 0 (length s) = s

For simplicity in Why3

158
function
from_array
(len:int) (def:'a) (map:int -> 'a) : seq 'a
159
No proof
160
axiom
length_from_array
: forall len def map. length (from_array len (def:'a) map) = max 0 len No proof
161
axiom
default_from_array
: forall len def map. default (from_array len (def:'a) map) = def No proof
162
axiom
get_from_array
: forall len def map j. get (from_array len (def:'a) map) j = if 0 <= j < len then map j else def
163
164
function
rev
(s:seq 'a) : seq 'a No proof
165
axiom
length_rev
: forall s: seq 'a. length (rev s) = length s No proof
166
axiom
default_rev
: forall s: seq 'a. default (rev s) = (default s) No proof
167
axiom
get_rev
: forall s: seq 'a. forall j. get (rev s) j = get s (length s - 1 - j)
168
169
end