代码拉取完成,页面将自动刷新
Imp.v
, RTClosure.v
, ImpExt.v
, ImpCF.v
to found the environmentDenotational_Semantics_2.v
,Denotational_Semantics_3.v
,Equivalence_Semantics_1.v
for further proofImp.v
contains the normal oneDenotational_Semantics_1.v
: the normal one denoted by skip_sem
and so onDenotational_Semantics_2.v
: the one with timeDenotational_Semantics_3.v
: the one with tracesequiv_sem_final.v
Actually, we don't use general theorem here. we suppose to prove that these three denotation semantics are truely equal, though it is really obviously. Thus that is why we just prove the equivlance of T1&T2 and T1&T3.
Equivalence_Denotational_Semantics_1_2.v
Equivalence_Denotational_Semantics_1_3.v
Equivalence_Semantics_1.v
: normal oneEquivalence_Semantics_2.v
: the one with timeEquivalence_Semantics_3.v
: the one with tracesIn our proof, we view the abstract denotation
as Type instead of each of the concrete denotational semantics.
denotation1
and denotation2
We want to construct a general theorem that given a relation R
, if all corresponding statement pairs satisfy such a relation, the denotation1
and denotation2
satisfy relation R
.skip_sem, asgn_sem, seq_sem, if_sem, loop_sem
as sem
.denotation
by sem
.CSkip, CAss, CSeq, CIf, CWhile
statements of 2 different denotations have relation R
respectively.Theorem final_proof_of_equiv{denotation1: Type}{denotation2: Type}:
forall (d1: sem denotation1) (d2: sem denotation2),
forall c,
forall (R : denotation1 -> denotation2 -> Prop),
CSkip_equiv d1 d2 R->
CAss_equiv d1 d2 R->
CSeq_equiv d1 d2 R->
CIf_equiv d1 d2 R->
CWhile_equiv d1 d2 R->
general_equiv(ceval_by_sem d1 c)(ceval_by_sem d2 c) R.
relation R
given in our proof is equivalence relation, so we can finally achieve the equivalence of two denotational semantics through this theorem.Definition sem_r(d1:state -> state -> Prop)(d2:state -> list state -> state -> Prop): Prop :=
forall st1 st2, d1 st1 st2 -> exists sts,d2 st1 sts st2.
Lemma sem_equiv_t2:
forall c st1 st2 t,
ceval_by_sem (Sem T2.skip_sem T2.asgn_sem T2.seq_sem T2.if_sem T2.loop_sem) c st1 t st2 <-> T2.ceval c st1 t st2.
equivalence
between denotational semantics and small step semantics.
Take the second denotational semantics as an example.Theorem semantic_equiv: forall c st1 st2,
(exists t: Z, ceval c st1 t st2) <-> multi_cstep (c, st1) (CSkip, st2).
F1903003 易文龙 @yiwenlong2001
F1903002 张若涵 @wangshanyw
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。