Iris issueshttps://gitlab.mpi-sws.org/iris/iris/-/issues2020-08-30T07:04:36Zhttps://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/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/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/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/342Missing {u,}rFunctors and conversions2020-09-10T17:45:28ZPaolo G. GiarrussoMissing {u,}rFunctors and conversionsSome missing utilities I noticed:
- there's no conversion function from `urFunctor` (COFE -> uCMRA) to an `rFunctor` (COFE -> CMRA), and an `rFunctor` to an `oFunctor` (COFE -> OFE)
- `gmapRF` does not exist and should be definable throu...Some missing utilities I noticed:
- there's no conversion function from `urFunctor` (COFE -> uCMRA) to an `rFunctor` (COFE -> CMRA), and an `rFunctor` to an `oFunctor` (COFE -> OFE)
- `gmapRF` does not exist and should be definable through the above conversion, and @jung suggests that's an oversight; OTOH, that alerted me to a bug; I only needed it because I tried writing `GFunctor (gmapRF ...)`, which does not seem useful
- `listRF` does not exist (which I noticed while grepping)https://gitlab.mpi-sws.org/iris/iris/-/issues/343Make CI fail when proofs depend on auto-generated names2021-04-12T17:11:13ZRalf Jungjung@mpi-sws.orgMake CI fail when proofs depend on auto-generated namesWe already did it in std++, now [that this is fixed](https://github.com/coq/coq/issues/12944) it is time to do the same in Iris: make CI ensure that we do not use auto-generated names.We already did it in std++, now [that this is fixed](https://github.com/coq/coq/issues/12944) it is time to do the same in Iris: make CI ensure that we do not use auto-generated names.https://gitlab.mpi-sws.org/iris/iris/-/issues/344Set Default Goal Selector2020-11-10T19:12:02ZRalf Jungjung@mpi-sws.orgSet Default Goal SelectorAs a follow-up to https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/491, @tchajed suggested to add
```
Set Default Goal Selector "!".
```
To enforce that we properly use goal selectors.As a follow-up to https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/491, @tchajed suggested to add
```
Set Default Goal Selector "!".
```
To enforce that we properly use goal selectors.https://gitlab.mpi-sws.org/iris/iris/-/issues/345Check for `options.v` should only consider files in _CoqProject2020-09-12T10:10:58ZRobbert KrebbersCheck for `options.v` should only consider files in _CoqProjectNow if I have random files in my theories folder, `make` will give errors.Now if I have random files in my theories folder, `make` will give errors.Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/38Refactor bigops2017-04-01T19:10:03ZRalf Jungjung@mpi-sws.orgRefactor bigopsCurrently, bigops are tied to CMRAs. This is silly, because it means we have to show extension for e.g. uPred (which so far we can only do after picking a silly validity), and also because it restricts us to pick *one* operator to be use...Currently, bigops are tied to CMRAs. This is silly, because it means we have to show extension for e.g. uPred (which so far we can only do after picking a silly validity), and also because it restricts us to pick *one* operator to be used in bigops, whereas we may also want to use big conjunction.
Instead we should do sth. like ssreflect does, with a typeclass/canonical structure for this special purpose that's completely separate from the main algebraic hierarchy.Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/19[Maybe] Make uPred work on OFEs2016-11-22T15:25:52ZRalf Jungjung@mpi-sws.org[Maybe] Make uPred work on OFEsI spent some time last week talking with Santiago, a student of Andrew Appel, and trying to figure out the exact relation of their and our model. We did not reach a definitive conclusion. In particular, we could not tell where exactly ou...I spent some time last week talking with Santiago, a student of Andrew Appel, and trying to figure out the exact relation of their and our model. We did not reach a definitive conclusion. In particular, we could not tell where exactly our CMRA requirements of non-expansiveness and the extension axiom appear in their model.
However, one thing became clear: They do have a separation algebra on what Santiago called "juicy heap", which is a heap that can store either values or assertions (so, it combines our physical state and invariant maps). Separation algebras are relational, so they had no trouble with equality not being decidable. (And Santiago confirmed my belief that working with this relational composition is a *huge* pain in many other places.) However, they also did not have to go through the length of having a limit construction corresponding to what our agreement CMRA does. This is not entirely surprising, we know we don't actually need these limits and in their approach, all these proof obligations are coming up and discharged much more "on-demand", and much later. (For example, they have to be really, really careful when defining the meaning of what corresponds to our invariant assertion. If they screw up, they will only notice much later, when some proof rule does not work out. On the other hand, all we have to check is non-expansiveness of the definition.)
It would be nice if we would not have to unnecessarily complicate our model with this limit construction. That would also give us a better position when comparing with Appel's stuff ;-)
Cc @robbertkrebbers
I guess this is blocked on "sorting the canonical structure mess" ;-)https://gitlab.mpi-sws.org/iris/iris/-/issues/20wp_store/wp_load run slowly with multiple points to assumptions in context2016-06-20T16:08:53ZJoseph Tassarottiwp_store/wp_load run slowly with multiple points to assumptions in contextThe wp_store and wp_load tactics appear to be very sensitive to the order of points to assumptions in the context. Consider the following snippet, placed after heap_e_spec in tests/heap_lang.v
```
Definition heap_e2 : expr [] :=
...The wp_store and wp_load tactics appear to be very sensitive to the order of points to assumptions in the context. Consider the following snippet, placed after heap_e_spec in tests/heap_lang.v
```
Definition heap_e2 : expr [] :=
let: "x" := ref #1 in
let: "y" := ref #1 in
'"x" <- !'"x" + #1 ;; !'"x".
Lemma heap_e2_spec E N :
nclose N ⊆ E → heap_ctx N ⊢ WP heap_e2 @ E {{ v, v = #2 }}.
Proof.
iIntros {HN} "#?". rewrite /heap_e2. iApply (wp_mask_weaken N); first done.
wp_alloc l. wp_let.
wp_alloc l'. wp_let.
time wp_load.
Abort.
```
The wp_load takes 109 seconds to complete on my machine. The problem appears to be in the call to iAssumptionCore in wp_load, which tries to find an assumption l |-> ?v in the context. Because of the order of assumptions, it will first try to unify with l' |-> 1. For some reason, this does not fail instantaneously. You can check that this is the source of delay with the following example:
Remark bad_unify (l l': loc): True.
Proof.
(evar (v: Z );
let v0 := eval unfold v in v in
unify (l ↦ #v0)%I (l' ↦ #1)%I).
Abort.
The obvious work-around is to just re-order the two points to facts in the context, or use "remember" to "hide" one of them temporarily, but this is obviously brittle. I am not an expert on how unification works under the hood, so it is hard for me to diagnose why it's so slow here.
First, does this occur for others? I am using coq 8.5pl1 and ssreflect ad273277ab38b. If so, is there some more robust work-around?https://gitlab.mpi-sws.org/iris/iris/-/issues/56iAssert ... as %X should get all assumptions2017-01-03T13:28:17ZRalf Jungjung@mpi-sws.orgiAssert ... as %X should get all assumptionsWhen I write `iAssert ... as %X`, it is syntactically clear that I am proving sth. persistent (even pure). Still, I have to add `with [#]` to be allowed to use all assumptions. Wouldn't it make sense to do that automatically? IIRC we ar...When I write `iAssert ... as %X`, it is syntactically clear that I am proving sth. persistent (even pure). Still, I have to add `with [#]` to be allowed to use all assumptions. Wouldn't it make sense to do that automatically? IIRC we are doing sth. like that with ´iDestruct ... as %X`.Iris 3.0Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/53Improve solve_ndisj2017-02-16T14:07:06ZRalf Jungjung@mpi-sws.orgImprove solve_ndisj<https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/c72bfec9e38531b7dc70f05c2415ed1e3f806899> demonstrates some cases that `solve_ndisj` cannot handle, and it'd be great if it could. Most of them could be handled if we added
```
Hint Ex...<https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/c72bfec9e38531b7dc70f05c2415ed1e3f806899> demonstrates some cases that `solve_ndisj` cannot handle, and it'd be great if it could. Most of them could be handled if we added
```
Hint Extern 1000 (_ ⊆ _) => set_solver : ndisj.
```
The one remaining case is more subtle. It is solved by `assert (↑shrN ⊆ (↑lrustN : coPset)) by solve_ndisj. set_solver.`, but is there a way we can plug solve_ndisj and set_solver together so that we don't have to say in advance which inclusions we need?
Cc @robbertkrebbers @jjourdanhttps://gitlab.mpi-sws.org/iris/iris/-/issues/40iRewrite and internal equality on predicates2016-10-27T14:34:24ZJannoiRewrite and internal equality on predicatesConsider the following example: (Ignore saved_prop_own, I only needed it to make Coq happy)
```
Lemma test {A} (P Q : A -c> iProp) a i φ :
saved_prop_own i φ ★ P ≡ Q ⊢ P a ≡ Q a.
Proof.
iIntros "[_ #E]".
Fail iR...Consider the following example: (Ignore saved_prop_own, I only needed it to make Coq happy)
```
Lemma test {A} (P Q : A -c> iProp) a i φ :
saved_prop_own i φ ★ P ≡ Q ⊢ P a ≡ Q a.
Proof.
iIntros "[_ #E]".
Fail iRewrite "E".
Abort.
```
It seems to me that iRewrite should succeed here. Is there a logical reason for it to fail? (As opposed to an engineering reason.)
(We are using commit 9c5a95d3b271f4e0d0c657964dfa386070d0b322 in case that matters.)https://gitlab.mpi-sws.org/iris/iris/-/issues/28docs: the universe $\cal U$ is used without definition2016-08-16T17:40:06ZJeehoon Kangjeehoon.kang@kaist.ac.krdocs: the universe $\cal U$ is used without definitionHere: https://gitlab.mpi-sws.org/FP/iris-coq/blob/master/docs/model.tex#L155
Without saying that $\cal U$ is the universe (in whatever sense), the sentence seems confusing to me..Here: https://gitlab.mpi-sws.org/FP/iris-coq/blob/master/docs/model.tex#L155
Without saying that $\cal U$ is the universe (in whatever sense), the sentence seems confusing to me..https://gitlab.mpi-sws.org/iris/iris/-/issues/39iIntros: bad error when trying to use a name that's already used2016-10-26T20:07:46ZRalf Jungjung@mpi-sws.orgiIntros: bad error when trying to use a name that's already usedIf there already is a variable `x` in the context, running `iIntros (x)` yields "No applicable tactic". That's not a very useful error, and it just took me a while to realize the actual problem. Is there a way to make this show the error...If there already is a variable `x` in the context, running `iIntros (x)` yields "No applicable tactic". That's not a very useful error, and it just took me a while to realize the actual problem. Is there a way to make this show the error generated by the underlying `intros`?Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/346Typeclass inference fails to trigger.2020-09-21T18:08:44ZArthur Azevedo de AmorimTypeclass inference fails to trigger.I am trying to use `auth_acc`, but typeclass inference misses an apparently obvious instance that I have to provide by hand. Am I doing something wrong?
```
From stdpp Require Import base gmap.
From iris.algebra Require Import gmap num...I am trying to use `auth_acc`, but typeclass inference misses an apparently obvious instance that I have to provide by hand. Am I doing something wrong?
```
From stdpp Require Import base gmap.
From iris.algebra Require Import gmap numbers.
From iris.proofmode Require Import tactics.
From iris.base_logic.lib Require Import auth invariants.
Section Test.
Context `{!invG Σ, !authG Σ (gmapUR nat natR)}.
Implicit Types m : gmap nat nat.
Definition my_inv m : iProp Σ := True.
Goal ∀ γ, auth_ctx γ nroot id my_inv ={⊤}=∗ False.
iIntros (γ) "Hctx".
iMod (auth_empty γ) as "#Hinit".
iMod (auth_acc _ _ _ _ _ ε with "[Hctx Hinit]") as "Hinv"; try by eauto.
(* Inhabited (gmap nat nat) is now shelved... *)
Abort.
End Test.
```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/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/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/351Decouple framing and IntoSep2022-01-17T02:16:40ZRalf 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/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/353CHANGELOG should spell out what changed in auth due to views MR better2020-10-03T10:02:54ZTej Chajedtchajed@gmail.comCHANGELOG should spell out what changed in auth due to views MR better!516 makes some changes that aren't obvious. For example, `auth_validI` is gone because it used the projections, should now explicitly use `auth_auth_validI`, `auth_frag_validI`, or `auth_both_validI` as appropriate.!516 makes some changes that aren't obvious. For example, `auth_validI` is gone because it used the projections, should now explicitly use `auth_auth_validI`, `auth_frag_validI`, or `auth_both_validI` as appropriate.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/355Break dependency of algebra on base_logic2020-10-20T15:11:03ZRalf Jungjung@mpi-sws.orgBreak dependency of algebra on base_logicCurrently, parts of algebra depend on base_logic for the "internalized" equality and validity lemmas. That is rather annoying as it means many things need to be recompiled to work on those parts of algebra. It also prevents us from separ...Currently, parts of algebra depend on base_logic for the "internalized" equality and validity lemmas. That is rather annoying as it means many things need to be recompiled to work on those parts of algebra. It also prevents us from separating the base_logic and program_logic folders into a separate package, should we ever want to do that.
The plan is to instead add a file like `base_logic/algebra.v` and prove those lemmas there, thus fixing the dependency inversion.https://gitlab.mpi-sws.org/iris/iris/-/issues/356gmap_view: add fraction support to gmap_view_auth2020-10-21T10:09:04ZRalf Jungjung@mpi-sws.orggmap_view: add fraction support to gmap_view_authTo fully supplement Perennial's `auth_map`, we need to equip `gmap_view_auth` with support for a fraction. `view` already supports fractions so this should not be too hard.To fully supplement Perennial's `auth_map`, we need to equip `gmap_view_auth` with support for a fraction. `view` already supports fractions so this should not be too hard.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/358Add a logic-level version of gmap_view2021-03-06T11:34:41ZRalf Jungjung@mpi-sws.orgAdd a logic-level version of gmap_viewWe now have `gmap_view` on the RA level, but this library seems useful enough that we want to have a logic-level wrapper as well, with notations for "owning a location in a ghost heap", so to speak. Perennial has `auth_map` (and some pre...We now have `gmap_view` on the RA level, but this library seems useful enough that we want to have a logic-level wrapper as well, with notations for "owning a location in a ghost heap", so to speak. Perennial has `auth_map` (and some predecessors) for this and it is used all over the place.https://gitlab.mpi-sws.org/iris/iris/-/issues/359Use the IPM to prove some example IPM extension theorems2020-10-21T11:00:32ZTej Chajedtchajed@gmail.comUse 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/361gen_heap: provide init lemma for non-empty heap that provides the points-to f...2020-11-10T18:03:57ZRalf Jungjung@mpi-sws.orggen_heap: provide init lemma for non-empty heap that provides the points-to factsOur current `gen_heap_init` can be used with a non-empty heap, but then the points-to facts for the initial location are lost. Sometimes however they are needed: both Perennial and time-credits violate the gen_heap abstraction to be able...Our current `gen_heap_init` can be used with a non-empty heap, but then the points-to facts for the initial location are lost. Sometimes however they are needed: both Perennial and time-credits violate the gen_heap abstraction to be able to initialize with a non-empty heap and obtain all the points-to facts.
We should just provide a lemma for this. However, this is blocked on `gmap_view` having such a lemma, which requires having "map fragments" besides the currently available "singleton fragments".https://gitlab.mpi-sws.org/iris/iris/-/issues/363Collect Iris versions required by artifacts2020-11-23T12:56:33ZRalf Jungjung@mpi-sws.orgCollect Iris versions required by artifactsI'd like to clean up https://gitlab.mpi-sws.org/iris/opam, to avoid opam issues due to having too many versions of a package. However, it turns out in the past some of the Iris paper artifacts are not self-contained, and instead rely on ...I'd like to clean up https://gitlab.mpi-sws.org/iris/opam, to avoid opam issues due to having too many versions of a package. However, it turns out in the past some of the Iris paper artifacts are not self-contained, and instead rely on the opam repository. We should figure out which versions of Iris are required by an artifact, and keep them in the repository.https://gitlab.mpi-sws.org/iris/iris/-/issues/364Implement typeclasses analogous to Fractional and AsFractional for discardabl...2020-10-21T10:59:16ZTej Chajedtchajed@gmail.comImplement 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/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/1Thread-local state, user-controlled fork2016-08-23T14:34:02ZRalf Jungjung@mpi-sws.orgThread-local state, user-controlled forkChange `core_lang` to get rid of evaluation contexts and let the user control what fork does. This will invalidate the Bind rule, I will create another issue for that.Change `core_lang` to get rid of evaluation contexts and let the user control what fork does. This will invalidate the Bind rule, I will create another issue for that.Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/6Add & update appendix2016-03-17T16:01:33ZRalf Jungjung@mpi-sws.orgAdd & update appendixI think we should have a version of the appendix that's in sync with the Coq development right in the repository. The latest public version is outdated, and I have sent various snapshots of the appendix to various people. Pointing them t...I think we should have a version of the appendix that's in sync with the Coq development right in the repository. The latest public version is outdated, and I have sent various snapshots of the appendix to various people. Pointing them to this git repository would make it possible for them to stay in sync with updates, while still making it clear that this is all in development and not polished.
As a prerequisite for this to be useful, we have to sync the appendix and the Coq sources again - at least the first part, describing the model. I am not sure yet whether we want the rest of the appendix in here as well. It's less related to the Coq development, but it's more what people are actually interested in. @janno suggested some kind of Hackathon, where we sit together and check that definitions actually match. That should probably happen after #4 is done. @swasey what do you think?https://gitlab.mpi-sws.org/iris/iris/-/issues/7Support stored propositions2016-01-20T13:26:21ZRalf Jungjung@mpi-sws.orgSupport stored propositionsIt would be nice to have support for "Stored propositions" as described in <http://www-users.cs.york.ac.uk/~miked/publications/verifying_custom_sync_constructs.pdf>.
@kaspersv suggested they could be hacked into Iris without changing ...It would be nice to have support for "Stored propositions" as described in <http://www-users.cs.york.ac.uk/~miked/publications/verifying_custom_sync_constructs.pdf>.
@kaspersv suggested they could be hacked into Iris without changing in the model. Let me quote his mail (with some parts of my mail also being inline):
>> And finally, of course, there's the question whether this could be done
>> in Iris. I am sure we could have the following proof rule:
>>
>> \inv^i (P) * \inv^i (Q) => \later (P <=> Q)
>
>Indeed, we can even strengthen it to inv^j (P) * inv^j (Q) => later (P = Q)
>because the interpretation of inv is slightly stronger in Iris than rintrp is
>in iCAP. In particular, inv^j (P) asserts that the invariant is n-equal to P,
>while iCAP only asserts that the region interpretation is n-equal to
>the given predicate when applied to any future world of the current
>world.
>
>> but we can't easily use the trick you did, with the 2-state STS, in
>> order to not actually store a P in the invariant. Did you think about this?
>
>Yes, we did think about an encoding, using two mutually exclusive
>ghost resources gh(0) and gh(1). The idea would be to create an
>invariant (P * gh(0)) \/ gh(1) and transfer gh(1) to the region. Then
>the question boils down to:
>
>(P * gh(0)) \/ gh(1) = (Q * gh(0)) \/ gh(1) |- P = Q
>
>I don’t think it is possible to prove this internally and we weren’t
>sufficiently motivated to check if it holds in the semantics, but it
>seems like it should.
As an alternative, @janno and me tossed around the idea of letting the user chose an arbitrary, locally non-expansive functor to construct the ghost monoid. That would allow the user to make use of my agreement construction, with "Ag(\later Prop)" being in the ghost monoid. This would then let the user do stored propositions without hacks like the above. @robbertkrebbers also seemed to like that. However, we would lose the axiom that ghost ownership is timeless, and I see no easy way to regain it for the part of the functor that has a discrete metric. So, probably, we would want to keep both a discrete monoid (where ownership is timeless) and a functor (where crazy things can happen) in the interface, and pair them together ourselves - which raises the question if that's worth it. The model would end up with a 4-tuple-monoid instead of the three-tuples is has currently (invariants, ghost, physical). Right now, I cannot imagine using any other monoid with propositions embedded. Of course it would be nice to have, for example, STSs with states indexed by propositions, but actually doing that would require making this STS a functor, and showing all the functorial properties and local non-expansiveness and so on - probably it would be much easier to go with stored propositions and index the STS by the name instead. For that reason, right now, I'd prefer the solution suggested by @kaspersv if it works.
@jtassaro: I mentioned this yesterday during our conversation.https://gitlab.mpi-sws.org/iris/iris/-/issues/10Defining RAs with a partial composition operation2016-01-18T16:38:58ZRalf Jungjung@mpi-sws.orgDefining RAs with a partial composition operationRight now, if your RA has a partial composition operation and you'd like to make a case distinction on something that's not decidable, you have to use some rather hideous trick. For example, in the case of STSs, composition is defined on...Right now, if your RA has a partial composition operation and you'd like to make a case distinction on something that's not decidable, you have to use some rather hideous trick. For example, in the case of STSs, composition is defined only if the intersection of the state sets is non-empty. To define this in Coq, the STS monoid actually carries around a `valid: Prop` piece of "data", and equality of monoid elements is defined as a quotient, equalizing all invalid elements. @robbertkrebbers convinced me this also comes up for some other monoid, I believe it was the fractions - but actually, I can't tell any more why this should come up there. Robbert, could you remind me?
It may be a good idea to axiomatize a class of "DRAs" (disjoint RAs), that have, instead of a validity predicate, a binary *disjointness* predicate. Composition would still have to be total, but commutativity (and potentially associativity) would only have to hold if the involved elements are disjoint. We could then have a functor from RAs to DRAs, using above construction with the `valid: Prop` and the quotient. This way, people could define such monoids much easier, but we wouldn't have to suffer the pain of using DRAs in the model. (Which would be really annoying; every time we use commutativity, we'd have to prove disjointness.)https://gitlab.mpi-sws.org/iris/iris/-/issues/11Structured Invariant identifiers2022-12-17T02:24:58ZGhost UserStructured Invariant identifiersI'm starting to get pretty annoyed working with global invariant names in Iris. In particular, if I have a library that creates multiple invariants, I can parameterise its specification with an infinite set of names that the library can ...I'm starting to get pretty annoyed working with global invariant names in Iris. In particular, if I have a library that creates multiple invariants, I can parameterise its specification with an infinite set of names that the library can use. However, it is very annoying to have to refer to particular distinct elements of this set in a precise way.
I believe proof outlines would benefit if we had an invariant identifier resource, unused(mask), that expressed that no invariants existed with an identifier in mask. This would allow the allocator to choose a name for invariants upon allocation, by consuming an unused resource:
> unused({ i }) * later P view-shift inv(i, P)
and of course the unused resource could be split arbitrarily:
> unused(mask_1 \uplus mask_2) <=> unused(mask_1) * unused(mask_2)
Libraries would then be parameterised by a single invariant identifier i and require the user to transfer ownership of unused({ concat(i, i') }) to the library upon instantiation. This would allow the library to use any invariant identifier starting with i for its invariants. In particular, it could choose to create two invariants with identifiers concat(i, "0") and concat(i, "1"), which would automatically be distinct in proof outlines.
I don't believe it is possible to define the unused resource in Iris, so I propose to extended Iris with a primitive invariant identifier resource.
Any comments or ideas for better solutions?
https://gitlab.mpi-sws.org/iris/iris/-/issues/12Prove stronger stepping frame rule2016-08-22T15:55:51ZRalf Jungjung@mpi-sws.orgProve stronger stepping frame ruleRight now, we have a "stepping frame rule" that looks as follows:
```text
{ P } e { Q } e is not a value
------------------------------------
{ \later R * P } e { R * Q }
```
Essentially, this allows us to step away a later ...Right now, we have a "stepping frame rule" that looks as follows:
```text
{ P } e { Q } e is not a value
------------------------------------
{ \later R * P } e { R * Q }
```
Essentially, this allows us to step away a later when framing around any non-value. (We also sometimes call this the "atomic frame rule", since atomic expressions are never values. But the one above is just as valid, and obviously stronger.)
However, I think I will need for my Rust stuff a stronger version of this rule, that allows me to strip away a later *inside an invariant* from any non-value. This comes up because I have non-atomic reads and writes that are, well, non-atomic, and I still want to strip away a later from something that is located inside an invariant[1]. This rule is rather awkward to write down in terms of Hoare triples and view shifts:
```text
R0 E1^==>^E2 \later R1 R1 E2^==>^E1 R2 { P } e { Q }_E1
e is not a value E2 <= E1
------------------------------------------------------------------
{ R0 * P } e { R2 * Q }_E1
```
It looks nicer in terms of primitive view shifts and weakest-pre:
```text
wp_E1 e Q * vs_E1^E2(\later vs_E2^E1(R))
e is not a value E2 <= E1
-------------------------------------
wp_E1 e (Q * R)
```
When we re-do the weakest-pre proofs for V2.0, I think this is the rule we should show. (And derive the old one, of course.)
[1] If you are curious: The invariant has two states "vs(P)" and "P", with an STS making sure that one can only go from the 1st state to the 2nd. The rule I need allows me to open this invariant alongside the non-atomic access, obtain "\later (vs(P) \/ P)", strip away the later, view shift to "P", and put that back into the invariant; taking out the witness that the view shift has been performed. I do not need any resource from the invariant to justify the memory access, so it's fine for that one to be non-atomic. But I *do* need to perform this view shift, because immediately after the access I will want to open the invariant again and know I get "\later P", without any more skips.
Cc: @robbertkrebbers @swasey @janno https://gitlab.mpi-sws.org/iris/iris/-/issues/14Evaluation-context language2016-03-29T18:01:52ZRalf Jungjung@mpi-sws.orgEvaluation-context languageWe should have a typeclass for an evaluation-context based language, and an instance to convert these into a general Iris language, and some specialized lifting lemmas for such languages.We should have a typeclass for an evaluation-context based language, and an instance to convert these into a general Iris language, and some specialized lifting lemmas for such languages.Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/15Unify frame-preserving updates and local updates2016-10-27T09:19:17ZRalf Jungjung@mpi-sws.orgUnify frame-preserving updates and local updatesThe two seem to have a lot in common, see e.g. `frac.v`.The two seem to have a lot in common, see e.g. `frac.v`.https://gitlab.mpi-sws.org/iris/iris/-/issues/17Sum CMRA / CMRA without core2016-06-21T09:02:04ZRalf Jungjung@mpi-sws.orgSum CMRA / CMRA without coreWe would like to support a sensible CMRA structure on sums. For example, we could use a sum CMRA to express `one_shot X` as `exclC unitC + ag X`. We could also express the disposable monoid using sums.
Right now, the CMRA structure on...We would like to support a sensible CMRA structure on sums. For example, we could use a sum CMRA to express `one_shot X` as `exclC unitC + ag X`. We could also express the disposable monoid using sums.
Right now, the CMRA structure on sums does not make much sense because both summands need to have a core. It is thus impossible to do a frame-preserving update from `inl a` to `inr b`. For sums to work out nicely, we need a way to have summands without a unit.
@robbertkrebbers and me agreed that the most promising way forward is to get rid of the core in the CMRA axioms, and instead add a typeclass for "CMRAs that also have a core". There should not be significant performance trouble because the `iFunctor` will bundle the core of the user CMRA. The main open question is whether the loss of reflexivity in the CMRA inclusion will be a problem.
Cc @robbertkrebbers Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/24Find nice syntax for our "CPS" WP specifications2016-10-27T09:23:29ZRalf Jungjung@mpi-sws.orgFind nice syntax for our "CPS" WP specificationsIt would be nice to have "something" that makes our specs more readable to someone not familiar with our "CPS" style of writing specs with an arbitrary postcondition (Φ).
I believe @janno has been working on something like that... wha...It would be nice to have "something" that makes our specs more readable to someone not familiar with our "CPS" style of writing specs with an arbitrary postcondition (Φ).
I believe @janno has been working on something like that... what was the status of that again?https://gitlab.mpi-sws.org/iris/iris/-/issues/25iSplitL "persistent_hyp": Improve error2016-08-06T00:12:25ZRalf Jungjung@mpi-sws.orgiSplitL "persistent_hyp": Improve errorCurrently, if I say `iSplitL "H"` where `H` is persistent, it says that `H` has not been found. That's confusing, "H" exists -- but it looked in the spatial context only. The tactic should either accept persistent hypotheses or the error...Currently, if I say `iSplitL "H"` where `H` is persistent, it says that `H` has not been found. That's confusing, "H" exists -- but it looked in the spatial context only. The tactic should either accept persistent hypotheses or the error should say "... has not been found in the spatial context" or so.Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/27mathpartir.sty is missing2016-08-09T13:09:45ZJeehoon Kangjeehoon.kang@kaist.ac.krmathpartir.sty is missingI believe the intention of `\usepackage{\basedir mathpartir}` in `iris.tex` is using the local `mathpartir.sty` file in the same directory. But it is missing in the repository.I believe the intention of `\usepackage{\basedir mathpartir}` in `iris.tex` is using the local `mathpartir.sty` file in the same directory. But it is missing in the repository.https://gitlab.mpi-sws.org/iris/iris/-/issues/32Support framing pure/Coq hypotheses2016-09-19T19:18:18ZJacques-Henri JourdanSupport framing pure/Coq hypothesesIn the following, iFrame does not have the expected behavior:
Lemma L `{irisG Λ Σ} : ∀ P:iProp Σ, □ P ⊢ P ★ True.
iIntros (P) "#HP". iFrame.In the following, iFrame does not have the expected behavior:
Lemma L `{irisG Λ Σ} : ∀ P:iProp Σ, □ P ⊢ P ★ True.
iIntros (P) "#HP". iFrame.Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/37saved_prop for predicate2016-10-05T23:07:43ZGhost Usersaved_prop for predicateI have a `Q: val -> iProp`, now I want to save predicate `Q` just like the saved proposition. How to do that?I have a `Q: val -> iProp`, now I want to save predicate `Q` just like the saved proposition. How to do that?https://gitlab.mpi-sws.org/iris/iris/-/issues/43Proof mode intro pattern lexer: _ should be allowed as part of varianme names2016-11-24T08:27:45ZRalf Jungjung@mpi-sws.orgProof mode intro pattern lexer: _ should be allowed as part of varianme names`A_B` is a fine variable name. It is parsed as `A _ B`.`A_B` is a fine variable name. It is parsed as `A _ B`.Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/45iLöb with non-empty revert list2016-11-30T12:14:50ZJannoiLöb with non-empty revert listWhen iLöb is given a list of iris assumptions it does not automatically generalize over all spatial assumptions any more. Adding a ∗ to the list of assumptions solves that problem.
Proposal: always add ∗ to the list of Iris assumptions.When iLöb is given a list of iris assumptions it does not automatically generalize over all spatial assumptions any more. Adding a ∗ to the list of assumptions solves that problem.
Proposal: always add ∗ to the list of Iris assumptions.Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/46Use the correct setoid equality in algebra/gset and algebra/coPset2016-11-30T12:14:50ZHai DangUse the correct setoid equality in algebra/gset and algebra/coPsetcofe_equiv takes precedence over available equivalences, which prevents rewriting with those equivalences. I have to make explicit those instances.
@janno suggested that it is due to this hint?
https://gitlab.mpi-sws.org/FP/iris-co...cofe_equiv takes precedence over available equivalences, which prevents rewriting with those equivalences. I have to make explicit those instances.
@janno suggested that it is due to this hint?
https://gitlab.mpi-sws.org/FP/iris-coq/blob/75518c9a4c5278b44120212060c2faceb875de3f/algebra/ofe.v#L52Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/52iMod and evar instantiation2019-06-17T07:54:22ZRalf Jungjung@mpi-sws.orgiMod and evar instantiationSee <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/acddfae5355a5e7540010c7ea6f423a892f9e887#note_17391>: `iMod ... as [$ ?]` fails even though `iMod ... as [H ?]; iFrame "H"` works fine.
@jjourdan suggests it may be related to C...See <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/acddfae5355a5e7540010c7ea6f423a892f9e887#note_17391>: `iMod ... as [$ ?]` fails even though `iMod ... as [H ?]; iFrame "H"` works fine.
@jjourdan suggests it may be related to Coq lazily propagating instantiated evars, and adding a magic tactic that does the propagation in the right point of executing the `iMod` could help.Iris 3.0Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/54iIntros fails to introduce Coq-level and Iris-level universal quantifiers at ...2016-12-21T19:01:39ZRalf Jungjung@mpi-sws.orgiIntros fails to introduce Coq-level and Iris-level universal quantifiers at onceSee for example <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/ca917d76e1318fb3a6e0aa0c61f777a2e62ac8d0#51956c642cbeef54a2f1728f704193c7e23720f3_97_98>: `iIntros (HTsat HEsat). iIntros (tid qE) "#LFT HE HL HC".` works but `iIntros ...See for example <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/commit/ca917d76e1318fb3a6e0aa0c61f777a2e62ac8d0#51956c642cbeef54a2f1728f704193c7e23720f3_97_98>: `iIntros (HTsat HEsat). iIntros (tid qE) "#LFT HE HL HC".` works but `iIntros (HTsat HEsat tid qE) "#LFT HE HL HC".` does not.Iris 3.0Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/55iNext unfolds things (more than simpl) even when there is no later to strip2018-02-20T00:50:15ZRalf Jungjung@mpi-sws.orgiNext unfolds things (more than simpl) even when there is no later to stripSee <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/blob/02ef8176f01f8de0563a2f5a8e1444bb9ee01b6d/theories/typing/cont.v#L40>: The context goas from
```
"HC" : elctx_interp E qE -∗ cctx_interp tid C
"HE" : elctx_interp E qE
"HL" ...See <https://gitlab.mpi-sws.org/FP/LambdaRust-coq/blob/02ef8176f01f8de0563a2f5a8e1444bb9ee01b6d/theories/typing/cont.v#L40>: The context goas from
```
"HC" : elctx_interp E qE -∗ cctx_interp tid C
"HE" : elctx_interp E qE
"HL" : llctx_interp L1 1
"HT" : tctx_interp tid (T' args)
```
to
```
"HC" : elctx_interp E qE -∗ cctx_interp tid C
"HE" : [∗ list] k↦x ∈ E, (λ (_ : nat) (x0 : elctx_elt), elctx_elt_interp x0 qE) k x
"HL" : [∗ list] k↦x ∈ L1, (λ (_ : nat) (x0 : llctx_elt), llctx_elt_interp x0 1) k x
"HT" : [∗ list] k↦x ∈ T' args, (λ (_ : nat) (x0 : tctx_elt), tctx_elt_interp tid x0) k x
```
but no later is removed. Not even simpl unfolds these definitions.Iris 3.0Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/60Consider the destruct pattern "_" as being persistent2017-01-01T19:10:30ZJacques-Henri JourdanConsider the destruct pattern "_" as being persistentIf I do:
```
iDestruct ("A" with "B") as "[#X #Y]".
```
Then "B" is not consumed because the destruct pattern only produce persistent hypotheses. So far so good.
But if I do:
```
iDestruct ("A" with "B") as "[#X _]".
```
That's not th...If I do:
```
iDestruct ("A" with "B") as "[#X #Y]".
```
Then "B" is not consumed because the destruct pattern only produce persistent hypotheses. So far so good.
But if I do:
```
iDestruct ("A" with "B") as "[#X _]".
```
That's not the case.https://gitlab.mpi-sws.org/iris/iris/-/issues/368Remove `inv` lemmas for agree/auth/view/etc and add `_L` variants to the ↔ lemma2023-08-03T14:56:20ZRobbert 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/369Document HeapLang2022-05-18T17:42:51ZRalf 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/370Add missing instances for `Duplicable` and fix `Hint Immediate` for `persiste...2020-11-04T12:05:50ZSimon Friis VindumAdd missing instances for `Duplicable` and fix `Hint Immediate` for `persistent_duplicable`Following the merge of !481 instances of `Duplicable` for `<subj>` and `embed` should be added.
@robbertkrebbers has kindly offered to do this.Following the merge of !481 instances of `Duplicable` for `<subj>` and `embed` should be added.
@robbertkrebbers has kindly offered to do this.https://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/373Quote does not handle ⊣⊢2020-11-05T11:12:30ZRodolphe LepigreQuote does not handle ⊣⊢The `solve_sep_equiv` tactic from `bi.tactics` cannot be used to solve goals of the form `_ ⊣⊢ _`.
This is due to `quote` only accepting goals of the form `_ ⊢ _` (see [here](https://gitlab.mpi-sws.org/iris/iris/-/blob/master/theories/b...The `solve_sep_equiv` tactic from `bi.tactics` cannot be used to solve goals of the form `_ ⊣⊢ _`.
This is due to `quote` only accepting goals of the form `_ ⊢ _` (see [here](https://gitlab.mpi-sws.org/iris/iris/-/blob/master/theories/bi/tactics.v#L136)). Can it be made more general?https://gitlab.mpi-sws.org/iris/iris/-/issues/374Avoid sequences of "_" by adjusting lemma statements2020-11-05T12:11:02ZRalf Jungjung@mpi-sws.orgAvoid sequences of "_" by adjusting lemma statementsSome Iris lemmas are prone to needing plenty of `_` almost every time they are used. I noticed this in particular for
* most big-op lemmas that access a single element, where the to-be-accessed element needs to be given explicitly, but o...Some Iris lemmas are prone to needing plenty of `_` almost every time they are used. I noticed this in particular for
* most big-op lemmas that access a single element, where the to-be-accessed element needs to be given explicitly, but often other arguments come first
* several allocation lemmas such as `inv_alloc`, where the to-be-allocated thing needs to be given explicitly, but other arguments come first
* many of the update lemmas, where typically one works with `iMod`, so the new values (e.g. new lower bound for mono_nat, or new key and value for gmap) need to be given, but they are often the last arguments
There are two ways to fix this:
* reorder arguments, so that those that are likely to be determined by unification come first
* make likely-to-be-determined-by-unification arguments implicit, so that we do not have to write out their `_`
I am in favor of the second approach because it has a better failure mode: if one of those arguments ends up *not* being determined by unification, we have use `lemma (arg:=val)` to explicitly give the value for this agument. For lemmas with many arguments, this name-based approach is anyway much easier to read and write than the position-based approach (no need to remember the exact order of arguments).
However, while implicit arguments are widely used in Iris, we usually control them on a per-section basis, not a per-lemma basis. @robbertkrebbers has objected the used of implicit arguments for this reason. (That is my understanding, anyway.)https://gitlab.mpi-sws.org/iris/iris/-/issues/375We have some lonely notations2020-11-05T12:15:18ZRalf Jungjung@mpi-sws.orgWe have some lonely notationsThe following is the list of notations that are "lonely", which means they are not in a scope: (in some heap_lang file, so there might be things this does not import)
```
Lonely notations
"✓{ n } x" := validN n x
"◯V a" := view_frag a
"◯...The following is the list of notations that are "lonely", which means they are not in a scope: (in some heap_lang file, so there might be things this does not import)
```
Lonely notations
"✓{ n } x" := validN n x
"◯V a" := view_frag a
"◯ a" := auth_frag a
"●{ q } a" := auth_auth q a
"●V{ q } a" := view_auth q a
"●V a" := view_auth (pos_to_Qp xH) a
"● a" := auth_auth (pos_to_Qp xH) a
"↑ x" := up_close x
"'λne' x .. y , t" := OfeMor (fun x => .. (OfeMor (fun y => t)) ..)
"'λ' x .. y , t" := fun x => .. (fun y => t) ..
"x ◎ y" := ccompose x y
"x ≥ y" := ge x y
"x ≤ y" := le x y
"x ≡{ n }≡ y" := dist n x y
"x ≡{ n }@{ A }≡ y" := dist n x y
"x ~~>: y" := cmra_updateP x y
"x ~~> y" := cmra_update x y
"x ~l~> y" := local_update x y
"x ||* y" := zip_with orb x y
"x =.>* y" := Forall2 bool_le x y
"x =.> y" := bool_le x y
"x :b: y" := cons_binder x y
"p .2" := snd p
"p .1" := fst p
"ps .*2" := fmap snd ps
"ps .*1" := fmap fst ps
"TT -t> A" := tele_fun TT A
"A -n> B" := ofe_morO A B
"A -d> B" := discrete_funO (fun _ => B)
"x +b+ y" := app_binder x y
"x &&* y" := zip_with andb x y
"'[tele_arg' x ; .. ; z ]" := TargS x .. (TargS z TargO) ..
"'[tele_arg' ]" := TargO
"'[tele' x .. z ]" := TeleS (fun x => .. (TeleS (fun z => TeleO)) ..)
"'[tele' ]" := TeleO
"(||)" := orb
" () " := tt
"(&&)" := andb
"( H 'with' pat )" := {| itrm := H; itrm_vars := hlist.hnil; itrm_hyps := pat |}
"( H $! x1 .. xn 'with' pat )" := {|
itrm := H;
itrm_vars := hlist.hcons x1 .. (hlist.hcons xn hlist.hnil) ..;
itrm_hyps := pat |}
"( H $! x1 .. xn )" := {|
itrm := H;
itrm_vars := hlist.hcons x1 .. (hlist.hcons xn hlist.hnil) ..;
itrm_hyps := EmptyString |}
"#[ Σ1 ; .. ; Σn ]" := gFunctors.app Σ1 .. (gFunctors.app Σn gFunctors.nil) ..
"#[ ]" := gFunctors.nil
"# l" := LitV l
```
Many of those are from Iris or std++, and are probably oversights.https://gitlab.mpi-sws.org/iris/iris/-/issues/378Graveyard for obsolete code2021-06-02T22:38:25ZRobbert KrebbersGraveyard for obsolete codeThere is some obsolete code in Iris, like Hoare triples, view shifts, STS, the logic-level wrapper for auth, that have bit rot quite a bit and should basically never be used by end-users.
Since this code supports some claims in papers, ...There is some obsolete code in Iris, like Hoare triples, view shifts, STS, the logic-level wrapper for auth, that have bit rot quite a bit and should basically never be used by end-users.
Since this code supports some claims in papers, it might be useful to keep it in some form. But what would be the best place?https://gitlab.mpi-sws.org/iris/iris/-/issues/379Make sealing consistent and document it2020-11-10T13:15:28ZRalf Jungjung@mpi-sws.orgMake sealing consistent and document itWe should document the "sealing" pattern that we use throughout Iris, and make sure that we use it in a consistent way. Things to take care of:
* Avoid eta-expanding the sealed definition; that means that the write lemma only applies to ...We should document the "sealing" pattern that we use throughout Iris, and make sure that we use it in a consistent way. Things to take care of:
* Avoid eta-expanding the sealed definition; that means that the write lemma only applies to the eta-expanded term. This immediately implies that sealing should be done outside of sections.
* Add an `unseal` tactic, either as `Local Ltac` or in a module to avoid polluting the global namespace.
* There is no need to make sealed definitions `Typeclasses Opaque`.
- no eta, ergo no sections
- unseal tactic
- no TC opaque
For example, here is how sealing of a logic-level RA wrapper could look like:
```
Definition mnat_own_auth_def `{!mnatG Σ} (γ : gname) (q : Qp) (n : nat) : iProp Σ :=
own γ (mnat_auth_auth q n).
Definition mnat_own_auth_aux : seal (@mnat_own_auth_def). Proof. by eexists. Qed.
Definition mnat_own_auth := mnat_own_auth_aux.(unseal).
Definition mnat_own_auth_eq : @mnat_own_auth = @mnat_own_auth_def := mnat_own_auth_aux.(seal_eq).
Arguments mnat_own_auth {Σ _} γ q n.
Definition mnat_own_lb_def `{!mnatG Σ} (γ : gname) (n : nat): iProp Σ :=
own γ (mnat_auth_frag n).
Definition mnat_own_lb_aux : seal (@mnat_own_lb_def). Proof. by eexists. Qed.
Definition mnat_own_lb := mnat_own_lb_aux.(unseal).
Definition mnat_own_lb_eq : @mnat_own_lb = @mnat_own_lb_def := mnat_own_lb_aux.(seal_eq).
Arguments mnat_own_lb {Σ _} γ n.
Local Ltac unseal := rewrite
?mnat_own_auth_eq /mnat_own_auth_def
?mnat_own_lb_eq /mnat_own_lb_def.
```
When there are operational typeclasses involved, the `_eq` lemma should also account for those to avoid having to rewrite twice:
```
Program Definition monPred_bupd_def `{BiBUpd PROP} (P : monPred) : monPred :=
MonPred (λ i, |==> P i)%I _.
Next Obligation. solve_proper. Qed.
Definition monPred_bupd_aux : seal (@monPred_bupd_def). Proof. by eexists. Qed.
Definition monPred_bupd := monPred_bupd_aux.(unseal).
Arguments monPred_bupd {_}.
Lemma monPred_bupd_eq `{BiBUpd PROP} : @bupd _ monPred_bupd = monPred_bupd_def.
Proof. rewrite -monPred_bupd_aux.(seal_eq) //. Qed.
```https://gitlab.mpi-sws.org/iris/iris/-/issues/380iDestruct does not handle some patterns that it probably could2020-11-11T16:57:53ZTej Chajedtchajed@gmail.comiDestruct does not handle some patterns that it probably couldThe pattern match in `iDestructHypGo` misses a handful of patterns that perhaps it could process. For example `IDone` could probably be given a sensible interpretation.
Similarly `iDestructHypFindPat` complains about `H //` even though ...The pattern match in `iDestructHypGo` misses a handful of patterns that perhaps it could process. For example `IDone` could probably be given a sensible interpretation.
Similarly `iDestructHypFindPat` complains about `H //` even though that could be processed as `iDestruct ... as H; done`. It does handle `H /=` (by running `simpl` after the destruct).https://gitlab.mpi-sws.org/iris/iris/-/issues/381Make sure we have Hint Mode for every typeclass2021-06-17T13:19:41ZRalf Jungjung@mpi-sws.orgMake sure we have Hint Mode for every typeclassWe should have `Hint Mode` for all our `Class`es. We could detect this with some kind of shell script that greps for `Class`, extracts the name, and then greps for `Hint Mode`.
Currently known missing `Mode`s:
* [ ] `IntoVal`
* [ ] `Wp`...We should have `Hint Mode` for all our `Class`es. We could detect this with some kind of shell script that greps for `Class`, extracts the name, and then greps for `Hint Mode`.
Currently known missing `Mode`s:
* [ ] `IntoVal`
* [ ] `Wp`
* [ ] `Twp`https://gitlab.mpi-sws.org/iris/iris/-/issues/385reshape_expr does not recognize `fill`2020-12-05T08:58:01ZRalf Jungjung@mpi-sws.orgreshape_expr does not recognize `fill`There was not much fallout from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/588, but the bits I saw look like `reshape_expr` is not able to traverse into a `fill K e`. That should be possible, right? If yes, it could avoid re-e...There was not much fallout from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/588, but the bits I saw look like `reshape_expr` is not able to traverse into a `fill K e`. That should be possible, right? If yes, it could avoid re-enabling that instance locally in ReLoC, C and Actris.https://gitlab.mpi-sws.org/iris/iris/-/issues/387Deprecate unqualified "Instance"2020-12-19T17:43:58ZRalf Jungjung@mpi-sws.orgDeprecate unqualified "Instance"With https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/594 (and potentially some follow-up changes), all `Hint` in Iris will be qualified with `Local` or `Global`. I think we should do the same with `Instance`.
@tchajed is there a w...With https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/594 (and potentially some follow-up changes), all `Hint` in Iris will be qualified with `Local` or `Global`. I think we should do the same with `Instance`.
@tchajed is there a way to adjust your script to do that, or will we have to ask the Coq devs for an (opt-in) deprecation warning for `Instance` first, similar to the `Hint` warning that your script is based on?https://gitlab.mpi-sws.org/iris/iris/-/issues/388Dropping support for Coq 8.102020-12-16T12:17:28ZTej Chajedtchajed@gmail.comDropping support for Coq 8.10At some point we should drop support for Coq 8.10.
The benefits are:
- Ltac2 is available starting with Coq 8.11. This would let us integrate https://gitlab.mpi-sws.org/iris/string-ident into Iris and support the `"%H"` intro pattern wi...At some point we should drop support for Coq 8.10.
The benefits are:
- Ltac2 is available starting with Coq 8.11. This would let us integrate https://gitlab.mpi-sws.org/iris/string-ident into Iris and support the `"%H"` intro pattern without any additional work from the user.
- Custom entries [had some bugs](https://github.com/coq/coq/pull/11530) that seem to block their use in !554; in Coq 8.11 and forward we can give good notation for dfracs.
We should probably release Iris 3.4 before dropping support. Before that out of the current MRs I think !572 is the most important, to avoid releasing the mnat library and then immediately renaming it.https://gitlab.mpi-sws.org/iris/iris/-/issues/389Citation guide2020-12-08T17:17:32ZTej Chajedtchajed@gmail.comCitation guideThe docs should have a page explaining what a paper using Iris should cite, between the several Iris papers, the journal paper, and the two IPM papers.The docs should have a page explaining what a paper using Iris should cite, between the several Iris papers, the journal paper, and the two IPM papers.https://gitlab.mpi-sws.org/iris/iris/-/issues/391Add append-only list RA to Iris2021-05-17T16:32:27ZRalf Jungjung@mpi-sws.orgAdd append-only list RA to IrisAppend-only lists are probably the most often requested RA that is not available in Iris. This is a special case of https://gitlab.mpi-sws.org/iris/iris/-/issues/244, that (a) can be landed without having to figure out how to formalize l...Append-only lists are probably the most often requested RA that is not available in Iris. This is a special case of https://gitlab.mpi-sws.org/iris/iris/-/issues/244, that (a) can be landed without having to figure out how to formalize lattices in general, and (b) would probably be a useful dedicated abstraction even if we get general lattices one day.
@haidang wrote [a version of this](https://gitlab.mpi-sws.org/iris/gpfsl/-/blob/graphs/theories/examples/list_cmra.v), which was forked at some point by @jtassaro [for Perennial](https://github.com/jtassarotti/iris-inv-hierarchy/blob/fupd-split-level/iris/algebra/mlist.v) while also adding a logic-level wrapper for `auth (mlist T)` with the following three core assertions:
* authoritative ownership of the full trace
* persistent ownership that some list is a prefix of the trace
* persistent ownership that index i in the trace has some particular value
Perennial also has [another version of this](https://github.com/mit-pdos/perennial/blob/master/src/algebra/append_list.v) by @tchajed that is based on (the Perennial version of) `gmap_view`. And finally, @msammler has [his own implementation](https://gitlab.mpi-sws.org/FCS/lang-sandbox-coq/-/blob/master/theories/lang/heap.v#L18) that is based on the list RA.
I do not have a strong preference for which approach to use for the version in Iris, but we should probably look at all of them to figure out what kinds of lemmas people need for this.Hai DangHai Danghttps://gitlab.mpi-sws.org/iris/iris/-/issues/392Masks in step-taking fupd notation2020-12-10T13:37:03ZRalf Jungjung@mpi-sws.orgMasks in step-taking fupd notationEarlier this year, I have changed the step-taking fupd notation (https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/462). I think this made things better, but I think there's still room for improvement -- in particular with https://gi...Earlier this year, I have changed the step-taking fupd notation (https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/462). I think this made things better, but I think there's still room for improvement -- in particular with https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/595 finally making the more-than-1-step case actually useful in Iris proper.
The current notation is
```coq
(** * Step-taking fancy updates. *)
(** These have two masks, but they are different than the two masks of a
mask-changing update: in [|={Eo}[Ei]▷=> Q], the first mask [Eo] ("outer
mask") holds at the beginning and the end; the second mask [Ei] ("inner
mask") holds around each ▷. This is also why we use a different notation
than for the two masks of a mask-changing updates. *)
Notation "|={ Eo } [ Ei ]▷=> Q" := (|={Eo,Ei}=> ▷ |={Ei,Eo}=> Q)%I : bi_scope.
Notation "|={ E }▷=> Q" := (|={E}[E]▷=> Q)%I : bi_scope.
(** For the iterated version, in principle there are 4 masks: "outer" and
"inner" of [|={Eo}[Ei]▷=>], as well as "begin" and "end" masks [E1] and [E2]
that could potentially differ from [Eo]. The latter can be obtained from
this notation by adding normal mask-changing update modalities: [
|={E1,Eo}=> |={Eo}[Ei]▷=>^n |={Eo,E2}=> Q] *)
Notation "|={ Eo } [ Ei ]▷=>^ n Q" := (Nat.iter n (λ P, |={Eo}[Ei]▷=> P) Q)%I : bi_scope.
Notation "|={ E }▷=>^ n Q" := (|={E}[E]▷=>^n Q)%I : bi_scope.
```
Now it turns out that an n-step update that opens and closes things at each step is basically never useful (or at least that is what things look like so far). So the iterated step-taking update should really open some masks once, then do a bunch of steps with updates, and then close some masks again: [rj1]
```coq
Notation "|={ Eo } [ Ei ]▷=>^ n Q" := (|={Eo,Ei}=> (Nat.iter n (λ P, |={Ei}▷=> P) (|={Ei,Eo}=> Q)))%I : bi_scope.
```
For `n=1` this is equivalent, but for larger `n` it is not (unless `Ei=Eo`). Since this is not just strictly iterating the single-step update any more, maybe the notation should be slightly different to reflect this, such as [rj1']
```coq
Notation "|={ Eo } [ Ei ]▷^ n => Q" := (|={Eo,Ei}=> (Nat.iter n (λ P, |={Ei}▷=> P) (|={Ei,Eo}=> Q)))%I : bi_scope.
```
And then, to make things even stranger, @jjourdan started using this kind of update in !595:
```coq
|={E1,E2}=> |={∅}▷=>^n |={E2,E1}=> P
```
I thought quite a bit about this update the last few days... the empty set makes it look like no invariants can be used "while counting down the steps", but that is not so: when considering masks as resources/tokens (which under the hood they are), this update lets us grab the tokens for `E1\E2` in the beginning, use them throughout the update in any way we please, and give them back in the end. We don't have good proof rules for this general case though. We do have rules for the easier case where `E2=∅`: then one can use `mask_fupd_intro'` to introduce the `|={E1,∅}=>` modality while obtaining `|={∅,E1}=> emp` that can be kept around, and can be used when the goal starts with `|={∅}=>`. In other words:
```coq
|={E1,∅}=> |={∅}▷=>^n |={∅,E1}=> P
----------------------------------
|={E1}=> |={E1}▷=>^n |={E1}=> P
```
So from this it looks like maybe we want to define the iterated step-taking update as [jh]
```coq
Notation "|={ Eo } [ Ei ]▷^ n => Q" := (|={Eo,Ei}=> (Nat.iter n (λ P, |={∅}▷=> P) (|={Ei,Eo}=> Q)))%I : bi_scope.
```
But we need to come up with better proof rules to actually make this conveniently usable, so maybe it's not worth it having such a flexible notation, and we should just have [rj2] (basically the special case of [rj1] where the inner mask is empty, which coincides with [jh] where the inner mask is empty)
```coq
Notation "|={ Eo }▷^ n => Q" := (|={Eo,∅}=> (Nat.iter n (λ P, |={∅}▷=> P) (|={∅,Eo}=> Q)))%I : bi_scope.
```
or maybe we take inspiration from some recent work by @simonspies and go for [simon]
```coq
Notation "|={ E1 , E2 }▷^ n => Q" := (|={E1,∅}=> (Nat.iter n (λ P, |={∅}▷=> P) (|={∅,E2}=> Q)))%I : bi_scope.
```
There's just too many variants that could make sense.^^ (We could also have variants of some earlier notations where the pre- and post-masks are different, but having a notation with three masks seems a bit unwieldy...)
My current thinking is that it's not worth to expose the full power of @jjourdan's theorem (we have no known user that requires it, I think, but we should check in RustBelt), so we can go with one of the last two and exploit that `|={E1,E2}=> |={∅}▷=>^n |={E2,E1}=> P` is implied by the easier-to-use `|={E1\E2,∅}=> |={∅}▷=>^n |={∅,E1\E2}=> P` (I am just a bit worried about how well `solve_nidjs` will be able to handle these masks).
The one thing that is clear is that the current multi-mask multi-step notation is not useful enough to justify its existence -- since there is no way to use it to state the new lemma in !595. That is the one design constraint I have identified so far: have a notation such that we can use it to state a many-step-fupd-lemma that is actually useful (and by this I mean use *just* this notation, not composing it with some pre- and post-updates like @jjourdan did). All of the above fit this condition to some extend, but [rj1] results in a very weak statement that we probably do not want. [jh] will be hard to write good rules for I think (but maybe I am wrong about this), which pushes me towards [rj2]; generalizing that to [simon] means we can even use this notation to define WP (even the WP in !595, where `={∅}▷=∗^(S $ steps_per_step stepcnt) |={∅,E}=>` could become `={∅,E}▷^(S $ steps_per_step stepcnt)=∗`).
That was lots of rambling... any thoughts?https://gitlab.mpi-sws.org/iris/iris/-/issues/393fupd_plainly_laterN = fupd_plain_laterN ?2020-12-23T11:12:46ZPaolo G. Giarrussofupd_plainly_laterN = fupd_plain_laterN ?It seems `fupd_plainly_laterN` is a misnamed copy of `fupd_plain_laterN`. I confirmed this by giving the following proof to the existing statement:
```coq
Lemma fupd_plainly_laterN E n P `{HP : !Plain P} :
(▷^n |={E}=> P) ⊢ |={...It seems `fupd_plainly_laterN` is a misnamed copy of `fupd_plain_laterN`. I confirmed this by giving the following proof to the existing statement:
```coq
Lemma fupd_plainly_laterN E n P `{HP : !Plain P} :
(▷^n |={E}=> P) ⊢ |={E}=> ▷^n ◇ P.
Proof. exact: fupd_plain_laterN. Qed.
```
I'm happy to leave the fix to anybody else.https://gitlab.mpi-sws.org/iris/iris/-/issues/394Document relation between Discrete and Timeless (in appendix?)2021-01-06T13:08:34ZPaolo G. GiarrussoDocument relation between Discrete and Timeless (in appendix?)See discussion in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/607#note_61127 by @robbertkrebbers:
> I also wondered about this a long time ago and came to the same conclusion as you: Discrete P → Timeless P holds, but is not s...See discussion in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/607#note_61127 by @robbertkrebbers:
> I also wondered about this a long time ago and came to the same conclusion as you: Discrete P → Timeless P holds, but is not so useful; Timeless P → Discrete P does not hold; discrete propositions are unlikely to exist.
> It might be worth documenting this somewhere, but I don't know what's the best place. Maybe the appendix?https://gitlab.mpi-sws.org/iris/iris/-/issues/395Generalize frac to dfrac in view camera2021-03-03T16:01:46ZSimon Friis VindumGeneralize frac to dfrac in view cameraThe use of `frac` in the view camera could be generalized to `dfrac`. This would make it possible to "freeze" or persist the authorative element. I don't have a use case for this myself, but, if I recall correctly, @jung or @tchajed had ...The use of `frac` in the view camera could be generalized to `dfrac`. This would make it possible to "freeze" or persist the authorative element. I don't have a use case for this myself, but, if I recall correctly, @jung or @tchajed had one?
The notation would be the same as for the points-to predicate, and in the future the custom entries `dfrac` notation could be reused for this. The view camera is rather new, so breaking changes here are less critical, and it thus seems like a fine place to start with regards to trying to use `dfrac` more.
What do you think? I'd like to work on this if there is support.https://gitlab.mpi-sws.org/iris/iris/-/issues/396Intro pattern `>` has wrong behavior with side-conditions of `iMod`2021-04-29T09:25:46ZRobbert KrebbersIntro pattern `>` has wrong behavior with side-conditions of `iMod````coq
Section atomic.
Context `{!heapG Σ}.
Implicit Types P Q : iProp Σ.
(* These tests check if a side-condition for [Atomic] is generated *)
Check "wp_iMod_fupd_atomic".
Lemma wp_iMod_fupd_atomic E1 E2 P :
(|={E1,E2}=> ...```coq
Section atomic.
Context `{!heapG Σ}.
Implicit Types P Q : iProp Σ.
(* These tests check if a side-condition for [Atomic] is generated *)
Check "wp_iMod_fupd_atomic".
Lemma wp_iMod_fupd_atomic E1 E2 P :
(|={E1,E2}=> P) -∗ WP #() #() @ E1 {{ _, True }}.
Proof.
iIntros ">H".
```
fails with
```
In environment
Σ : gFunctors
heapG0 : heapG Σ
E1, E2 : coPset
P : iProp Σ
Unable to unify
"unseal environments.pre_envs_entails_aux ?PROP (environments.env_intuitionistic ?M11809)
(environments.env_spatial ?M11809) ?M11814"
with
"∀ (σ : language.state heap_lang) (e' : language.expr heap_lang) (κ :
list
(language.observation
heap_lang))
(σ' : language.state heap_lang) (efs : list (language.expr heap_lang)),
language.prim_step (#() #()) σ κ e' σ' efs
→ match stuckness_to_atomicity NotStuck with
| StronglyAtomic => is_Some (language.to_val e')
| WeaklyAtomic => irreducible e' σ'
end".
```
See also https://mattermost.mpi-sws.org/iris/pl/r47q3gcq4fddxnhpddj91yb1wyhttps://gitlab.mpi-sws.org/iris/iris/-/issues/397`iRename` fails with bad error message when not in proof mode2021-02-17T08:48:22ZRobbert Krebbers`iRename` fails with bad error message when not in proof mode```coq
Lemma silly : True.
Proof.
iRename "H" into "H".
```
fails with
```
Unable to unify
"unseal environments.pre_envs_entails_aux ?PROP (environments.env_intuitionistic ?M11770)
(environments.env_spatial ?M11770) ?M11775"
wit...```coq
Lemma silly : True.
Proof.
iRename "H" into "H".
```
fails with
```
Unable to unify
"unseal environments.pre_envs_entails_aux ?PROP (environments.env_intuitionistic ?M11770)
(environments.env_spatial ?M11770) ?M11775"
with "True".
```
The tactic probably does not call `iStartProof` at the beginning.https://gitlab.mpi-sws.org/iris/iris/-/issues/398Use `dom` instead of `∀ k, is_Some (.. !! k) ...`2021-02-17T08:48:46ZRobbert KrebbersUse `dom` instead of `∀ k, is_Some (.. !! k) ...`See for example `big_sepM_sep_zip_with`, `big_sepM_sep_zip`, `big_sepM2_intuitionistically_forall`, `big_sepM2_forall`.
The version with `dom` is more intuitive, and likely easier to prove because one can reason equationally with lemmas...See for example `big_sepM_sep_zip_with`, `big_sepM_sep_zip`, `big_sepM2_intuitionistically_forall`, `big_sepM2_forall`.
The version with `dom` is more intuitive, and likely easier to prove because one can reason equationally with lemmas for `dom`. However, the fact that the set (here `gset`) has to specified explicitly might be annoying.
Note that if we perform this change, there are also some lemmas in std++ that need to be changed.https://gitlab.mpi-sws.org/iris/iris/-/issues/399Upstream more big_op lemmas from Perennial2021-02-17T08:49:05ZRalf Jungjung@mpi-sws.orgUpstream more big_op lemmas from PerennialPerennial has a bunch of big_op lemmas at <https://github.com/mit-pdos/perennial/tree/master/src/algebra/big_op>. At least some of those are certainly worth upstreaming, but I find it hard to figure out where to draw the line.Perennial has a bunch of big_op lemmas at <https://github.com/mit-pdos/perennial/tree/master/src/algebra/big_op>. At least some of those are certainly worth upstreaming, but I find it hard to figure out where to draw the line.https://gitlab.mpi-sws.org/iris/iris/-/issues/400Integrate Tej's simp-lang?2021-02-17T08:49:46ZRalf Jungjung@mpi-sws.orgIntegrate Tej's simp-lang?@tchajed has created https://github.com/tchajed/iris-simp-lang, which is a simple "demo language" to show how to use the Iris language interface. It even comes with an [accompanying Youtube video](https://www.youtube.com/watch?v=HndwyM04...@tchajed has created https://github.com/tchajed/iris-simp-lang, which is a simple "demo language" to show how to use the Iris language interface. It even comes with an [accompanying Youtube video](https://www.youtube.com/watch?v=HndwyM04KEU&feature=youtu.be)! I took a look and watched the video, and I really like it.
I propose we give this more visibility by referencing it from the Iris repo and website, and also we should find some way to ensure that the Coq code remains compatible with latest Iris. The easiest way to do that would be to add an "iris_simp_lang" package in this repository and move the code there. The README could go into the subfolder. @tchajed would that work for you, or did you have other plans? I don't want to appropriate your work, just ensure that it does not bitrot. I could imagine declaring you the maintainer of that subdirectory, so you could e.g. merge MRs for it yourself. @robbertkrebbers what do you think?
I also have some more specific low-level comments, which I leave here just so I do not forget -- but it probably make more sense to discuss the high-level points first. It's really just one remark so far:
* In `heap_ra`, I find it confusing that you end up basically copying (parts of) `gen_heap`. IMO it would make more sense to either use `gen_heap`, or else (for the purpose of exposition) to define something that specifically works for values and locations of this language, but then it should not be called "gen(eral)".https://gitlab.mpi-sws.org/iris/iris/-/issues/401wp_bind does not report a failure message2021-03-05T17:25:13ZTej Chajedtchajed@gmail.comwp_bind does not report a failure messageThe `first [ t1 | fail ]` here is incorrect: https://gitlab.mpi-sws.org/iris/iris/-/blob/4c96a5043ab4f648f4082f2398888c879efd3c36/iris_heap_lang/proofmode.v#L200
```coq
first [ reshape_expr e ltac:(fun K e' => unify e' efoc; wp_bind...The `first [ t1 | fail ]` here is incorrect: https://gitlab.mpi-sws.org/iris/iris/-/blob/4c96a5043ab4f648f4082f2398888c879efd3c36/iris_heap_lang/proofmode.v#L200
```coq
first [ reshape_expr e ltac:(fun K e' => unify e' efoc; wp_bind_core K)
| fail "wp_bind: cannot find" efoc "in" e ]
```
The failure causes the entire construct to fail with a generic error message; what was intended is `fail 1` to bubble it up. Furthermore there's no test of this failure.
This bug was originally reported by François Pottier against https://github.com/tchajed/iris-simp-lang/, which inherited this bug from heap_lang.Tej Chajedtchajed@gmail.comTej Chajedtchajed@gmail.comhttps://gitlab.mpi-sws.org/iris/iris/-/issues/402iFrame performance issues2022-05-06T12:56:32ZRalf Jungjung@mpi-sws.orgiFrame performance issuesThere are some situations where iFrame is rather slow.
- For example [here](https://gitlab.mpi-sws.org/iris/examples/-/merge_requests/43#note_60969) it seems to backtrack a lot on the disjunctions. Maybe it should just not descend into ...There are some situations where iFrame is rather slow.
- For example [here](https://gitlab.mpi-sws.org/iris/examples/-/merge_requests/43#note_60969) it seems to backtrack a lot on the disjunctions. Maybe it should just not descend into disjunctions at all by default?
- Also, @tchajed noticed that `iFrame` is doing a lot of `AsFractional` everywhere, which might also be a too expensive default -- this is tracked separately in https://gitlab.mpi-sws.org/iris/iris/-/issues/351.
- Cc https://gitlab.mpi-sws.org/iris/iris/-/issues/183 for the general "power vs performance" tradeoff in `iFrame`.
- https://gitlab.mpi-sws.org/iris/iris/-/issues/434 for diverging iFrame because Hint Mode is accidentally being circumvented.https://gitlab.mpi-sws.org/iris/iris/-/issues/403Iris 3.42021-03-06T12:22:13ZRalf Jungjung@mpi-sws.orgIris 3.4There was a Coq 8.13 release, so following our promise for the Coq Platform, we should make a compatible release ASAP (the Coq release was already more than a month ago).
[Milestone with potential release blockers](https://gitlab.mpi-sw...There was a Coq 8.13 release, so following our promise for the Coq Platform, we should make a compatible release ASAP (the Coq release was already more than a month ago).
[Milestone with potential release blockers](https://gitlab.mpi-sws.org/iris/iris/-/milestones/6)https://gitlab.mpi-sws.org/iris/iris/-/issues/404Make string-ident a standard part of Iris2021-03-24T11:03:52ZLennard Gähergaeher@mpi-sws.orgMake string-ident a standard part of IrisSince support for Coq 8.10 has been dropped for a while now and 8.11 is required, the `string-ident` plugin could be integrated into Iris master so that the named `%H` intro pattern becomes available in the IPM by default.
Mainly, this w...Since support for Coq 8.10 has been dropped for a while now and 8.11 is required, the `string-ident` plugin could be integrated into Iris master so that the named `%H` intro pattern becomes available in the IPM by default.
Mainly, this would have the benefits of
* not having to explicitly require the user to install the plugin in developments using Iris,
* and thus be beneficial to overall code quality of developments using Iris (since there would be a clear argument for using the new intro pattern instead of using auto-generated names).
@jung suggested I create an issue for this.https://gitlab.mpi-sws.org/iris/iris/-/issues/405Tracking issue for HeapLang interpreter2021-02-16T11:03:04ZRalf Jungjung@mpi-sws.orgTracking issue for HeapLang interpreterThis is the tracking issue for the HeapLang interpreter added in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/564. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
...This is the tracking issue for the HeapLang interpreter added in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/564. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Open issues
* Generalize the monad and move it to std++, and generalize the tactics for the monad.
* Find some way to avoid the `pretty_string` instance, or move it to std++.https://gitlab.mpi-sws.org/iris/iris/-/issues/406Slow typechecking / nonterminating Qed when using auxiliary definitions in RAs2021-03-18T08:26:06ZArmaël GuéneauSlow typechecking / nonterminating Qed when using auxiliary definitions in RAs```coq
From iris.base_logic Require Export invariants gen_heap.
From iris.program_logic Require Export weakestpre ectx_lifting.
From iris.proofmode Require Import tactics.
From iris.algebra Require Import frac auth gmap excl list.
Defin...```coq
From iris.base_logic Require Export invariants gen_heap.
From iris.program_logic Require Export weakestpre ectx_lifting.
From iris.proofmode Require Import tactics.
From iris.algebra Require Import frac auth gmap excl list.
Definition memspecUR : ucmraT :=
gmapUR nat (prodR fracR (agreeR (leibnizO nat))).
Definition regspecUR : ucmraT :=
gmapUR nat (prodR fracR (agreeR (leibnizO nat))).
Definition memreg_specUR := prodUR regspecUR memspecUR.
Definition exprUR : cmraT := (exclR (leibnizO nat)).
Definition cfgUR : ucmraT := prodUR (optionUR exprUR) memreg_specUR.
Class cfgSG Σ := CFGSG {
cfg_invG :> inG Σ (authR cfgUR);
cfg_name : gname }.
Section S.
Context `{cfgSG Σ}.
Lemma spec_heap_valid (e:option (excl (leibnizO nat))) a q w
(rm: gmapUR nat (prodR fracR (agreeR (leibnizO nat))))
(mm: gmapUR nat (prodR fracR (agreeR (leibnizO nat)))) :
False →
own cfg_name (● (e,(rm,mm))) ∗
own cfg_name (◯ (ε, (∅,{[ a := (q, to_agree w) ]})))
-∗ False.
Proof. intro.
iIntros "(Hown & Ha)".
iDestruct (own_valid_2 with "Hown Ha") as "HH". exfalso. assumption.
Qed.
End S.
```
The snippet above:
- works fine with Iris 3.3
- takes a very long time at Qed with Iris 3.4 (modulo replacing `cmraT` with `cmra` in the script)
The issue seems to be with the use of auxiliary definitions to define the resource algebra `cfgUR`. Manually inlining `cfgUR` and the other auxiliary definitions in the definition of `cfgSG` makes it work again with Iris 3.4.
Since the fix is relatively simple, this issue doesn't seem to be too big of a deal, but I thought that I'd report it just in case.
Coq version used: 8.12.1 in both cases.https://gitlab.mpi-sws.org/iris/iris/-/issues/407Tracking issue for list RA2021-03-17T11:50:01ZRalf Jungjung@mpi-sws.orgTracking issue for list RAThis is the tracking issue for the list RA that went to staging in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/654. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper....This is the tracking issue for the list RA that went to staging in https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/654. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Open issues
* The laws of the list camera are kind of weird, because it's very awkward to deal with "holes" in the list, which typically occurs when separating ghost state.
* Is the list RA ever actually needed, or can we replace it by `gmap` + `map_seq`? That deals better with "holes", but [lacks some closure properties](https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/371#note_62685) that can sometimes be useful.https://gitlab.mpi-sws.org/iris/iris/-/issues/408bi.weakestpre imports a module from program_logic2021-06-18T13:09:56ZRalf Jungjung@mpi-sws.orgbi.weakestpre imports a module from program_logic`bi.weakestpre` imports `program_logic.language`, which is a layering violation. We should somehow fix this, either by breaking the dependency or by moving one of the two modules to the other side.`bi.weakestpre` imports `program_logic.language`, which is a layering violation. We should somehow fix this, either by breaking the dependency or by moving one of the two modules to the other side.https://gitlab.mpi-sws.org/iris/iris/-/issues/409Proposed change to naming convention for "dataful" `*G`s2021-06-03T09:08:26ZRalf Jungjung@mpi-sws.orgProposed change to naming convention for "dataful" `*G`sSome of our `*G` typeclasses are different than others: they contain not just `inG` but actual relevant data; usually a `gname` but in the case of `irisG` also some further information about how the Iris program logic is being instantiat...Some of our `*G` typeclasses are different than others: they contain not just `inG` but actual relevant data; usually a `gname` but in the case of `irisG` also some further information about how the Iris program logic is being instantiated. These dataful classes come with a `*PreG` that represent their `inG` (dataless) part.
Dataful `*G`s need to be treated differently, e.g. they have special initialization lemmas and they should not be bundled in library's `*G` as that leads to duplication of said data. So I propose to adjust our naming convention such that one can tell from the name whether a `*G` is dataful or not.
The new naming convention is up for bikeshedding; here are some proposals coming to my mind:
1. We call the dataful class `*DataG` and its `inG`-only part `*G`. So e.g. `heapG` → `heapDataG` and `heapPreG` → `heapG`.
2. We call the dataful class `*DataG` and its `inG`-only part `*PreG`. So e.g. `heapG` → `heapDataG`; `heapPreG` stays.
2. We call the dataful class `*DG` and its `inG`-only part `*PreG`. So e.g. `heapG` → `heapDG`; `heapPreG` stays.
I think I prefer (2) or (3) over (1) because it prevents confusion due to accidentally using the `inG`-only part, and also because it is easier for migration since we don't reuse an old name for a different purpose.
@robbertkrebbers @tchajed @jtassaro what do you think?Ralf Jungjung@mpi-sws.orgRalf Jungjung@mpi-sws.orghttps://gitlab.mpi-sws.org/iris/iris/-/issues/410Modality for `Timeless`2021-04-19T07:51:21ZRalf Jungjung@mpi-sws.orgModality for `Timeless`We have long been looking for a modality corresponding to `Timeless`. @simonspies recently made a proposal, which I am trying to recall (please correct me of this is wrong^^):
```
<timeless> P := ▷ False → P
Timeless P := <timeless> P ⊢ ...We have long been looking for a modality corresponding to `Timeless`. @simonspies recently made a proposal, which I am trying to recall (please correct me of this is wrong^^):
```
<timeless> P := ▷ False → P
Timeless P := <timeless> P ⊢ P
```
Unlike prior attempts, this is a *monadic* modality, i.e. it is easy to introduce but hard to eliminate. That makes it less useful -- I was hoping that `<timeless> P` would be *stronger* than `P` and basically say that the proof only requires timeless resources (restriction of the context, and thus comonadic); instead, here `<timeless> P` is *weaker* than `P`, it basically says "I have a proof of `P` at step-index 0".
The existing `later_false_em` can now be written as `▷ P ⊢ ▷ False ∨ <timeless> P` (or `▷ P ⊢ ◇ <timeless> P`).
But this could still be interesting and useful in other situations we have not considered yet, so it is worth exploring. One open question is which primitive laws we need to derive all the properties of `Timeless` that we currently have. For the record, this is the current definition of `Timeless`:
```
Timeless' P := ▷ P ⊢ ▷ False ∨ P
(* or *)
Timeless' P := ▷ P ⊢ ◇ P
```
By `later_false_em`, we have `Timeless P → Timeless' P` (so the new class is at least as strong). I am not sure about the other direction.https://gitlab.mpi-sws.org/iris/iris/-/issues/411Taking ∃ out of ▷ without Inhabited, more easily2021-04-29T09:25:44ZYusuke MatsushitaTaking ∃ out of ▷ without Inhabited, more easilyIn Iris Proof Mode, destruction of `▷ (∃ (x: A), Φ a)` into `(x) "H"` (where `"H"` will assert `▷ Φ x`) always requires `Inhabited A`, because it uses the lemma `later_exist`.
In some situations, `Inhabited A` is not known a priori.
If w...In Iris Proof Mode, destruction of `▷ (∃ (x: A), Φ a)` into `(x) "H"` (where `"H"` will assert `▷ Φ x`) always requires `Inhabited A`, because it uses the lemma `later_exist`.
In some situations, `Inhabited A` is not known a priori.
If we use the lemma `later_exist_except_0` instead, we get `▷ Φ x` without having `Inhabited A`, under the `◇` modality.
In Iris we are often under the `◇` modality because the update modality `|=>` contains `◇`.
I hope the operation of taking `∃x` out of `▷` without `Inhabited` becomes easier to use.
One possibility is to let Iris Proof Mode apply `later_exist_except_0` when the goal is under the `◇` modality.https://gitlab.mpi-sws.org/iris/iris/-/issues/412Use dfrac everywhere2023-03-18T18:30:39ZRalf Jungjung@mpi-sws.orgUse dfrac everywhere`auth` and `view` support dfrac now, but many of the abstractions built on top of it do not yet:
* [x] `algebra.lib.gmap_view`
* [x] `algebra.lib.mono_nat`
* [ ] `base_logic.lib.ghost_map`
* [ ] `base_logic.lib.mono_nat`
There are more ...`auth` and `view` support dfrac now, but many of the abstractions built on top of it do not yet:
* [x] `algebra.lib.gmap_view`
* [x] `algebra.lib.mono_nat`
* [ ] `base_logic.lib.ghost_map`
* [ ] `base_logic.lib.mono_nat`
There are more `auth`-based abstractions in `algebra.lib` but those do not expose *any* fraction on their authoritative part yet.
Some more are not actually built on top of `view`, but these are or could be exposing fractions that it might be useful to turn into `dfrac`:
* [ ] `base_logic.lib.ghost_var`
* [ ] Cancelable invariants
* [ ] Saved propositions (could be made essentially "`ghost_var` with higher-order ghost state", supporting both persistent immutable and ephemeral mutable saved propositions)
However, before we do all this, we should figure out if there is a way to do that without making these APIs *harder* to use for the common case of only needing fraction `1`. For `gset_bij`, we are already in the situation that users need to write `DfracOwn 1` a lot; I wouldn't want the same to happen e.g. for `ghost_map`.https://gitlab.mpi-sws.org/iris/iris/-/issues/413Better errors when tactic fails to automatically resolve some side-condition2021-07-22T12:54:29ZRalf Jungjung@mpi-sws.orgBetter errors when tactic fails to automatically resolve some side-condition@robbertkrebbers and me sketched a plan (or rather, two possible plans) for how to show better error messages for common stumbling blocks, such as `iMod` with mismatching masks:
1. `ElimModal` already has support for a pure side-conditio...@robbertkrebbers and me sketched a plan (or rather, two possible plans) for how to show better error messages for common stumbling blocks, such as `iMod` with mismatching masks:
1. `ElimModal` already has support for a pure side-condition; we could introduce something like
```
Definition pm_error (s : string) := False
```
and add instances with `error "foo"` as their side-condition; together with some support in `iSolveSideCondition` this could be used to then show better, instance-specific error messages when `iMod` fails.
2. We could add a new typeclass like `ElimModalError` that is used to compute an error message when `ElimModal` failed to find an instance.
Since this is used for diagnostics only, there are no backwards compatibility concerns -- so I feel like we should start with the first approach, since it is easy to implement; we can always switch to something more principled later.https://gitlab.mpi-sws.org/iris/iris/-/issues/414Tracking issue for monotone RA2023-09-11T07:41:21ZRalf Jungjung@mpi-sws.orgTracking issue for monotone RAThis is the tracking issue for the "monotone" RA from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/597. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Open iss...This is the tracking issue for the "monotone" RA from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/597. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Open issues
* How should the RA be called? `monotone` is a very general term, it would be good to find something more specific. Currently it is called `mra` which is short but cryptic. `principal` should then likely become `mra_principal` and all lemmas be prefixed with `mra` as well.
* Do a solid review of the API surface.
Cc @amintimany @robbertkrebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/415Tracking issue for append-only list RA2021-11-22T17:58:29ZRalf Jungjung@mpi-sws.orgTracking issue for append-only list RAThis is the tracking issue for the append-only list RA from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/661. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Op...This is the tracking issue for the append-only list RA from https://gitlab.mpi-sws.org/iris/iris/-/merge_requests/661. A tracking issue is where we track and discuss what still needs to happen to make a module move to Iris proper.
## Open issues
* Do we really want notation for the mono_list algebra elements? The main "pro" reason here is that `dfrac` otherwise becomes somewhat painful. OTOH, mono_nat and gset_bij algebras do not have notation either. It'd be safe to start without notation
and add them on-demand.
* On the logic layer, should `mono_list_auth` take `Qp` or `dfrac`? Eventually we want to move everything to `dfrac` but again the concern is that (without good notation), this will make the library more annoying to use. This is discussed in more generality at https://gitlab.mpi-sws.org/iris/iris/-/issues/412.
* Do a solid review of the API surface.https://gitlab.mpi-sws.org/iris/iris/-/issues/416big_sep lemmas fail to apply when goal is not eta-expanded2021-05-26T11:31:56ZRalf Jungjung@mpi-sws.orgbig_sep lemmas fail to apply when goal is not eta-expandedI just ran into a strange problem:
```coq
Lemma test {A B} (Φ : nat → A → B → PROP) (l1 : list A) (l2 : list B) :
⊢ big_sepL2 Φ l1 l2.
Proof.
Fail iApply big_sepL2_delete.
(* The command has indeed failed with message:
Tactic failu...I just ran into a strange problem:
```coq
Lemma test {A B} (Φ : nat → A → B → PROP) (l1 : list A) (l2 : list B) :
⊢ big_sepL2 Φ l1 l2.
Proof.
Fail iApply big_sepL2_delete.
(* The command has indeed failed with message:
Tactic failure: iApply: cannot apply
(([∗ list] k↦y1;y2 ∈ ?Goal0;?Goal1, ?Goal k y1 y2)
∗-∗ ?Goal ?Goal2 ?Goal3 ?Goal4
∗ ([∗ list] k↦y1;y2 ∈ ?Goal0;?Goal1, if decide (k = ?Goal2) then emp else ?Goal k y1 y2))%I. *)
iApply (big_sepL2_delete Φ).
(* This works. *)
```
For some reason Coq needs to be manually given `Φ` here. That should not be the case.
The only difference between the lemma statement and the goal is an eta-expansion of `Φ`.https://gitlab.mpi-sws.org/iris/iris/-/issues/417Revert !118: Use ∃ instead of SIgma for extension axiom2022-08-02T16:52:12ZRobbert KrebbersRevert !118: Use ∃ instead of SIgma for extension axiomI am trying to define a camera for general multisets, so multisets where the types can be an arbitrary OFE instead of a countable type (as for `gmultiset`).
The approach I'm following is to define:
```coq
Record multiset A := MultiSet ...I am trying to define a camera for general multisets, so multisets where the types can be an arbitrary OFE instead of a countable type (as for `gmultiset`).
The approach I'm following is to define:
```coq
Record multiset A := MultiSet { multiset_car : list A }.
```
And define `dist` and `(≡)` to be modulo permutations. For permutations I use https://coq.inria.fr/distrib/current/stdlib/Coq.Lists.SetoidPermutation.html
Unfortunately, this does not work: the extension axiom of cameras does not seem provable.
```coq
✓{n} x → x ≡{n}≡ y1 ⋅ y2 →
{ z1 : A & { z2 | x ≡ z1 ⋅ z2 ∧ z1 ≡{n}≡ y1 ∧ z2 ≡{n}≡ y2 } }
```
The problem is that I need to construct `z1` and `z2` as a sigma type, not an ordinary exist. But the type of permutations is a `Prop`, so I cannot do this.
Here's the whole code I have so far:
```coq
From Coq Require Import SetoidPermutation.
From iris.algebra Require Export cmra.
Lemma PermutationA_mono {A} (R1 R2 : relation A) xs1 xs2 :
(∀ x1 x2, R1 x1 x2 → R2 x1 x2) →
PermutationA R1 xs1 xs2 → PermutationA R2 xs1 xs2.
Proof. induction 2; econstructor; by eauto. Qed.
Record multiset A := MultiSet { multiset_car : list A }.
Arguments MultiSet {_} _.
Arguments multiset_car {_} _.
Section multiset.
Context {A : ofe}.
Implicit Types x y : A.
Implicit Types X Y : multiset A.
Local Instance multiset_equiv_instance : Equiv (multiset A) := λ X1 X2,
∀ n, PermutationA (≡{n}≡) (multiset_car X1) (multiset_car X2).
Local Instance multiset_dist_instance : Dist (multiset A) := λ n X1 X2,
PermutationA (≡{n}≡) (multiset_car X1) (multiset_car X2).
Local Instance multiset_valid_instance : Valid (multiset A) := λ _, True.
Local Instance multiset_validN_instance : ValidN (multiset A) := λ _ _, True.
Local Instance multiset_unit_instance : Unit (multiset A) := MultiSet [].
Local Instance multiset_op_instance : Op (multiset A) := λ X1 X2,
MultiSet (multiset_car X1 ++ multiset_car X2).
Local Instance multiset_pcore_instance : PCore (multiset A) := λ X, Some ε.
Global Instance multiset_singleton : Singleton A (multiset A) := λ x,
MultiSet [x].
Lemma multiset_ofe_mixin : OfeMixin (multiset A).
Proof.
split; rewrite /equiv /dist /multiset_equiv_instance /multiset_dist_instance /=.
- done.
- intros n. split.
+ by intros X.
+ intros X1 X2 ?. done.
+ intros X1 X2 X3 ??. by etrans.
- intros n X1 X2. apply PermutationA_mono, dist_S.
Qed.
Canonical Structure multisetO := Ofe (multiset A) multiset_ofe_mixin.
Global Instance multiset_ofe_discrete : OfeDiscrete A → OfeDiscrete multisetO.
Proof.
intros HA [xs1] [xs2] Hxs n. revert Hxs. apply PermutationA_mono.
by intros x1 x2 ->%(discrete _).
Qed.
Lemma multiset_cmra_mixin : CmraMixin (multiset A).
Proof.
apply cmra_total_mixin; try by eauto.
- intros X n Y1 Y2 HY. by apply (PermutationA_app _).
- by intros n X1 X2.
- intros X1 X2 X3. admit. (* boring case *)
- intros X1 X2 n. apply (PermutationA_app_comm _).
- by intros X n.
- intros X1 X2 _. exists ε. by intros n.
- intros n [xs] [ys1] [ys2] _. rewrite /equiv /dist /op
/multiset_equiv_instance /multiset_dist_instance /multiset_op_instance /=.
(* Stuck here. The witness [PermutationA (dist n) xs (ys1 ++ ys2)] basically
says how the elements in [xs] are distributed over [ys1] and [ys2].
Intuitively, it says element 0 of [xs] goes to position [i0] in
[ys1 ++ ys2], element 1 of [xs] goes to position [i1] in ys1 ++ ys2 and so
on. *)
(* I would like to use the lemma [PermutationA_decompose], but that does
not work since it gives an [∃]. *)
(* I tried to prove it by induction on the list instead, but that seems
pointless. At some point I need to invert on the [PermutationA] witness,
which is not possible. *)
induction ys1 as [|y1 ys1 IH]; intros Hxs; simpl in *.
{ by exists (MultiSet []), (MultiSet xs). }
admit.
Admitted.
Canonical Structure multisetR := Cmra (multiset A) multiset_cmra_mixin.
Lemma multiset_ucmra_mixin : UcmraMixin (multiset A).
Proof. split; [done | | done]. by intros X n. Qed.
Canonical Structure multisetUR := Ucmra (multiset A) multiset_ucmra_mixin.
Global Instance multiset_cancelable X : Cancelable X.
Proof. Admitted.
Global Instance multiset_singleton_ne : NonExpansive (singleton (B:=multiset A)).
Proof. intros n x1 x2. by repeat constructor. Qed.
Global Instance multiset_singleton_proper :
Proper ((≡) ==> (≡)) (singleton (B:=multiset A)).
Proof. apply (ne_proper _). Qed.
Global Instance multiset_singleton_dist_inj n :
Inj (dist n) (dist n) (singleton (B:=multiset A)).
Proof. intros x1 x2. Admitted.
Global Instance multiset_singleton_inj :
Inj (≡) (≡) (singleton (B:=multiset A)).
Proof.
intros x1 x2 Hx. apply equiv_dist=> n. apply (inj singleton). by rewrite Hx.
Qed.
End multiset.
Global Arguments multisetO : clear implicits.
Global Arguments multisetR : clear implicits.
Global Arguments multisetUR : clear implicits.
```https://gitlab.mpi-sws.org/iris/iris/-/issues/418library inG instances should be local2021-06-02T14:46:21ZRalf Jungjung@mpi-sws.orglibrary inG instances should be localCurrently, the `libG → inG` instances in library are usually `Global`. This is bad, we should treat them as library implementation details and make them `Local`.Currently, the `libG → inG` instances in library are usually `Global`. This is bad, we should treat them as library implementation details and make them `Local`.https://gitlab.mpi-sws.org/iris/iris/-/issues/419Iron slowdown investigation2021-06-17T07:20:40ZRalf Jungjung@mpi-sws.orgIron slowdown investigationIron has [slowed down by 1.8%](https://coq-speed.mpi-sws.org/d/Ne7jkX6kk/coq-speed?orgId=1&var-metric=instructions&var-project=iron&var-branch=master&var-config=All&var-group=().*&from=1621369920715&to=1622831955880) just by updating Iri...Iron has [slowed down by 1.8%](https://coq-speed.mpi-sws.org/d/Ne7jkX6kk/coq-speed?orgId=1&var-metric=instructions&var-project=iron&var-branch=master&var-config=All&var-group=().*&from=1621369920715&to=1622831955880) just by updating Iris from `dev.2021-03-06.3.b0708b01` to `dev.2021-06-03.0.2959900d`. I am not sure if we can do anything about that, but it would be good to at least figure out which changes caused the slowdown (though it looks like there at several, so this might be "death by a thousand cuts").https://gitlab.mpi-sws.org/iris/iris/-/issues/420Use siProp more in building the uPred (and BI) interfaces2023-03-04T18:40:53ZRalf Jungjung@mpi-sws.orgUse siProp more in building the uPred (and BI) interfacesuPred defines a few (primitive) connectives that could all be defined in terms of an `siProp` mbedding:
- internal equality
- pure embedding
- plainly modality
- CMRA validity
Then we can have CMRA validity in any logic with an `siProp`...uPred defines a few (primitive) connectives that could all be defined in terms of an `siProp` mbedding:
- internal equality
- pure embedding
- plainly modality
- CMRA validity
Then we can have CMRA validity in any logic with an `siProp` embedding. Going this route might also finally let us get rid of `base_logic.algebra` and instead prove these lemmas in `siProp` so they can be used "for free" in any BI with an `siProp` embedding. We might even want to use `siProp` to define some of our algebraic classes.
@haidang started working on this since some of this is useful for BedRock. Here's the full plan we came up with to stage that (not saying @haidang is doing all these stages, and the later ones are obviously subject to change):
1. Add uPred_si_embed and uPred_si_emp_valid to upred.v; remove uPred_pure, uPred_internal_eq, uPred_plainly. Re-define those in terms of that and re-derive all the old rules in bi.v. The interesting part will be figuring out the laws for the new connectives such that we can derive all the laws for the old things that got removed.
2. (depends on 1) Add proof mode support for embed and emp_valid.
3. (depends on 1) Define uPred_cmra_valid in terms of uPred_si_embed via some new siProp for CMRA validity.
4. (depends on 1) Add iris/base_logic/lib/monpred_si_embed.v and transitive embedding.
5. (depends on 3, 2) State base_logic.algebra lemmas in siProp so they work for all logics that have an siProp embedding.
6. (depends on 3; having 5 would be useful) Add BiOwn to abstract over RA ownership.
7. (depends on 1) State uPred_entails as an siProp.
8. (probably best after 5 or together with 5) Change CMRA axioms so that validity is defined as an siProp.
9. (depends on ?, speculative) Use siProp in BI interface? For what exactly? Get rid of pure so we can define it in general for all BIs with an siProp embedding? Use siProp entailments?
10. (depends on ?, probably best after 8, highly speculative) Change OFE axioms to use `siProp` for dinstance? Still need to derive `Prop`-based version for setoid rewriting though.Robbert KrebbersRobbert Krebbershttps://gitlab.mpi-sws.org/iris/iris/-/issues/421Bad error message for failing iInduction2021-06-14T13:59:19ZRalf Jungjung@mpi-sws.orgBad error message for failing iInductionI am not sure what is going wrong with the following `iInduction`, and IPM's error doesn't tell me:
```
Inductive val :=
| PairV (v1 v2 : val)
| InjLV (v : val)
| InjRV (v : val).
Lemma test {Σ} (val_rel : val → val → iProp Σ) v_t...I am not sure what is going wrong with the following `iInduction`, and IPM's error doesn't tell me:
```
Inductive val :=
| PairV (v1 v2 : val)
| InjLV (v : val)
| InjRV (v : val).
Lemma test {Σ} (val_rel : val → val → iProp Σ) v_t v_s :
val_rel v_t v_s -∗ True.
Proof. iInduction v_t as [| |] "IH" forall v_s.
(* Error: No matching clauses for match. *)
```