Re: ACTION-29 Recursion: Wrap Up

Recursion can sometimes be hard to avoid in a language since it often 
falls out without any specific supporting constructs. This leaves handling 
of recursion to implementations, and can lead to unexpected results for 
users. So saying nothing in this case may be ignoring the fact that the 
recursion is still there, and its implications are unspecified. Saying 
that how recursion is handled is up to implementations at least calls this 
out.


Jim Amsden, Senior Technical Staff Member
OSLC and Linked Lifecycle Data
919-525-6575




From:   "Peter F. Patel-Schneider" <pfpschneider@gmail.com>
To:     Holger Knublauch <holger@topquadrant.com>, 
public-data-shapes-wg@w3.org
Date:   02/24/2016 09:13 AM
Subject:        Re: ACTION-29 Recursion: Wrap Up



I think that the way to do this would be to not have recursion as a part 
of
SHACL.  As far as I know, W3C recommendations are generally open, in that 
they
allow for implementations to extend the language but still be advertised 
as
compliant.  (Some other standards do not allow this.  I think that 
ECMAScript
falls into this category.)

This would be much more like the situation in OWL, where a particular 
language
was recommended but many reasoning implementations handled a larger 
language.

peter


On 02/23/2016 10:33 PM, Holger Knublauch wrote:
> Could we simply say "handling of recursion is left to the discretion of 
the
> implementations" and close all related tickets? This way, we can 
basically
> outsource the problem to the open source and research communities and 
move on.
> The description logics community also made progress over time, after the 
OWL
> standards were published.
> 
> Engines that have larger coverage get bonus points, but implementations 
that
> just want to cover basic SHACL compliance don't have to worry about all 
the
> details. We simply wouldn't define test cases that use recursion. The 
ShEx
> people can support it if they like.
> 
> Holger
> 
> 
> On 24/02/2016 12:24, Arthur Ryman wrote:
>> I've had this action for a while but have not been able to make
>> progress due to other commitments. I'd like to summarize my thoughts
>> here and will then close the action.
>>
>> Recursion arises when the evaluation of a shape at a node depends
>> directly or indirectly on itself. If we allow this situation to occur,
>> then we are obligated to define what it means.
>>
>> I believe SHACL has well-founded semantics in the absence of
>> recursion. That is our starting point. Any new semantics that allows
>> recursion must agree with the current semantics in the absence of
>> recursion.
>>
>> The SHACL specification currently prohibits recursion. However, there
>> is some motivation for allowing limited forms of recursion. See [1].
>>
>> I believe we can assign a well-founded sematics to recursion that does
>> not involve either negation or disjunction. I wrote a Z specification
>> that defined the semantics of this type of recursion as it appeared in
>> OSLC Resource Shapes. [2] I had hoped to apply that approach to the
>> current SHACL spec, but have not found the time. I still believe this
>> approach is feasible.
>>
>> [1]
>> 
https://www.w3.org/2014/data-shapes/wiki/ISSUE-66:_SHACL_spec_ill-founded_due_to_non-convergence_on_data_loops

>>
>>
>> [2] http://arxiv.org/abs/1505.04972
>>
>> -- Arthur
>>
> 
>