This fixes the problem in iris/iris!275 (comment 42062)

Marianna Rapoport authored 6 years ago and Ralf Jung committed 6 years ago

- Removing head of list of observations after each reduction step in definition of wp
- Adding support for observations to state_interp and world
- Applying Ralf's suggestions to previous commit (e.g. replacing /\ and -> with unicode characters)

It can be infered now.

This reverts commit 913059d2.

This reverts commit 849abb8d, reversing changes
made to 8de0b894.  The merge was done
accidentally, before review happened.

This has some advantages:

- Evaluation contexts behave like a proper "Huet's zipper", and thus:
  + We no longer need to reverse the list of evaluation context items in the
    `reshape_expr` tactic.
  + The `fill` function becomes tail-recursive.
- It gives rise to more definitional equalities in simulation proofs using
  binary logical relations proofs.

  In the case of binary logical relations, we simulate an expressions in some
  ambient context, i.e. `fill K e`. Now, whenever we reshape `e` by turning it
  into `fill K' e'`, we end up with `fill K (fill K' e')`. In order to use the
  rules for the expression that is being simulated, we need to turn
  `fill K (fill K' e')` into `fill K'' e'` for some `K'`. In case of the old
  `foldr`-based approach, we had to rewrite using the lemma `fill_app` to
  achieve that. However, in case of the old `foldl`-based `fill`, we have that
  `fill K (fill K' e')` is definitionally equal to `fill (K' ++ K) e'` provided
  that `K'` consists of a bunch of `cons`es (which is always the case, since we
  obtained `K'` by reshaping `e`).

Note that this change hardly affected `heap_lang`. Only the proof of
`atomic_correct` broke. I fixed this by proving a more general lemma
`ectxi_language_atomic` about `ectxi`-languages, which should have been there
in the first place.

This patch was created using

  find -name *.v | xargs -L 1 awk -i inplace '{from = 0} /^From/{ from = 1; ever_from = 1} { if (from == 0 && seen == 0 && ever_from == 1) { print "Set Default Proof Using \"Type*\"."; seen = 1 } }1 '

and some minor manual editing

(which are useful in Amin's logical relations development).

This generalization is surprisingly easy in Iris 3.0, so I could not
resist not doing it :).

* Values are considered as atomic expressions (this does not hurt, and
  this makes the proofs of atomicity simpler).

I also reverted 7952bca4 since there is no need for atomic to be a
boolean predicate anymore. Moreover, I introduced a hint database
fsaV for solving side-conditions related to FSAs, in particular,
side-conditions related to expressions being atomic.

and show that this is an instance of evaluation contexts