Theory Pid_Scheduler

theory Pid_Scheduler
imports Gen_Scheduler_Refine Partial_Order_Reduction.Transition_System_Extensions

  lemma system_complete_language_eq_lsystem_accept:
    fixes ex en init int
    defines "S   g_V = UNIV, g_E = rel_of_enex (en, ex), g_V0 = {init}, sa_L = int "
    assumes "sa S"
    shows "snth ` transition_system_complete.language ex (λ a p. a  en p) (λ p. p = init) int = {w. sa.accept S w}"
  proof -
    interpret jsys?: transition_system_complete ex "λ a p. a  en p" "λ p. p = init" int by this
    interpret psys?: sa S by fact
    show ?thesis
    unfolding jsys.language_def
    unfolding psys.accept_def
    proof safe
      fix p w
      assume 1: "run w init"
      show " r. is_run r  snth (smap int (init ## trace w init)) = L  r"
      unfolding is_run_def ipath_def
      unfolding S_def graph_rec.simps sa_rec.simps
      unfolding rel_of_enex_def Let_def
      proof (intro allI exI conjI)
        fix i
        show "(init ## trace w init) !! 0  {init}" by simp
        show "snth (smap int (init ## trace w init)) = int  snth (init ## trace w init)"
          by (metis (full_types) fun_comp_eq_conv smap_alt)
        have 10: "w = stake i w @- [w !! i] @- sdrop (Suc i) w" using id_stake_snth_sdrop by auto
        have 20: "run (stake i w @- [w !! i] @- sdrop (Suc i) w) init" using 1 10 by simp
        have 1: "w !! i  en (target (stake i w) init)" using 20 by auto
        have 2: "ex (w !! i) (target (stake i w) init) = target (stake (Suc i) w) init"
          using 20 unfolding stake_Suc by auto
        show "((init ## trace w init) !! i, (init ## trace w init) !! Suc i) 
          {(s, ex a s) |s a. a  en s}" using 1 2 by force
      fix r
      assume 1: "is_run r"
      obtain w where 2: "r 0 = init" " i. w i  en (r i)" " i. r (Suc i) = ex (w i) (r i)"
        using 1
        unfolding is_run_def ipath_def
        unfolding S_def graph_rec.simps
        unfolding rel_of_enex_def Let_def
        by simp metis
      have 3: "L  r = snth (smap int (smap r nats))" unfolding assms(1) by auto
      have 4: "(init ## trace (smap w nats) init) !! i = smap r nats !! i" for i
        using 2 by (induct i) (auto)
      have 5: "smap r nats = init ## trace (smap w nats) init" using eqI_snth 4 by metis
      have 6: "target (stake k (smap w nats)) init = smap r nats !! k" for k
        unfolding sscan_scons_snth 5 by rule
      have 7: "run (smap w nats) init" using 2(2) 6 by (auto intro: snth_run)
      show "L  r  (!!) ` {smap int (p ## trace w p) |p w. p = init  run w p}"
        unfolding 3 using 5 7 by force

  (* TODO: Move *)  
  lemma prod_splitE:
    assumes "a b. p=(a,b)  P a b"
    obtains a b where "p=(a,b)" "P a b"
    using assms
    by (cases p) auto

  lemma sngp_sym_conv: "(λp. p=x) = (=) x" by auto  

  lemma in_multiset_of_conv_nth: "x ∈# mset l  (i<length l. x = l!i)"
    by (metis in_multiset_in_set in_set_conv_nth)
  lemma multiset_of_em_conv_nth: "mset l = {#x#} + m' 
     (i<length l. x = l!i  m' = mset l - {#x#})"
    by (metis add_diff_cancel_left' in_multiset_of_conv_nth 
      insert_DiffM multi_member_this)

  type_synonym pid = nat
  record ('c,'ls,'gs) pid_global_config =
    processes :: "('c,'ls) local_config list"  
    state :: 'gs

  definition pidgc_α 
    :: "('c,'ls,'gs) pid_global_config  ('c,'ls,'gs) global_config" where
    "pidgc_α pgc       
      global_config.processes = mset (pid_global_config.processes pgc),
      global_config.state = pid_global_config.state pgc

  abbreviation pid_valid :: "('c,'ls,'gs) pid_global_config  pid  bool" 
    "pid_valid gc pid  pid < length (pid_global_config.processes gc)"
  abbreviation "lc_of_pid gc pid 
     pid_global_config.processes gc ! pid"
  abbreviation "cmd_of_pid gc pid 
     local_config.command (lc_of_pid gc pid)"
  abbreviation "ls_of_pid gc pid 
     local_config.state (lc_of_pid gc pid)"

  context Gen_Scheduler'

    definition pid_gstep_succ 
      :: "('c,'ls,'gs) pid_global_config  ('c,'ls,'gs) pid_global_config set" 
      "pid_gstep_succ gc  do {
        ― ‹ Select process ›
        let lcs = pid_global_config.processes gc;
        pid  {0..<length lcs};
        let lc = lcs!pid;
        ― ‹ Focus state ›
        let gs = pid_global_config.state gc;
        let ls = local_config.state lc;
        ― ‹ Select action ›
        let cmd = local_config.command lc;
        (a,cmd')  {(a,cmd'). cstep cmd a cmd'};
        if en (ls,gs) a then {do { 
          ― ‹ Execute ›
          let (ls,gs) = ex (ls,gs) a;
          ― ‹ Unfocus state. ›
          let lc =  local_config.command = cmd', local_config.state = ls;
            pid_global_config.processes = lcs[pid:=lc],
            pid_global_config.state = gs  
      else {}

    lemma pid_gstep_succE:
      assumes "gc'  pid_gstep_succ gc"
      obtains pid a c' ls' gs' where
        "pid_valid gc pid"
        "cstep (cmd_of_pid gc pid) a c'"
        "en (ls_of_pid gc pid, pid_global_config.state gc) a"
        "ex (ls_of_pid gc pid, pid_global_config.state gc) a = (ls',gs')"
        "gc' =  
          pid_global_config.processes = (pid_global_config.processes gc)
            [pid := 
               local_config.command = c', local_config.state = ls'
          pid_global_config.state = gs'"
      using assms
      unfolding pid_gstep_succ_def
      by (auto 
        split: if_split_asm prod.splits 
        elim!: prod_splitE
        simp: all_conj_distrib)

  lemma pid_gstep_succI:
      "pid_valid gc pid"
      "cstep (cmd_of_pid gc pid) a c'"
      "en (ls_of_pid gc pid, pid_global_config.state gc) a"
      "ex (ls_of_pid gc pid, pid_global_config.state gc) a = (ls',gs')"
    shows "
        pid_global_config.processes = (pid_global_config.processes gc)
          [pid := 
             local_config.command = c', local_config.state = ls'
        pid_global_config.state = gs'
        pid_gstep_succ gc"
    using assms
    unfolding pid_gstep_succ_def
    by fastforce

  lemma pid_gc_state_eq: 
    "pid_global_config.state pgc = global_config.state (pidgc_α pgc)"
    unfolding pidgc_α_def by auto  
  lemma pid_gc_proc_eq:
    assumes "pid_valid gc pid"  
    shows "
      global_config.processes (pidgc_α gc) 
      = {#lc_of_pid gc pid#} 
      + (global_config.processes (pidgc_α gc) - {#lc_of_pid gc pid#})"
    using assms
    by (auto simp: pidgc_α_def multiset_of_em_conv_nth)

  lemma pid_gstep_correct: 
    "gstep_succ (pidgc_α pgc) = pidgc_α`pid_gstep_succ pgc"
    apply safe
    apply (erule gstep_succE)
    apply (clarsimp simp: pidgc_α_def multiset_of_em_conv_nth)
    apply (frule (3) pid_gstep_succI)
    apply (erule image_eqI[rotated])
    apply (auto simp: pidgc_α_def mset_update add_ac union_mset_add_mset_right) []

    apply (erule pid_gstep_succE)
    apply (clarsimp simp: pidgc_α_def mset_update)
    apply (simp add: pid_gc_state_eq)
    apply (frule (2) gstep_succI[rotated])
    apply (rule pid_gc_proc_eq, assumption)
    apply (auto simp: add_ac pidgc_α_def union_mset_add_mset_left) []

  abbreviation "pid_gstep  rel_of_succ pid_gstep_succ"
  definition "pid_step  stutter_extend_edges UNIV pid_gstep"


locale Pid_Gen_Scheduler_linit = 
  Gen_Scheduler'_linit cstep en ex init label
  for cstep :: "'c  'a  'c  bool"
  and en :: "('ls×'gs)  'a  bool"
  and ex :: "('ls×'gs)  'a  ('ls×'gs)"
  and init :: "('c,'ls,'gs) global_config set"
  and label :: "('c,'ls,'gs) global_config  'l" +
  fixes pid_init :: "('c,'ls,'gs) pid_global_config"
  and pid_label :: "('c,'ls,'gs) pid_global_config  'l"
  assumes pid_init_eq: "gc  init  (gc=pidgc_α pid_init)"
  assumes pid_label_eq: "label (pidgc_α pgc) = pid_label pgc"

  definition pid_system_automaton' :: "(('c,'ls,'gs) pid_global_config, 'l) sa_rec"
    where "pid_system_automaton' 
       g_V = UNIV, g_E = pid_gstep, g_V0 = {pid_init}, sa_L = pid_label "

  lemma pid_system_automaton'_simps[simp]:
    "g_V pid_system_automaton' = UNIV"
    "g_E pid_system_automaton' = pid_gstep"
    "g_V0 pid_system_automaton' = {pid_init}"
    "sa_L pid_system_automaton' = pid_label"
    unfolding pid_system_automaton'_def by auto

  definition pid_system_automaton :: "(('c,'ls,'gs) pid_global_config, 'l) sa_rec"
    where "pid_system_automaton 
       g_V = UNIV, g_E = pid_step, g_V0 = {pid_init}, sa_L = pid_label "

  lemma pid_system_automaton_simps[simp]:
    "g_V pid_system_automaton = UNIV"
    "g_E pid_system_automaton = pid_step"
    "g_V0 pid_system_automaton = {pid_init}"
    "sa_L pid_system_automaton = pid_label"
    unfolding pid_system_automaton_def by auto

  lemma pid_system_automaton_alt_def: "pid_system_automaton = stutter_extend pid_system_automaton'"
    unfolding pid_step_def pid_system_automaton'_def pid_system_automaton_def stutter_extend_def
    by simp

  sublocale pid': sa pid_system_automaton' by unfold_locales auto
  sublocale pid: sa pid_system_automaton
    unfolding pid_system_automaton_alt_def using pid'.stutter_extend_sa by this

  sublocale bisim: lbisimulation "br pidgc_α (λ_. True)" pid_system_automaton system_automaton
  proof -
    interpret bisim: lbisimulation "br pidgc_α (λ_. True)" pid_system_automaton' system_automaton'
      apply unfold_locales
      apply (auto simp: build_rel_def pid_init_eq pid_gstep_correct pid_label_eq)
    interpret bisim: lbisimulation "br pidgc_α (λ_. True)" pid_system_automaton system_automaton
      unfolding system_automaton_alt_def pid_system_automaton_alt_def
      using bisim.lstutter_extend by this
    show "lbisimulation (br pidgc_α (λ _. True)) pid_system_automaton system_automaton"
      by unfold_locales

  lemma pid_accept_eq: "pid.accept = sa.accept" by (rule bisim.accept_bisim)

  lemma pid_run_conv: "sa.g.is_run r  (r'. r=pidgc_α o r'  pid.g.is_run r')"
    by (rule bisim.br_run_conv[OF refl])   

  lemma pid_run_sim: "pid.g.is_run r  sa.g.is_run (pidgc_α o r)"
    by (rule bisim.s1.br_run_sim[OF refl])

section "Global Actions"

text ‹
  A global action consists of a PID and a control flow graph edge
type_synonym (in -) ('c,'a) global_action = "pid × 'c × 'a × 'c"

abbreviation (in -) "fs_of_pid gc pid  (ls_of_pid gc pid,pid_global_config.state gc)"

  definition ga_gen 
    :: "('c,'ls,'gs) pid_global_config  ('c,'a) global_action set"
    "ga_gen gc  { (pid,c,a,c') .
      cstep c a c' 
     pid_valid gc pid 
     c=cmd_of_pid gc pid
     en (fs_of_pid gc pid) a }"

  definition ga_gex
    :: "('c,'a) global_action  ('c,'ls,'gs) pid_global_config  ('c,'ls,'gs) pid_global_config"
    "ga_gex ga gc  let 
      (pid,c,a,c') = ga;
      fs = fs_of_pid gc pid;
      (ls',gs') = ex fs a;
      gc' =  
          pid_global_config.processes = (pid_global_config.processes gc)
            [pid := 
               local_config.command = c', local_config.state = ls'
          pid_global_config.state = gs'

  definition "ga_gstep  rel_of_enex (ga_gen,ga_gex)"
  definition "ga_en  stutter_extend_en ga_gen"
  definition "ga_ex  stutter_extend_ex ga_gex"
  definition "ga_step  stutter_extend_edges UNIV ga_gstep"
  lemma ga_step_alt: "ga_step = rel_of_enex (ga_en,ga_ex)"
    unfolding ga_step_def ga_gstep_def ga_en_def ga_ex_def
    by (auto simp: stutter_extend_pred_of_enex_conv)

  lemma some_ga_en_eq: 
    "Some a  ga_en gc  a  ga_gen gc"
    by (auto simp: ga_en_def)
  lemma some_ga_ex_eq: 
    "ga_ex (Some a) gc = ga_gex a gc"
    "ga_ex  Some = ga_gex"
    by (auto simp: ga_ex_def intro!: ext)
  lemma none_ga_en_eq: "None  ga_en gc  ga_gen gc = {}"
    by (auto simp: ga_en_def stutter_extend_en_def)
  lemma ga_ex_none[simp]: "ga_ex None = id"   
    by (auto simp: ga_ex_def)

  lemma ga_gstep_eq: "ga_gstep = pid_gstep"
    apply safe
    apply (auto 
      simp: ga_gstep_def ga_gen_def ga_gex_def 
      split: prod.splits elim!: prod_splitE
      intro: pid_gstep_succI) []
    apply (fastforce 
      simp: pred_of_succ_def ga_gstep_def ga_gen_def ga_gex_def
      split: prod.splits
      elim!: pid_gstep_succE)

  lemma ga_step_eq: "ga_step = pid_step" 
    unfolding ga_step_def pid_step_def ga_gstep_eq by rule

  definition ga_automaton :: "(('c,'ls,'gs) pid_global_config, 'l) sa_rec"
    where "ga_automaton   g_V = UNIV, g_E = ga_step, g_V0 = {pid_init}, sa_L = pid_label "

  lemma ga_automaton_simps[simp]:
    "g_V ga_automaton = UNIV"
    "g_E ga_automaton = ga_step"
    "g_V0 ga_automaton = {pid_init}"
    "sa_L ga_automaton = pid_label"
    unfolding ga_automaton_def by simp+

  lemma ga_pid_system_automaton: "ga_automaton = pid_system_automaton"
    unfolding ga_automaton_def pid_system_automaton_def ga_step_eq by rule

  sublocale jsys: transition_system ga_ex "λ a p. a  ga_en p" .
  sublocale ga: sa ga_automaton unfolding ga_pid_system_automaton by unfold_locales

  sublocale ga_bisim: lbisimulation Id ga_automaton pid_system_automaton
    unfolding ga_pid_system_automaton by auto

  lemma ga_accept_eq: "ga.accept = sa.accept" 
    by (simp add: ga_bisim.accept_bisim pid_accept_eq) 

  lemma ga_run_eq: "pid.g.is_run r = ga.is_run r"
    using ga_bisim.br_run_conv[of id "λ_. True" r]
    by (auto simp: build_rel_def[abs_def])

  sublocale jsys: transition_system_initial ga_ex "λ a p. a  ga_en p" "λ p. p = pid_init" . 

  lemma reachable_alt: "jsys.nodes = ga.E* `` ga.V0"
  proof safe
    fix gc
    assume "gc  jsys.nodes"
    thus "gc  ga.E* `` ga.V0"
      unfolding ga_automaton_def ga_step_alt rel_of_enex_def
      by (induct, auto intro: rtrancl_into_rtrancl)
    fix gc gc'
    assume "(gc, gc')  ga.E*" "gc  ga.V0"
    thus "gc'  jsys.nodes" unfolding ga_automaton_def ga_step_alt by induct auto

  lemma rtrancl_step_exec_word_conv:  
    "(gc, gc')  ga_step*  (w. jsys.path w gc  gc' = w gc)"
  proof safe
    assume "(gc, gc')  ga_step*"
    thus " w. jsys.path w gc  gc' = w gc"
      apply induction
      apply force
      apply (force simp: ga_step_alt pred_of_enex_def)
    fix w
    assume "jsys.path w gc"
    thus "(gc, w gc)  ga_step*"
      apply induction
      apply (auto simp: ga_step_alt rel_of_enex_def
        intro: converse_rtrancl_into_rtrancl)

  sublocale jsys: transition_system_complete ga_ex "λ a p. a  ga_en p" "λ p. p = pid_init" pid_label .

  lemma accept_eq_lang: "snth ` jsys.language = Collect sa.accept"
    unfolding ga_accept_eq[symmetric]
    unfolding ga_automaton_def
    unfolding ga_step_alt
    apply (rule system_complete_language_eq_lsystem_accept)
    unfolding ga_step_alt[symmetric]
    unfolding ga_automaton_def[symmetric]
    by unfold_locales