on recursion in SHACL

Following up one of the recent responses to my comments on Shapes Constraint
Language (SHACL) lead me to look at how recursion works in Shapes Constraint
Language (SHACL), W3C Editor's Draft 22 September 2016.


Here is the initial discussion of recursion, from Section 4.8.1.

"A shape may refer to itself directly or indirectly via sh:shape,
sh:filterShape, etc. Such a shape is said to be recursive. The meaning of
non-recursive shapes is always well-founded. In contrast, the meaning of a
recursive shape may not be well-founded. The handling of recursive shapes in
SHACL is left to implementations. Some implementations MAY reject shapes
graphs containing recursive shape definitions. Some implementations MAY
report a failure if a recursion has been detected at validation time."

This is the wrong place for the initial discussion of recursion.  First,
sh:filterShape was discussed much earlier, in Section 2.2.  Second, the
discussion of recursion deserves not to be buried within the discussion of
sh:shape.

The definition of recursive shapes is much too sloppy.  What is covered by
the "etc."?  Is
  s:s1 rdf:type sh:Shape ;
    rdfs:comment s:s1 .
a recursive shape?

What is the process for rejecting a shape graph containing recursive shape
definitions?  The term "reject" occurs only in this one place.

What does well-founded mean here?

The meaning of "a recursion has been detected at validation time" has
several problems.  Validation time is not defined.  What counts as detecting
a recursion is not defined.



Here is another aspect of recursion in SHACL, from Section 9.4.

"Recursive use of functions is undefined: If a SPARQL-based function
contains calls to other functions so that the same function with the same
combination of parameters would be visited twice then the result of the
function call is undefined. An implementation may either return no result
(unbound) or terminate the surrounding SPARQL query with an error."

It is not that all recursive use of functions is undefined.  What is
undefined here by the more detailed description is a call to the same
function and with the same parameters within another call.  It appears that
this is an attempt to prevent infinite recursion.  Such calls, however, need
not lead to infinite recursion if uncaught, even in a limited language like
SPARQL.  Nor is it that all cases of infinite recursion involve calls of
this sort.  As detecting such calls is neither necessary nor sufficient to
prevent infinite recursion it is puzzling as to why a complex and
potentially expensive mechanism is being described, and maybe even mandated.


Peter F. Patel-Schneider
Nuance Communications

Received on Friday, 23 September 2016 17:01:16 UTC