source: src/Clight/Cexec.ma @ 871

include "utilities/extralib.ma".
include "common/IO.ma".
include "common/SmallstepExec.ma".
include "Clight/Csem.ma".

(*
include "Plogic/russell_support.ma".

definition P_to_P_option_res : ∀A:Type[0].∀P:A → CProp[0].option (res A) → CProp[0] ≝
  λA,P,a.match a with [ None ⇒ False | Some y ⇒ match y return λ_.CProp[0] with [ Error ⇒ True | OK z ⇒ P z ]].

definition err_inject : ∀A.∀P:A → Prop.∀a:option (res A).∀p:P_to_P_option_res A P a.res (Sig A P) ≝ 
  λA.λP:A → Prop.λa:option (res A).λp:P_to_P_option_res A P a. 
  (match a return λa'.a=a' → res (Sig A P) with
   [ None ⇒ λe1.?
   | Some b ⇒ λe1.(match b return λb'.b=b' → ? with
     [ Error ⇒ λ_. Error ?
     | OK c ⇒ λe2. OK ? (dp A P c ?)
     ]) (refl ? b)
   ]) (refl ? a).
[ >e1 in p; normalize; *;
| >e1 in p >e2 normalize; //
] qed.

definition err_eject : ∀A.∀P: A → Prop. res (Sig A P) → res A ≝ 
  λA,P,a.match a with [ Error m ⇒ Error ? m | OK b ⇒
    match b with [ dp w p ⇒ OK ? w] ].

definition sig_eject : ∀A.∀P: A → Prop. Sig A P → A ≝ 
  λA,P,a.match a with [ dp w p ⇒ w].

coercion err_inject : 
  ∀A.∀P:A → Prop.∀a.∀p:P_to_P_option_res ? P a.res (Sig A P) ≝ err_inject 
  on a:option (res ?) to res (Sig ? ?).
coercion err_eject : ∀A.∀P:A → Prop.∀c:res (Sig A P).res A ≝ err_eject 
  on _c:res (Sig ? ?) to res ?.
coercion sig_eject : ∀A.∀P:A → Prop.∀c:Sig A P.A ≝ sig_eject 
  on _c:Sig ? ? to ?.
*)
definition P_res: ∀A.∀P:A → Prop.res A → Prop ≝
  λA,P,a. match a with [ Error _ ⇒ True | OK v ⇒ P v ].

axiom TypeMismatch : String.
axiom ValueIsNotABoolean : String.

definition exec_bool_of_val : ∀v:val. ∀ty:type. res bool ≝
  λv,ty. match v in val with
  [ Vint i ⇒ match ty with
    [ Tint _ _ ⇒ OK ? (¬eq i zero)
    | _ ⇒ Error ? (msg TypeMismatch)
    ]
  | Vfloat f ⇒ match ty with
    [ Tfloat _ ⇒ OK ? (¬Fcmp Ceq f Fzero)
    | _ ⇒ Error ? (msg TypeMismatch)
    ]
  | Vptr _ _ _ _ ⇒ match ty with
    [ Tpointer _ _ ⇒ OK ? true
    | _ ⇒ Error ? (msg TypeMismatch)
    ]
  | Vnull _ ⇒ match ty with
    [ Tpointer _ _ ⇒ OK ? false
    | _ ⇒ Error ? (msg TypeMismatch)
    ]
  | _ ⇒ Error ? (msg ValueIsNotABoolean)
  ].

lemma bool_of_val_complete : ∀v,ty,r. bool_of_val v ty r → ∃b. r = of_bool b ∧ exec_bool_of_val v ty = OK ? b.
#v #ty #r #H elim H; #v #t #H' elim H';
  [ #i #is #s #ne %{ true} % //; whd in ⊢ (??%?); >(eq_false … ne) //;
  | #r #b #pc #i #i0 #s %{ true} % //
  | #f #s #ne %{ true} % //; whd in ⊢ (??%?); >(Feq_zero_false … ne) //;
  | #i #s %{ false} % //;
  | #r #r' #t %{ false} % //;
  | #s %{ false} % //; whd in ⊢ (??%?); >(Feq_zero_true …) //;
  ]
qed.

(* Prove a few minor results to make proof obligations easy. *)

lemma bind_OK: ∀A,B,P,e,f.
  (∀v. e = OK A v → match f v with [ Error _ ⇒ True | OK v' ⇒ P v' ]) →
  match bind A B e f with [ Error _ ⇒ True | OK v ⇒ P v ].
#A #B #P #e #f elim e; /2/; qed.

