Skip to content

Improve `iFrame` to instantiate existential quantifiers

Ike Mulder requested to merge snyke7/iris:ci/better_frame_exist into master

This MR enables iFrame to instantiate existential quantifiers. For example:

Lemma test_iFrame_exists_instantiate (Φ Ψ : nat  PROP) P Q :
  P  Φ 0  Ψ 1  Q   n, Φ n   m, Ψ m  P  Q.
  iIntros "(HP & HΦ & HΨ & HQ)".
  iFrame "HΨ". (* instantiates the inner existential quantifier [m] *)
  iFrame "HP". (* keeps the outer existential quantifier [n] around *)
  iFrame "HΦ". (* instantiates the outer existential quantifier [n] *)

The tricky part of this functionality is achieving acceptable performance. A naive implementation with two Frame instances (one to instantiate, one to keep the quantifier around) would need to check 2^n possibilities for n quantifiers.

This MR circumvents that: it uses a more general lemma for Frameing under existentials, which allows us to defer making this choice.
Suppose we want to find a frame instance Frame P (∃ a, Φ a) ?R (~= P ∗ R ⊢ ∃ a, Φ a, and we wish to compute R).
Operationally, this MR does the following:

  • Run typeclass search for Frame P (Φ ?a) ?R', with ?a an evar. If this fails, we quit.
  • If a has been unified with a concrete term, the remaining goal R is just R'
  • If a remains an evar, the remaining goal R will be ∃ a, R'.

The approach in the code is a bit more general---it will find all the freshly generated evars occurring in a, and turn these back into existential quantifiers.

The MR currently removes support for framing existential quantifiers that occur beneath definitions. This can be fixed, but it would be good to discuss if this should be default behavior.

I discussed and showed this to some people at the Iris workshop. I've tried to simplify the code a bit since then. !989 (merged) was also needed to ensure this MR behaves well.

Edited by Ike Mulder

Merge request reports