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

add formal substitutions and deep memoization #62

Open
thibautbenjamin opened this issue Sep 25, 2024 · 0 comments
Open

add formal substitutions and deep memoization #62

thibautbenjamin opened this issue Sep 25, 2024 · 0 comments

Comments

@thibautbenjamin
Copy link
Owner

Ideas to improve the performance:

  • Add formal substitutions to the unchecked syntax and to the kernel syntax. Instead of computing every term down to applied coherences, we could just have a syntax for applied term. The unchecked syntax should carry around checked terms to apply the same way it carries around checked coherences. typechecking of the checked terms should be much faster, as we only need to check the substitution, and that it matches the context of the term, using the cut rule. Checking term equality becomes more complex. If we are lucky, the two things are the same term applied to the same substitution. If it's not the case, we need to compute the terms down to coherences and checked that it's the same coherence applied to the same substitution. However, the comparison of substitution can now only be made by comparing locally maximal variables, because the substitutions are already checked, which gets around having to compute everything and should save a significant amount of time overall. Another benefit arises when constructing terms: it's not necessary anymore to compute applied substitutions everywhere but instead just store formal applications.

  • Deep memoization: An idea due to Jamie, implemented in hotomotopy.io -> in the syntax tree, any two equal subterm should be physically the same, and every single operation should be memoized so that the same computation is never repeated twice. This seems harder to implement and I don't think it will have a big impact if we already implement the previous idea. But if even with the previous idea we are too slow we can try this.

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