Documentation

PolyFun.ITree.WP.Bisim

Weakest preconditions are invariant under weak bisimulation #

The total and partial readings of PolyFun.ITree.WP.Basic read a silent step as its continuation, so they cannot tell trees apart by their silent steps. They are invariant under finite stripping of silent steps (ITree.TauSteps.wpTotal_eq) and under weak bisimulation. The relational form compares trees with different return types: t ≈[RR] s and postconditions related along RR give wp t post ≤ wp s post' (ITree.WeakBisimRel.wpTotal_le, ITree.WeakBisimRel.wpPartial_le).

Silent divergence is respected: a tree weakly bisimilar to ITree.diverge is ITree.diverge (ITree.TauSteps.diverge_target_eq), so it keeps its readings ⊥ and ⊤.

Main results #

theorem ITree.TauSteps.wpTotal_eq {F : PFunctor.{uA, uB}} {α : Type uα} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {post : α → l} {t t' : ITree F α} (h : t.TauSteps t') :
wpTotal Φ t post = wpTotal Φ t' post
theorem ITree.TauSteps.wpPartial_eq {F : PFunctor.{uA, uB}} {α : Type uα} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {post : α → l} {t t' : ITree F α} (h : t.TauSteps t') :
wpPartial Φ t post = wpPartial Φ t' post
theorem ITree.WeakBisimRel.wpTotal_le {F : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {RR : α → β → Prop} {post : α → l} {post' : β → l} (hpost : ∀ (a : α) (b : β), RR a b → post a ≤ post' b) {t : ITree F α} {s : ITree F β} (h : WeakBisimRel RR t s) :
wpTotal Φ t post ≤ wpTotal Φ s post'

Total correctness transfers along a relational weak bisimulation whose related return values have related postconditions.

theorem ITree.WeakBisimRel.wpPartial_le {F : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {RR : α → β → Prop} {post : α → l} {post' : β → l} (hpost : ∀ (a : α) (b : β), RR a b → post a ≤ post' b) {t : ITree F α} {s : ITree F β} (h : WeakBisimRel RR t s) :
wpPartial Φ t post ≤ wpPartial Φ s post'

Partial correctness transfers along a relational weak bisimulation whose related return values have related postconditions.

theorem ITree.WeakBisim.wpTotal_eq {F : PFunctor.{uA, uB}} {α : Type uα} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {post : α → l} {t s : ITree F α} (h : t.WeakBisim s) :
wpTotal Φ t post = wpTotal Φ s post
theorem ITree.WeakBisim.wpPartial_eq {F : PFunctor.{uA, uB}} {α : Type uα} {l : Type w} [CompleteLattice l] {Φ : F.OpSpec l} (hΦ : Φ.Monotone) {post : α → l} {t s : ITree F α} (h : t.WeakBisim s) :
wpPartial Φ t post = wpPartial Φ s post