4 ms·
Do you see a good way to include backtracking in an imperative programming language? I can imagine how unification would work, since the ubiquitous "pattern ma
by radomir_cernoch 2y ago
Do you see a good way to include backtracking in an imperative programming language?
I can imagine how unification would work, since the ubiquitous "pattern matching" is a special case of Prolog's unification. But I've never seen how backtracking could be useful...
- vmchale 2y agobacktracking 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.