| COM | sci_misc_01 | ---- Objects that would be in above theories, but were |
| COM | sci_misc_02 | created after these theories were declared done. ---- |
| COM | sci_misc_base_0 | ---- sci_base: Basic List lemmas ------------------------- |
| THM | filter_mt | 'a:S. l:'a List. P:'a  . mt(filter(P;filter( x. (P x);l))) |
| THM | list_el_1_filter | y: . l: List. list_el( ;y;l)  ||filter( x.(x = y);l)|| 1 |
| COM | sci_misc_pred_12 | ---- sci_pred: Staying Rewrites -------------------------- |
| THM | staying_cs_ni_rw | s:state. p:PId. q:PId?. e:zexp.
(status-q_ = Delleft)
 (status-q_ = Delright)
 (staying(csq:=e s;p)   staying(s;p)) |
| THM | staying_inlist_rw | s:state. p:PId.
staying(statusp:=Inlist s;p)
  list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
list_el(mesg;read_cache_goneQ(p::[]);buf[m]_)
( qq: . list_el(mesg;delrightR(qq::ok{}::[]);buf[p]_)) |
| THM | staying_inqueue_rw | s:state. p:PId. staying(statusp:=Inqueue s;p)   False |
| THM | staying_hsend_ni_rw | s:state. p:PId. q: . r:PId. T: . args: List.
(T = read_cache_freshQ)
 (T = read_cache_goneQ)
 (T = delleftR)
 (T = delrightR)
 (staying([h<-(hsend(r;q;T(args))::h)] s;p)   staying(s;p)) |
| THM | staying_hreceive_ni_rw | s:state. p:PId. q: .
(next_mesg(q;s.h).type = read_cache_freshQ)
 (next_mesg(q;s.h).type = read_cache_goneQ)
 (next_mesg(q;s.h).type = delleftR)
 (next_mesg(q;s.h).type = delrightR)
 (next_mesg(q;s.h).type = 0)
 (staying([h<-(hreceive(q;h)::h)] s;p)   staying(s;p)) |
| THM | staying_hreceive_diff_rw | s:state. p:PId. q: .
(q = p)
 (q = m)
 (next_mesg(q;s.h).type = 0)
 (staying([h<-(hreceive(q;h)::h)] s;p)   staying(s;p)) |
| THM | staying_znil_rw | s:state. p:PId. x:Atom. e:zexp.
staying(xnil:=e s;p)   staying(s;p) |
| ML | sci_staying_simpset | map ((simpset_add `sci_staying`) o lemma_simp)
``staying_inlist_rw staying_inqueue_rw staying_znil_rw`` ;;
map (simpset_add `sci_staying`)
[lemma_cond_simp `staying_cs_ni_rw` [IdSimpCond];
lemma_cond_simp `staying_diff_id_rw` [DiffIds ORELSE (Unab ``mk_id`
` THEN DiffId)];
lemma_cond_simp `staying_hsend_ni_rw` [DiffMesgTypesOrTrivial];
lemma_cond_simp `staying_hreceive_diff_rw` [DiffBufferPids;ProcNotM
em;DiffRecTypes]
];;
|
| COM | sci_misc_rank_1 | ---- sci_rank: General Definitions and Theorems ---------- |
| THM | rank_fn_nil | x: . rank_fn(x;[]) = -1 |
| THM | rank_fn_zero_snoc | x: . l: List. list_el( ;x;l)  rank_fn(x;snoc(x;l)) = 0 |
| THM | ranked_cons | x,y: . l: List. ranked(x;y::l)   x = y ranked(x;l) |
| COM | sci_misc_rank_2 | ---- sci_rank: Pid versions of theorems needed(?) for rank |
| THM | rank_0_snoc_pid | x:PId. l:PId List.
rank_fn(x;l) = 0  ( l':PId List. l = snoc(x;l')) |
| THM | rank_1_snoc_pid | x:PId. l:PId List.
rank_fn(x;l) = 1  ( y:PId. l':PId List. l = snoc(y;snoc(x;l'))) |
| THM | rank_filter_hd_pid | p,q:PId. l:PId List.
ranked(q;l)
 rank_fn(p;l) = ||l|| - 1
 rank_fn(q;l) = ||l|| - 2
 rank_fn(q;filter( x. (x = p);l))
