leanprover-community / leanprover-community/iris-lean

Iris data structures

Open
#427 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

The paper Inductive Predicates via Least Fixpoints in Higher-Order Separation Logic talks about defining "Iris Inductives". I think this would be a great feature to add to core Iris-Lean. Here's an illustrative example from the paper translated into Lean-y syntax:

iinductive IsListWithTail (tl : loc) : loc → list val → iProp GF where
  | nil : tl ↦ NIL -∗ IsListWithTail tl tl []
  | cons {v vs l l'} : l ↦ CONS (v,#l') -∗ IsListWithTail tl l' vs -∗ IsListWithTail tl l (v :: vs)
  | del {vs l l'} : l ↦ #l' -∗ IsListWithTail tl l' vs -∗ IsListWithTail tl l vs

I think we have all the theory for this, though getting an iinductive which behaves like a Lean inductive includes plenty of corner cases that would need some care. I'm similarly curious if we might be able to write a nice version of istructure-- I'd expect that to be a lot easier.

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 linked paper's discussion of Iris Inductives and comparing its illustrative iinductive syntax with the existing Iris-Lean implementation. The issue names no files or tests, so first locate the definitions and elaboration entry points for related core constructs. Done would require an agreed scope for iinductive, including its corner cases, and corresponding validation; istructure is presented as a separate possible feature.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.