blob: be74b244a1bd5d09d0614f0d674131bf88fb4630 [file]
/-
Copyright (c) 2025 Lean FRO LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sebastian Graf
-/
module
prelude
public import Std.Do.WP
set_option linter.missingDocs true
@[expose] public section
/-!
# Hoare triples
Hoare triples form the basis for compositional functional correctness proofs about monadic programs.
As usual, `Triple x P Q` holds iff the precondition `P` entails the weakest precondition
`wp⟦x⟧ Q` of `x : m α` for the postcondition `Q`.
It is thus defined in terms of an instance `WP m ps`.
-/
namespace Std.Do
universe u v
variable {m : Type u → Type v} {ps : PostShape.{u}}
/--
A Hoare triple for reasoning about monadic programs. A Hoare triple `Triple x P Q` is a
*specification* for `x`: if assertion `P` holds before `x`, then postcondition `Q` holds after
running `x`.
`⦃P⦄ x ⦃Q⦄` is convenient syntax for `Triple x P Q`.
-/
def Triple [WP m ps] {α : Type u} (x : m α) (P : Assertion ps) (Q : PostCond α ps) : Prop :=
P ⊢ₛ wp⟦x⟧ Q
@[inherit_doc Std.Do.Triple]
scoped syntax:lead (name := triple) "⦃" term "⦄ " term:lead " ⦃" term "⦄" : term
/--
Unexpands Hoare triples to their high-level syntax during pretty printing.
-/
@[app_unexpander Triple]
meta def unexpandTriple : Lean.PrettyPrinter.Unexpander
| `($_ $x $P $Q) => do
`(⦃$(← SPred.Notation.unpack P)⦄ $x ⦃$Q⦄)
| _ => throw ()
namespace Triple
theorem iff [WP m ps] {α : Type u} {x : m α} {P : Assertion ps} {Q : PostCond α ps} :
(Triple x P Q) ↔ (P ⊢ₛ wp⟦x⟧ Q) := by rfl
theorem iff_conseq [WP m ps] {α : Type u} {x : m α} {P : Assertion ps} {Q : PostCond α ps} :
(Triple x P Q) ↔ (∀ ⦃P' Q'⦄, (P' ⊢ₛ P) → (Q ⊢ₚ Q') → P' ⊢ₛ wp⟦x⟧ Q') := by
constructor
· intro h P' Q' hP hQ;
apply SPred.entails.trans hP
apply SPred.entails.trans h
apply (wp x).mono _ _ hQ
. intro h; apply h .rfl .rfl
theorem entails_wp_of_pre_post [WP m ps] {α : Type u} {x : m α} {P P' : Assertion ps} {Q Q' : PostCond α ps}
(h : Triple x P' Q') (hpre : P ⊢ₛ P') (hpost : Q' ⊢ₚ Q) : P ⊢ₛ wp⟦x⟧ Q := Triple.iff_conseq.mp h hpre hpost
theorem entails_wp_of_pre [WP m ps] {α : Type u} {x : m α} {P P' : Assertion ps} {Q : PostCond α ps}
(h : Triple x P' Q) (hpre : P ⊢ₛ P') : P ⊢ₛ wp⟦x⟧ Q := Triple.iff_conseq.mp h hpre .rfl
theorem entails_wp_of_post [WP m ps] {α : Type u} {x : m α} {P : Assertion ps} {Q Q' : PostCond α ps}
(h : Triple x P Q') (hpost : Q' ⊢ₚ Q) : P ⊢ₛ wp⟦x⟧ Q := Triple.iff_conseq.mp h .rfl hpost
instance [WP m ps] (x : m α) : SPred.Tactic.PropAsSPredTautology (Triple x P Q) spred(P → wp⟦x⟧ Q) where
iff := Triple.iff |>.trans (SPred.entails_true_intro _ _).symm
theorem pure [Monad m] [WPMonad m ps] {α : Type u} {Q : PostCond α ps} (a : α) (himp : P ⊢ₛ Q.1 a) :
Triple (pure (f:=m) a) P Q := Triple.iff.mpr (himp.trans (by simp))
theorem bind [Monad m] [WPMonad m ps] {α β : Type u} {P : Assertion ps} {Q : α → Assertion ps} {R : PostCond β ps}
(x : m α) (f : α → m β)
(hx : Triple x P (Q, R.2))
(hf : ∀ b, Triple (f b) (Q b) R) :
Triple (x >>= f) P R := by
apply Triple.iff.mpr
apply SPred.entails.trans (Triple.iff.mp hx)
simp only [WP.bind]
apply (wp x).mono _ _
simp only [PostCond.entails, Assertion, ExceptConds.entails.refl, and_true]
exact (fun b => Triple.iff.mp (hf b))
/--
Conjunction for two Hoare triple specifications of a program `x`.
This theorem is useful for decomposing proofs, because unrelated facts about `x` can be proven
separately and then combined with this theorem.
-/
theorem and [WP m ps] (x : m α) (h₁ : Triple x P₁ Q₁) (h₂ : Triple x P₂ Q₂) : Triple x spred(P₁ ∧ P₂) (Q₁ ∧ₚ Q₂) :=
Triple.iff.mpr <| (SPred.and_mono (Triple.iff.mp h₁) (Triple.iff.mp h₂)).trans ((wp x).conjunctive Q₁ Q₂).mpr
/--
Modus ponens for two Hoare triple specifications of a program `x`.
This theorem is useful for separating proofs. If `h₁ : Triple x P₁ Q₁` proves a basic property about
`x` and `h₂ : Triple x P₂ (Q₁ →ₚ Q₂)` is an advanced proof for `Q₂` that builds on the basic proof
for `Q₁`, then `mp x h₁ h₂` is a proof for `Q₂` about `x`.
-/
theorem mp [WP m ps] (x : m α) (h₁ : Triple x P₁ Q₁) (h₂ : Triple x P₂ (Q₁ →ₚ Q₂)) : Triple x spred(P₁ ∧ P₂) (Q₁ ∧ₚ Q₂) :=
Triple.iff.mpr <| SPred.and_mono (Triple.iff.mp h₁) (Triple.iff.mp h₂) |>.trans ((wp x).conjunctive Q₁ (Q₁ →ₚ Q₂)).mpr |>.trans ((wp x).mono _ _ PostCond.and_imp)
end Triple