= ||filter( x. (x = p);l)|| - 1 |
| THM | rank_fn_two_filter_pid | p,q,r:PId. l:PId List.
ranked(q;l)
 (p = r)
 (p = q)
 rank_fn(p;l) = rank_fn(q;l) + 1
 rank_fn(r;l) = rank_fn(p;l) + 1
 rank_fn(r;filter( x. (x = p);l))
= rank_fn(q;filter( x. (x = p);l)) + 1 |
| THM | first_occ_1_filter_pid | y:PId. l:PId List. ||filter( x.(x = y);first_occurrences(l))|| 1 |
| ML | rank_simpset1 | map ((simpset_add `rank`) o lemma_simp)
``rank_fn_nil ranked_cons``;;
|
| COM | sci_misc_rank_6 | ---- sci_rank: hasrank Rewrites -------------------------- |
| THM | hasrank_hreceive_freshq_same_rw | s:state. p:PId.
next_mesg(m;s.h) = read_cache_freshQ(p::[])
 status-p_ = Pending
 list_el(mesg;read_cache_freshQ(p::[]);but_last_el(buf[m]_))
 list_el(mesg;read_cache_goneQ(p::[]);buf[m]_)
 next_he(m;s.h).src = p
 (hasrank([h<-(hreceive(m;h)::h)] s;p)   True) |
| THM | hasrank_hreceive_goneq_same_rw | s:state. p:PId.
next_mesg(m;s.h) = read_cache_goneQ(p::[])
 status-p_ = Pending
 list_el(mesg;read_cache_goneQ(p::[]);but_last_el(buf[m]_))
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
 next_he(m;s.h).src = p
 (hasrank([h<-(hreceive(m;h)::h)] s;p)   True) |
| COM | sci_misc_rank_9 | ---- sci_rank: One-Directional Rank Comparison Lemmas----- |
| THM | rank_succ_two_invalid | s:state. p,q,r:PId.
status-q_ = Delright status-q_ = Delleft
 hasrank(s;r)
 rank(s;p) = rank(s;q) + 1
 rank(s;q) = rank(s;r) + 1
 rank(csq:=invalid{} s;p) = rank(csq:=invalid{} s;r) + 1 |
| THM | rank_succ_two_off | s:state. p,q,r:PId.
hasrank(s;r)
 rank(s;p) = rank(s;q) + 1
 rank(s;q) = rank(s;r) + 1
 rank(statusq:=Off s;p) = rank(statusq:=Off s;r) + 1 |
| COM | sci_misc_rank_10 | ---- sci_rank: Rank Zero Lemmas -------------------------- |
| THM | rank_zero_off_diff | s:state. p,q:PId.
hasrank(s;q)
 (p = q)
 rank(s;q) = 0
 rank(statusp:=Off s;q) = 0 |
| THM | rank_zero_delleftr_diff | s:state. p,q,p':PId.
hasrank(s;q)
 (p = q)
 rank(s;q) = 0
 rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)] s;q) = 0 |
| THM | rank_zero_query_diff | s:state. q:PId.
hasrank(s;q)
 next_mesg(m;s.h) = read_cache_freshQ(next_he(m;s.h).src::[])
next_mesg(m;s.h) = read_cache_goneQ(next_he(m;s.h).src::[])
 (next_he(m;s.h).src = q)
 rank(s;q) = 0
 rank([h<-(hreceive(m;h)::h)] s;q) = 0 |
| THM | rank_zero_one_delleftr | s:state. p,q,p':PId.
status-p_ = Delleft
 rank(s;p) = 0
 rank(s;q) = 1
 rank([h<-(hsend(p';p;delleftR(p'::ok{}::[]))::h)] s;q) = 0 |
| THM | rank_zero_one_invalid | s:state. p,q:PId.
status-p_ = Delleft
 rank(s;p) = 0
 rank(s;q) = 1
 rank(csp:=invalid{} s;q) = 0 |
| THM | rank_zero_one_invalid_del | s:state. p,q:PId.
status-p_ = Delright status-p_ = Delleft
 rank(s;p) = 0
 rank(s;q) = 1
 rank(csp:=invalid{} s;q) = 0 |
