FStarLang / FStarLang/FStar

Recursive function that passes itself to a helper function not equal its definition

Open
#121 9 comments 0 reactions 0 assignees View on GitHub
component/typechecker kind/bug
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.