lifting.v 4.61 KB
Newer Older
1 2
From iris.program_logic Require Export weakestpre.
From iris.program_logic Require Import wsat ownership.
Robbert Krebbers's avatar
Robbert Krebbers committed
3
Local Hint Extern 10 (_  _) => omega.
Robbert Krebbers's avatar
Robbert Krebbers committed
4
Local Hint Extern 100 (_  _) => set_solver.
Robbert Krebbers's avatar
Robbert Krebbers committed
5
Local Hint Extern 10 ({_} _) =>
6 7 8
  repeat match goal with
  | H : wsat _ _ _ _ |- _ => apply wsat_valid in H; last omega
  end; solve_validN.
Robbert Krebbers's avatar
Robbert Krebbers committed
9 10

Section lifting.
11
Context {Λ : language} {Σ : iFunctor}.
12 13 14
Implicit Types v : val Λ.
Implicit Types e : expr Λ.
Implicit Types σ : state Λ.
15 16
Implicit Types P Q : iProp Λ Σ.
Implicit Types Φ : val Λ  iProp Λ Σ.
Robbert Krebbers's avatar
Robbert Krebbers committed
17

18
Notation wp_fork ef := (default True ef (flip (wp ) (λ _, True)))%I.
19

Robbert Krebbers's avatar
Robbert Krebbers committed
20
Lemma wp_lift_step E1 E2
21
    (φ : expr Λ  state Λ  option (expr Λ)  Prop) Φ e1 σ1 :
Ralf Jung's avatar
Ralf Jung committed
22
  E2  E1  to_val e1 = None 
23
  reducible e1 σ1 
Robbert Krebbers's avatar
Robbert Krebbers committed
24
  ( e2 σ2 ef, prim_step e1 σ1 e2 σ2 ef  φ e2 σ2 ef) 
Ralf Jung's avatar
Ralf Jung committed
25
  (|={E1,E2}=>  ownP σ1    e2 σ2 ef,
26 27
    ( φ e2 σ2 ef  ownP σ2) - |={E2,E1}=> WP e2 @ E1 {{ Φ }}  wp_fork ef)
   WP e1 @ E1 {{ Φ }}.
Robbert Krebbers's avatar
Robbert Krebbers committed
28
Proof.
Ralf Jung's avatar
Ralf Jung committed
29 30
  intros ? He Hsafe Hstep. rewrite pvs_eq wp_eq.
  uPred.unseal; split=> n r ? Hvs; constructor; auto.
