Recursive function that passes itself to a helper function not equal its definition
- Dominant language
- F*
- Stars
- 3.1k
- Forks
- 266
- Avg merge
- 21h 1m
- Merged PRs (30d)
- 54
Description
F\* cannot prove that my parallel substitution function is equal to its definition when applied to an abstraction. The following assert fails:
```
assert(subst (EAbs t e1) s1 = EAbs t (subst e1 (subst_eabs subst s1)));
```
This is exactly the case that F\* couldn't prove terminating, so either the termination problem is causing F\* to ignore this match branch, or there is something strange going on.
[3:16:03 PM] Catalin Hritcu: Hey Nik, what happens after F\* can't prove a function terminating and it yields a corresponding error; does the definition of the function still get fed to Z3?
[3:16:25 PM] Catalin Hritcu: i.e. does a termination failure affect the logical encoding?
[3:17:38 PM] Catalin Hritcu: I'm asking because the termination argument of my parallel substitution function is highly nontrivial, still I was hoping to prove the rest before returning to termination
[3:18:13 PM] Catalin Hritcu: just that it seems that F\* doesn't properly use the non-obviously terminating definition in other proofs
Contributor guide
Research direction
Start from the failing assertion involving subst, EAbs, and subst_eabs, then inspect how F* handles the recursive function after reporting a termination failure. Determine whether the non-terminating definition is encoded for subsequent proofs, and make the assertion behavior consistent with that result.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100