Documentation

PolyFun.Control.Monad.WriterT.WP

WriterT on core's weakest-precondition stack #

Core lifts a WPMonad interpretation through its own transformers (StateT, ReaderT, ExceptT, OptionT); WriterT is Mathlib's, so its lift lives here. The carrier is ω → Pred, indexed by the log written so far: bind multiplies the prefix's log into the continuation's, so a postcondition that mentions the log has to be told what has already been written, and reading the interpretation at the unit recovers the log-oblivious one.

WriterT.wpMonadOf takes explicit empty/append operations and their laws, so it also interprets append-based logs without a Monoid instance. The monoid specialization is scoped under WriterT.MonoidWP, and the specialization to logs combined by ++ from ∅ under core's Std.Associative and Std.LawfulIdentity is scoped under WriterT.AppendWP, which also supplies the writer's LawfulMonad instance (WriterT.lawfulMonad_monad). Clients opt in with open scoped WriterT.MonoidWP or open scoped WriterT.AppendWP, or install an explicit interpretation locally. Importing the module does not choose a writer interpretation. Exactness over an exact base is a global instance keyed on WriterT.wpMonadOf (WriterT.instExactWPMonadWpMonadOf), so it holds under either scope and for a local interpretation. The @[spec] rules for tell, monadLift, mk, and run are registered in the same two scopes, beside the entailments they wrap, so vcgen uses them exactly where a writer interpretation is selected.

@[instance_reducible]
def WriterT.wpInstOf {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} (append : ω → ω → ω) [Std.WP.WP (m (α × ω)) (α × ω) Pred EPred] :
Std.WP.WP (WriterT ω m α) α (ω → Pred) EPred

WriterT's WP interpretation: the base interpretation of the run, with the postcondition told the log accumulated so far.

Equations
  • One or more equations did not get rendered due to their size.
