- From: Holger Knublauch <holger@topquadrant.com>
- Date: Wed, 17 Jun 2015 19:11:25 +1000
- To: public-data-shapes-wg@w3.org
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