Tabling the wolf, sheep, cabbage

I tried that a little while ago and couldn’t get it work (I still ended up with infinite loops, but gave up at that point rather than digging into it). But things might have changed, so I can re-try.

I noticed in Constraint Solving and Planning with Picat that there’s an “nt” mode (Section 4.2, page 81 of the PDF):

The last mode, Mn , can be nt, indicating that the corresponding argument will not be tabled.

It’s not clear to me why this can only be used for the last mode; perhaps it’s because the last argument is presumed to be a return value?

Adding a cross reference for “lazy” and “eager” tabling from

I have little clue what this means. If you just want to ignore some argument just write a wrapper without the argument. Otherwise, tabling creates a table per call variant which stores the instances of this variant for which the predicate is true. Mode directed tabling or answer subsumption change this in the sense that for specified arguments we do not add all variants to the table, but instead maintain a single “aggregated” answer. There is a lot to say about the semantics. From a termination point of view this can turn an infinite number of anwers into a finite number.

I want the value. But I don’t want it to be tabled (it’s just the path or a “trace” of the intermediate steps, and because it can contain cycles, it can grow to an unbounded extent).

But when I think a bit more about the problem, I realize that if the “trace” value isn’t tabled, only a single result will be returned (in effect, the same as a mode of “-”). This requires more thought … I’ll re-try the lattice(Pred) approach again to see if I can get it working this time.

New application, same issue?

I’m looking at implementing a packrat (memoizing) parser and tabling seems to be a good place to start, but I’m getting stuck. Ideally (I think) I need an argument subsumption mode that indicates that argument is to be ignored for tabling purposes, i.e., treat it as an anonymous variable.

In this particular application, the argument is a term defining the grammar which a) is fairly large, b) is potentially cyclic, and c) is constant for the lifetime of the table (1 parsing operation).

I can almost do this by using the “-” (first) mode, but it trips over the cyclic term. And I can’t easily use a wrapper because the grammar is required to produce the results to be tabled.

Has anything changed since the last post over a year ago? Should I be using tabling for this?