| THM | rank_zero_one_off | s:state. p,q:PId.
rank(s;p) = 0  rank(s;q) = 1  rank(statusp:=Off s;q) = 0 |
| COM | sci_misc_rank_11 | ---- Maxrank Lemmas -------------------------------------- |
| THM | maxrank_hreceive_freshq_rw | n: . s:state. p:PId.
next_mesg(m;s.h) = read_cache_freshQ(p::[])
 status-p_ = Pending
 list_el(mesg;read_cache_freshQ(p::[]);but_last_el(buf[m]_))
 list_el(mesg;read_cache_goneQ(p::[]);buf[m]_)
 next_he(m;s.h).src = p
 (maxrank(n;[h<-(hreceive(m;h)::h)] s;p)   True) |
| THM | maxrank_hreceive_goneq_rw | n: . s:state. p:PId.
next_mesg(m;s.h) = read_cache_goneQ(p::[])
 status-p_ = Pending
 list_el(mesg;read_cache_goneQ(p::[]);but_last_el(buf[m]_))
 list_el(mesg;read_cache_freshQ(p::[]);buf[m]_)
 next_he(m;s.h).src = p
 (maxrank(n;[h<-(hreceive(m;h)::h)] s;p)   True) |
| COM | sci_misc_inv9b_5 | ---- sci_inv9b: Some consequences introduced by Amy ------ |
| THM | next_mesg_only_response | n:
inv{}(sci_program{}(n);
s.( p,msgR: . args,args': List.
response(msgR)
 next_mesg(p;s.h) = msgR(args)
 list_el(mesg;msgR(args');but_last_el(buf[p]_)))) |
| COM | sci_misc_inv_rw_12 | ---- sci_inv_rw: NonInterference Theorems for Staying ---- |
| THM | staying_ni_m1 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( q:P. staying(action_m1{} s;q)   staying(s;q)) |
| THM | staying_ni_m2 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( q:P. staying(action_m2{} s;q)   staying(s;q)) |
| THM | staying_ni_m3 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( q:P. staying(action_m3{} s;q)   staying(s;q)) |
| THM | staying_ni_m4 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( q:P. staying(action_m4{} s;q)   staying(s;q)) |
| THM | staying_ni_p1 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p,q:P. staying(action_p1{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p2 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p,q:P. staying(action_p2{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p3 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId.
(p = q)  (staying(action_p3{}(p) s;q)   staying(s;q))) |
| THM | staying_ni_p4 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId.
(p = q)  (staying(action_p4{}(p) s;q)   staying(s;q))) |
| THM | staying_ni_p5 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p5{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p6 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId.
(p = q)  (staying(action_p6{}(p) s;q)   staying(s;q))) |
| THM | staying_ni_p7 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p7{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p8 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p8{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p9 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p9{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p13 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p13{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p14 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p14{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p15 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p15{}(p) s;q)   staying(s;q)) |
| THM | staying_ni_p16 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId.
(p = q)  (staying(action_p16{}(p) s;q)   staying(s;q))) |
| THM | staying_ni_p17 | n: . s:state.
in_exec{}(sci_program{}(n); s)
 ( p:P. q:PId. staying(action_p17{}(p) s;q)   staying(s;q)) |
| ML | sci_staying_ni_simpset | map ((simpset_add `sci_staying_ni`) o lemma_simp)
``staying_ni_m1 staying_ni_m2 staying_ni_m3 staying_ni_m4
staying_ni_p1 staying_ni_p2 staying_ni_p5 staying_ni_p7
staying_ni_p8 staying_ni_p9 staying_ni_p13 staying_ni_p14
staying_ni_p15 staying_ni_p17`` ;;
map (simpset_add `sci_visiting_ni`)
[lemma_cond_simp `staying_ni_p3` [Trivial ORELSE DiffBufferPids];
lemma_cond_simp `staying_ni_p4` [Trivial ORELSE DiffBufferPids];
lemma_cond_simp `staying_ni_p6` [Trivial ORELSE DiffBufferPids];
lemma_cond_simp `visiting_ni_p16` [Trivial ORELSE DiffBufferPids]
] ;; |