kanren icon indicating copy to clipboard operation
kanren copied to clipboard

Fix associative-commutative relations and the use of term walk groundedness

Open brandonwillard opened this issue 2 years ago • 0 comments

ground_order doesn't really order terms in a way that avoids infinite recursion in term_walko (e.g. when called by the kanren.assoccomm goals). There should be a way to handle this—at least better than it currently does.

This PR adds a new test, test_eq_assoccomm_scaling, (an expected failure) that demonstrates how poorly the assoccomm goals perform.

The test creates a decently sized term graph containing assoc-comm operators and another one that differs only at the top-level (i.e. one graph starts with an add operator and the other a mul). This should be no problem, since the two cannot unify from the start due to the operator discrepancy. However, due to the way the assoccomm goals descend into all permutations, it currently takes too long to fail. The changes in this PR attempt to address this issue.

  • [ ] Get test_eq_assoccomm_scaling to pass

This PR replaces #27.

brandonwillard avatar Nov 14 '21 19:11 brandonwillard