archive-nl.com » NL » R » ROBBERTKREBBERS.NL

Total: 145

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Module pointer_casts
    end abstract try inversion 1 naive solver constructor Defined Lemma size of castable Γ τ τ p τ τ p ptr size of Γ τ p size of Γ τ Proof destruct 1 simpl rewrite size of char auto using Nat divide 1 l Qed Lemma align of castable Γ τ1 τ2 Γ τ1 TType τ2 align of Γ τ2 align of Γ τ1 Proof inversion clear 2 rewrite align

    Original URL path: http://robbertkrebbers.nl/research/ch2o/pointer_casts.html (2015-08-10)
    Open archived version from archive


  • Module fragmented
    nat xss list fragment A Prop xss Fragment x seq i len i Global Instance fragmented dec x i xss Decision fragmented x i xss Typeclasses Opaque fragmented Definition to fragments x A list fragment A Fragment x seq 0 len Definition of fragments xss list fragment A option A match xss with Fragment x 0 xss guard fragmented x 1 xss Some x None end Lemma to fragments fragmented x fragmented x 0 to fragments x Proof unfold fragmented to fragments by rewrite Nat sub 0 r Qed Lemma to fragments length x length to fragments x len Proof unfold to fragments by rewrite fmap length seq length Qed Lemma of to fragments x xss of fragments xss Some x to fragments x xss Proof unfold of fragments to fragments fragmented fragmented dec PropHolds in destruct len as n lia by destruct xss as y xss split intros simplify option equality rewrite Nat sub 0 r Nat sub 0 r in Qed Lemma of to fragments 1 x xss of fragments xss Some x to fragments x xss Proof by apply of to fragments Qed Lemma of to fragments 2 x of fragments to fragments x Some x Proof

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fragmented.html (2015-08-10)
    Open archived version from archive

  • Module contexts
    in a generic way Instance list subst Subst A B B Subst list A B B fix go l list A b B B let Subst go in match l with b a l subst l subst a b end Lemma subst nil Subst A B B b subst b b Proof done Qed Lemma subst app Subst A B B l1 l2 list A b subst l1 l2 b subst l2 subst l1 b Proof revert b induction l1 simpl auto Qed Lemma subst snoc Subst A B B l1 list A a b subst l1 a b subst a subst l1 b Proof exact subst app l1 a b Qed Instance list subst injective Subst A B B a Injective subst a l list A Injective subst l Proof intros l red induction l as x l IH simpl intros auto eapply injective subst IH eassumption Qed Contexts with multiple holes Less commonly used kinds of contexts are those with multiple holes These can be represented as dependent types indexed by the number of holes We define a class DepSubst for substitution The function depsubst E xs is supposed to substitute the values of the vector xs in the holes of E Class DepSubst I A I Type B I Type C depsubst i A i B i C Instance Params depsubst 6 Arguments depsubst simpl nomatch Tactics The tactic simplify subst equality H simplifies an assumption H that is an equality involving subst It repeatedly tries to use injectivity of subst or to perform case analysis on the context Such case analyses are only performed for contexts for which an instance of DestructSubst is declared Class DestructSubst Subst A B C Tactic Notation simplify subst equality hyp H match type of H with subst a subst a

    Original URL path: http://robbertkrebbers.nl/research/ch2o/contexts.html (2015-08-10)
    Open archived version from archive

  • Module optionmap
    alter A PartialAlter option K A optionmap M A λ f i m match i m with None OptionMap o m OptionMap f o m Some k OptionMap o m OptionMap o partial alter f k m end Global Instance optionmap to list A FinMapToList option K A optionmap M A λ m match m with OptionMap o m default o λ x None x prod map Some id map to list m end Global Instance optionmap omap OMap optionmap M λ A B f m match m with OptionMap o m OptionMap o f omap f m end Global Instance optionmap merge Merge optionmap M λ A B C f m1 m2 match m1 m2 with OptionMap o1 m1 OptionMap o2 m2 OptionMap f o1 o2 merge f m1 m2 end Global Instance optionmap fmap FMap optionmap M λ A B f m match m with OptionMap o m OptionMap f o f m end Global Instance FinMap option K optionmap M Proof split intros Hlookup f equal apply Hlookup None apply map eq intros k apply Hlookup Some k intros apply lookup empty k done intros f t k simpl done apply lookup partial alter intros f t k k simpl try intuition congruence intros apply lookup partial alter ne congruence intros simpl apply lookup fmap done intros x m unfold map to list simpl constructor rewrite elem of list fmap by intros by apply NoDup fmap NoDup map to list apply NoDup fmap NoDup map to list intros m k x unfold map to list split destruct m as y m simpl rewrite elem of cons elem of list fmap intros simplify equality done by apply elem of map to list rewrite elem of list fmap intros simplify equality by apply elem of map to list destruct

    Original URL path: http://robbertkrebbers.nl/research/ch2o/optionmap.html (2015-08-10)
    Open archived version from archive

  • Module restricted_smallstep
    free m o τ s 1 rcstep free params top m k f o τ s v s Γ δ ρ ₛ State CParams f o τ s k Stmt v s m State k Return f v foldr mem free m o τ s 1 rcstep return m k f E v Γ δ ρ ₛ State CFun E k Return f v m State k Expr subst E v E m For non local control flow rcstep label here m k l Γ δ ρ ₛ State k Stmt l label l m State k Stmt label l m rcstep throw here m k s Γ δ ρ ₛ State CStmt catch k Stmt 0 s m State k Stmt catch s m rcstep throw further m k s n Γ δ ρ ₛ State CStmt catch k Stmt S n s m State k Stmt n catch s m cstep case here m k mx Γ δ ρ ₛ State k Stmt mx scase mx m State k Stmt scase mx m rcstep goto in m k Es l s l labels s Γ δ ρ ₛ State k Stmt l subst Es s m State CStmt Es k Stmt l s m rcstep switch in m k Es mx s maybe CSwitch Es None mx cases s Γ δ ρ ₛ State k Stmt mx subst Es s m State CStmt Es k Stmt mx s m rcstep top out m k Es v s Γ δ ρ ₛ State CStmt Es k Stmt v s m State k Stmt v subst Es s m rcstep goto out m k Es l s l labels s Γ δ ρ ₛ State CStmt Es k Stmt l s m State k Stmt l subst Es s m rcstep throw out m k Es n s Es catch Γ δ ρ ₛ State CStmt Es k Stmt n s m State k Stmt n subst Es s m For block scopes rcstep in block m k d o τ s direction in d s o dom indexset m Γ δ ρ ₛ State k Stmt d local τ s m State CLocal o τ k Stmt d s mem alloc Γ o false perm full val new Γ τ m rcstep out block m k d o τ s direction out d s Γ δ ρ ₛ State CLocal o τ k Stmt d s m State k Stmt d local τ s mem free o m where Γ δ ρ ₛ S1 S2 rcstep Γ δ ρ S1 S S2 S C scope The reflexive transitive closure Notation Γ δ ρ ₛ S1 S2 rtc rcstep Γ δ ρ S1 S2 at level 74 δ at next level ρ at next level format Γ δ ρ ₛ S1 S2 C scope Notation Γ δ ρ ₛ S1 n S2 bsteps rcstep Γ δ ρ n S1 S2 at level 74 δ at next level ρ at next level n at level 1 format Γ δ ρ ₛ S1 n S2 C scope Inversions Coq s inversion tactic is rather slow for large inductive types as our cstep We therefore define some special purpose inversion schemes The way of defining these schemes is based on small inversions Monin 2010 Section inversion Context Env K Γ env K δ funenv K ρ stack K Lemma rcstep focus inv P state K Prop S1 S2 Γ δ ρ ₛ S1 S2 let State k φ m S1 in match φ with Stmt skip P State k Stmt skip m P S2 Stmt goto l P State k Stmt l goto l m P S2 Stmt throw n P State k Stmt n throw n m P S2 Stmt label l P State k Stmt label l m P S2 Stmt scase mx P State k Stmt scase mx m P S2 Stmt e P State CExpr e k Expr e m P S2 Stmt ret e P State CExpr e ret k Expr e m P S2 Stmt loop s P State CStmt loop k Stmt s m P S2 Stmt if e s1 else s2 P State CExpr e if s1 else s2 k Expr e m P S2 Stmt switch e s P State CExpr e switch s k Expr e m P S2 Expr e Ω v k e e Ω v E k CExpr e k P State k Stmt e mem unlock Ω m Ω v k e e Ω v E k CExpr e ret k P State k Stmt v ret e mem unlock Ω m Ω vb k e s1 s2 e Ω VBase vb E base val branchable m vb base val is 0 vb k CExpr e if s1 else s2 k P State CStmt if e else s2 k Stmt s1 mem unlock Ω m Ω vb k e s1 s2 e Ω VBase vb E base val branchable m vb base val is 0 vb k CExpr e if s1 else s2 k P State CStmt if e s1 else k Stmt s2 mem unlock Ω m Ω vb k e s1 s2 e Ω VBase vb E base val branchable m vb k CExpr e if s1 else s2 k P State k Undef UndefBranch if s1 else s2 Ω VBase vb m Ω τ i x k e s e Ω intV τ i x E Some x cases s k CExpr e switch s k P State CStmt switch e k Stmt Some x s mem unlock Ω m Ω τ i x k e s e Ω intV τ i x E Some x cases s None cases s k CExpr e switch s k P State CStmt switch e k Stmt None s mem unlock Ω m Ω τ i x k e s e Ω intV τ i x E Some x cases s None cases s k CExpr e switch s k P State k Stmt switch e s mem unlock Ω m Ω vb k e s e Ω VBase vb E base val branchable m vb k CExpr e switch s k P State k Undef UndefBranch switch s Ω VBase vb m E ectx K e1 e2 m2 e subst E e1 Γ rlocals ρ k ₕ e1 m e2 m2 P State k Expr subst E e2 m2 E ectx K Ω f τ s τ Ω s vs e subst E call Ω FunPtr f τ s τ Ω s vs E length Ω s length vs P State CFun E k Call f vs mem unlock Ω Ω s m E ectx K e1 e subst E e1 is redex e1 Γ rlocals ρ k ₕ safe e1 m P State k Undef UndefExpr E e1 m P S2 Return f v k E k CFun E k P State k Expr subst E v E m P S2 Stmt local τ s o o dom indexset m P State CLocal o τ k Stmt s mem alloc Γ o false perm full val new Γ τ m P S2 Stmt s1 s2 P State CStmt s2 k Stmt s1 m P S2 Stmt catch s P State CStmt catch k Stmt s m P S2 Stmt s k o τ k CLocal o τ k P State k Stmt local τ s mem free o m k s2 k CStmt s2 k P State CStmt s k Stmt s2 m k s1 k CStmt s1 k P State k Stmt s1 s m k k CStmt catch k P State k Stmt catch s m k k CStmt loop k P State k Stmt loop s m k e s2 k CStmt if e else s2 k P State k Stmt if e s else s2 m k e s1 k CStmt if e s1 else k P State k Stmt if e s1 else s m k e k CStmt switch e k P State k Stmt switch e s m k f o τ s k CParams f o τ s k P State k Return f voidV foldr mem free m o τ s 1 P S2 Call f vs s os δ f Some s Forall fresh dom indexset m os length os length vs P State CParams f zip os type of vs k Stmt s mem alloc list Γ os vs m P S2 Stmt v s k f o τ s k CParams f o τ s k P State k Return f v foldr mem free m o τ s 1 k o τ k CLocal o τ k P State k Stmt v local τ s mem free o m k Es k CStmt Es k P State k Stmt v subst Es s m P S2 Stmt n s k k CStmt catch k n 0 P State k Stmt catch s m k n k CStmt catch k n S n P State k Stmt n catch s m k o τ k CLocal o τ k P State k Stmt n local τ s mem free o m k Es k CStmt Es k Es catch P State k Stmt n subst Es s m P S2 Stmt l s s label l P State k Stmt s m s o τ s local τ s l labels s o dom indexset m P State CLocal o τ k Stmt l s mem alloc Γ o false perm full val new Γ τ m k o τ k CLocal o τ k l labels s P State k Stmt l local τ s mem free o m s Es s subst Es s l labels s P State CStmt Es k Stmt l s m k Es k CStmt Es k l labels s P State k Stmt l subst Es s m P S2 Stmt mx s s scase mx P State k Stmt s m s o τ s local τ s mx cases s o dom indexset m P State CLocal o τ k Stmt mx s mem alloc Γ o false perm full val new Γ τ m s Es s subst Es s maybe CSwitch Es None mx cases s P State CStmt Es k Stmt mx s m P S2 Undef P S2 end Proof intros p case p simpl eauto 2 by intros simpl eauto by intros simpl eauto by intros simpl eauto Qed Lemma rcstep expr inv P state K Prop m k Ek Ω v S2 Γ δ ρ ₛ State Ek k Expr Ω v m S2 match Ek with CExpr e P State k Stmt e mem unlock Ω m P S2 CExpr e ret P State k Stmt v ret e mem unlock Ω m P S2 CExpr e if s1 else s2 vb v VBase vb base val branchable m vb base val is 0 vb P State CStmt if e else s2 k Stmt s1 mem unlock Ω m vb v VBase vb base val branchable m vb base val is 0 vb P State CStmt if e s1 else k Stmt s2 mem unlock Ω m vb v VBase vb base val branchable m vb P State k Undef UndefBranch if s1 else s2 Ω v m P S2 CExpr e switch s τ i x v intV τ i x Some x cases s P State CStmt switch e k Stmt Some x s mem unlock Ω m τ i x v intV τ i x Some x cases s None cases s P State CStmt switch e k Stmt None s mem unlock Ω m τ i x v intV τ i x Some x cases s None cases s P State k Stmt switch e s mem unlock Ω m vb s v VBase vb base val branchable m vb P State k Undef UndefBranch switch s Ω VBase vb m P S2 P S2 end Proof intros p pattern S2 apply rcstep focus inv p try solve intros simplify equality eauto intros Ee e1 e2 m2 Hv p simplify list subst equality Hv inversion p intros Ee Ω f τ s τ Ω s vs Hv simplify list subst equality Hv intros Ee e1 Hv simplify list subst equality Hv by destruct EVal not redex Ω inr v Qed Lemma rcstep stmt up inv P state K Prop m k Ek s S2 Γ δ ρ ₛ State Ek k Stmt s m S2 match Ek with CStmt s2 P State CStmt s k Stmt s2 m P S2 CStmt s1 P State k Stmt s1 s m P S2 CStmt catch P State k Stmt catch s m P S2 CStmt loop P State k Stmt loop s m P S2 CStmt if e else s2 P State k Stmt if e s else s2 m P S2 CStmt if e s1 else P State k Stmt if e s1 else s m P S2 CStmt switch e P State k Stmt switch e s m P S2 CLocal o τ P State k Stmt local τ s mem free o m P S2 CParams f o τ s P State k Return f voidV foldr mem free m o τ s 1 P S2 P S2 end Proof intros p pattern S2 apply rcstep focus inv p intros simplify equality eauto Qed Lemma rcstep stmt top inv P state K Prop m k Ek v s S2 Γ δ ρ ₛ State Ek k Stmt v s m S2 match Ek with CStmt Es P State k Stmt v subst Es s m P S2 CParams f o τ s P State k Return f v foldr mem free m o τ s 1 P S2 CLocal o τ P State k Stmt v local τ s mem free o m P S2 P S2 end Proof intros p pattern S2 apply rcstep focus inv p intros simplify equality eauto Qed End inversion The previously defined inversion schemes all work for reductions of a different shape We therefore define the tactic fast inv rcstep to automatically pick the most suitable inversion scheme It also performs the necessary generalization of assumptions Ltac fast inv rcstep H match type of H with ₛ S1 S2 try match S1 with State Stmt d is var d destruct d try done end is var S2 block goal repeat match goal with H context S2 var neq H H revert H end pattern S2 first apply rcstep expr inv H apply rcstep stmt up inv H apply rcstep stmt top inv H apply rcstep focus inv H clear H intros unblock goal end Some reduction are not of a shape that fits any of the previously defined inversion schemes The tactic slow inv rcstep inverts a reduction using Coq s standard inversion tactic and works for reductions of all shapes Ltac slow inv rcstep H match type of H with ₛ S1 S2 inversion H clear H end The tactic inv rcstep inverts a reduction step and performs some clean up and discharges impossible cases afterwards Tactic Notation inv rcstep hyp H match type of H with ₛ S1 S2 perform the actual inversion and print a message for debugging in case slow inversion has been used first fast inv rcstep H idtac slow inversion on S1 slow inv rcstep H clean up and discharge impossible cases simplify list subst equality repeat match goal with done H suffix of progress simpl in H simplify suffix of H ₕ by inversion H H is redex inversion H H direction in d s direction out d s by destruct direction in out d s H labels subst rewrite sctx item subst labels in H first by decompose elem of decompose elem of idtac end end Tactic Notation inv rcstep match goal with H ₛ inv rcstep H end Tactic Notation inv rcsteps hyp H as simple intropattern H2 let H fresh in rename H into H inversion H as H2 clear H try subst Tactic Notation inv rcsteps hyp H inv rcsteps H as Tactic Notation last rcstep hyp H let H fresh in inv rcsteps H as H solve inv rcstep H Step tactics Ltac do rcstep let go first econstructor by eauto with cstep by eauto with cstep in match goal with Γ δ ρ ₛ State k Stmt d s m S iter fun s change Γ δ ρ ₛ State k Stmt d s m S go quote stmt s Γ δ ρ ₛ State k Expr e m S iter fun e change Γ δ ρ ₛ State k Expr e m S go quote expr e go end Ltac solve rcred repeat match goal with red rcstep State Stmt d is var d destruct d simplify equality try contradiction H l red rcstep State Stmt l progress decompose elem of H H mx red rcstep State Stmt mx progress decompose elem of H end match goal with red rcstep eexists do rcstep by eauto with cstep end Theorems Section theorems Context Env K Γ env K δ funenv K Implicit Types k ctx K Lemma rlocals nil k rlocals k locals k Proof by induction k as f equal Qed Lemma rlocals app k1 k2 ρ rlocals ρ k1 k2 rlocals rlocals ρ k2 k1 Proof induction k1 as simpl auto with f equal Qed Lemma cstep rcstep S1 S2 Γ δ ₛ S1 S2 Γ δ ₛ S1 S2 Proof by destruct 1 constructor rewrite rlocals nil Qed Lemma csteps rcsteps S1 S2 Γ δ ₛ S1 S2 Γ δ ₛ S1 S2 Proof induction 1 econstructor eauto using cstep rcstep Qed Lemma rcstep cstep S1 S2 Γ δ ₛ S1 S2 Γ δ ₛ S1 S2 Proof by destruct 1 constructor rewrite rlocals nil Qed Lemma rcred ectx E ectx

    Original URL path: http://robbertkrebbers.nl/research/ch2o/restricted_smallstep.html (2015-08-10)
    Open archived version from archive

  • Module axiomatic_expressions_help
    inversion clear Hframe as mA mf Hm simplify equality simplify mem disjoint hyps split intros S p rewrite ectx full to item correct i apply rcred ectx assert ms i delete i nat ms list mf mA by rewrite app comm cons sep disjoint equiv delete eapply ax red ax expr cond ρ A ax expr post Ps i τ lrs i with Δ n ms i InExpr delete i nat ms list mf mA eauto using cmap union list lookup valid econstructor auto 1 by rewrite sep associative sep union delete by auto apply cmap union valid 2 auto apply cmap union list valid Forall delete Forall vlookup eauto using cmap union list lookup valid simpl contradict Hi eauto using ax expr post expr nf eauto using ax graph weaken pattern S apply rcstep expr depsubst inv p clear p clear i Hi intros i e m2 p assert ms i delete i nat ms list mf mA by rewrite app comm cons sep disjoint equiv delete feed inversion ax step ax expr cond ρ A ax expr post Ps i τ lrs i Γ δ Δ ρ n Expr es i ms i ms i delete i nat ms list mf mA InExpr delete i nat ms list mf mA State Expr e m2 as Δ n m Hunframe subst auto eauto using cmap union list lookup valid constructor rewrite sep associative by auto auto apply cmap union valid 2 auto apply cmap union list valid Forall delete Forall vlookup eauto using cmap union list lookup valid by rewrite sep union delete by done by rewrite sep union delete by done eauto using ax graph weaken clear Hm inversion clear Hunframe simplify equality simplify mem disjoint hyps apply mk ax next with Δ m delete i nat ms list simpl auto constructor auto by rewrite sep associative by auto rewrite ectx full subst locks HE left id L rewrite sep union insert by auto rewrite mem locks union list by rewrite sep disjoint equiv insert auto apply union list preserving Forall2 fmap Forall2 vlookup intros j destruct decide i j subst by rewrite vlookup insert by rewrite vlookup insert ne rewrite sep union insert by auto assert mf mA vinsert i m ms rewrite sep disjoint equiv insert auto apply IH eauto using indexes valid weaken funenv valid weaken intros j destruct decide i j subst by rewrite vlookup insert rewrite vlookup insert ne by done eauto using cmap union list delete lookup valid exists mA split ands eauto using assert weaken indexes valid weaken intros j destruct decide i j subst by rewrite vlookup insert by rewrite vlookup insert ne intros j destruct decide i j subst by rewrite vlookup insert rewrite vlookup insert ne by done apply ax graph weaken with Δ S n eauto clear i Hi intros i E Ω f τ s τ Ω s vs Hesi p assert Ω Ω s mem locks ms i as H Ω transitivity locks es i

    Original URL path: http://robbertkrebbers.nl/research/ch2o/axiomatic_expressions_help.html (2015-08-10)
    Open archived version from archive

  • Module base
    m λ f mbind f m only parsing C scope Notation f mbind f only parsing C scope Notation λ m f mbind f m only parsing C scope Notation x y z y λ x z at level 65 only parsing next at level 35 right associativity C scope Infix fmap at level 65 right associativity C scope Class MGuard M Type Type mguard P dec Decision P A M A M A Notation guard P o mguard P o at level 65 only parsing next at level 35 right associativity C scope Operations on maps In this section we define operational type classes for the operations on maps In the file fin maps we will axiomatize finite maps The function lookup m k should yield the element at key k in m Class Lookup K A M Type lookup K M option A Instance Params lookup 4 Notation m i lookup i m at level 20 C scope Notation lookup only parsing C scope Notation m λ i lookup i m only parsing C scope Notation i lookup i only parsing C scope Arguments lookup simpl nomatch The function insert k a m should update the element at key k with value a in m Class Insert K A M Type insert K A M M Instance Params insert 4 Notation k a insert k a at level 5 right associativity format k a C scope Arguments insert simpl nomatch The function delete delete k m should delete the value at key k in m If the key k is not a member of m the original map should be returned Class Delete K M Type delete K M M Instance Params delete 3 Arguments delete simpl nomatch The function alter f k m should update the value at key k using the function f which is called with the original value Class AlterD K A M Type f A A alter K M M Notation Alter K A M f A A AlterD K A M f type Instance Params alter 5 Arguments alter simpl nomatch The function alter f k m should update the value at key k using the function f which is called with the original value at key k or None if k is not a member of m The value at k should be deleted if f yields None Class PartialAlter K A M Type partial alter option A option A K M M Instance Params partial alter 4 Arguments partial alter simpl nomatch The function dom C m should yield the domain of m That is a finite collection of type C that contains the keys that are a member of m Class Dom K M Type dom C Empty C Union C Singleton K C M C Instance Params dom 7 Arguments dom simpl nomatch The function merge f m1 m2 should merge the maps m1 and m2 by constructing a new map whose value at key k is f m1 k m2 k provided that k is a member of either m1 or m2 Class Merge A M Type merge option A option A option A M M M Instance Params merge 3 Arguments merge simpl nomatch We lift the insert and delete operation to lists of elements Definition insert list Insert K A M l list K A m M M fold right λ p fst p snd p m l Instance Params insert list 4 Definition delete list Delete K M l list K m M M fold right delete m l Instance Params delete list 3 Definition insert consecutive Insert nat A M i nat l list A m M M fold right λ x f i i x f S i λ m l i Instance Params insert consecutive 3 The function union with f m1 m2 is supposed to yield the union of m1 and m2 using the function f to combine values of members that are in both m1 and m2 Class UnionWith A M Type union with A A option A M M M Instance Params union with 3 Similarly for intersection and difference Class IntersectionWith A M Type intersection with A A option A M M M Instance Params intersection with 3 Class DifferenceWith A M Type difference with A A option A M M M Instance Params difference with 3 Definition intersection with list IntersectionWith A M f A A option A M list M M fold right intersection with f Arguments intersection with list Common properties These operational type classes allow us to refer to common mathematical properties in a generic way For example for injectivity of k it allows us to write injective k instead of app inv head k Class Injective A B R S f A B injective x y A S f x f y R x y Class Idempotent A R f A A A idempotent x R f x x x Class Commutative A B R f B B A commutative x y R f x y f y x Class LeftId A R i A f A A A left id x R f i x x Class RightId A R i A f A A A right id x R f x i x Class Associative A R f A A A associative x y z R f x f y z f f x y z Class LeftAbsorb A R i A f A A A left absorb x R f i x i Class RightAbsorb A R i A f A A A right absorb x R f x i i Class AntiSymmetric A R A A Prop anti symmetric x y R x y R y x x y Arguments injective Arguments idempotent Arguments commutative Arguments left id Arguments right id Arguments associative Arguments left absorb Arguments right absorb Arguments anti symmetric Instance Commutative Proof red intuition Qed Instance Commutative Proof red intuition Qed Instance Associative Proof red

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/base.html (2015-08-10)
    Open archived version from archive

  • Module tactics
    tac2 tac1 tac2 tac1 tac2 The tactic is non dependent H determines whether the goal s conclusion or assumptions depend on H Tactic Notation is non dependent constr H match goal with context H fail 1 context H fail 1 idtac end Ltac var eq x1 x2 match x1 with x2 idtac fail 1 end Ltac var neq x1 x2 match x1 with x2 fail 1 idtac end Tactic Notation repeat on hyps tactic3 tac repeat match goal with H progress tac H end Ltac block hyps repeat on hyps fun H match type of H with block idtac T change block T in H end Ltac unblock hyps unfold block in The tactic injection H is a variant of injection that introduces the generated equalities Ltac injection H block goal injection H clear H intros unblock goal The tactic simplify equality repeatedly substitutes discriminates and injects equalities and tries to contradict impossible inequalities Ltac simplify equality repeat match goal with H by destruct H H False by destruct H H x subst x H x subst x H discriminate H H f f apply injective f in H H injection H H x x clear H end Coq s default remember tactic does have an option to name the generated equality The following tactic extends remember to do so Tactic Notation remember constr t as ident x ident E remember t as x match goal with E x rename E into E end Given a tactic tac2 generating a list of terms iter tac1 tac2 runs tac x for each element x until tac x succeeds If it does not suceed for any element of the generated list the whole tactic wil fail Tactic Notation iter tactic tac tactic l let rec go l match l with x l tac x go l end in go l Given H A 1 A n B where each A i is non dependent the tactic feed tac H tac by creates a subgoal for each A i and calls tac p with the generated proof p of B Tactic Notation feed tactic tac constr H let rec go H let T type of H in lazymatch eval hnf in T with T1 T2 let HT1 fresh feed in assert T1 as HT1 go H HT1 clear HT1 T1 tac H end in go H The tactic efeed tac H is similar to feed but it also instantiates dependent premises of H with evars Tactic Notation efeed tactic tac constr H let rec go H let T type of H in lazymatch eval hnf in T with T1 T2 let HT1 fresh feed in assert T1 as HT1 go H HT1 clear HT1 T1 let e fresh feed in evar e T1 let e eval unfold e in e in clear e go H e T1 tac H end in go H The following variants of pose proof specialize inversion and destruct use the feed tactic before invoking the actual tactic Tactic

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/tactics.html (2015-08-10)
    Open archived version from archive



  •