What is goal tabling in Clojure core.logic?
78 views
Skip to first unread message
Gordon Gustafson
Sep 8, 2018, 4:11:16 PM9/8/18
to minikanren
I've found these, but I'm still a little confused:
1. What exactly is tabling for? Is it for helping programs terminate, or is it a performance optimization?
2. Can it be used to 'cache' the results of a goal that's expensive to compute?
3. Are there any more examples of how to use tabling, particularly ^:tabled with the defne/defna/defnu forms?
Rick Moynihan
Sep 9, 2018, 2:18:07 PM9/9/18
to minikanren
These are good questions, I've been going through a similar experience again recently. Initially confusing tabling with core.logic's pldb implementation, and the ^:index metadata flags.
I've been really enjoying using core.logic, but the lack of documentation and doc strings leaves you constantly guessing. In particular it makes it hard to know what functions are part of the logic programming API and what are part of the implementation. I suspect some are both, for interrop scenarios etc.
The approach I and I think others have taken is to leverage the minikanren literature & papers, along with the excellent Reasoned Schemer. As far as I've seen core.logic implements most of this stuff, so you can find the equivalent and use it. This said, it would clearly help to have better documentation in core.logic. I'd offer to help in this regard, but I'm a beginer here myself.
Regarding tabling have you looked at W. Byrds thesis, it covers it:
R.
William Byrd
Sep 10, 2018, 1:43:43 AM9/10/18
to minikanren
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 minikanren+...@googlegroups.com.
> To post to this group, send email to minik...@googlegroups.com.
> Visit this group at https://groups.google.com/group/minikanren.
> For more options, visit https://groups.google.com/d/optout.
> 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?
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?
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?
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 minikanren+...@googlegroups.com.
> To post to this group, send email to minik...@googlegroups.com.
> Visit this group at https://groups.google.com/group/minikanren.
> For more options, visit https://groups.google.com/d/optout.
Reply all
Reply to author
Forward
0 new messages