On Fri, Jul 12, 2013 at 4:13 AM, Dave Reynolds <[email protected]> wrote: > On 11/07/13 18:48, Joshua TAYLOR wrote: >> >> I'm experiencing some confusion about how tabling and the side effects >> (or required computation) of builtins interact. In particular, here's >> a set of rules that implicitly describes a list structure (a -> b -> >> c) where a value for each element can be computed only after the value >> for its successor (if any) has been computed). I've represented this >> with three backwards chaining rules. The computed value is simply a >> string concatenation of 'value ' and the node's URI. >> >> >> [rule_a: (a value ?value) <- (b value ?value0) (a compute ?value)] >> [rule_b: (b value ?value) <- (c value ?value0) (b compute ?value)] >> [rule_c: (c value ?value) <- (c compute ?value)] >> [tableAndHide: -> tableAll() hide(compute)] >> [compute: (?s compute ?o) <- bound(?s) print( ## computing value for >> ?s ) strConcat('value ', ?s, ?o)] >> >> >> When I write the inference model built on a reasoner with these rules, >> the print builtin is called more times than I would have expected. >> The output is >> >> >> ## computing value for c >> ## computing value for b >> ## computing value for a >> ## computing value for a >> <a> <value> "value a" . >> >> ## computing value for b >> <b> <value> "value b" . >> >> ## computing value for c >> <c> <value> "value c" . >> >> >> In the very beginning, it's good that the print values are called in >> the order c, b, a, but I'm confused as to why when each node in the >> graph is printed, the corresponding print statement from the compute >> rule is executed again. I had expected the tabling to memoize the >> value. What am I missing here? A complete working example (whose >> output is the above) is included here. > > > Tabling stores the results of goals for a particular shape. So whether you > re-evaluate rules depends on the order in which you ask goals. In your case > this depends on the N3 writer so is rather outside your control. > > If I modify your code to do: > > printStatements(infModel, null, null, null); > printStatements(infModel, null, null, null); > > Then the output is: > > > ## computing value for c > - (c value 'value c') > > ## computing value for b > - (b value 'value b') > > ## computing value for a > - (a value 'value a') > - (c value 'value c') > - (b value 'value b') > - (a value 'value a') > > As you would expect. > > If I asked a grounded goal first: > > printStatements(infModel, infModel.createResource("a"), null, null); > printStatements(infModel, null, null, null); > > Then I get: > > > ## computing value for a > ## computing value for c > ## computing value for b > ## computing value for a > - (a value 'value a') > - (a value 'value a') > - (b value 'value b') > - (c value 'value c') > > The apparent duplicate computation for 'a' is because in the first case > rule_a is satisfying goal: > (a ? ?) > in the second case it satisfying: > (? ? ?) > > It so happens that all solutions for rule_a will match the first pattern so > the second pattern won't turn up any new answers. But the current rule > engine is not clever enough to know that. It just sees that it has results > tabled for a special case and is now being asked about a more general case > so can't be sure the table is complete for the new goal. > > Actually it's worse than that, if I remember rightly the tabling is rather > too goal specific and you not only get redundant computation but redundant > storage.
Thanks, I think this explanation has helped a lot. I didn't dig into the details, but by looking at the reasoner trace, it appears that writing the InfModel in N3 first asks for all triples (* * *) and then when writing a particular resource r out, asks for triples (r * *). Based on your explanation, I can see why the rule is getting called again. As to why this issue arose: I've been implementing the builtin for generating backward chaining rules that will visit trees in the RDF graph in a particular order (as mentioned in an earlier thread [1]) in order to ensure that a particular builtin is called on the nodes of the tree in a post-order traversal. As this showed, I can guarantee the post-order traversal, but I was surprised by the *repeated* calling. I think I'll just have to make the builtin do some memoization in order to avoid repeated computation, since it looks like I have to accept the builtin getting *called* repeatedly. That's not a problem though. Yet again, thanks for the quick and clear answer! //JT [1] http://mail-archives.apache.org/mod_mbox/jena-users/201307.mbox/%3CCA+Q4Jn=_gsG6rE-CPmnxtborYwfWct2B=au4tphseb0mcsz...@mail.gmail.com%3E -- Joshua Taylor, http://www.cs.rpi.edu/~tayloj/