Instances For

    Lawful writer monads #

    theorem WriterT.lawfulMonad_monad {m : Type u → Type v} {ω : Type u} [Monad m] [LawfulMonad m] (empty : ω) (append : ω → ω → ω) (left_id : ∀ (w : ω), append empty w = w) (right_id : ∀ (w : ω), append w empty = w) (assoc : ∀ (a b c : ω), append (append a b) c = append a (append b c)) :

    The writer monad of explicit log operations is lawful when empty is a two-sided unit of an associative append.

    theorem WriterT.AppendWP.instLawfulIdentityListAppend {β : Type u} :
    Std.LawfulIdentity (fun (x1 x2 : List β) => x1 ++ x2) ∅

    List's identity for ++ at the spelling ∅ of the writer monad's empty log. Core states it at [], and instance search does not re-abstract the identity, an outParam, in the hypotheses of the instances below, so they need the ∅ form.

    theorem WriterT.AppendWP.instLawfulMonad {m : Type u → Type v} {ω : Type u} [Monad m] [LawfulMonad m] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] :

    The writer monad of an append-based log is lawful.

    @[instance_reducible]
    def WriterT.wpMonadOf {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] (empty : ω) (append : ω → ω → ω) (right_id : ∀ (w : ω), append w empty = w) (assoc : ∀ (a b c : ω), append (append a b) c = append a (append b c)) [LawfulMonad (WriterT ω m)] :
    Std.WP.WPMonad (WriterT ω m) (ω → Pred) EPred

    Interpret a writer with explicit log operations. The lawfulness witness must use the same WriterT.monad empty append; no monoid instance is installed on the log type.

    Equations
    Instances For
      instance WriterT.instExactWPMonadWpMonadOf {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [ExactWPMonad m Pred EPred] (empty : ω) (append : ω → ω → ω) (right_id : ∀ (w : ω), append w empty = w) (assoc : ∀ (a b c : ω), append (append a b) c = append a (append b c)) [LawfulMonad (WriterT ω m)] :
      ExactWPMonad (WriterT ω m) (ω → Pred) EPred

      Over an exact base interpretation, the explicit writer interpretation is exact.

      @[deprecated WriterT.instExactWPMonadWpMonadOf (since := "2026-11-16")]
      theorem WriterT.exactWPMonad_wpMonadOf {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [ExactWPMonad m Pred EPred] (empty : ω) (append : ω → ω → ω) (right_id : ∀ (w : ω), append w empty = w) (assoc : ∀ (a b c : ω), append (append a b) c = append a (append b c)) [LawfulMonad (WriterT ω m)] :
      ExactWPMonad (WriterT ω m) (ω → Pred) EPred

      Alias of WriterT.instExactWPMonadWpMonadOf.


      Over an exact base interpretation, the explicit writer interpretation is exact.

      theorem WriterT.wpInstOf_apply_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] (append : ω → ω → ω) (x : WriterT ω m α) (post : α → ω → Pred) (epost : EPred) (w : ω) :
      Std.WP.wp x post epost w = Std.WP.wp x.run (fun (p : α × ω) => post p.1 (append w p.2)) epost

      The explicit writer interpretation exposes its accumulated-log equation. Not @[simp]: the scoped readings state their own equations on core's wp (WriterT.wp_apply_eq, WriterT.AppendWP.wp_apply_eq).

      theorem WriterT.le_wp_tell_of {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] (append : ω → ω → ω) (out : ω) (post : PUnit.{u + 1} → ω → Pred) (epost : EPred) :
      Lean.Order.PartialOrder.rel (fun (w : ω) => post PUnit.unit (append w out)) (Std.WP.wp (tell out) post epost)

      Writing a log fragment extends the accumulated log with the chosen append operation.

      theorem WriterT.le_wp_liftTell_of {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] (empty : ω) (append : ω → ω → ω) (right_id : ∀ (w : ω), append w empty = w) (x : m α) (post : α → ω → Pred) (epost : EPred) :
      Lean.Order.PartialOrder.rel (fun (w : ω) => Std.WP.wp x (fun (a : α) => post a w) epost) (Std.WP.wp (MonadLift.monadLift x) post epost)

      Lifting with the chosen empty log leaves the accumulated prefix unchanged.

      theorem WriterT.wp_run_eq_of {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] (empty : ω) (append : ω → ω → ω) (left_id : ∀ (w : ω), append empty w = w) (x : WriterT ω m α) (post : α × ω → Pred) (epost : EPred) :
      Std.WP.wp x.run post epost = Std.WP.wp x (fun (a : α) (w : ω) => post (a, w)) epost empty

      Starting the accumulated-log interpretation at a left identity gives the base run.

      Append-based logs #

      WriterT.AppendWP interprets a log combined by ++ from ∅, such as a list, under core's Std.Associative (· ++ ·) and Std.LawfulIdentity (· ++ ·) ∅.

      @[instance_reducible]
      def WriterT.AppendWP.instWPMonad {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] :
      Std.WP.WPMonad (WriterT ω m) (ω → Pred) EPred

      Opt-in writer interpretation for append-based logs: the postcondition is told the log accumulated so far, extended on the right by ++.

      Equations
      Instances For
        @[simp]
        theorem WriterT.AppendWP.wp_apply_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] (x : WriterT ω m α) (post : α → ω → Pred) (epost : EPred) (w : ω) :
        Std.WP.wp x post epost w = Std.WP.wp x.run (fun (p : α × ω) => post p.1 (w ++ p.2)) epost
        theorem WriterT.AppendWP.le_wp_tell {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] (out : ω) (post : PUnit.{u + 1} → ω → Pred) (epost : EPred) :
        Lean.Order.PartialOrder.rel (fun (w : ω) => post PUnit.unit (w ++ out)) (Std.WP.wp (tell out) post epost)

        Writing to an append-based log extends the accumulated log on the right.

        theorem WriterT.AppendWP.le_wp_monadLift {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] (x : m α) (post : α → ω → Pred) (epost : EPred) :
        Lean.Order.PartialOrder.rel (fun (w : ω) => Std.WP.wp x (fun (a : α) => post a w) epost) (Std.WP.wp (MonadLift.monadLift x) post epost)

        A lifted base computation leaves an append-based log unchanged.

        @[simp]
        theorem WriterT.AppendWP.wp_mk_apply_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] (x : m (α × ω)) (post : α → ω → Pred) (epost : EPred) (w : ω) :
        Std.WP.wp (WriterT.mk x) post epost w = Std.WP.wp x (fun (p : α × ω) => post p.1 (w ++ p.2)) epost
        theorem WriterT.AppendWP.wp_run_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [EmptyCollection ω] [Append ω] [Std.Associative fun (x1 x2 : ω) => x1 ++ x2] [Std.LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] (x : WriterT ω m α) (post : α × ω → Pred) (epost : EPred) :
        Std.WP.wp x.run post epost = Std.WP.wp x (fun (a : α) (w : ω) => post (a, w)) epost ∅

        Running an append-based writer computation from the empty log.

        @[instance_reducible]
        def WriterT.MonoidWP.instWPMonad {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] :
        Std.WP.WPMonad (WriterT ω m) (ω → Pred) EPred

        Opt-in writer interpretation for multiplicative monoid logs.

        Equations
        Instances For
          @[simp]
          theorem WriterT.wp_apply_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] (x : WriterT ω m α) (post : α → ω → Pred) (epost : EPred) (w : ω) :
          Std.WP.wp x post epost w = Std.WP.wp x.run (fun (p : α × ω) => post p.1 (w * p.2)) epost
          theorem WriterT.le_wp_tell {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] (out : ω) (post : PUnit.{u + 1} → ω → Pred) (epost : EPred) :
          Lean.Order.PartialOrder.rel (fun (w : ω) => post PUnit.unit (w * out)) (Std.WP.wp (tell out) post epost)

          Writing to the log advances the accumulated log the postcondition sees.

          theorem WriterT.le_wp_monadLift {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] (x : m α) (post : α → ω → Pred) (epost : EPred) :
          Lean.Order.PartialOrder.rel (fun (w : ω) => Std.WP.wp x (fun (a : α) => post a w) epost) (Std.WP.wp (MonadLift.monadLift x) post epost)

          A lifted base computation writes nothing.

          @[simp]
          theorem WriterT.wp_mk_apply_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] (x : m (α × ω)) (post : α → ω → Pred) (epost : EPred) (w : ω) :
          Std.WP.wp (WriterT.mk x) post epost w = Std.WP.wp x (fun (p : α × ω) => post p.1 (w * p.2)) epost
          theorem WriterT.wp_run_eq {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Std.WP.Assertion Pred] [Std.WP.Assertion EPred] {α : Type u} [Monad m] [Std.WP.WPMonad m Pred EPred] [Monoid ω] (x : WriterT ω m α) (post : α × ω → Pred) (epost : EPred) :
          Std.WP.wp x.run post epost = Std.WP.wp x (fun (a : α) (w : ω) => post (a, w)) epost 1

          Running a writer computation from the empty log.

          vcgen rules #

          The rules for tell, monadLift, WriterT.mk and WriterT.run wrap the entailments above. The rules for multiplicative logs are stated for the interpretation of WriterT.MonoidWP, and the rules for append-based logs for that of WriterT.AppendWP. Each set is registered in the scope of its interpretation, so vcgen uses it exactly where that interpretation is installed.

          theorem Std.WP.Spec.tell_WriterT {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [Monoid ω] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] (out : ω) (post : PUnit.{u + 1} → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => post PUnit.unit (w * out) ⦄ tell out ⦃ post; epost ⦄

          tell on a multiplicative log, read by WriterT.MonoidWP, multiplies the log on the right.

          theorem Std.WP.Spec.monadLift_WriterT {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [Monoid ω] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : m α) (post : α → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => wp x (fun (a : α) => post a w) epost ⦄ MonadLift.monadLift x ⦃ post; epost ⦄

          A lifted base computation leaves a multiplicative log unchanged.

          theorem Std.WP.Spec.mk_WriterT {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [Monoid ω] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : m (α × ω)) (post : α → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => wp x (fun (p : α × ω) => post p.1 (w * p.2)) epost ⦄ WriterT.mk x ⦃ post; epost ⦄

          WriterT.mk x on a multiplicative log multiplies in the log x returns.

          theorem Std.WP.Spec.run_WriterT {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [Monoid ω] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : WriterT ω m α) (post : α × ω → Pred) {epost : EPred} :
          ⦃ wp x (fun (a : α) (w : ω) => post (a, w)) epost 1 ⦄ x.run ⦃ post; epost ⦄

          Running a writer computation on a multiplicative log starts from the unit.

          theorem Std.WP.Spec.tell_WriterT_append {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [EmptyCollection ω] [Append ω] [Associative fun (x1 x2 : ω) => x1 ++ x2] [LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] (out : ω) (post : PUnit.{u + 1} → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => post PUnit.unit (w ++ out) ⦄ tell out ⦃ post; epost ⦄

          tell on an append-based log, read by WriterT.AppendWP, extends the log on the right.

          theorem Std.WP.Spec.monadLift_WriterT_append {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [EmptyCollection ω] [Append ω] [Associative fun (x1 x2 : ω) => x1 ++ x2] [LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : m α) (post : α → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => wp x (fun (a : α) => post a w) epost ⦄ MonadLift.monadLift x ⦃ post; epost ⦄

          A lifted base computation leaves an append-based log unchanged.

          theorem Std.WP.Spec.mk_WriterT_append {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [EmptyCollection ω] [Append ω] [Associative fun (x1 x2 : ω) => x1 ++ x2] [LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : m (α × ω)) (post : α → ω → Pred) {epost : EPred} :
          ⦃ fun (w : ω) => wp x (fun (p : α × ω) => post p.1 (w ++ p.2)) epost ⦄ WriterT.mk x ⦃ post; epost ⦄

          WriterT.mk x on an append-based log appends the log x returns.

          theorem Std.WP.Spec.run_WriterT_append {m : Type u → Type v} {ω : Type u} {Pred : Type w} {EPred : Type z} [Monad m] [EmptyCollection ω] [Append ω] [Associative fun (x1 x2 : ω) => x1 ++ x2] [LawfulIdentity (fun (x1 x2 : ω) => x1 ++ x2) ∅] [Assertion Pred] [Assertion EPred] [WPMonad m Pred EPred] {α : Type u} (x : WriterT ω m α) (post : α × ω → Pred) {epost : EPred} :
          ⦃ wp x (fun (a : α) (w : ω) => post (a, w)) epost ∅ ⦄ x.run ⦃ post; epost ⦄

          Running an append-based writer computation starts from the empty log.