Re: ISSUE-22: Proposal based on sh:hasShape

On 6/17/2015 2:35, Peter F. Patel-Schneider wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
>
>
> On 06/15/2015 05:35 PM, Holger Knublauch wrote:
>> On 6/15/2015 23:35, Peter F. Patel-Schneider wrote:
>>>> Wouldn't this problem be resolved by disallowing memoizing?
>>>> sh:hasShape is our own function that we can define in whatever way we
>>>> want.
>>> Some form of memoizing is needed in procedural approaches to recursion
>>> so that loops terminate.
>> I don't see why. In my proposal sh:hasShape will terminate on the first
>> truly recursive call (with exactly the same arguments).
> This is a simple form of memoization.
>
>> Do you have a counter example?
> A counter example to what?  That some form of memoizing is needed?

I am looking for an example where my proposal with sh:hasShape (throwing 
an exception on recursion) would still lead to infinite loops.

>
>> BTW I have fixed the issue with walking the AND and OR operands from left
>> to right, as discussed yesterday:
>>
>> https://github.com/w3c/data-shapes/commit/0b7a54857026b1ab1852912e60df99094b
> 5482d0
>
> You
> have now stated that and and or are evaluated left to right and
> short-circuit when they hit false for and and true for or.  (Well, except
> for the bugs.)
>
> What happens if the recursive shape is returning a value that overrides
> false for and or true for or?

I have meanwhile implemented the aforementioned approach to return 
"unknown" if sh:hasShape cannot perform its job. This can happen in the 
case of an infinite recursion, or if the engine cannot find an 
executable language for a shape (e.g. only a JavaScript body is present, 
but no SPARQL). This appears to work quite nicely. Any SPARQL function 
may return nothing, to signal an error. I have changed sh:hasShape to 
either return true, false or nothing, and changed the code in the places 
where sh:hasShape was used so that any errors propagate up the call 
stack. To support this, I have adjusted the SPARQL constraint result 
evaluation so that if a result variable ?error is set to true then a 
sh:FatalError will be created, signaling a stop to further execution. 
For example, sh:NotConstraint is now defined as

SELECT ?this ?error
WHERE {
 BIND (sh:hasShape(?this, ?shape, ?shapesGraph) AS ?hasShape) .
 BIND (!bound(?hasShape) AS ?error) .
 FILTER (?error || ?hasShape) .
}


which means it will return ?error = true if ?hasShape has produced 
"unknown" (!bound(?hasShape)).

All these are SPARQL implementation details. The simple version of the 
story is that recursion is supported until it reaches a duplicate call 
on the stack, and errors propagate up to the root constraint.

The latest details can be viewed at

     http://w3c.github.io/data-shapes/shacl-ref/

The actual changes to the vocabulary were only done to a branch, because 
they are not approved yet:

https://github.com/w3c/data-shapes/commit/dbe442aa4f78ee3c2ae06b766f9c80f502a2729f

I have also added numerous test cases for various recursive shapes, 
including Simon's scenario:

https://github.com/w3c/data-shapes/blob/dbe442aa4f78ee3c2ae06b766f9c80f502a2729f/data-shapes-test-suite/tests/features/core/recursive-003.ttl

All seems to work fine now.

Regards,
Holger

Received on Wednesday, 17 June 2015 09:13:45 UTC