Require Import String.
Require Import List.
Require Import Compare_dec.
Require Import Program.
Require Import Utils.
Require Import DataSystem.
Require Import NRA.
Require Import NRASugar.
Require Import NRAExt.
Require Import TNRA.
Import ListNotations.
Local Open Scope list_scope.
Section TNRAUtil.
Context {
m:
basic_model}.
Context (τ
constants:
tbindings).
Local Open Scope nra_scope.
Lemma ATdot {
p s τ
c τ
in τ
pf τ
out} :
p ▷ τ
in >=>
Rec Closed τ
pf ⊣ τ
c ->
tdot τ
s =
Some τ
out ->
NRAUnop (
OpDot s)
p ▷ τ
in >=> τ
out ⊣ τ
c.
Proof.
intros.
repeat econstructor; eauto.
Qed.
Lemma ATdot_inv {
p s τ
c τ
in τ
out}:
NRAUnop (
OpDot s)
p ▷ τ
in >=> τ
out ⊣ τ
c ->
exists τ
pf k,
p ▷ τ
in >=>
Rec k τ
pf ⊣ τ
c /\
tdot τ
s =
Some τ
out.
Proof.
inversion 1; subst.
inversion H2; subst.
repeat econstructor; eauto.
Qed.
Auxiliary lemmas specific to some of the NRA expressions used in
the translation
Definition nra_context_type tbind tpid :
rtype :=
Rec Closed (("
PBIND"%
string,
tbind) :: ("
PDATA"%
string,
tpid) ::
nil) (
eq_refl _).
Lemma ATnra_data τ
c τ τ
in :
nra_data ▷
nra_context_type τ τ
in >=> τ
in ⊣ τ
c.
Proof.
eapply ATdot.
-
econstructor.
-
reflexivity.
Qed.
Lemma ATnra_data_inv'
k τ
c τ τ
in pf τ
out:
nra_data ▷
Rec k [("
PBIND"%
string, τ); ("
PDATA"%
string, τ
in)]
pf >=> τ
out ⊣ τ
c ->
τ
in = τ
out.
Proof.
unfold nra_data.
intros H.
inversion H;
clear H;
subst.
inversion H2;
clear H2;
subst.
inversion H5;
clear H5;
subst.
destruct τ';
inversion H3;
clear H3;
subst.
destruct τ';
inversion H4;
clear H4;
subst.
destruct τ';
inversion H6;
clear H6;
subst.
rtype_equalizer.
subst.
destruct p;
destruct p0;
simpl in *;
subst.
inversion H0;
trivial.
Qed.
Lemma ATnra_data_inv τ
c τ τ
in τ
out:
nra_data ▷
nra_context_type τ τ
in >=> τ
out ⊣ τ
c ->
τ
in = τ
out.
Proof.
Local Hint Constructors nra_type unary_op_type binary_op_type :
qcert.
Local Hint Resolve ATdot ATnra_data :
qcert.
Lemma ATunnest_two (
s1 s2:
string) (
op:
NRA.nra) τ
c τ
in τ₁
pf1 τ
s τ
rem pf2 :
op ▷ τ
in >=> (
Coll (
Rec Closed τ₁
pf1)) ⊣ τ
c ->
tdot τ₁
s1 =
Some (
Coll τ
s) ->
τ
rem = (
rremove (
rec_concat_sort τ₁ ((
s2,τ
s)::
nil))
s1) ->
unnest_two s1 s2 op ▷
τ
in >=>
Coll (
Rec Closed τ
rem pf2) ⊣ τ
c.
Proof.
intros;
subst.
econstructor;
qeauto.
Unshelve.
qeauto.
unfold rec_concat_sort.
qeauto.
Qed.
Lemma ATRecEither s τ
c τ
l τ
r pf1 pf2:
nra_type τ
c (
NRARecEither s) (
Either τ
l τ
r)
(
Either
(
Rec Closed ((
s,τ
l)::
nil)
pf1)
(
Rec Closed ((
s,τ
r)::
nil)
pf2)).
Proof.
econstructor; qeauto.
Qed.
Ltac nra_inverter :=
match goal with
| [
H:
Coll _ =
Coll _ |-
_] =>
inversion H;
clear H
| [
H: `?τ₁ =
Coll₀ (`?τ₂) |-
_] =>
rewrite (
Coll_right_inv τ₁ τ₂)
in H;
subst
| [
H:
Coll₀ (`?τ₂) = `?τ₁ |-
_] =>
symmetry in H
| [
H:@
nra_type _ _ NRAID _ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAMap _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAMapProduct _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAEither _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAEitherConcat _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRARecEither _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRADefault _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAApp _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAProduct _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRASelect _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAUnop _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRABinop _ _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAConst _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
nra_data)
_ _ |-
_ ] =>
apply ATnra_data_inv'
in H
| [
H:@
nra_type _ _ (
nra_data) (
nra_context_type _ _)
_ |-
_ ] =>
apply ATnra_data_inv in H
| [
H: (
_,
_) = (
_,
_) |-
_ ] =>
inversion H;
clear H
| [
H:
map (
fun x2 :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x2, ` (
snd x2))) ?
x0 = [] |-
_] =>
apply (
map_rtype_nil x0)
in H;
simpl in H;
subst
| [
H: (
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_)
=
(
map
(
fun x' :
string * {τ₀' :
rtype₀ |
wf_rtype₀ τ₀' =
true} =>
(
fst x',
proj1_sig (
snd x')))
_) |-
_ ] =>
apply map_rtype_fequal in H;
trivial
| [
H:
Rec _ _ _ =
Rec _ _ _ |-
_ ] =>
generalize (
Rec_inv H);
clear H;
intro H;
try subst
| [
H:
context [(
_::
nil) =
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_] |-
_] =>
symmetry in H
| [
H:
context [
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_ = (
_::
_) ] |-
_] =>
apply map_eq_cons in H;
destruct H as [? [? [? [??]]]]
| [
H:
Coll₀
_ =
Coll₀
_ |-
_ ] =>
inversion H;
clear H
| [
H:
Rec₀
_ _ =
Rec₀
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:
nra_type _ _ (
snd ?
x)
_ |-
_] =>
destruct x;
simpl in *;
subst
| [
H:
unary_op_type OpBag _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpFlatten _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpRec _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpDot _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpRecRemove _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpRight _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpLeft _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
binary_op_type OpRecConcat _ _ _ |-
_ ] =>
inversion H;
clear H
| [
H:
binary_op_type OpAnd _ _ _ |-
_ ] =>
inversion H;
clear H
| [
H:
binary_op_type OpRecMerge _ _ _ |-
_ ] =>
inversion H;
clear H
end;
try rtype_equalizer;
try assumption;
try subst;
simpl in *;
try nra_inverter.
Lemma ATunnest_two_inv (
s1 s2:
string) (
op:
NRA.nra) τ
c τ
in rec :
unnest_two s1 s2 op ▷
τ
in >=>
Coll rec ⊣ τ
c ->
exists τ₁
pf1 τ
s τ
rem pf2,
op ▷ τ
in >=> (
Coll (
Rec Closed τ₁
pf1)) ⊣ τ
c /\
tdot τ₁
s1 =
Some (
Coll τ
s) /\
rec = (
Rec Closed τ
rem pf2) /\
τ
rem = (
rremove (
rec_concat_sort τ₁ ((
s2,τ
s)::
nil))
s1).
Proof.
unfold unnest_two.
intros H.
inversion H;
clear H;
intros.
nra_inverter.
destruct x;
simpl in *.
repeat eexists;
intuition;
eauto.
Qed.
End TNRAUtil.
Ltac nra_inverter :=
match goal with
| [
H:
Coll _ =
Coll _ |-
_] =>
inversion H;
clear H
| [
H: `?τ₁ =
Coll₀ (`?τ₂) |-
_] =>
rewrite (
Coll_right_inv τ₁ τ₂)
in H;
subst
| [
H:
Coll₀ (`?τ₂) = `?τ₁ |-
_] =>
symmetry in H
| [
H:@
nra_type _ _ NRAID _ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAMap _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAMapProduct _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAEither _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAEitherConcat _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRARecEither _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRADefault _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAApp _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAProduct _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRASelect _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAUnop _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRABinop _ _ _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
NRAConst _)
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:@
nra_type _ _ (
nra_data)
_ _ |-
_ ] =>
apply ATnra_data_inv'
in H
| [
H:@
nra_type _ _ (
nra_data) (
nra_context_type _ _)
_ |-
_ ] =>
apply ATnra_data_inv in H
| [
H: (
_,
_) = (
_,
_) |-
_ ] =>
inversion H;
clear H
| [
H:
map (
fun x2 :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x2, ` (
snd x2))) ?
x0 = [] |-
_] =>
apply (
map_rtype_nil x0)
in H;
simpl in H;
subst
| [
H: (
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_)
=
(
map
(
fun x' :
string * {τ₀' :
rtype₀ |
wf_rtype₀ τ₀' =
true} =>
(
fst x',
proj1_sig (
snd x')))
_) |-
_ ] =>
apply map_rtype_fequal in H;
trivial
| [
H:
Rec _ _ _ =
Rec _ _ _ |-
_ ] =>
generalize (
Rec_inv H);
clear H;
intro H;
try subst
| [
H:
context [(
_::
nil) =
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_] |-
_] =>
symmetry in H
| [
H:
context [
map
(
fun x :
string * {τ₀ :
rtype₀ |
wf_rtype₀ τ₀ =
true} =>
(
fst x,
proj1_sig (
snd x)))
_ = (
_::
_) ] |-
_] =>
apply map_eq_cons in H;
destruct H as [? [? [? [??]]]]
| [
H:
Coll₀
_ =
Coll₀
_ |-
_ ] =>
inversion H;
clear H
| [
H:
Rec₀
_ _ =
Rec₀
_ _ |-
_ ] =>
inversion H;
clear H
| [
H:
nra_type _ _ (
snd ?
x)
_ |-
_] =>
destruct x;
simpl in *;
subst
| [
H:
unary_op_type OpBag _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpFlatten _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpRec _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpDot _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type (
OpRecRemove _)
_ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpRight _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
unary_op_type OpLeft _ _ |-
_ ] =>
inversion H;
clear H;
subst
| [
H:
binary_op_type OpRecConcat _ _ _ |-
_ ] =>
inversion H;
clear H
| [
H:
binary_op_type OpAnd _ _ _ |-
_ ] =>
inversion H;
clear H
| [
H:
binary_op_type OpRecMerge _ _ _ |-
_ ] =>
inversion H;
clear H
end;
try rtype_equalizer;
try assumption;
try subst;
simpl in *;
try nra_inverter.