library smtlib-low-level-theory.theory — module DSeqmodule DSeq57
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
use int.Int70use int.MinMax7172type seq 'a73
The length is always greater than or equal to 0, there is only one empty sequence for each default value.
function length (x:seq 'a) : int No proof76axiom length_nonneg: forall x: seq 'a. length x >= 077
A sequence s is totaly defined because its value outside its bound is defined by default s.
function default (x:seq 'a) : 'a81
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
function get (x:seq 'a) (i:int) : 'a No proof94axiom prop_get: forall x:seq 'a.95forall i. not (0 <= i < length x) -> get x i = default x96
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
function const (len:int) (x:'a) : seq 'a106No proof107axiom length_const: forall x:'a. forall len. length (const len x) = max 0 len No proof108axiom default_const: forall x:'a. forall len. default (const len x) = x No proof109axiom get_const: forall x:'a. forall len. forall i. get (const len x) i = x110
Modification outside the bound of the sequence keep the original sequence
function set (x:seq 'a) (i:int) (a:'a) : seq 'a No proof113axiom length_set: forall x:seq 'a. forall i a. length (set x i a) = length x No proof114axiom default_set: forall x:seq 'a. forall i a. default (set x i a) = default x No proof115axiom get_set[@rewrite]: forall x:seq 'a. forall i a j.116get (set x i a) j = if 0 <= i = j < length x then a else get x j117
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.
function extract (x:seq 'a) (pos len:int) : seq 'a No proof133axiom length_extract: forall x: seq 'a. forall pos len. length (extract x pos len) = max 0 len No proof134axiom default_extract: forall x: seq 'a. forall pos len. default (extract x pos len) = (default x) No proof135axiom get_extract: forall x: seq 'a. forall pos len j.1360 <= j < len -> get (extract x pos len) j = get x (pos+j)137
The value of dst are kept except at the intersection of its bound and pos..pos+len-1
function update (dst:seq 'a) (pos len:int) (src:seq 'a) : seq 'a No proof142axiom length_update: forall dst src: seq 'a. forall pos len. length (update dst pos len src) = length dst No proof143axiom default_update: forall dst src: seq 'a. forall pos len. default (update dst pos len src) = (default dst) No proof144axiom get_update: forall dst src: seq 'a. forall pos len j.1450 <= j < length dst -> get (update dst pos len src) j = if pos <= j < pos+len then get src (j-pos) else get dst j146No proof147lemma extract_update: forall dst src: seq 'a.148forall pos len. 0 <= pos <= pos+len <= length dst ->149default src = default dst ->150extract (update dst pos len src) pos len = extract src 0 len151No proof152lemma extract_length: forall s: seq 'a.153extract s 0 (length s) = s154
For simplicity in Why3
function from_array (len:int) (def:'a) (map:int -> 'a) : seq 'a158No proof159axiom length_from_array: forall len def map. length (from_array len (def:'a) map) = max 0 len No proof160axiom default_from_array: forall len def map. default (from_array len (def:'a) map) = def No proof161axiom get_from_array: forall len def map j. get (from_array len (def:'a) map) j = if 0 <= j < len then map j else def162163function rev (s:seq 'a) : seq 'a No proof164axiom length_rev: forall s: seq 'a. length (rev s) = length s No proof165axiom default_rev: forall s: seq 'a. default (rev s) = (default s) No proof166axiom get_rev: forall s: seq 'a. forall j. get (rev s) j = get s (length s - 1 - j)167168end169