Robbert Krebbers's avatar
Robbert Krebbers committed
31 32
  intros rf k Ef σ1' ???; destruct (Hvs rf (S k) Ef σ1')
    as (r'&(r1&r2&?&?&Hwp)&Hws); auto; clear Hvs; cofe_subst r'.
Ralf Jung's avatar
Ralf Jung committed
33
  destruct (wsat_update_pst k (E2  Ef) σ1 σ1' r1 (r2  rf)) as [-> Hws'].
34
  { apply equiv_dist. rewrite -(ownP_spec k); auto. }
35
  { by rewrite assoc. }
Robbert Krebbers's avatar
Robbert Krebbers committed
36
  constructor; [done|intros e2 σ2 ef ?; specialize (Hws' σ2)].
Robbert Krebbers's avatar
Robbert Krebbers committed
37
  destruct (λ H1 H2 H3, Hwp e2 σ2 ef k (update_pst σ2 r1) H1 H2 H3 rf k Ef σ2)
Robbert Krebbers's avatar
Robbert Krebbers committed
38
    as (r'&(r1'&r2'&?&?&?)&?); auto; cofe_subst r'.
39
  { split. by eapply Hstep. apply ownP_spec; auto. }
40
  { rewrite (comm _ r2) -assoc; eauto using wsat_le. }
41
  exists r1', r2'; split_and?; try done. by uPred.unseal; intros ? ->.
Robbert Krebbers's avatar
Robbert Krebbers committed
42
Qed.
43

44
Lemma wp_lift_pure_step E (φ : expr Λ  option (expr Λ)  Prop) Φ e1 :
Robbert Krebbers's avatar
Robbert Krebbers committed
45
  to_val e1 = None 
46
  ( σ1, reducible e1 σ1) 
Robbert Krebbers's avatar
Robbert Krebbers committed
47
  ( σ1 e2 σ2 ef, prim_step e1 σ1 e2 σ2 ef  σ1 = σ2  φ e2 ef) 
48
  (  e2 ef,  φ e2 ef  WP e2 @ E {{ Φ }}  wp_fork ef)  WP e1 @ E {{ Φ }}.
Robbert Krebbers's avatar
Robbert Krebbers committed
49
Proof.
Ralf Jung's avatar
Ralf Jung committed
50 51
  intros He Hsafe Hstep; rewrite wp_eq; uPred.unseal.
  split=> n r ? Hwp; constructor; auto.
52
  intros rf k Ef σ1 ???; split; [done|]. destruct n as [|n]; first lia.
Robbert Krebbers's avatar
Robbert Krebbers committed
53
  intros e2 σ2 ef ?; destruct (Hstep σ1 e2 σ2 ef); auto; subst.
Robbert Krebbers's avatar
Robbert Krebbers committed
54
  destruct (Hwp e2 ef k r) as (r1&r2&Hr&?&?); auto.
55 56 57
  exists r1,r2; split_and?; try done.
  - rewrite -Hr; eauto using wsat_le.
  - uPred.unseal; by intros ? ->.
Robbert Krebbers's avatar
Robbert Krebbers committed
58
Qed.
59 60

(** Derived lifting lemmas. *)
61
Import uPred.
62

63
Lemma wp_lift_atomic_step {E Φ} e1
64 65
    (φ : expr Λ  state Λ  option (expr Λ)  Prop) σ1 :
  atomic e1 
66
  reducible e1 σ1 
67
  ( e2 σ2 ef,
68 69
    prim_step e1 σ1 e2 σ2 ef  φ e2 σ2 ef) 
  ( ownP σ1    v2 σ2 ef,  φ (of_val v2) σ2 ef  ownP σ2 - Φ v2  wp_fork ef)
70
   WP e1 @ E {{ Φ }}.
71
Proof.
72 73 74
  intros. rewrite -(wp_lift_step E E (λ e2 σ2 ef,
    is_Some (to_val e2)  φ e2 σ2 ef) _ e1 σ1) //;
    try by (eauto using atomic_not_val, atomic_step).
75 76 77
  rewrite -pvs_intro. apply sep_mono, later_mono; first done.
  apply forall_intro=>e2'; apply forall_intro=>σ2'.
  apply forall_intro=>ef; apply wand_intro_l.
78
  rewrite always_and_sep_l -assoc -always_and_sep_l.
79
  apply const_elim_l=>-[[v2 Hv] ?] /=.
80
  rewrite -pvs_intro.
81 82 83
  rewrite (forall_elim v2) (forall_elim σ2') (forall_elim ef) const_equiv //.
  rewrite left_id wand_elim_r -(wp_value _ _ e2' v2) //.
  by erewrite of_to_val.
84 85
Qed.

86
Lemma wp_lift_atomic_det_step {E Φ e1} σ1 v2 σ2 ef :
87
  atomic e1 
88
  reducible e1 σ1 
89 90
  ( e2' σ2' ef', prim_step e1 σ1 e2' σ2' ef' 
    σ2 = σ2'  to_val e2' = Some v2  ef = ef') 
91
  ( ownP σ1   (ownP σ2 - Φ v2  wp_fork ef))  WP e1 @ E {{ Φ }}.
92
Proof.
93 94
  intros. rewrite -(wp_lift_atomic_step _ (λ e2' σ2' ef',
    σ2 = σ2'  to_val e2' = Some v2  ef = ef') σ1) //.
95
  apply sep_mono, later_mono; first done.
96
  apply forall_intro=>e2'; apply forall_intro=>σ2'; apply forall_intro=>ef'.
97
  apply wand_intro_l.
98 99
  rewrite always_and_sep_l -assoc -always_and_sep_l to_of_val.
  apply const_elim_l=>-[-> [[->] ->]] /=. by rewrite wand_elim_r.
100 101
Qed.

102
Lemma wp_lift_pure_det_step {E Φ} e1 e2 ef :
103 104
  to_val e1 = None 
  ( σ1, reducible e1 σ1) 
105
  ( σ1 e2' σ2 ef', prim_step e1 σ1 e2' σ2 ef'  σ1 = σ2  e2 = e2'  ef = ef')
106
   (WP e2 @ E {{ Φ }}  wp_fork ef)  WP e1 @ E {{ Φ }}.
107
Proof.
108 109
  intros.
  rewrite -(wp_lift_pure_step E (λ e2' ef', e2 = e2'  ef = ef') _ e1) //=.
110
  apply later_mono, forall_intro=>e'; apply forall_intro=>ef'.
111
  by apply impl_intro_l, const_elim_l=>-[-> ->].
112 113
Qed.

Robbert Krebbers's avatar
Robbert Krebbers committed
114
End lifting.