Calc proofs on partial terms
- Dominant language
- F*
- Stars
- 3.1k
- Forks
- 267
- Avg merge
- 10h 45m
- Merged PRs (30d)
- 54
Description
This fails withouth the `px (x+1)` call, needed only to make the formulas involved well-typed, but not for the proof itself.
```fstar
module ImpureCalc
open FStar.Calc
assume val p : int -> prop
assume val t : x:int{p x} -> int
assume val px : x:int -> Lemma (p x)
assume val txy : x:int{p x} -> Lemma (let _ = px (x+1) in t x == t (x + 1))
let test (x : int{p x}) =
px (x + 1); // needed
calc (==) {
t x;
== { txy x }
t (x + 1);
}
```
It would be nice if each justification could be used to check the well-formedness of the following step, or something similar to that. I'm not sure it's doable, particularly since `calc` is meant to hide steps from one another, but opening this to track the discussion.
Reported by @msprotz for a more contrived example in HACL*.
Contributor guide
Research direction
Start by reproducing the `ImpureCalc` example and focus on the `calc` block and its `txy` justification. Investigate whether each justification can establish the well-formedness of the following step without the separate `px (x + 1)` call; done means the example type-checks and the proof still succeeds without that call.
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
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100