CHANGELOG.md

In this changelog, we document "large-ish" changes to Iris that affect even the way the logic is used on paper. We also document changes in the Coq development; every API-breaking change should be listed, but not every new lemma.

Iris master

Coq 8.11 is no longer supported in this version of Iris.

Changes in algebra:

• Generalize the authorative elements of the view, auth and gset_bij cameras to be parameterized by a discardable fraction (dfrac) instead of a fraction (frac). Normal fractions are now denoted ●{#q} a and ●V{#q} a. Lemmas affected by this have been renamed such that the "frac" in their name has been changed into "dfrac". (by Simon Friis Vindum)
• Generalize namespace_map to reservation_map which enhances gmap positive A with a notion of 'tokens' that enable allocating a particular name in the map. See algebra.reservation_map for further information.
• Add dyn_reservation_map which further extends reservation_map with the ability to dynamically allocate an infinite set of tokens. This is useful to perform synchronized allocation of the same name in two maps/APIs without dedicated support from one of the involved maps/APIs. See algebra.dyn_reservation_map for further information.
• Demote the Camera structure on list to iris_staging since its composition is not very well-behaved.
• Extend gmap_view with lemmas for "big" operations on maps.

Changes in bi:

• Add new lemmas big_sepM2_delete_l and big_sepM2_delete_r.
• Rename big_sepM2_lookup_1 → big_sepM2_lookup_l and big_sepM2_lookup_2 → big_sepM2_lookup_r.

Changes in proofmode:

• Add support for pure names %H in intro patterns. This is now natively supported whereas the previous experimental support required installing https://gitlab.mpi-sws.org/iris/string-ident. (by Tej Chajed)
• Add support for destructing existentials with the intro pattern [%x ...]. (by Tej Chajed)

Changes in base_logic:

• Add ghost_map, a logic-level library for a gmap K V with an authoritative view and per-element points-to facts written k ↪[γ] w.
• Generalize the soundness lemma of the base logic step_fupdN_soundness. It applies even if invariants stay open accross an arbitrary number of laters. (by Jacques-Henri Jourdan)

Changes in program_logic:

• Change definition of weakest precondition to use a variable number of laters (i.e., logical steps) for each physical step of the operational semantics, depending on the number of physical steps executed since the begining of the execution of the program. See merge request !595. This implies several API-breaking changes, which can be easily fixed in client formalizations in a backward compatible manner as follows:
  • Ignore the new parameter ns in the state interpretation, which corresponds to a step counter.
  • Use the constant function "0" for the new field num_laters_per_step of irisG.
  • Use fupd_intro _ _ for the new field state_interp_mono of irisG.
  • Some proofs using lifting lemmas and adequacy theorems need to be adapted to ignore the new step counter. (by Jacques-Henri Jourdan)
• Remove wp_frame_wand_l; add wp_frame_wand as more symmetric replacement.

Changes in heap_lang:

• Rename Build_loc constructor for loc type to Loc.
• Add atomic Xchg ("exchange"/"swap") operation. (by Simon Hudon, Google LLC)

The following sed script helps adjust your code to the renaming (on macOS, replace sed by gsed, installed via e.g. brew install gnu-sed). Note that the script is not idempotent, do not run it twice.

sed -i -E -f- $(find theories -name "*.v") <<EOF
# auth and view renames from frac to dfrac
s/\b(auth|view)_(auth|both|update)_frac_(is_op|op_invN|op_inv|inv_L|validN|op_validN|valid|op_valid|valid_2|valid_discrete|includedN|included|alloc|validI|validI_2|validI_1|validI|)\b/\1_\2_dfrac_\3/g
s/\bgset_bij_auth_frac_(\w*)\b/gset_bij_auth_dfrac_\1/g
s/\bgset_bij_auth_empty_frac_valid\b/gset_bij_auth_empty_dfrac_valid/g
s/\bbij_both_frac_valid\b/bij_both_dfrac_valid/g
s/\bbig_sepM2_lookup_1\b/big_sepM2_lookup_l/g
s/\bbig_sepM2_lookup_2\b/big_sepM2_lookup_r/g
EOF

Iris 3.4.0 (released 2021-02-16)

The highlights and most notable changes of this release are as follows:

• Coq 8.13 is now supported; the old Coq 8.9 and Coq 8.10 are not supported any more.
• The new view RA construction generalizes auth to user-defined abstraction relations. (thanks to Gregory Malecha for the inspiration)
• The new dfrac RA extends frac (fractions 0 < q ≤ 1) with support for "discarding" some part of the fraction in exchange for a persistent witness that discarding has happened. This can be used to easily generalize fractional permissions with support for persistently owning "any part" of the resource. (by Simon Friis Vindum)
• The new gmap_view RA provides convenient lemmas for ghost ownership of heap-like structures with an "authoritative" view. Thanks to dfrac, it supports both exclusive (mutable) and persistent (immutable) ownership of individual map elements.
• With this release we are beginning to provide logic-level abstractions for ghost state, which have the advantage that the user does not have to directly interact with RAs to use them.
  • ghost_var provides a logic-level abstraction of ghost variables: a mutable "variable" with fractional ownership.
  • mono_nat provides a "monotone counter" with a persistent witnesses representing a lower bound of the current counter value. (by Tej Chajed)
  • gset_bij provides a monotonically growing partial bijection; this is useful in particular when building binary logical relations for languages with a heap.
• HeapLang provides a persistent read-only points-to assertion l ↦□ v. (by Simon Friis Vindum)
• We split Iris into multiple opam packages: coq-iris no longer contains HeapLang, which is now in a separate package coq-iris-heap-lang. The two packages coq-iris-deprecated (for old modules that we eventually plan to remove entirely) and coq-iris-staging (for new modules that are not yet ready for prime time) exist only as development versions, so they are not part of this release.
• The proofmode now does a better job at picking reasonable names when moving variables into the Coq context without a name being explicitly given by the user. However, the exact variable names remain unspecified. (by Tej Chajed)

Further details are given in the changelog below.

This release of Iris was managed by Ralf Jung and Robbert Krebbers, with contributions by Arthur Azevedo de Amorim, Dan Frumin, Enrico Tassi, Hai Dang, Michael Sammler, Paolo G. Giarrusso, Rodolphe Lepigre, Simon Friis Vindum, Tej Chajed, and Yusuke Matsushita. Thanks a lot to everyone involved!

Changes in algebra:

• Add constructions to define a camera through restriction of the validity predicate (iso_cmra_mixin_restrict) and through an isomorphism (iso_cmra_mixin).
• Add a frac_agree library which encapsulates frac * agree A for some OFE A, and provides some useful lemmas.
• Add the view camera view, which generalizes the authoritative camera auth by being parameterized by a relation that relates the authoritative element with the fragments.
• Add the camera of discardable fractions dfrac. This is a generalization of the normal fractional camera. See algebra.dfrac for further information.
• Add gmap_view, a camera providing a "view of a gmap". The authoritative element is any gmap; the fragment provides fractional ownership of a single key, including support for persistent read-only ownership through dfrac. See algebra.lib.gmap_view for further information.
• Add mono_nat, a wrapper for auth max_nat. The result is an authoritative nat where a fragment is a lower bound whose ownership is persistent. See algebra.lib.mono_nat for further information.
• Add the gset_bij resource algebra for monotone partial bijections. See algebra.lib.gset_bij for further information.
• Rename agree_op_inv' → to_agree_op_inv, agree_op_invL' → to_agree_op_inv_L, and add to_agree_op_invN.
• Rename auth_auth_frac_op_invL → auth_auth_frac_op_inv_L, excl_auth_agreeL → excl_auth_agree_L, frac_auth_agreeL → frac_auth_agree_L, and ufrac_auth_agreeL → ufrac_auth_agree_L.
• Fix direction of auth_auth_validN to make it consistent with similar lemmas, e.g., auth_auth_valid. The direction is now ✓{n} (● a) ↔ ✓{n} a.
• Rename auth_both_valid to auth_both_valid_discrete and auth_both_frac_valid to auth_both_frac_valid_discrete. The old name is used for new, stronger lemmas that do not assume discreteness.
• Redefine the authoritative camera in terms of the view camera. As part of this change, we have removed lemmas that leaked implementation details. Hence, the only way to construct elements of auth is via the elements ●{q} a and ◯ b. The constructor Auth, and the projections auth_auth_proj and auth_frag_proj no longer exist. Lemmas that referred to these constructors have been removed, in particular: auth_equivI, auth_validI, auth_included, auth_valid_discrete, and auth_both_op. For validity, use auth_auth_valid*, auth_frag_valid*, or auth_both_valid* instead.
• Rename auth_update_core_id into auth_update_frac_alloc.
• Rename cmra_monotone_valid into cmra_morphism_valid (this rename was forgotten in !56).
• Move the *_validI and *_equivI lemmas to a new module, base_logic.algebra. That module is exported by base_logic.base_logic so it should usually be available everywhere without further changes.
• The authoritative fragment ✓ (◯ b : auth A) is no longer definitionally equal to ✓ b.
• Change *_valid lemma statements involving fractions to use Qp addition and inequality instead of RA composition and validity (also in base_logic and the higher layers).
• Move algebra.base module to prelude.prelude.
• Strengthen cmra_op_discrete to assume only ✓{0} (x1 ⋅ x2) instead of ✓ (x1 ⋅ x2).
• Rename the types ofeT→ofe, cmraT→cmra, ucmraT→ucmra, and the constructors OfeT→Ofe, CmraT→Cmra, and UcmraT→Ucmra since the T suffix is not needed. This change makes these names consistent with bi, which also does not have a T suffix.
• Rename typeclass instances of CMRA operational typeclasses (Op, Core, PCore, Valid, ValidN, Unit) to have a _instance suffix, so that their original names are available to use as lemma names.
• Rename frac_valid'→frac_valid, frac_op'→frac_op, ufrac_op'→ufrac_op, coPset_op_union → coPset_op, coPset_core_self → coPset_core, gset_op_union → gset_op, gset_core_self → gset_core, gmultiset_op_disj_union → gmultiset_op, gmultiset_core_empty → gmultiset_core, nat_op_plus → nat_op, max_nat_op_max → max_nat_op. Those names were previously blocked by typeclass instances.

Changes in bi:

• Add big op lemmas big_op{L,L2,M,M2,S}_intuitionistically_forall and big_sepL2_forall, big_sepMS_forall, big_sepMS_impl, and big_sepMS_dup.
• Add lemmas to big-ops that provide ownership of a single element and permit changing the quantified-over predicate when re-assembling the big-op: big_sepL_lookup_acc_impl, big_sepL2_lookup_acc_impl, big_sepM_lookup_acc_impl, big_sepM2_lookup_acc_impl, big_sepS_elem_of_acc_impl, big_sepMS_elem_of_acc_impl.
• Add lemmas big_sepM_filter' and big_sepM_filter matching the corresponding big_sepS lemmas.
• Add lemmas for big-ops of magic wands: big_sepL_wand, big_sepL2_wand, big_sepM_wand, big_sepM2_wand, big_sepS_wand, big_sepMS_wand.
• Add notation ¬ P for P → False to bi_scope.
• Add fupd_mask_intro which can be conveniently iApplyed to goals of the form |={E1,E2}=> to get rid of the fupd in the goal if E2 ⊆ E1. The lemma fupd_mask_weaken Enew can be iApplyed to shrink the first mask to Enew without getting rid of the modality; the same effect can also be obtained slightly more conveniently by using iMod with fupd_mask_subseteq Enew. To make the new names work, rename some existing lemmas: fupd_intro_mask → fupd_mask_intro_subseteq, fupd_intro_mask' → fupd_mask_subseteq (implicit arguments also changed here), fupd_mask_weaken → fupd_mask_intro_discard. Remove fupd_mask_same since it was unused and obscure. In the BiFUpd axiomatization, rename bi_fupd_mixin_fupd_intro_mask to bi_fupd_mixin_fupd_mask_subseteq and weaken the lemma to be specifically about emp (the stronger version can be derived).
• Remove bi.tactics with tactics that predate the proofmode (and that have not been working properly for quite some time).
• Strengthen persistent_sep_dup to support propositions that are persistent and either affine or absorbing.
• Fix the statement of the lemma fupd_plainly_laterN; the old lemma was a duplicate of fupd_plain_laterN.
• Strengthen big_sepL2_app_inv by weakening a premise (it is sufficient for one of the two pairs of lists to have equal length).
• Rename equiv_entails → equiv_entails_1_1, equiv_entails_sym → equiv_entails_1_2, and equiv_spec → equiv_entails.
• Remove the laws pure_forall_2 : (∀ a, ⌜ φ a ⌝) ⊢ ⌜ ∀ a, φ a ⌝ from the BI interface and factor it into a type class BiPureForall.

Changes in proofmode:

• The proofmode now preserves user-supplied names for existentials when using iDestruct ... as (?) "...". This is backwards-incompatible if you were relying on the previous automatic names (which were always "H", possibly freshened). It also requires some changes if you were implementing IntoExist yourself, since the typeclass now forwards names. If your instance transforms one IntoExist into another, you can generally just forward the name from the premise.
• The proofmode also preserves user-supplied names in iIntros, for example with iIntros (?) and iIntros "%", as described for destructing existentials above. As part of this change, it now uses a base name of H for pure facts rather than the previous default of a. This also requires some changes if you were implementing FromForall, in order to forward names.
• Make iFrame "less" smart w.r.t. clean up of modalities. It now consistently removes the modalities <affine>, <absorbing>, <persistent> and □ only if the result after framing is True or emp. In particular, it no longer removes <affine> if the result after framing is affine, and it no longer removes □ if the result after framing is intuitionistic.
• Allow framing below an <affine> modality if the hypothesis that is framed is affine. (Previously, framing below <affine> was only possible if the hypothesis that is framed resides in the intuitionistic context.)
• Add Coq side-condition φ to class ElimAcc (similar to what we already had for ElimInv and ElimModal).
• Add a tactic iSelect pat tac (similar to select in std++) which runs the tactic tac H with the name H of the last hypothesis of the intuitionistic or spatial context matching pat. The tactic iSelect is used to implement:
  • iRename select (pat)%I into name which renames the matching hypothesis,
  • iDestruct select (pat)%I as ... which destructs the matching hypothesis,
  • iClear select (pat)%I which clears the matching hypothesis,
  • iRevert select (pat)%I which reverts the matching hypothesis,
  • iFrame select (pat)%I which cancels the matching hypothesis.

Changes in base_logic:

• Add a ghost_var library that provides (fractional) ownership of a ghost variable of arbitrary Type.
• Define a ghost state library on top of the mono_nat resource algebra. See base_logic.lib.mono_nat for further information.
• Define a ghost state library on top of the gset_bij resource algebra. See base_logic.lib.gset_bij for further information.
• Extend the gen_heap library with read-only points-to assertions using discardable fractions.
  • The mapsto connective now takes a dfrac rather than a frac (i.e., positive rational number Qp).
  • The notation l ↦{ dq } v is generalized to discardable fractions dq : dfrac.
  • The new notation l ↦{# q} v is used for a concrete fraction q : frac (e.g., to enable writing l ↦{# 1/2} v).
  • The new notation l ↦□ v is used for the discarded fraction. This persistent proposition provides read-only access to l.
  • The lemma mapsto_persist : l ↦{dq} v ==∗ l ↦□ v is used for making the location l read-only.
  • See the changes to HeapLang for an indication on how to adapt your language.
  • See the changes to iris-examples for an indication on how to adapt your development. In particular, instead of ∃ q, l ↦{q} v you likely want to use l ↦□ v, which has the advantage of being persistent (rather than just duplicable).
• Change type of some ghost state lemmas (mostly about allocation) to use ∗ instead of ∧ (consistent with our usual style). This affects the following lemmas: own_alloc_strong_dep, own_alloc_cofinite_dep, own_alloc_strong, own_alloc_cofinite, own_updateP, saved_anything_alloc_strong, saved_anything_alloc_cofinite, saved_prop_alloc_strong, saved_prop_alloc_cofinite, saved_pred_alloc_strong, saved_pred_alloc_cofinite, auth_alloc_strong, auth_alloc_cofinite, auth_alloc.
• Change uPred_mono to only require inclusion at the smaller step-index.
• Put iProp/iPreProp-isomorphism into the own construction. This affects clients that define higher-order ghost state constructions. Concretely, when defining an inG, the functor no longer needs to be applied to iPreProp, but should be applied to iProp. This avoids clients from having to push through the iProp/iPreProp-isomorphism themselves, which is now handled once and for all by the own construction.
• Rename gen_heap_ctx to gen_heap_interp, since it is meant to be used in the state interpretation of WP and since _ctx is elsewhere used as a suffix indicating "this is a persistent assumption that clients should always have in their context". Likewise, rename proph_map_ctx to proph_map_interp.
• Move uPred.prod_validI, uPred.option_validI, and uPred.discrete_fun_validI to the new base_logic.algebra module. That module is exported by base_logic.base_logic so these names are now usually available everywhere, and no longer inside the uPred module.
• Remove the gen_heap notations l ↦ - and l ↦{q} -. They were barely used and looked very confusing in context: l ↦ - ∗ P looks like a magic wand.
• Change gen_inv_heap notation l ↦□ I to l ↦_I □, so that ↦□ can be used by gen_heap.
• Strengthen mapsto_valid_2 conclusion from ✓ (q1 + q2)%Qp to ⌜✓ (q1 + q2)%Qp ∧ v1 = v2⌝.
• Change gen_heap_init to also return ownership of the points-to facts for the initial heap.
• Rename mapsto_mapsto_ne to mapsto_frac_ne, and add a simpler mapsto_ne that does not require reasoning about fractions.
• Deprecate the auth and sts modules. These were logic-level wrappers around the underlying RAs; as far as we know, they are unused since they were not flexible enough for practical use.
• Deprecate the viewshift module, which defined a binary view-shift connective with an implicit persistence modality. It was unused and too easily confused with ={_}=∗, the binary view-shift (fancy update) without a persistence modality.