scala - Tutorial to start with program and datatype refinement -

i read code generation isabelle/hol theories manual. however, still feel bit lost. need things linorder? how can use e.g., red-black trees make things faster? how locale used in context of program refinement? ...

is there tutorial started refinement? if not, there short, self contained, correct example?

---

can develop example?

let's assume have a :: 'a set , know finite a. how proceed generate example efficient code a ∈ a?

how express our knowledge of finite a. how can keep mathematical theory (a ∈ a) separate code generation , optimization?

okay, i'll try best answer question. please feel free comment , edit improve it. if want karma, can copy answer , repost (if answer better, i'll delete answer).

---

this user-guide helped me started.

---

okay, let's assume have our theory in locale mylocale.

locale mylocale =   fixes :: "'a set"   begin     definition isina :: "'a => bool"       "isina ⟷ ∈ a"   end 

let's assume implement isina function implementing locale's set a list. then, can generate code , show correctness

definition code_isina_list :: "'a list => 'a => bool"   "code_isina_list al ⟷ ∈ set al"  lemma code_isina_list_correct:   "code_isina_list al = mylocale.isina (set al) a"   by(simp add: mylocale.isina_def code_isina_list_def)  export_code code_isina_list in scala file - 

this yields following scala code

def code_isina_list[a : hol.equal](al: list[a], a: a): boolean =   lista.member[a](al, a) 

the lista.member functions linear-time algorithm. can better?

let's assume have linorder on our type 'a. example, have linorder on natural numbers, strings, lists, tuples, ... express assumption writing 'a ::linorder instead of 'a. 1 datatype can leverage linorder property red-black-tree. in our locale, a set. in sets, order of elements not matter. can use more efficient red-black tree instead of lists. red-black tree can more efficient lists because elements can ordered arbitrarily while lists dictate fixed order. use red-black trees, import collections framework archive of formal proofs. @ beginning of our thy-file add imports section

"./isabelle_afp/collections/collections" 

now can implement red-black tree (rs) version , show correctness. function rs_α (type alpha<tab> in jedit alpha) collections framework maps red-black tree corresponding set.

definition code_isina_rs :: "('a ::linorder) rs => 'a => bool"   "code_isina_rs al ⟷ rs_memb al"  lemma code_isina_rs_correct:   "code_isina_rs ars = mylocale.isina (rs_α ars) a"   by(simp add: mylocale.isina_def code_isina_rs_def rs_correct)  export_code code_isina_rs in scala file - 

we yield following code

def code_isina_rs[a : orderings.linorder](al: rbt.rbt[a, unit], a: a): boolean =   rbtsetimpl.rs_memb[a].apply(a).apply(al) 

the rs_memb function has logarithmic runtime. todo: really? can up?

let's further improve our code. let's assume want stick code_isina_list version, because lists easier in our code. can implement code_isina_list in terms of code_isina_rs. therefore, use list_to_rs converts list red-black tree. [code] attribute, tell code generator use new version.

lemma [code]: "code_isina_list al ⟷ code_isina_rs (list_to_rs al) a"   by(simp add: code_isina_list_def code_isina_rs_def rs_correct)  export_code code_isina_list in scala file - 

we yield following code.

def code_isina_list[a : orderings.linorder](al: list[a], a: a): boolean =   code_isina_rs[a](rbtsetimpl.list_to_rs[a].apply(al), a) 

i guess creating red-black , lookup in more expensive simpler list version, example. if need more lookups, red-black tree version can more efficient.

let's test code in isabelle jedit types. start natural numbers.

value[code] "code_isina_list [(1::nat), 3, 7, 4] 4" 

this results in true

next, try strings.

value[code] "code_isina_list [''a'', ''b'', ''xyz''] ''b''" 

this results in

wellsortedness error:   type char list not of sort linorder   no type arity list :: linorder 

the error message tells no linorder defined on string type. import following theories.

"~~/src/hol/library/list_lexord" "~~/src/hol/library/code_char" "~~/src/hol/library/code_char_chr" "~~/src/hol/library/code_char_ord" 

now desired result true. code works tuples.

value[code] "code_isina_list [(''a'', ''a''), (''b'', ''c''), (''xyz'', '''')] (''b'', ''c'')"