Module Qcert.NRA.Typing.TNRAEq
Require
Import
Equivalence
.
Require
Import
Morphisms
.
Require
Import
Setoid
.
Require
Import
EquivDec
.
Require
Import
Program
.
Require
Import
List
.
Require
Import
String
.
Require
Import
DataSystem
.
Require
Import
NRA
.
Require
Import
NRAEq
.
Require
Import
TNRA
.
Section
TNRAEq
.
Local
Open
Scope
nra_scope
.
Context
{
m
:
basic_model
}.
Definition
typed_nra
τ
c
τ
in
τ
out
:= {
op
:
nra
|
op
▷ τ
in
>=> τ
out
⊣ τ
c
}.
Definition
tnra_eq
{τ
c
} {τ
in
τ
out
} (
op1
op2
:
typed_nra
τ
c
τ
in
τ
out
) :
Prop
:=
forall
(
x
:
data
)
c
(
dt_x
:
x
▹ τ
in
)
(
dt_c
:
bindings_type
c
τ
c
),
brand_relation_brands
⊢ (
proj1_sig
op1
) @ₐ
x
⊣
c
=
brand_relation_brands
⊢ (
proj1_sig
op2
) @ₐ
x
⊣
c
.
Global
Instance
tnra_equiv
{τ
c
} {τ
in
τ
out
:
rtype
} :
Equivalence
(@
tnra_eq
τ
c
τ
in
τ
out
).
Proof.
constructor
.
-
unfold
Reflexive
,
tnra_eq
.
intros
;
reflexivity
.
-
unfold
Symmetric
,
tnra_eq
.
intros
;
rewrite
(
H
x0
c
dt_x
dt_c
);
reflexivity
.
-
unfold
Transitive
,
tnra_eq
.
intros
;
rewrite
(
H
x0
c
dt_x
dt_c
);
rewrite
(
H0
x0
c
dt_x
dt_c
);
reflexivity
.
Qed.
Notation
"
t1
⇝
t2
⊣ τ
c
" := (
typed_nra
τ
c
t1
t2
) (
at
level
80) :
nra_scope
.
Notation
"
X
≡τ
Y
" := (
tnra_eq
X
Y
) (
at
level
80) :
nra_scope
.
Local
Hint
Resolve
data_type_normalized
:
qcert
.
Local
Hint
Resolve
bindings_type_Forall_normalized
:
qcert
.
Lemma
nra_eq_impl_tnra_eq
{τ
c
} {τ
in
τ
out
} (
op1
op2
: τ
in
⇝ τ
out
⊣ τ
c
) :
`
op1
≡ₐ `
op2
->
op1
≡τ
op2
.
Proof.
unfold
tnra_eq
,
nra_eq
;
intros
.
eapply
H
;
eauto
with
qcert
.
Qed.
Lemma
nra_eq_pf_irrel
{
op
} {τ
c
} {τ
in
τ
out
} (
pf1
pf2
:
op
▷ τ
in
>=> τ
out
⊣ τ
c
) :
tnra_eq
(
exist
_
_
pf1
) (
exist
_
_
pf2
).
Proof.
red
;
intros
;
simpl
.
reflexivity
.
Qed.
Definition
tnra_rewrites_to
{τ
c
} {τ
in
τ
out
} (
op1
op2
:
nra
) :
Prop
:=
op1
▷ τ
in
>=> τ
out
⊣ τ
c
->
(
op2
▷ τ
in
>=> τ
out
⊣ τ
c
) /\ (
forall
(
x
:
data
)
c
(
dt_x
:
x
▹ τ
in
)
(
dt_c
:
bindings_type
c
τ
c
),
brand_relation_brands
⊢
op1
@ₐ
x
⊣
c
=
brand_relation_brands
⊢
op2
@ₐ
x
⊣
c
).
Notation
"
A
↦ₐ
B
⊣
C
⊧
op1
⇒
op2
" := (@
tnra_rewrites_to
C
A
B
op1
op2
) (
at
level
80) :
nra_scope
.
Lemma
rewrites_typed_and_untyped
{τ
c
} {τ
in
τ
out
} (
op1
op2
:
nra
):
(
op1
▷ τ
in
>=> τ
out
⊣ τ
c
->
op2
▷ τ
in
>=> τ
out
⊣ τ
c
) ->
op1
≡ₐ
op2
-> τ
in
↦ₐ τ
out
⊣ τ
c
⊧
op1
⇒
op2
.
Proof.
intros
.
unfold
tnra_rewrites_to
;
simpl
;
intros
.
split
;
eauto
with
qcert
.
Qed.
Lemma
tnra_rewrites_eq_is_typed_eq
{τ
c
} {τ
in
τ
out
:
rtype
} (
op1
op2
:
typed_nra
τ
c
τ
in
τ
out
):
(τ
in
↦ₐ τ
out
⊣ τ
c
⊧ `
op1
⇒ `
op2
) ->
op1
≡τ
op2
.
Proof.
unfold
tnra_rewrites_to
,
tnra_eq
;
intros
.
elim
H
;
clear
H
;
intros
.
apply
(
H0
x
c
dt_x
dt_c
).
dependent
induction
op1
;
simpl
.
assumption
.
Qed.
Lemma
tnra_typed_eq_and_type_propag
{τ
c
} {τ
in
τ
out
:
rtype
} (
op1
op2
:
typed_nra
τ
c
τ
in
τ
out
):
op1
≡τ
op2
->
((`
op1
) ▷ τ
in
>=> τ
out
⊣ τ
c
-> (`
op2
) ▷ τ
in
>=> τ
out
⊣ τ
c
) -> τ
in
↦ₐ τ
out
⊣ τ
c
⊧ (`
op1
) ⇒ (`
op2
).
Proof.
unfold
tnra_rewrites_to
,
tnra_eq
;
intros
.
split
.
apply
H0
;
assumption
.
assumption
.
Qed.
End
TNRAEq
.
Notation
"
m
⊢ₐ
A
↦
B
⊣
C
⊧
op1
⇒
op2
" := (@
tnra_rewrites_to
m
C
A
B
op1
op2
) (
at
level
80) :
nra_scope
.
Notation
"
t1
⇝
t2
⊣
tc
" := (
typed_nra
tc
t1
t2
) (
at
level
80) :
nra_scope
.
Notation
"
X
≡τ
Y
" := (
tnra_eq
X
Y
) (
at
level
80) :
nra_scope
.
Notation
"
X
≡τ'
Y
" := (
tnra_eq
(
exist
_
_
X
) (
exist
_
_
Y
)) (
at
level
80) :
nra_scope
.