Documentation

PolyFun.ITree.Interp.Sim

Interpretation into interaction trees #

When the target monad is an interaction tree, interp is simulate by definition, so the strong computation equations and the weak-bisimulation laws of simulation transfer verbatim: the computation rules hold as equalities, interpretation respects weak bisimulation of the source, and interpreting through the identity handler or through a composite handler behaves as expected. The generic laws of PolyFun.ITree.Interp.Laws give the same facts up to the target's equivalence, which for an interaction tree is weak bisimulation; these are the sharper forms.

theorem ITree.interp_pure_eq {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α : Type u} (h : PFunctor.Handler (ITree F) E) (r : α) :
interp h (pure r) = pure r
theorem ITree.interp_step_eq {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α : Type u} (h : PFunctor.Handler (ITree F) E) (t : ITree E α) :
interp h t.step = (interp h t).step
theorem ITree.interp_query_eq_bind {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α : Type u} (h : PFunctor.Handler (ITree F) E) (a : E.A) (k : E.B a → ITree E α) :
interp h (query a k) = (h a).bind fun (b : E.B a) => (interp h (k b)).step
theorem ITree.interp_weakBisimRel {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α β : Type u} {RR : α → β → Prop} (h : PFunctor.Handler (ITree F) E) {t : ITree E α} {s : ITree E β} (hts : WeakBisimRel RR t s) :
WeakBisimRel RR (interp h t) (interp h s)

Interpretation respects weak bisimulation of the source tree.

theorem ITree.interp_id_weak {E : PFunctor.{u, u}} {α : Type u} (t : ITree E α) :

Interpreting through the identity handler changes nothing up to weak bisimulation.

theorem ITree.interp_comp_weak {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α : Type u} {G : PFunctor.{u, u}} (outer : PFunctor.Handler (ITree F) G) (inner : PFunctor.Handler (ITree G) E) (t : ITree E α) :
(interp outer (interp inner t)).WeakBisim (interp (Handler.comp outer inner) t)

Interpreting twice is interpreting through the composite handler.

theorem ITree.interp_bind_weak {E : PFunctor.{u, u}} {F : PFunctor.{uFA, uFB}} {α β : Type u} (h : PFunctor.Handler (ITree F) E) (t : ITree E α) (k : α → ITree E β) :
(interp h (t.bind k)).WeakBisim ((interp h t).bind fun (a : α) => interp h (k a))

Interpretation into a tree distributes over sequencing up to weak bisimulation.