3 ms·
backtracking is perilous in general; logic programming languages have really nice abilities for such but I don't know how to avoid pathological inefficiency.
by vmchale 2y ago
backtracking is perilous in general; logic programming languages have really nice abilities for such but I don't know how to avoid pathological inefficiency.
- YeGoblynQueenne 2y agoWith memoization as in tabling (a.k.a. SLG-Resolution): https://www.swi-prolog.org/pldoc/man?section=tabling https://www.swi-prolog.org/pldoc/man?section=tabling Re-evaluation of a tabled predicate is avoided by memoizing the answers. This can realise huge performance enhancements as illustrated in section 7.1. It also comes with two downsides: the memoized answers are not automatically updated or invalidated if the world (set of predicates on which the answers depend) changes and the answer tables must be stored (in memory). Known to the Prolog community since about the 1980's if I got my references right.