Documentation

PolyFun.PFunctor.Resumption.DomainLaws

Fusion and substitution for continuous resumption interpretations #

Strict continuous maps commuting with the operation algebra commute with interpretation. Substitution changes the return interpretation and preserves the query algebra, even for infinite trees and unbounded branching.

theorem PFunctor.Resumption.denote_fusion {P : PFunctor.{uA, uB}} {α : Type uα} {D : Type uD} {E : Type uE} [OmegaCompletePartialOrder D] [OrderBot D] [OmegaCompletePartialOrder E] [OrderBot E] (ret : α → D) (alg : ContinuousAlgebra P D) (target : ContinuousAlgebra P E) (f : D →𝒄 E) (hbot : f ⊥ = ⊥) (halg : ∀ (a : P.A) (k : P.B a → D), f ((alg a) k) = (target a) fun (b : P.B a) => f (k b)) (tree : P.Resumption α) :
f (denote ret alg tree) = denote (fun (a : α) => f (ret a)) target tree

A strict continuous algebra morphism commutes with interpretation.

theorem PFunctor.Resumption.denote_bind {P : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {D : Type uD} [OmegaCompletePartialOrder D] [OrderBot D] (ret : β → D) (alg : ContinuousAlgebra P D) (tree : P.Resumption α) (next : α → P.Resumption β) :
denote ret alg (tree.bind next) = denote (fun (a : α) => denote ret alg (next a)) alg tree

Substitution is interpreted by assigning each source return its continuation's meaning.