leanprover-community / leanprover-community/iris-lean

Guarded fixpoints

Open
#428 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

claimed experiment feat
Dominant language
Lean
Stars
218
Forks
63
Avg merge
1d 23h
Merged PRs (30d)
22

Description

Can we metaprogram away the functor/fixpoint construction everyone copy-pastes for defining partial weakest preconditions? I'm picturing something that behaves like partial_fixpoint but for guarded recursion:

def wp (s : Stuckness) (E : CoPset) (e₁ : Expr) (Φ : Val -> IProp GF) : IProp GF :=
  match toVal e₁ with
  | some v => iprop(|={E}=> Φ v)
  | none => iprop(∀ (σ₁ : State) (ns : Nat) (obs obs' : List Obs) (nt : Nat),
    stateInterp σ₁ ns (obs ++ obs') nt ={E,∅}=∗
    ⌜s.MaybeReducible (e₁, σ₁)⌝ ∗
    ∀ e₂ σ₂ eₜ, ⌜(e₁, σ₁) -<obs>-> (e₂, σ₂, eₜ)⌝ -∗
      £ (ι.numLatersPerStep ns + 1) ={∅}▷=∗^[ι.numLatersPerStep ns + 1] |={∅,E}=>
      stateInterp σ₂ (ns + 1) obs' (nt + eₜ.length) ∗
      wp E e₂ Φ ∗ [∗list] e' ∈ eₜ, wp ⊤ e' ι.forkPost)
guarded_fixpoint

Like partial_fixpoint and coinductive_fixpoint etc, I'd imagine that guarded_fixpoint first tries to solve the contractivity goal by something like aesop_contractive, but also gives an escape hatch for doing it manually

guarded_fixpoint contractive by  
    ...

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading the existing partial_fixpoint and coinductive_fixpoint implementations, then inspect how aesop_contractive is used. Define the guarded_fixpoint interface, including automatic contractivity solving and the manual contractive by escape hatch. Done means the issue's guarded recursion example can use the new command.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.