FStarLang / FStarLang/FStar

Calc proofs on partial terms

Open
#2,013 0 comments 0 reactions 0 assignees View on GitHub
component/calc kind/enhancement kind/question
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.