FStarLang / FStarLang/FStar

Avoid lemma duplication between `bool` and `prop` predicates

Open
#3,095 1 comment 0 reactions 0 assignees View on GitHub
area/usability component/libraries
Dominant language
F*
Stars
3.1k
Forks
266
Avg merge
21h 1m
Merged PRs (30d)
54

Description

From @TWal in https://github.com/FStarLang/FStar/pull/3094#issuecomment-1810450113 :

> The bool and prop properties are causing a lot of redundancy in ulib, but is it needed?
While I agree that we need to define each predicate twice (although it would have been better with some consistent naming convention, e.g. noRepeats vs no_repeats_p, or memP vs no_repeats_p), probably that each lemma could be defined only once?
I feel like we could define lemmas only on the prop predicates, and using a lemma stating the equivalence between bool / prop predicates it would suffice to deduce the lemmas on bool predicates?
Probably that it could even be done automatically with carefully crafted SMT patterns?
>
> The comment above the lemma mem_memP seem to go in this direction
>
> ```
> (** Correctness of [mem] for types with decidable equality. TODO:
> replace [mem] with [memP] in relevant lemmas and define the right
> SMTPat to automatically recover lemmas about [mem] for types with
> decidable equality *)
> ```

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the duplicated bool and prop predicates and the ulib lemma named mem_memP, using the discussion linked from PR 3094 as context. Done means determining whether prop-side lemmas plus predicate-equivalence lemmas can replace the bool-side duplicates, potentially through suitable SMT patterns, without losing the relevant deductions.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.