lemma sig_bind_OK: ∀A,B. ∀P:A → Prop. ∀P':B → Prop. ∀e:res (Sig A P). ∀f:Sig A P → res B.
  (∀v:A. ∀p:P v. match f (dp A P v p) with [ Error _ ⇒ True | OK v' ⇒ P' v'] ) →
  match bind (Sig A P) B e f with [ Error _ ⇒ True | OK v' ⇒ P' v' ].
#A #B #P #P' #e #f elim e;
[ #v0 elim v0; #v #Hv #IH @IH
| #m #_ @I
] qed.

lemma bind2_OK: ∀A,B,C,P,e,f.
  (∀v1,v2. e = OK ? 〈v1,v2〉 → match f v1 v2 with [ Error _ ⇒ True | OK v' ⇒ P v' ]) →
  match bind2 A B C e f with [ Error _ ⇒ True | OK v ⇒ P v ].
#A #B #C #P #e #f elim e; //; #v cases v; /2/; qed.

lemma opt_bind_OK: ∀A,B,P,m,e,f.
  (∀v. e = Some A v → match f v with [ Error _ ⇒ True | OK v' ⇒ P v' ]) →
  match bind A B (opt_to_res A m e) f with [ Error _ ⇒ True | OK v ⇒ P v ].
#A #B #P #m #e #f elim e; normalize; /2/; qed.


axiom BadCast : String. (* TODO: refine into more precise errors? *)

definition try_cast_null : ∀m:mem. ∀i:int. ∀ty:type. ∀ty':type. res val  ≝
λm:mem. λi:int. λty:type. λty':type.
match eq i zero with
[ true ⇒
  match ty with
  [ Tint _ _ ⇒
    match ty' with
    [ Tpointer r _ ⇒ OK ? (Vnull r)
    | Tarray r _ _ ⇒ OK ? (Vnull r)
    | Tfunction _ _ ⇒ OK ? (Vnull Code)
    | _ ⇒ Error ? (msg BadCast)
    ]
  | _ ⇒ Error ? (msg BadCast)
  ]
| false ⇒ Error ? (msg BadCast)
].

definition exec_cast : ∀m:mem. ∀v:val. ∀ty:type. ∀ty':type. res val ≝
λm:mem. λv:val. λty:type. λty':type.
match v with
[ Vint i ⇒
  match ty with
  [ Tint sz1 si1 ⇒
    match ty' with
    [ Tint sz2 si2 ⇒ OK ? (Vint (cast_int_int sz2 si2 i))
    | Tfloat sz2 ⇒ OK ? (Vfloat (cast_float_float sz2 (cast_int_float si1 i)))
    | Tpointer _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
    | Tarray _ _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
    | Tfunction _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
    | _ ⇒ Error ? (msg BadCast)
    ]
  | Tpointer _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
  | Tarray _ _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
  | Tfunction _ _ ⇒ do r ← try_cast_null m i ty ty'; OK val r
  | _ ⇒ Error ? (msg TypeMismatch)
  ]
| Vfloat f ⇒
  match ty with
  [ Tfloat sz ⇒
    match ty' with
    [ Tint sz' si' ⇒ OK ? (Vint (cast_int_int sz' si' (cast_float_int si' f)))
    | Tfloat sz' ⇒ OK ? (Vfloat (cast_float_float sz' f))
    | _ ⇒ Error ? (msg BadCast)
    ]
  | _ ⇒ Error ? (msg TypeMismatch)
  ]
| Vptr r b _ ofs ⇒
    do s ← match ty with [ Tpointer s _ ⇒ OK ? s | Tarray s _ _ ⇒ OK ? s | Tfunction _ _ ⇒ OK ? Code | _ ⇒ Error ? (msg TypeMismatch) ];
    do u ← match eq_region_dec r s with [ inl _ ⇒ OK ? it | inr _ ⇒ Error ? (msg BadCast) ];
    do s' ← match ty' with
         [ Tpointer s _ ⇒ OK ? s | Tarray s _ _ ⇒ OK ? s | Tfunction _ _ ⇒ OK ? Code
         | _ ⇒ Error ? (msg BadCast)];
    match pointer_compat_dec b s' with
    [ inl p' ⇒ OK ? (Vptr s' b p' ofs)
    | inr _ ⇒ Error ? (msg BadCast)
    ]
| Vnull r ⇒
    do s ← match ty with [ Tpointer s _ ⇒ OK ? s | Tarray s _ _ ⇒ OK ? s | Tfunction _ _ ⇒ OK ? Code | _ ⇒ Error ? (msg TypeMismatch) ];
    do u ← match eq_region_dec r s with [ inl _ ⇒ OK ? it | inr _ ⇒ Error ? (msg BadCast) ];
    do s' ← match ty' with
         [ Tpointer s _ ⇒ OK ? s | Tarray s _ _ ⇒ OK ? s | Tfunction _ _ ⇒ OK ? Code
         | _ ⇒ Error ? (msg BadCast) ];
    OK ? (Vnull s')
| _ ⇒ Error ? (msg BadCast)
].

definition load_value_of_type' ≝
λty,m,l. match l with [ pair loc ofs ⇒ load_value_of_type ty m loc ofs ].

(* To make the evaluation of bare lvalue expressions invoke exec_lvalue with
   a structurally smaller value, we break out the surrounding Expr constructor
   and use exec_lvalue'. *)

axiom BadlyTypedTerm : String.
axiom UnknownIdentifier : String.
axiom BadLvalueTerm : String.
axiom FailedLoad : String.
axiom FailedOp : String.

let rec exec_expr (ge:genv) (en:env) (m:mem) (e:expr) on e : res (val×trace) ≝
match e with
[ Expr e' ty ⇒
  match e' with
  [ Econst_int i ⇒ OK ? 〈Vint i, E0〉
  | Econst_float f ⇒ OK ? 〈Vfloat f, E0〉
  | Evar _ ⇒
      do 〈l,tr〉 ← exec_lvalue' ge en m e' ty;
      do v ← opt_to_res ? (msg FailedLoad) (load_value_of_type' ty m l);
      OK ? 〈v,tr〉
  | Ederef _ ⇒
      do 〈l,tr〉 ← exec_lvalue' ge en m e' ty;
      do v ← opt_to_res ? (msg FailedLoad) (load_value_of_type' ty m l);
      OK ? 〈v,tr〉
  | Efield _ _ ⇒
      do 〈l,tr〉 ← exec_lvalue' ge en m e' ty;
      do v ← opt_to_res ? (msg FailedLoad) (load_value_of_type' ty m l);
      OK ? 〈v,tr〉
  | Eaddrof a ⇒
      do 〈lo,tr〉 ← exec_lvalue ge en m a;
      match ty with
      [ Tpointer r _ ⇒
        match lo with [ pair loc ofs ⇒ 
          match pointer_compat_dec loc r with
          [ inl pc ⇒ OK ? 〈Vptr r loc pc ofs, tr〉
          | inr _ ⇒ Error ? (msg TypeMismatch)
          ]
        ]
      | _ ⇒ Error ? (msg BadlyTypedTerm)
      ]
  | Esizeof ty' ⇒ OK ? 〈Vint (repr (sizeof ty')), E0〉
  | Eunop op a ⇒
      do 〈v1,tr〉 ← exec_expr ge en m a;
      do v ← opt_to_res ? (msg FailedOp) (sem_unary_operation op v1 (typeof a));
      OK ? 〈v,tr〉
  | Ebinop op a1 a2 ⇒
      do 〈v1,tr1〉 ← exec_expr ge en m a1;
      do 〈v2,tr2〉 ← exec_expr ge en m a2;
      do v ← opt_to_res ? (msg FailedOp) (sem_binary_operation op v1 (typeof a1) v2 (typeof a2) m);
      OK ? 〈v,tr1⧺tr2〉
  | Econdition a1 a2 a3 ⇒
      do 〈v,tr1〉 ← exec_expr ge en m a1;
      do b ← exec_bool_of_val v (typeof a1);
      do 〈v',tr2〉 ← match b return λ_.res (val×trace) with
                 [ true ⇒ (exec_expr ge en m a2)
                 | false ⇒ (exec_expr ge en m a3) ];
      OK ? 〈v',tr1⧺tr2〉
(*      if b then exec_expr ge en m a2 else exec_expr ge en m a3)*)
  | Eorbool a1 a2 ⇒
      do 〈v1,tr1〉 ← exec_expr ge en m a1;
      do b1 ← exec_bool_of_val v1 (typeof a1);
      match b1 return λ_.res (val×trace) with [ true ⇒ OK ? 〈Vtrue,tr1〉 | false ⇒
        do 〈v2,tr2〉 ← exec_expr ge en m a2;
        do b2 ← exec_bool_of_val v2 (typeof a2);
        OK ? 〈of_bool b2, tr1⧺tr2〉 ]
  | Eandbool a1 a2 ⇒
      do 〈v1,tr1〉 ← exec_expr ge en m a1;
      do b1 ← exec_bool_of_val v1 (typeof a1);
      match b1 return λ_.res (val×trace) with [ true ⇒
        do 〈v2,tr2〉 ← exec_expr ge en m a2;
        do b2 ← exec_bool_of_val v2 (typeof a2);
        OK ? 〈of_bool b2, tr1⧺tr2〉
      | false ⇒ OK ? 〈Vfalse,tr1〉 ]
  | Ecast ty' a ⇒
      do 〈v,tr〉 ← exec_expr ge en m a;
      do v' ← exec_cast m v (typeof a) ty';
      OK ? 〈v',tr〉
  | Ecost l a ⇒
      do 〈v,tr〉 ← exec_expr ge en m a;
      OK ? 〈v,tr⧺(Echarge l)〉
  ]
]
and exec_lvalue' (ge:genv) (en:env) (m:mem) (e':expr_descr) (ty:type) on e' : res (block × offset × trace) ≝
  match e' with
  [ Evar id ⇒ 
      match (get … id en) with
      [ None ⇒ do l ← opt_to_res ? [MSG UnknownIdentifier; CTX ? id] (find_symbol ? ? ge id); OK ? 〈〈l,zero_offset〉,E0〉 (* global *)
      | Some loc ⇒ OK ? 〈〈loc,zero_offset〉,E0〉 (* local *)
      ]
  | Ederef a ⇒
      do 〈v,tr〉 ← exec_expr ge en m a;
      match v with
      [ Vptr _ l _ ofs ⇒ OK ? 〈〈l,ofs〉,tr〉
      | _ ⇒ Error ? (msg TypeMismatch)
      ]
  | Efield a i ⇒
      match (typeof a) with
      [ Tstruct id fList ⇒
          do 〈lofs,tr〉 ← exec_lvalue ge en m a;
          do delta ← field_offset i fList;
          OK ? 〈〈\fst lofs,shift_offset (\snd lofs) (repr delta)〉,tr〉
      | Tunion id fList ⇒
          do 〈lofs,tr〉 ← exec_lvalue ge en m a;
          OK ? 〈lofs,tr〉
      | _ ⇒ Error ? (msg BadlyTypedTerm)
      ]
  | _ ⇒ Error ? (msg BadLvalueTerm)
  ]
and exec_lvalue (ge:genv) (en:env) (m:mem) (e:expr) on e : res (block × offset × trace) ≝
match e with [ Expr e' ty ⇒ exec_lvalue' ge en m e' ty ].

lemma P_res_to_P: ∀A,P,e,v.  P_res A P e → e = OK A v → P v.
#A #P #e #v #H1 #H2 >H2 in H1; whd in ⊢ (% → ?); //; qed.

(* We define a special induction principle tailored to the recursive definition
   above. *)

definition is_not_lvalue: expr_descr → Prop ≝
λe. match e with [ Evar _ ⇒ False | Ederef _ ⇒ False | Efield _ _ ⇒ False | _ ⇒ True ].

definition Plvalue ≝ λP:(expr → Prop).λe,ty.
match e return λ_.Prop with [ Evar _ ⇒ P (Expr e ty) | Ederef _ ⇒ P (Expr e ty) | Efield _ _ ⇒ P (Expr e ty) | _ ⇒ True ].

(* TODO: Can we do this sensibly with a map combinator? *)
let rec exec_exprlist (ge:genv) (e:env) (m:mem) (l:list expr) on l : res (list val×trace) ≝
match l with
[ nil ⇒ OK ? 〈nil val, E0〉
| cons e1 es ⇒
  do 〈v,tr1〉 ← exec_expr ge e m e1;
  do 〈vs,tr2〉 ← exec_exprlist ge e m es;
  OK ? 〈cons val v vs, tr1⧺tr2〉
].

let rec exec_alloc_variables (en:env) (m:mem) (l:list (ident × type)) on l : env × mem ≝
match l with
[ nil ⇒ 〈en, m〉
| cons h vars ⇒
  match h with [ pair id ty ⇒
    match alloc m 0 (sizeof ty) Any with [ pair m1 b1 ⇒
      exec_alloc_variables (set … id b1 en) m1 vars
]]].

axiom WrongNumberOfParameters : String.
axiom FailedStore : String.

(* TODO: can we establish that length params = length vs in advance? *)
let rec exec_bind_parameters (e:env) (m:mem) (params:list (ident × type)) (vs:list val) on params : res mem ≝
  match params with
  [ nil ⇒ match vs with [ nil ⇒ OK ? m | cons _ _ ⇒ Error ? (msg WrongNumberOfParameters) ]
  | cons idty params' ⇒ match idty with [ pair id ty ⇒
      match vs with
      [ nil ⇒ Error ? (msg WrongNumberOfParameters)
      | cons v1 vl ⇒
          do b ← opt_to_res ? [MSG UnknownIdentifier; CTX ? id] (get … id e);
          do m1 ← opt_to_res ? [MSG FailedStore; CTX ? id] (store_value_of_type ty m b zero_offset v1);
          exec_bind_parameters e m1 params' vl
      ]
  ] ].

definition sz_eq_dec : ∀s1,s2:intsize. (s1 = s2) + (s1 ≠ s2).
#s1 cases s1; #s2 cases s2; /2/; %2 ; % #H destruct; qed.
definition sg_eq_dec : ∀s1,s2:signedness. (s1 = s2) + (s1 ≠ s2).
#s1 cases s1; #s2 cases s2; /2/; %2 ; % #H destruct; qed.
definition fs_eq_dec : ∀s1,s2:floatsize. (s1 = s2) + (s1 ≠ s2).
#s1 cases s1; #s2 cases s2; /2/; %2 ; % #H destruct; qed.

definition eq_nat_dec : ∀n,m:nat. Sum (n=m) (n≠m).
#n #m lapply (refl ? (eqb n m)) cases (eqb n m) in ⊢ (???% → ?) #E
[ %1 | %2 ] @(eqb_elim … E) // #_ #H destruct qed. 

let rec type_eq_dec (t1,t2:type) : Sum (t1 = t2) (t1 ≠ t2) ≝
match t1 return λt'. (t' = t2) + (t' ≠ t2) with
[ Tvoid ⇒ match t2 return λt'. (Tvoid = t') + (Tvoid ≠ t') with [ Tvoid ⇒ inl ?? (refl ??) | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tint sz sg ⇒ match t2 return λt'. (Tint ?? = t') + (Tint ?? ≠ t')  with [ Tint sz' sg' ⇒
    match sz_eq_dec sz sz' with [ inl e1 ⇒
    match sg_eq_dec sg sg' with [ inl e2 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tfloat f ⇒ match t2 return λt'. (Tfloat ? = t') + (Tfloat ? ≠ t')  with [ Tfloat f' ⇒
    match fs_eq_dec f f' with [ inl e1 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tpointer s t ⇒ match t2 return λt'. (Tpointer ?? = t') + (Tpointer ?? ≠ t')  with [ Tpointer s' t' ⇒
    match eq_region_dec s s' with [ inl e1 ⇒
      match type_eq_dec t t' with [ inl e2 ⇒ inl ??? 
      | inr e2 ⇒ inr ?? (nmk ? (λH.match e2 with [ nmk e' ⇒ e' ? ])) ] 
    | inr e1 ⇒ inr ?? (nmk ? (λH.match e1 with [ nmk e' ⇒ e' ? ])) ] | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tarray s t n ⇒ match t2 return λt'. (Tarray ??? = t') + (Tarray ??? ≠ t')  with [ Tarray s' t' n' ⇒
    match eq_region_dec s s' with [ inl e1 ⇒
      match type_eq_dec t t' with [ inl e2 ⇒
        match eq_nat_dec n n' with [ inl e3 ⇒ inl ???
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
        | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tfunction tl t ⇒ match t2 return λt'. (Tfunction ?? = t') + (Tfunction ?? ≠ t')  with [ Tfunction tl' t' ⇒
    match typelist_eq_dec tl tl' with [ inl e1 ⇒ 
    match type_eq_dec t t' with [ inl e2 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
  | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tstruct i fl ⇒
    match t2 return λt'. (Tstruct ?? = t') + (Tstruct ?? ≠ t')  with [ Tstruct i' fl' ⇒
    match ident_eq i i' with [ inl e1 ⇒
    match fieldlist_eq_dec fl fl' with [ inl e2 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tunion i fl ⇒
    match t2 return λt'. (Tunion ?? = t') + (Tunion ?? ≠ t')  with [ Tunion i' fl' ⇒
    match ident_eq i i' with [ inl e1 ⇒
    match fieldlist_eq_dec fl fl' with [ inl e2 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    |  _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tcomp_ptr r i ⇒ match t2 return λt'. (Tcomp_ptr ? ? = t') + (Tcomp_ptr ? ? ≠ t')  with [ Tcomp_ptr r' i' ⇒ 
    match eq_region_dec r r' with [ inl e1 ⇒
      match ident_eq i i' with [ inl e2 ⇒ inl ???
      | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | _ ⇒ inr ?? (nmk ? (λH.?)) ]
]
and typelist_eq_dec (tl1,tl2:typelist) : (tl1 = tl2) + (tl1 ≠ tl2) ≝
match tl1 return λtl'. (tl' = tl2) + (tl' ≠ tl2) with
[ Tnil ⇒ match tl2 return λtl'. (Tnil = tl') + (Tnil ≠ tl') with [ Tnil ⇒ inl ?? (refl ??) | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Tcons t1 ts1 ⇒ match tl2 return λtl'. (Tcons ?? = tl') + (Tcons ?? ≠ tl') with [ Tnil ⇒ inr ?? (nmk ? (λH.?)) | Tcons t2 ts2 ⇒ 
    match type_eq_dec t1 t2 with [ inl e1 ⇒
    match typelist_eq_dec ts1 ts2 with [ inl e2 ⇒ inl ???
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
    | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ] ]
]
and fieldlist_eq_dec (fl1,fl2:fieldlist) : (fl1 = fl2) + (fl1 ≠ fl2) ≝
match fl1 return λfl'. (fl' = fl2) + (fl' ≠ fl2) with
[ Fnil ⇒ match fl2 return λfl'. (Fnil = fl') + (Fnil ≠ fl') with [ Fnil ⇒ inl ?? (refl ??) | _ ⇒ inr ?? (nmk ? (λH.?)) ]
| Fcons i1 t1 fs1 ⇒ match fl2 return λfl'. (Fcons ??? = fl') + (Fcons ??? ≠ fl') with [ Fnil ⇒ inr ?? (nmk ? (λH.?)) | Fcons i2 t2 fs2 ⇒ 
    match ident_eq i1 i2 with [ inl e1 ⇒
      match type_eq_dec t1 t2 with [ inl e2 ⇒
        match fieldlist_eq_dec fs1 fs2 with [ inl e3 ⇒ inl ???
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ]
        | inr e ⇒ inr ?? (nmk ? (λH.match e with [ nmk e' ⇒ e' ? ])) ] ]
]. destruct; //; qed.

definition assert_type_eq : ∀t1,t2:type. res (t1 = t2) ≝
λt1,t2. match type_eq_dec t1 t2 with [ inl p ⇒ OK ? p | inr _ ⇒ Error ? (msg TypeMismatch)].

let rec is_is_call_cont (k:cont) : Sum (is_call_cont k) (Not (is_call_cont k)) ≝
match k return λk'.(is_call_cont k') + (¬is_call_cont k') with
[ Kstop ⇒ ?
| Kcall _ _ _ _ ⇒ ?
| _ ⇒ ?
]. 
[ 1,8: %1 ; //
| *: %2 ; /2/
] qed.

definition is_Sskip : ∀s:statement. (s = Sskip) + (s ≠ Sskip) ≝
λs.match s return λs'.(s' = Sskip) + (s' ≠ Sskip) with
[ Sskip ⇒ inl ?? (refl ??)
| _ ⇒ inr ?? (nmk ? (λH.?))
]. destruct
qed.


(* execution *)

definition store_value_of_type' ≝
λty,m,l,v.
match l with [ pair loc ofs ⇒
  store_value_of_type ty m loc ofs v ].

axiom NonsenseState : String.
axiom ReturnMismatch : String.
axiom UnknownLabel : String.
axiom BadFunctionValue : String.

let rec exec_step (ge:genv) (st:state) on st : (IO io_out io_in (trace × state)) ≝
match st with
[ State f s k e m ⇒
  match s with
  [ Sassign a1 a2 ⇒
    ! 〈l,tr1〉 ← exec_lvalue ge e m a1;
    ! 〈v2,tr2〉 ← exec_expr ge e m a2;
    ! m' ← opt_to_io … (msg FailedStore) (store_value_of_type' (typeof a1) m l v2);
    ret ? 〈tr1⧺tr2, State f Sskip k e m'〉
  | Scall lhs a al ⇒
    ! 〈vf,tr2〉 ← exec_expr ge e m a;
    ! 〈vargs,tr3〉 ← exec_exprlist ge e m al;
    ! fd ← opt_to_io … (msg BadFunctionValue) (find_funct ? ? ge vf);
    ! p ← err_to_io … (assert_type_eq (type_of_fundef fd) (fun_typeof a));
(* requires associativity of IOMonad, so rearrange it below
    ! k' ← match lhs with
         [ None ⇒ ret ? (Kcall (None ?) f e k)
         | Some lhs' ⇒
           ! locofs ← exec_lvalue ge e m lhs';
           ret ? (Kcall (Some ? 〈locofs, typeof lhs'〉) f e k)
         ];
    ret ? 〈E0, Callstate fd vargs k' m〉)
*)
    match lhs with
         [ None ⇒ ret ? 〈tr2⧺tr3, Callstate fd vargs (Kcall (None ?) f e k) m〉
         | Some lhs' ⇒
           ! 〈locofs,tr1〉 ← exec_lvalue ge e m lhs';
           ret ? 〈tr1⧺tr2⧺tr3, Callstate fd vargs (Kcall (Some ? 〈locofs, typeof lhs'〉) f e k) m〉
         ]
  | Ssequence s1 s2 ⇒ ret ? 〈E0, State f s1 (Kseq s2 k) e m〉
  | Sskip ⇒
      match k with
      [ Kseq s k' ⇒ ret ? 〈E0, State  f s k' e m〉
      | Kstop ⇒
          match fn_return f with
          [ Tvoid ⇒ ret ? 〈E0, Returnstate Vundef k (free_list m (blocks_of_env e))〉
          | _ ⇒ Wrong ??? (msg NonsenseState)
          ]
      | Kcall _ _ _ _ ⇒
          match fn_return f with
          [ Tvoid ⇒ ret ? 〈E0, Returnstate Vundef k (free_list m (blocks_of_env e))〉
          | _ ⇒ Wrong ??? (msg NonsenseState)
          ]
      | Kwhile a s' k' ⇒ ret ? 〈E0, State f (Swhile a s') k' e m〉
      | Kdowhile a s' k' ⇒
          ! 〈v,tr〉 ← exec_expr ge e m a;
          ! b ← err_to_io … (exec_bool_of_val v (typeof a));
          match b with
          [ true ⇒ ret ? 〈tr, State f (Sdowhile a s') k' e m〉
          | false ⇒ ret ? 〈tr, State f Sskip k' e m〉
          ]
      | Kfor2 a2 a3 s' k' ⇒ ret ? 〈E0, State f a3 (Kfor3 a2 a3 s' k') e m〉
      | Kfor3 a2 a3 s' k' ⇒ ret ? 〈E0, State f (Sfor Sskip a2 a3 s') k' e m〉
      | Kswitch k' ⇒ ret ? 〈E0, State f Sskip k' e m〉
      | _ ⇒ Wrong ??? (msg NonsenseState)
      ]
  | Scontinue ⇒
      match k with
      [ Kseq s' k' ⇒ ret ? 〈E0, State f Scontinue k' e m〉
      | Kwhile a s' k' ⇒ ret ? 〈E0, State f (Swhile a s') k' e m〉
      | Kdowhile a s' k' ⇒ 
          ! 〈v,tr〉 ← exec_expr ge e m a;
          ! b ← err_to_io … (exec_bool_of_val v (typeof a));
          match b with
          [ true ⇒ ret ? 〈tr, State f (Sdowhile a s') k' e m〉
          | false ⇒ ret ? 〈tr, State f Sskip k' e m〉
          ]
      | Kfor2 a2 a3 s' k' ⇒ ret ? 〈E0, State f a3 (Kfor3 a2 a3 s' k') e m〉
      | Kswitch k' ⇒ ret ? 〈E0, State f Scontinue k' e m〉
      | _ ⇒ Wrong ??? (msg NonsenseState)
      ]
  | Sbreak ⇒
      match k with
      [ Kseq s' k' ⇒ ret ? 〈E0, State f Sbreak k' e m〉
      | Kwhile a s' k' ⇒ ret ? 〈E0, State f Sskip k' e m〉
      | Kdowhile a s' k' ⇒ ret ? 〈E0, State f Sskip k' e m〉
      | Kfor2 a2 a3 s' k' ⇒ ret ? 〈E0, State f Sskip k' e m〉
      | Kswitch k' ⇒ ret ? 〈E0, State f Sskip k' e m〉
      | _ ⇒ Wrong ??? (msg NonsenseState)
      ]
  | Sifthenelse a s1 s2 ⇒ 
      ! 〈v,tr〉 ← exec_expr ge e m a;
      ! b ← err_to_io … (exec_bool_of_val v (typeof a));
      ret ? 〈tr, State f (if b then s1 else s2) k e m〉
  | Swhile a s' ⇒ 
      ! 〈v,tr〉 ← exec_expr ge e m a;
      ! b ← err_to_io … (exec_bool_of_val v (typeof a));
      ret ? 〈tr, if b then State f s' (Kwhile a s' k) e m
                      else State f Sskip k e m〉
  | Sdowhile a s' ⇒ ret ? 〈E0, State f s' (Kdowhile a s' k) e m〉
  | Sfor a1 a2 a3 s' ⇒
      match is_Sskip a1 with
      [ inl _ ⇒ 
          ! 〈v,tr〉 ← exec_expr ge e m a2;
          ! b ← err_to_io … (exec_bool_of_val v (typeof a2));
          ret ? 〈tr, State f (if b then s' else Sskip) (if b then (Kfor2 a2 a3 s' k) else k) e m〉
      | inr _ ⇒ ret ? 〈E0, State f a1 (Kseq (Sfor Sskip a2 a3 s') k) e m〉
      ]
  | Sreturn a_opt ⇒
    match a_opt with
    [ None ⇒ match fn_return f with
      [ Tvoid ⇒ ret ? 〈E0, Returnstate Vundef (call_cont k) (free_list m (blocks_of_env e))〉
      | _ ⇒ Wrong ??? (msg ReturnMismatch)
      ]
    | Some a ⇒ 
        match type_eq_dec (fn_return f) Tvoid with
        [ inl _ ⇒ Wrong ??? (msg ReturnMismatch)
        | inr _ ⇒
          ! 〈v,tr〉 ← exec_expr ge e m a;
          ret ? 〈tr, Returnstate v (call_cont k) (free_list m (blocks_of_env e))〉
        ]
    ]
  | Sswitch a sl ⇒ 
      ! 〈v,tr〉 ← exec_expr ge e m a;
      match v with [ Vint n ⇒ ret ? 〈tr, State f (seq_of_labeled_statement (select_switch n sl)) (Kswitch k) e m〉
                   | _ ⇒ Wrong ??? (msg TypeMismatch)]
  | Slabel lbl s' ⇒ ret ? 〈E0, State f s' k e m〉
  | Sgoto lbl ⇒
      match find_label lbl (fn_body f) (call_cont k) with
      [ Some sk' ⇒ match sk' with [ pair s' k' ⇒ ret ? 〈E0, State f s' k' e m〉 ]
      | None ⇒ Wrong ??? [MSG UnknownLabel; CTX ? lbl]
      ]
  | Scost lbl s' ⇒ ret ? 〈Echarge lbl, State f s' k e m〉
  ]
| Callstate f0 vargs k m ⇒
  match f0 with
  [ CL_Internal f ⇒ 
    match exec_alloc_variables empty_env m ((fn_params f) @ (fn_vars f)) with [ pair e m1 ⇒
      ! m2 ← exec_bind_parameters e m1 (fn_params f) vargs;
      ret ? 〈E0, State f (fn_body f) k e m2〉
    ]
  | CL_External f argtys retty ⇒ 
      ! evargs ← check_eventval_list vargs (typlist_of_typelist argtys);
      ! evres ← do_io f evargs (proj_sig_res (signature_of_type argtys retty));
      ret ? 〈Eextcall f evargs (mk_eventval ? evres), Returnstate (mk_val ? evres) k m〉
  ]
| Returnstate res k m ⇒
  match k with
  [ Kcall r f e k' ⇒
    match r with
    [ None ⇒ ret ? 〈E0, (State f Sskip k' e m)〉
    | Some r' ⇒
      match r' with [ pair l ty ⇒
          ! m' ← opt_to_io … (msg FailedStore) (store_value_of_type' ty m l res);
          ret ? 〈E0, (State f Sskip k' e m')〉
      ]
    ]
  | _ ⇒ Wrong ??? (msg NonsenseState)
  ]
].

axiom MainMissing : String.

let rec make_initial_state (p:clight_program) : res (genv × state) ≝
  do ge ← globalenv Genv ?? p;
  do m0 ← init_mem Genv ?? p;
  do b ← opt_to_res ? (msg MainMissing) (find_symbol ? ? ge (prog_main ?? p));
  do f ← opt_to_res ? (msg MainMissing) (find_funct_ptr ? ? ge b);
  OK ? 〈ge,Callstate f (nil ?) Kstop m0〉.

let rec is_final (s:state) : option int ≝
match s with
[ Returnstate res k m ⇒
  match k with
  [ Kstop ⇒
    match res with
    [ Vint r ⇒ Some ? r
    | _ ⇒ None ?
    ]
  | _ ⇒ None ?
  ]
| _ ⇒ None ?
].

definition is_final_state : ∀st:state. (Sig ? (final_state st)) + (¬∃r. final_state st r).
#st elim st;
[ #f #s #k #e #m %2 ; % *; #r #H inversion H; #i #m #e destruct;
| #f #l #k #m %2 ; % *; #r #H inversion H; #i #m #e destruct;
| #v #k #m cases k; 
  [ cases v;
    [ 2: #i %1 ; %{ i} //;
    | 1: %2 ; % *;   #r #H inversion H; #i #m #e destruct;
    | #f %2 ; % *;   #r #H inversion H; #i #m #e destruct;
    | #r %2 ; % *;   #r #H inversion H; #i #m #e destruct;
    | #r #b #pc #of %2 ; % *;   #r #H inversion H; #i #m #e destruct;
    ]
  | #a #b %2 ; % *; #r #H inversion H; #i #m #e destruct;
  | 3,4: #a #b #c %2 ; % *; #r #H inversion H; #i #m #e destruct;
  | 5,6,8: #a #b #c #d %2 ; % *; #r #H inversion H; #i #m #e destruct;
  | #a %2 ; % *; #r #H inversion H; #i #m #e destruct;
  ]
] qed.

let rec exec_steps (n:nat) (ge:genv) (s:state) :
 IO io_out io_in (trace×state) ≝
match is_final_state s with
[ inl _ ⇒ ret ? 〈E0, s〉
| inr _ ⇒
  match n with
  [ O ⇒ ret ? 〈E0, s〉
  | S n' ⇒
      ! 〈t,s'〉 ← exec_step ge s;
(*      ! 〈t,s'〉 ← match s with
                 [ State f s k e m ⇒ match m with [ mk_mem c n p ⇒ exec_step ge (State f s k e (mk_mem c n p)) ]
                 | Callstate fd args k m ⇒ match m with [ mk_mem c n p ⇒ exec_step ge (Callstate fd args k (mk_mem c n p)) ]
                 | Returnstate r k m ⇒ match m with [ mk_mem c n p ⇒ exec_step ge (Returnstate r k (mk_mem c n p)) ]
                 ] ;*)
      ! 〈t',s''〉 ← match s' with
                 [ State f s k e m ⇒ match m with [ mk_mem c n p ⇒ exec_steps n' ge (State f s k e (mk_mem c n p)) ]
                 | Callstate fd args k m ⇒ match m with [ mk_mem c n p ⇒ exec_steps n' ge (Callstate fd args k (mk_mem c n p)) ]
                 | Returnstate r k m ⇒ match m with [ mk_mem c n p ⇒ exec_steps n' ge (Returnstate r k (mk_mem c n p)) ]
                 ] ;
(*      ! 〈t',s''〉 ← exec_steps n' ge s';*)
      ret ? 〈t ⧺ t',s''〉
  ]
].

definition mem_of_state : state → mem ≝
λs.match s with [ State f s k e m ⇒ m | Callstate f a k m ⇒ m | Returnstate r k m ⇒ m ].

definition clight_exec : execstep io_out io_in ≝
  mk_execstep … is_final mem_of_state exec_step.

definition clight_fullexec : fullexec io_out io_in ≝
  mk_fullexec ?? clight_exec ? make_initial_state.