Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Register
  • Sign in
  • Iris Iris
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 171
    • Issues 171
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 15
    • Merge requests 15
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Releases
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Iris
  • IrisIris
  • Merge requests
  • !783

Added capability for stripping multiple laters per step in HeapLang

  • Review changes

  • Download
  • Email patches
  • Plain diff
Merged Jonas Kastberg requested to merge jihgfee/iris-coq:later_stripping into master Mar 22, 2022
  • Overview 50
  • Commits 13
  • Pipelines 14
  • Changes 5

In !595 (merged) the Iris program logic was extended with capability for stripping an amount of laters per step relative to the amount of steps taking thus far.

This was, however, never ported to HeapLang. It was instead instantiated with the constant function λ _, 0, retaining the original functionality of the language.

This MR seeks to add this functionality by:

  • Adding a monotonically increasing number to the state interpretation (and ghost functor) of HeapLang
  • Adding non-invasive lemmas that lets the user interact with this number by
    • Obtaining a new lower bound steps_lb 0 in the presence of any wp (via wp_lb_init)
    • Incrementing an existing lower bound steps_lb n to steps_lb (S n) when taking a step (via wp_lb_update)
    • Derive propositions P guarded under a number of laters relative to an existing lower bound steps_lb n (via wp_step_fupdN_lb).

The following formal rules summarises the idea in Hoare Triple notation (OBS: lemma names differ): Screenshot_2022-03-23_at_18.27.32 The usefulness of this functionality is illustrated here: actris!26 (merged)

In particular, we previously had to use a skipN instruction within a lock to strip an amount of laters relative to the physical state. With this change we can instead track this amount in the logic, and strip all of the necessary laters.

The change seems entirely non-invasive, seeing that all user-level specifications remain intact.

EDIT: Thanks to @lgaeher for suggesting the more general theorem for total adequacy, which let me bump the total adequacy theorem of HeapLang

Edited Mar 23, 2022 by Jonas Kastberg
Assignee
Assign to
Reviewers
Request review from
Time tracking
Source branch: later_stripping