Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Extensional TT as formulated is not suitable for automated unification #34

Open
Russoul opened this issue Jan 28, 2024 · 0 comments
Open

Comments

@Russoul
Copy link
Owner

Russoul commented Jan 28, 2024

I've hit this problem while working on #6.
When solving a unification problem of the sort:

Σ₀ (Γ ⊦ ? : A) Σ₁ (Γ ⊦ ? = t : A)

We need to be able to check whether t can be typed in Σ₀, otherwise we wouldn't be able to instantiate ?.
But checking that can't be automated because t might depend on equality assumptions in Σ₁. That dependence in not reflected in t itself (so forgotten) and can't be reconstructed either (theoretically impossible due to presence of equality reflection). Hence that part of unification is not amenable to automation. Hence unification overall is not amenable to automation.

We have to resolve this somehow if we hope to have a usable language. What's certain is that the foundation doesn't cut it as is and must be rethought.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant