Hi Gordon! > I've found these, but I'm still a little confused: > https://github.com/clojure/core.logic/wiki/Tabling > https://github.com/clojure/core.logic/wiki/Features#user-content-tabling > https://clojuredocs.org/clojure.core.logic/tabled > > 1. What exactly is tabling for? Is it for helping programs terminate, or is > it a performance optimization?
Both. Tabling can be thought of an an extended version of memoization that works with mutually-recursive goals, even goals that produce infinitely many results. Also, unlike traditional memoization, tabling can handle calls whose arguments contain fresh logic variables. > 2. Can it be used to 'cache' the results of a goal that's expensive to > compute? Yes. Just like memoization, tabling can change the asymptotic running time of certain algorithms, although perhaps at the cost of additional space. Tabling can also cut off certain infinite loops, such as trying to find all paths between two nodes in a directed graph that contains cycles. Normally, a run* would result in divergence, since core.logic/miniKanren would try going through the cycle once, twice, ..., a billion times, ..., etc. Tabling would cache the result of the first time through the cycle, and use the result for subsequent calls, cutting off the loop. Of course, maybe you *want* to consider paths with different numbers of times through a cycle to be distinct answers. If this is the case, you shouldn't table the path relation (and you shouldn't use a run*). > 3. Are there any more examples of how to use tabling, particularly ^:tabled > with the defne/defna/defnu forms? I'm not familiar with core.logic's tabling forms, but as Rick pointed out, my dissertation contains a section on tabling, with examples. I believe David Nolen adapted the core.logic code from the dissertation code, which was written by Ramana Kumar and me, while working with Dan Friedman. Knowing David, the core.logic code may be improved over the original tabling code. The tabling code in my dissertation has a few issues: 1. tabling only works for unification, not for other constraints, such as disequality constraints 2. tabling only works for pure relations, without side effects, which only unify the arguments passed into the relation--no conda or condu is allowed, and no unifying with logic variables that aren't passed into the relation 3. the tabling implementation in the dissertation is quite slow, especially compared with the modern 'faster-miniKanren' implementation I don't know which, if any, of these issues are also present in the core.logic tabling implementation. I suspect that core.logic's tabling is faster, since core.logic in general is faster than the rather slow version of miniKanren in my dissertation. A great, extremely readable introduction to tabling (using Prolog, but the idea is the same) is: David S. Warren. 1992. Memoing for logic programs. Commun. ACM 35, 3 (March 1992), 93-111. DOI=http://dx.doi.org/10.1145/131295.131299 Hope this helps! Cheers, --Will > -- > You received this message because you are subscribed to the Google Groups > "minikanren" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/minikanren. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "minikanren" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/minikanren. For more options, visit https://groups.google.com/d/optout.
