Iris issueshttps://gitlab.mpi-sws.org/iris/iris/-/issues2020-11-05T08:41:29Zhttps://gitlab.mpi-sws.org/iris/iris/-/issues/371Add validI lemmas for discrete RAs2020-11-05T08:41:29ZRalf Jungjung@mpi-sws.orgAdd validI lemmas for discrete RAsOur discrete RAs lack "validI" lemmas that reflect their validity into an equivalent logical statement. Those are rarely needed because whenever one uses the proof mode, one can just turn validity into a Coq assumption and then use the `...Our discrete RAs lack "validI" lemmas that reflect their validity into an equivalent logical statement. Those are rarely needed because whenever one uses the proof mode, one can just turn validity into a Coq assumption and then use the `Prop`-level lemmas. But e.g. when proving equivalences, it can be useful to have a way to rewrite validity into an equivalent logical statement.
https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/558 added the lemma for frac, but other RAs are still missing:
* [ ] `gset_disj`
* [ ] `coPset`, `coPset_disj`
* [ ] `sts`
* [ ] `dfrac`https://gitlab.mpi-sws.org/iris/iris/-/issues/369Document HeapLang2021-07-01T15:42:37ZRalf Jungjung@mpi-sws.orgDocument HeapLangThe HeapLang syntax, operational semantics, and lifted weakestpre rules should probably be stated in the Iris Documentation. Currently [my thesis](https://people.mpi-sws.org/~jung/phd/thesis-screen.pdf#figure.3.1) and the ["Future is Our...The HeapLang syntax, operational semantics, and lifted weakestpre rules should probably be stated in the Iris Documentation. Currently [my thesis](https://people.mpi-sws.org/~jung/phd/thesis-screen.pdf#figure.3.1) and the ["Future is Ours" paper](https://plv.mpi-sws.org/prophecies/paper.pdf#%5B%7B%22num%22%3A171%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C45.828%2C641.295%2Cnull%5D) describe overlapping but incomparable subsets of the operational semantics, and there are likely bits that are missing from both.https://gitlab.mpi-sws.org/iris/iris/-/issues/368Remove `inv` lemmas for agree/auth/view/etc and add `_L` variants to the ↔ lemma2020-11-04T09:54:59ZRobbert KrebbersRemove `inv` lemmas for agree/auth/view/etc and add `_L` variants to the ↔ lemmaSee the discussion here https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/551#note_58488See the discussion here https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/551#note_58488https://gitlab.mpi-sws.org/iris/iris/-/issues/366`Export` everywhere does not permit consistent shadowing2020-11-05T11:54:13ZRalf Jungjung@mpi-sws.org`Export` everywhere does not permit consistent shadowingWhen using `Export`, even if imports are ordered consistently, there is sometimes no way to obtain consistent shadowing:
```
From stdpp Require base.
Module or.
Export stdpp.base.
Definition or_comm := 10.
End or.
Module and.
Expo...When using `Export`, even if imports are ordered consistently, there is sometimes no way to obtain consistent shadowing:
```
From stdpp Require base.
Module or.
Export stdpp.base.
Definition or_comm := 10.
End or.
Module and.
Export stdpp.base.
Definition and_comm := 11.
End and.
Module A.
Import or and.
Locate or_comm.
(*
Constant stdpp.base.or_comm
Constant Coq.Init.Logic.or_comm (shorter name to refer to it in current context is Logic.or_comm)
Constant Top.or.or_comm (shorter name to refer to it in current context is or.or_comm)
*)
Locate and_comm.
(*
Constant Top.and.and_comm
Constant Coq.Init.Logic.and_comm (shorter name to refer to it in current context is Logic.and_comm)
Constant stdpp.base.and_comm (shorter name to refer to it in current context is base.and_comm)
*)
End A.
```
Here, importing `and` overwrites `or_comm` because of the `stdpp.base` export.
I think the only way to avoid this is to avoid `Export`ing except when the re-exported symbols are conceptually really part of that library (such as `stdpp.prelude`).https://gitlab.mpi-sws.org/iris/iris/-/issues/364Implement typeclasses analogous to Fractional and AsFractional for discardabl...2020-10-21T10:59:16ZTej Chajedtchajed@mit.eduImplement typeclasses analogous to Fractional and AsFractional for discardable fractionsI think it would make sense to have a library analogous to fractional for discardable fractions. I think it needs to say `Φ (p ⋅ q) ⊣⊢ Φ p ∗ Φ q` like for fractions (using dfrac composition) and also perhaps `Persistent (Φ DfracDiscarded)`.I think it would make sense to have a library analogous to fractional for discardable fractions. I think it needs to say `Φ (p ⋅ q) ⊣⊢ Φ p ∗ Φ q` like for fractions (using dfrac composition) and also perhaps `Persistent (Φ DfracDiscarded)`.https://gitlab.mpi-sws.org/iris/iris/-/issues/359Use the IPM to prove some example IPM extension theorems2020-10-21T11:00:32ZTej Chajedtchajed@mit.eduUse the IPM to prove some example IPM extension theoremsThe current proofs for some HeapLang tactics use a bunch of separation logic theorems manually, like this proof:
```coq
Lemma tac_wp_free Δ Δ' s E i K l v Φ :
MaybeIntoLaterNEnvs 1 Δ Δ' →
envs_lookup i Δ' = Some (false, l ↦ v)%I →
...The current proofs for some HeapLang tactics use a bunch of separation logic theorems manually, like this proof:
```coq
Lemma tac_wp_free Δ Δ' s E i K l v Φ :
MaybeIntoLaterNEnvs 1 Δ Δ' →
envs_lookup i Δ' = Some (false, l ↦ v)%I →
(let Δ'' := envs_delete false i false Δ' in
envs_entails Δ'' (WP fill K (Val $ LitV LitUnit) @ s; E {{ Φ }})) →
envs_entails Δ (WP fill K (Free (LitV l)) @ s; E {{ Φ }}).
Proof.
rewrite envs_entails_eq=> ? Hlk Hfin.
rewrite -wp_bind. eapply wand_apply; first exact: wp_free.
rewrite into_laterN_env_sound -later_sep envs_lookup_split //; simpl.
rewrite -Hfin wand_elim_r (envs_lookup_sound' _ _ _ _ _ Hlk).
apply later_mono, sep_mono_r, wand_intro_r. rewrite right_id //.
Qed.
```
It would be much nicer to use the proof mode to do these proofs, which is also nicely circular because we're extending the proof mode using the proof mode. For example, the above proof can be written:
```coq
rewrite envs_entails_eq=> ? Hlk Hfin.
rewrite into_laterN_env_sound.
iIntros "HΔ'".
iApply wp_bind.
pose proof (envs_lookup_sound' _ false _ _ _ Hlk) as HΔ'split.
set (Δ'':=envs_delete false i false Δ') in *.
iDestruct (HΔ'split with "HΔ'") as "[Hl HΔ'']".
iApply (wp_free with "Hl").
iNext. iIntros "_".
iApply (Hfin with "HΔ''").
```
This proof isn't shorter but you can figure out how to write such a proof using only the proof mode rather than convoluted uses of theorems like `sep_mono_r` and `wand_intro_r`. This particular case become slightly messier because if you do `iDestruct envs_lookup_sound with "HΔ'"` then the proof mode reduces `envs_delete` and the result is horrendous.
I don't think we need to re-do all of the proofs; I'm thinking having a few such examples would go a long way as examples that demonstrate how to extend the IPM in a nice way. We couldn't port all of the theorems anyway since of course some of these theorems are actually used to implement the IPM.https://gitlab.mpi-sws.org/iris/iris/-/issues/357Cancelable locks2020-10-21T11:00:44ZRobbert KrebbersCancelable locksIt would be really useful to have a version of cancelable locks, where the `is_lock` predicate is equipped with a fraction. That way, we could have a couple of things:
1. A Hoare triple for the physical free operation `{{ is_lock lk 1 R...It would be really useful to have a version of cancelable locks, where the `is_lock` predicate is equipped with a fraction. That way, we could have a couple of things:
1. A Hoare triple for the physical free operation `{{ is_lock lk 1 R }} free lk {{ R }}`
2. A rule `is_lock lk 1 R ==∗ ▷ R ∗ (▷ R' ==∗ is_lock lk 1 R')` that allows a "strong update" of the payload of the lock.
Now that we have the discardable fractional permissions, we could use those to get back the ordinary lock-spec by picking the fraction to be `DfracDiscarded`.
To implement this, we probably first want to generalize cancelable invariants, by a.) adding a discardable fraction b.) adding a rule for changing the proposition in case one owns the entire fraction.
Questions:
- For locks, do we want to equip `is_lock` with a fraction, or do we want to add a token `lock_own` (which would be timeless).
- If we equip `is_lock` with a fraction, we won't break backwards compatibility that much. One just needs to add `DfracDiscarded` everywhere. If we have a token for the fraction, backwards compatibility is a bigger issue. We could of course define `is_lock ... := new_is_lock ... ∗ lock_own DfracDiscarded` or something like that.
Any thoughts?https://gitlab.mpi-sws.org/iris/iris/-/issues/354Discardable camera improvements2020-10-09T13:50:33ZRalf Jungjung@mpi-sws.orgDiscardable camera improvements## Generalization
I think the variant of `dfrac` that I implemented with https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/531 can be generalized to a "discardable-anything":
```coq
Inductive discardable (A: cmraT) :=
| DOwn : A →...## Generalization
I think the variant of `dfrac` that I implemented with https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/531 can be generalized to a "discardable-anything":
```coq
Inductive discardable (A: cmraT) :=
| DOwn : A → dfrac
| DDiscarded : dfrac
| DBoth : A → dfrac.
```
with validity something like
```coq
Instance discardable_valid (A: cmraT) : Valid (discardable A) := λ x,
match x with
| DOwn q => ✓ q
| DDiscarded => True
| DBoth q => exists p, ✓ (q ⋅ p)
end%Qc.
```
I think this should work... what I am not sure about is if this is useful.^^
## old [discarded](https://gitlab.mpi-sws.org/iris/iris/-/issues/354#note_57686) idea: `option Qp`
After https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/531, the public interface of `dfrac` can basically be described via a smart constructor that takes `option Qp` -- in fact I am adding such a notation in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/486. We can probably rephrase all the existing lemmas in terms of that single constructor, and @robbertkrebbers agrees that that would make a better interface.
Cc @simonfv @tchajedhttps://gitlab.mpi-sws.org/iris/iris/-/issues/352Tracking issue for records2021-03-18T09:21:04ZRalf Jungjung@mpi-sws.orgTracking issue for records@tchajed, @robbertkrebbers and me are discussing ideas for equipping Iris with support for "named records", based on a first implementation of sch a scheme by Tej for Perennial. This is a tracking issue where we track which pieces of wor...@tchajed, @robbertkrebbers and me are discussing ideas for equipping Iris with support for "named records", based on a first implementation of sch a scheme by Tej for Perennial. This is a tracking issue where we track which pieces of work depend on what, and what needs to be done next.
The current status is that some unforeseen issues came up after merging https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/479, but we'd rather not change the naming system until we have a way to reliably control the names used for existentials in a record. Record design itself [is blocked on some fundamental questions](https://gitlab.mpi-sws.org/iris/iris/-/issues/352#note_65075).
* [List of related MRs](https://gitlab.mpi-sws.org/iris/iris/-/merge_requests?scope=all&utf8=%E2%9C%93&state=all&label_name[]=T-records)https://gitlab.mpi-sws.org/iris/iris/-/issues/351Decouple framing and IntoSep2021-10-01T18:44:20ZRalf Jungjung@mpi-sws.orgDecouple framing and IntoSepCurrently, `IntoSep` does a few things that can be rather expensive, like `AsFractional` conversion. This is very useful for destruct patterns, but `IntoSep` is also used for framing, and there we want to be cheap. @tchajed already disab...Currently, `IntoSep` does a few things that can be rather expensive, like `AsFractional` conversion. This is very useful for destruct patterns, but `IntoSep` is also used for framing, and there we want to be cheap. @tchajed already disabled some `IntoSep` instances in Perennial for this reason.
It might make sense to have a separate IntoSep for framing that is more optimized for performance and, for example, does not try to exploit fractional things.
This is somewhat similar to https://gitlab.mpi-sws.org/iris/iris/-/issues/186.
To avoid making a mess, probably we should figure out https://gitlab.mpi-sws.org/iris/iris/-/issues/139 first.https://gitlab.mpi-sws.org/iris/iris/-/issues/349Parameterize WP (and more) by the notion of fancy update2020-09-22T07:47:46ZRalf Jungjung@mpi-sws.orgParameterize WP (and more) by the notion of fancy updateFor Perennial, @jtassaro developed a notion of "fancy updates" that satisfies all the laws we have in Iris, plus way more. Unfortunately this means we cannot directly use anything from `base_logc/lib` and above, even though all these pro...For Perennial, @jtassaro developed a notion of "fancy updates" that satisfies all the laws we have in Iris, plus way more. Unfortunately this means we cannot directly use anything from `base_logc/lib` and above, even though all these proofs do go through unchanged.
This change is likely not canonical enough to be upstreamable, and I see no way to make our notion of fancy updates itself general enough that @jtassaro's update are an instance of them. The design space is very wide open here.
It would thus be useful if we could parameterize the definition of WP by the notion of fancy update, and similar for some of the things in `base_logic/lib` -- everything that mentions fancy updates, basically (or at least anything useful; I don't think it is worth doing this with STS and auth). Maybe some things can be changed to use basic updates instead of fancy updates, which would avoid the need for parameterization.
Even semantic invariants themselves can be defined generally for any fancy update; the only thing that each update would need to prove is the allocation lemma(s).
@robbertkrebbers what do you think?https://gitlab.mpi-sws.org/iris/iris/-/issues/348Always enabled invariants2020-09-30T19:14:58ZRalf Jungjung@mpi-sws.orgAlways enabled invariants@jtassaro has a fork of Iris with some interesting features that we might want to copy. In particular, for Perennial he added "always-enabled invariants", which have no mask, can always be opened, but cannot be kept open. The accessor le...@jtassaro has a fork of Iris with some interesting features that we might want to copy. In particular, for Perennial he added "always-enabled invariants", which have no mask, can always be opened, but cannot be kept open. The accessor lemma is (roughly):
```
Lemma ae_inv_acc_bupd E P Q :
ae_inv P -∗
(▷ P ==∗ ◇ (▷ P ∗ Q)) -∗
|={E}=> Q.
```
This seems like it could be useful beyond Perennial. In particular, this forms a layer of abstraction *beneath* the invariants that we have: `ownI` (underlying `inv`) can be defined in terms of `ae_inv` with something like
```
ownI i Q := Q ∗ ownD {[i]} ∨ ownE {[i]})
```
(That's not how Joe defined them, but I am pretty sure it could be done.)https://gitlab.mpi-sws.org/iris/iris/-/issues/347"solve_inG" is very slow for larger RA combinators2021-03-03T13:07:08ZRalf Jungjung@mpi-sws.org"solve_inG" is very slow for larger RA combinatorsIn his Iris fork, @jtassaro has a [rather large RA](https://github.com/jtassarotti/iris-inv-hierarchy/blob/0ecbb628ff5c49826873f800a2127e5bfcfb48ae/theories/base_logic/lib/wsat.v#L43) that completely explodes `solve_inG`. Before https://...In his Iris fork, @jtassaro has a [rather large RA](https://github.com/jtassarotti/iris-inv-hierarchy/blob/0ecbb628ff5c49826873f800a2127e5bfcfb48ae/theories/base_logic/lib/wsat.v#L43) that completely explodes `solve_inG`. Before https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/498, it took around 15s, and then `Qed` took another 15s.
Since !498, they just don't terminate any more. I can make the proof itself go through by adding a `simpl in *` in `solve_inG` (before [this `intros`](https://github.com/jtassarotti/iris-inv-hierarchy/blob/0ecbb628ff5c49826873f800a2127e5bfcfb48ae/theories/base_logic/lib/own.v#L45)), but then `Qed` still takes forever. To make `Qed` work I added some awful hack that seemingly successfully guides Coq towards using the right reduction strategy for `Qed`.
I am not sure what we can do here, besides entirely sealing functors and thus making them non-computational (so we'd have to prove unfolding lemmas about them all, and somehow use them in `solve_inG`).https://gitlab.mpi-sws.org/iris/iris/-/issues/341Coecisting fractional and persistent read-only ownership2020-08-25T09:34:48ZRalf Jungjung@mpi-sws.orgCoecisting fractional and persistent read-only ownershipAs part of https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/486, @tchajed and @simonfv raised the point that sometimes it would be useful to convert ownership of *some fraction* of a map element to persistent read-only ownership. Ri...As part of https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/486, @tchajed and @simonfv raised the point that sometimes it would be useful to convert ownership of *some fraction* of a map element to persistent read-only ownership. Right now, our encoding through `frac * agree T + agree T` (or equivalently `(frac + ()) * agree T`) requires ownership of the full fraction for that move.
I think such a construction is possible, but it requires https://gitlab.mpi-sws.org/iris/iris/-/issues/257. Then we could relate an authoritative map to a fragment that's more like `option (frac * agree T) * option (agree T)`, and ensure that the second `option` is `None` unless the sum of all fraction fragments is less than 1.https://gitlab.mpi-sws.org/iris/iris/-/issues/340Polymorphic equality for HeapLang2020-08-22T19:06:03ZDan FruminPolymorphic equality for HeapLangIt would be nice to have polymorphic equality testing, like in OCaml or StandardML.
Current equality testing is used both for CmpXchng and for `=`, so it only operates on unboxed values.It would be nice to have polymorphic equality testing, like in OCaml or StandardML.
Current equality testing is used both for CmpXchng and for `=`, so it only operates on unboxed values.https://gitlab.mpi-sws.org/iris/iris/-/issues/339Add "reservation map" CMRA2020-09-09T12:29:51ZRalf Jungjung@mpi-sws.orgAdd "reservation map" CMRAFor the Rust GhostCell paper, we designed and @pythonsq implemented a "reservation map" RA that is useful when one needs to synchronously reserve two equal names in two different abstractions.
1. The reservation map lets you reserve an i...For the Rust GhostCell paper, we designed and @pythonsq implemented a "reservation map" RA that is useful when one needs to synchronously reserve two equal names in two different abstractions.
1. The reservation map lets you reserve an infinite amount of names in a first frame-preserving update.
2. Next you can use that infinite set to reserve a particular name in some other abstraction, with the usual "strong allocation" lemma that picks the new name from any infinite set.
3. Finally you can take that one name you got, and since it is in the infinite set you reserved, you may now own that name in the reservation map after a second frame-preserving update.
The code for this is at https://gitlab.mpi-sws.org/FP/ghostcell/-/blob/master/theories/typing/lib/gsingleton.v. @pythonsq do you think you will have time to clean this up and make it into an MR?https://gitlab.mpi-sws.org/iris/iris/-/issues/338Missing unseal tactic for siProp2020-08-30T07:04:36ZPaolo G. GiarrussoMissing unseal tactic for siProp
Here's what I've used:
```coq
(* XXX Taken from uPred.unseal / monPred.unseal, since this logic is missing for siLogic. *)
Ltac unseal_prepare := (* Coq unfold is used to circumvent bug #5699 in rewrite /foo *)
unfold bi_affinely, bi_...
Here's what I've used:
```coq
(* XXX Taken from uPred.unseal / monPred.unseal, since this logic is missing for siLogic. *)
Ltac unseal_prepare := (* Coq unfold is used to circumvent bug #5699 in rewrite /foo *)
unfold bi_affinely, bi_absorbingly, bi_except_0, bi_pure, bi_emp,
monPred_upclosed, bi_and, bi_or,
bi_impl, bi_forall, bi_exist, bi_sep, bi_wand,
bi_persistently, bi_affinely, bi_later;
simpl.
(* Should be siProp.unseal. *)
Ltac siProp_unseal := unseal_prepare; siProp_primitive.unseal.
```
The second part is easy, but the first not (tho it was worse before the bi-sbi merge), and deserves to be abstracted.https://gitlab.mpi-sws.org/iris/iris/-/issues/335iris.sty incompatible with acmart2020-07-15T12:25:40ZRalf Jungjung@mpi-sws.orgiris.sty incompatible with acmartThe `\nequiv` macro in `iris.sty` clashes with something that is import by the `acm` template. In our own papers, we work around this by undefining `\nequiv` locally, but that's not great.
We should either always overwrite whatever the ...The `\nequiv` macro in `iris.sty` clashes with something that is import by the `acm` template. In our own papers, we work around this by undefining `\nequiv` locally, but that's not great.
We should either always overwrite whatever the existing `\nequiv` is, or else change the name of our macro.https://gitlab.mpi-sws.org/iris/iris/-/issues/334Expand test coverage of proofmode2020-07-14T07:13:05ZTej Chajedtchajed@mit.eduExpand test coverage of proofmodeThe proof mode tests don't cover the following:
- [ ] `iRename`
- [ ] `iTypeOf`
- [ ] `iInduction`'s ability to freshen the inductive hypothesis
I have tests for the first two on my [bytes-ident](https://gitlab.mpi-sws.org/tchajed/iris...The proof mode tests don't cover the following:
- [ ] `iRename`
- [ ] `iTypeOf`
- [ ] `iInduction`'s ability to freshen the inductive hypothesis
I have tests for the first two on my [bytes-ident](https://gitlab.mpi-sws.org/tchajed/iris-coq/-/tree/bytes-ident) branch.https://gitlab.mpi-sws.org/iris/iris/-/issues/331simpl breaks error checking of `iNext (S i)`2020-07-14T08:21:09ZPaolo G. Giarrussosimpl breaks error checking of `iNext (S i)`I'd expect `iNext (S i)` to introduce exactly `S i` later, and fail otherwise. However, after e.g. `simpl` turns `▷^(S i) P` into `▷ ▷^i P`, that will sometimes introduce _one_ later, as shown below.
```coq
From iris.proofmode Require I...I'd expect `iNext (S i)` to introduce exactly `S i` later, and fail otherwise. However, after e.g. `simpl` turns `▷^(S i) P` into `▷ ▷^i P`, that will sometimes introduce _one_ later, as shown below.
```coq
From iris.proofmode Require Import tactics.
Lemma foo i {PROP} P : P ⊢@{PROP} ▷^(S i) P.
Proof.
iIntros "H".
Fail iNext 2.
iNext (S i).
Fail iNext i.
Fail iNext.
iExact "H".
Restart.
iIntros "H /=".
Fail iNext 2.
iNext (S i).
iNext i. (* !!! *)
Abort.
```
### Iris version
```
$ opam show coq-iris -f version
dev.2020-05-24.2.af5e50e7
```
with Coq 8.11.1.