Builtins called repeatedly even with tabling?

[Joshua TAYLOR <jo...@gmail.com>]

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.

Thanks in advance!
Joshua Taylor


import com.hp.hpl.jena.rdf.model.InfModel;
import com.hp.hpl.jena.rdf.model.ModelFactory;
import com.hp.hpl.jena.reasoner.rulesys.GenericRuleReasoner;
import com.hp.hpl.jena.reasoner.rulesys.Rule;
import com.hp.hpl.jena.vocabulary.ReasonerVocabulary;

public class RepeatedBuiltinExample {

	private final static String rules = "\n" +
			// Given a list structure, a -> b -> c, for each element, the
element to its right
			// must have a value before its own value can be computed.
			"[rule_a: (a value ?value) <- (b value ?value0) (a compute ?value)]\n" +
			"[rule_b: (b value ?value) <- (c value ?value0) (b compute ?value)]\n" +
			"[rule_c: (c value ?value) <- (c compute ?value)]\n" +
			// Table everything, and don't show compute in the model
			"[tableAndHide: -> tableAll() hide(compute)]\n" +
			// The value of the compute property for a node is 'value [node]'.
			"[compute: (?s compute ?o) <- bound(?s) print( ## computing value
for ?s ) strConcat('value ', ?s, ?o)]";

	public static void main( final String[] args ) {
		final GenericRuleReasoner reasoner = new GenericRuleReasoner(
Rule.parseRules( rules ));
		reasoner.setMode( GenericRuleReasoner.HYBRID );
		reasoner.setParameter(ReasonerVocabulary.PROPtraceOn, false);
		final InfModel infModel = ModelFactory.createInfModel( reasoner,
ModelFactory.createDefaultModel() );
		infModel.write( System.out, "N3" );
	}
}

-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/

Re: Builtins called repeatedly even with tabling?

[Joshua TAYLOR <jo...@gmail.com>]

On Fri, Jul 12, 2013 at 4:13 AM, Dave Reynolds
<da...@gmail.com> 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=Au4tpHseB0McsZaDw@mail.gmail.com%3E

-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/

Re: Builtins called repeatedly even with tabling?

[Dave Reynolds <da...@gmail.com>]

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.

Dave

>
> Thanks in advance!
> Joshua Taylor
>
>
> import com.hp.hpl.jena.rdf.model.InfModel;
> import com.hp.hpl.jena.rdf.model.ModelFactory;
> import com.hp.hpl.jena.reasoner.rulesys.GenericRuleReasoner;
> import com.hp.hpl.jena.reasoner.rulesys.Rule;
> import com.hp.hpl.jena.vocabulary.ReasonerVocabulary;
>
> public class RepeatedBuiltinExample {
>
> 	private final static String rules = "\n" +
> 			// Given a list structure, a -> b -> c, for each element, the
> element to its right
> 			// must have a value before its own value can be computed.
> 			"[rule_a: (a value ?value) <- (b value ?value0) (a compute ?value)]\n" +
> 			"[rule_b: (b value ?value) <- (c value ?value0) (b compute ?value)]\n" +
> 			"[rule_c: (c value ?value) <- (c compute ?value)]\n" +
> 			// Table everything, and don't show compute in the model
> 			"[tableAndHide: -> tableAll() hide(compute)]\n" +
> 			// The value of the compute property for a node is 'value [node]'.
> 			"[compute: (?s compute ?o) <- bound(?s) print( ## computing value
> for ?s ) strConcat('value ', ?s, ?o)]";
>
> 	public static void main( final String[] args ) {
> 		final GenericRuleReasoner reasoner = new GenericRuleReasoner(
> Rule.parseRules( rules ));
> 		reasoner.setMode( GenericRuleReasoner.HYBRID );
> 		reasoner.setParameter(ReasonerVocabulary.PROPtraceOn, false);
> 		final InfModel infModel = ModelFactory.createInfModel( reasoner,
> ModelFactory.createDefaultModel() );
> 		infModel.write( System.out, "N3" );
> 	}
> }
>