metamath / metamath-knife

Metamath-knife can rapidly verify Metamath proofs, providing strong confidence that the proofs are correct.
Apache License 2.0
25 stars 10 forks source link

Unification and Substitution #16

Closed tirix closed 2 years ago

tirix commented 2 years ago

This introduces formula unification and substitution, which are straightforward once the formula syntax tree is known. This PR also comes along with a handful of simple tests cases for unification and substitution.

tirix commented 2 years ago

This is a naive implementation of formula unification and substitution, in the sense that it is not optimized.

Currently, the syntax tree nodes of a formula are stored in a Vec, which belongs to the formula. I plan to replace this by an Arc pointer to a slice, so that several formulas can use the same underlying node storage.

This would allow at least two optimizations:

I included more ideas for improvements in the header of formula.rs.

david-a-wheeler commented 2 years ago

Looks okay, I appreciate the included test. That next stage ("Arc"ing) should produce a substantial performance boost.

tirix commented 2 years ago

Thanks for the review @david-a-wheeler ! I'll give Mario some more time if he wants to have a look.

I think next on the list would be a clippy pass, then this improvement (maybe some benchmarking to measure how much this improves would be nice?)