Mercurial > hg > Members > ryokka > HoareLogic
changeset 2:b05a4156da01
add HTProof
author | ryokka |
---|---|
date | Thu, 13 Dec 2018 19:05:43 +0900 |
parents | ab73094377a2 |
children | 6be8ee856666 |
files | Hoare.agda whileTest.agda |
diffstat | 2 files changed, 56 insertions(+), 35 deletions(-) [+] |
line wrap: on
line diff
--- a/Hoare.agda Thu Dec 13 17:45:50 2018 +0900 +++ b/Hoare.agda Thu Dec 13 19:05:43 2018 +0900 @@ -47,8 +47,8 @@ While : Cond -> Comm -> Comm -- Hoare Triple -data HT : Set where - ht : Cond -> Comm -> Cond -> HT +-- data HT : Set where +-- ht : Cond -> Comm -> Cond -> HT {- prPre pr prPost
--- a/whileTest.agda Thu Dec 13 17:45:50 2018 +0900 +++ b/whileTest.agda Thu Dec 13 19:05:43 2018 +0900 @@ -5,8 +5,9 @@ open import Data.Product open import Relation.Nullary open import Relation.Binary +open import Relation.Binary.PropositionalEquality open import SET - +import Level record Env : Set where field @@ -14,44 +15,55 @@ vari : ℕ open Env +PrimComm = Env → Env + +Cond = Env → Bool + neg : (Env → Bool) → (Env → Bool) neg x e = not (x e) - + and : (Env → Bool) → (Env → Bool) → (Env → Bool) and x y e = (x e) ∧ (y e) -enveq : (Env → Bool) → (Env → Bool) → Set -enveq x y = {!!} - -sem : (Env → Bool) → Pred Env -sem x y = {!!} - -tautValid : (b1 b2 : Env → Bool) -> enveq b1 b2 -> - (s : Env) -> sem b1 s -> sem b2 s -tautValid = {!!} - -respNeg : (b : Env → Bool) -> (s : Env) -> - Iff (sem (neg b) s) (¬ sem b s) -respNeg = {!!} +data Comm : Set where + Skip : Comm + Abort : Comm + PComm : PrimComm -> Comm + Seq : Comm -> Comm -> Comm + If : Cond -> Comm -> Comm -> Comm + While : Cond -> Comm -> Comm -respAnd : (b1 b2 : Env → Bool) -> (s : Env) -> - Iff (sem (and b1 b2) s) - ((sem b1 s) × (sem b2 s)) -respAnd = {!!} - -PrimSemComm : ∀ {l} -> (Env → Env) -> Rel Env l -PrimSemComm = {!!} +data HTProof : Cond -> Comm -> Cond -> Set (Level.suc (Level.suc Level.zero)) where + PrimRule : {bPre : Cond} -> {pcm : PrimComm} -> {bPost : Cond} -> + (pr : Cond -> PrimComm -> Cond -> Set (Level.suc Level.zero)) -> + HTProof bPre (PComm pcm) bPost + SkipRule : (b : Cond) -> HTProof b Skip b + AbortRule : (bPre : Cond) -> (bPost : Cond) -> + HTProof bPre Abort bPost + WeakeningRule : {bPre : Cond} -> {bPre' : Cond} -> {cm : Comm} -> + {bPost' : Cond} -> {bPost : Cond} -> + bPre ≡ bPre' -> + HTProof bPre' cm bPost' -> + bPost' ≡ bPost -> + HTProof bPre cm bPost + SeqRule : {bPre : Cond} -> {cm1 : Comm} -> {bMid : Cond} -> + {cm2 : Comm} -> {bPost : Cond} -> + HTProof bPre cm1 bMid -> + HTProof bMid cm2 bPost -> + HTProof bPre (Seq cm1 cm2) bPost + IfRule : {cmThen : Comm} -> {cmElse : Comm} -> + {bPre : Cond} -> {bPost : Cond} -> + {b : Cond} -> + HTProof (and bPre b) cmThen bPost -> + HTProof (and bPre (neg b)) cmElse bPost -> + HTProof bPre (If b cmThen cmElse) bPost + WhileRule : {cm : Comm} -> {bInv : Cond} -> {b : Cond} -> + HTProof (and bInv b) cm bInv -> + HTProof bInv (While b cm) (and bInv (neg b)) + Rule : {cm : Comm} -> {bInv : Cond} -> {b : Cond} -> {w : Cond} -> + HTProof w cm bInv -> + HTProof bInv (While b cm) (and bInv (neg b)) -Axiom :( Env → Bool) -> (Env → Env) -> (Env → Bool) -> Set -Axiom = {!!} - -axiomValid : ∀ {l} -> (bPre : Env → Bool ) -> (pcm : (Env → Env)) -> (bPost : Env → Bool) -> - (ax : Axiom bPre pcm bPost) -> (s1 s2 : Env) -> - sem bPre s1 -> PrimSemComm {l} pcm s1 s2 -> sem bPost s2 -axiomValid = {!!} - -open import Hoare (Env → Bool) (Env → Env) neg and enveq Env sem tautValid - respNeg respAnd PrimSemComm Axiom axiomValid lt : ℕ → ℕ → Bool lt x y with x <? y @@ -98,7 +110,16 @@ termCond : Env → Bool termCond env = (vari env) == 10 +iff : Bool → Bool → Bool +iff true true = true +iff false false = true +iff _ _ = false + +proposition1 : Cond → PrimComm → Cond → Env → Set +proposition1 pre cmd post = λ (env : Env) → {!!} -- iff (pre env) (post (cmd env)) proof1 : HTProof initCond program termCond -proof1 = {!!} +proof1 = SeqRule (PrimRule {!!} ) + (SeqRule (PrimRule {!!} ) + (Rule {!!} (WhileRule ?)))