Re: can subqueries be executed first in SPARQL?

> On 2016-06-17, at 23:25, Peter F. Patel-Schneider <pfpschneider@gmail.com> wrote:
> 
> On 06/17/2016 12:55 PM, james anderson wrote:
>> good evening;
> [...]
> 
>>>> we understand the recommendation differently.
>>>> in particular, from the document context, it should be a “graph pattern”.
>>> 
>>> You appear to be saying that definition of substitute should be
>>> 
>>> *************
>>> Definition: Substitute
>>> 
>>> Let μ be a solution mapping
>>> substitute(pattern, μ) = the pattern formed by replacing every occurrence
>>>   of a variable v in pattern by μ(v) for each v in dom(μ), for pattern a
>>>   SPARQL algebra construct that is a graph pattern
>>> substitute(xyxy, μ) = xyxy, otherwise
>>> *************
>> 
>> that would not be adequate.
>> it would be necessary to define this specific to the lexical boundary which
>> applies to each form.
> 
> OK, so you don't think that the simplest fix is correct.
> 
> [As above but also requiring that substitutions only happen when the
> variable is in scope according to SPARQL.]
> 
>>> This at least adds the scope rules from SPARQL into the picture.
>>> Unfortunately the scope rules in SPARQL don't help here, for multiple
>>> reasons, including that they do not distinguish between what might be
>>> considered different variables with the same name.
>> 
>> please elaborate.
> 
> SPARQL doesn't have the concept of different variables with the same name.
> Variables in SPARQL are just tokens (of the form ?v or $v with v having a
> particular syntactic form).  Whether the variable v is in-scope or not only
> depends on this token, v, and not at all on which occurence of the token is
> being considered.  In many programming languages you can't (just) talk about
> a particular variable token being in scope, you have to talk about a
> particular variable definition being in scope.

perhaps i just do not follow your distinction between “token” and “definition”, but it is not clear, why it is relevant as the only values in sparql which inhere in tokens are blank nodes, literals, and iri - and in the last instance, optionally dependent on prefix bindings with indefinite scope and indefinite extent.
the only way a variable can contribute to the result of some algebra operation is if, at some point in the sparql expression, it came to be associated with a constant term.
that is, bound by some defining form.

the language includes any number of forms which bind variables.
the recommendation, unfortunately, does not provide a clear and complete description of the scope and extent of those bindings, but it does provide some.
perhaps we agree, that the exposition in the recommendation with respect to scope is inadequate.
from that, you assert, there is none.
i suggest, one has to reconcile that which is there with an adequate model for scope and extent - whether explicitly or implicitly, if one is to implement the sparql.

> 
>>> Or maybe substitute should drop variables from the solution mapping as soon
>>> as the variable goes out of scope.  That's sounding better, but needs
>>> careful consideration of just when to drop variables and what to do with,
>>> for example, Projects whose variable has been substituted.
>> 
>> we agree on the necessity to examine each type of form.
> 
> Well I agree that the effects of EXISTS *should* depend on the form of the
> algebra construct that is its argument.  However, I do not agree that it is
> *necessary* to do so in the current defintion of SPARQL.  On the contrary, I
> argue that the current definition of SPARQL mandates that the meaning of
> EXISTS is performed only by replacing variable tokens in its argument
> without any consideration at all of where they occur.

18.2.1

> 
>>> As well, there
>>> is no notion of scope in the SPARQL algebra so this has to be either
>>> defined there or scope dragged into the algebra during translation or some
>>> other method for determining when to drop variables devised that matches
>>> scoping.
>> 
>> while i would agree, were the claim to have been that the definitions for the
>> scope and extent of variable bindings in sparql are incomplete, i do not agree
>> that there are none.
>> were there none, it would be difficult for a processor to translate sparql to
>> lisp, then compile that to native code and produce execution results which,
>> with limited exceptions - some of which have exactly to do with rules for
>> scope and extent, conform to those stipulated by the test suite.
> 
> Not at all.  The SPARQL algebra, which is what is important here, has no
> notion of scope at all.  When considering expressions in Filter and Extend
> there is only one multiset of solution mappings to consider when determining
> how to interpret a variable.  Variables elsewhere either generate multisets
> from information in a graph or are in multisets that are combined together
> or generate solution sequences from multisets or solution sequences, again
> without any notion of scope.

that follows some definition for extent.
yes, section 18 refers to sparql text.
that is what scope is about.
an algebra must arrange for references as prescribed by the scoping rules.

>  Many constructs in the SPARQL algebra
> manipulate these multisets or solution sequences, but this is again without
> any consideration of variable scope.
> 
> This is actually a variation on how some early LISP implementations worked.
> They had a stack of variable bindings which certain constructs augmented and
> was used to find the current value of a variable in a process that only
> considered the variable as a token with no consideration of scope.

that may not be a definition which involves lexical scope, and any description may have been incomplete with respect to other, later, more complete models, but it is a definition of scope.

> 
> [...]
> 
>> is it possible to interpret a variable absent a definition of its scope and
>> extent?
> 
> Yes indeed, as I have tried to explain above.

i do not understand, that you succeeded.

> 
> Of course, it is always possible to infer some scope and extent properties
> of a language from a definition that doesn't use scope.
> 
>> 18.2.1 does not suggest that the recommendation believes that.
>> their nature is one of the things which defines a language.
> 
> 18.2.1 talks about variable scope.  However, all that it ends up doing is
> determining when certain syntactic constructs are syntactically illegal and
> determining how to translate SELECT *.

while i would admit the exposition of “in-scope” to be convoluted, confusing and incomplete, as it is inverted with respect to that which i would have expected from a language definition, which the recommendation is, the table in that section has been both necessary and sufficient to interpret the notion “in-scope” with sufficient accuracy to implement a compiler which conforms to it.
given which, the “all that” qualification does not apply.

as an aside, i recall “syntax” test which purport to demonstrate scoping rules.
they are misguided as, while “scope” is a lexical concern, it is misguided to treat it as an immediately syntactic concern.

> It doesn't do many of the things
> that one would think of as needed for variable scoping in a programming
> language, like determining whether a variable mention is a local or a global
> variable.

those follow from particular models for scope.
if a language does not support global variables, does that mean it does not define scope?
as it were, yes, i understand the sparql recommendation to provide account of global scope with respect to prefix bindings only.
given which, it was possible for me to introduce it for variables in order to manage the exists case and yet stay within the language definition

> 
> One could say that this notion of scoping is so important for SPARQL that it
> should affect the meaning of EXISTS.  

i leave out the subjunctive.

> For example, that only substitutions
> that are in-scope for SELECT ... should be carried through into its
> pattern.  I don't see any support for anything like this in the SPARQL 1.1
> Query specification.

i understand the section 18 table to prescribe that for any form which is contained in an exists.

> 
>> that sparql’s conception does not agree with that of basic - or any other
>> “programming language”, does not, in itself diminish the conception.
>> yes, the language would be well served, should someone have the opportunity to
>> work through it with a clear notion of those.
>> that does not mean, they do not exist.
>> 
>> where, with exists, you took the half full glass, filled it, and then complain
>> that you do not like the blend, here you take the half full glass, empty it
>> and then complain, that you were not served.
> 
> Not at all.  I took this clear part of the definition of EXISTS in the
> SPARQL 1.1 Query specification, did nothing to it, and haven't complained
> that it is incomplete.  (There are indeed technical problems with substitute
> and I have indeed complained that the result of this part of the definition
> is counter to informal wording elsewhere in the specification and also
> counter to intuitions.  This is different from complaining that there is
> something missing from the definition of EXISTS.)  Similarly I have not
> complained at all that there is something lacking in SPARQL because it is
> lacking a notion of scope.
> 
>>>> my approach, as indicated earlier, has been to employ dynamic bindings, with
>>>> the intent follow the incompletely defined intent of substitution, to the
>>>> extent is can be reconciled with lexical contours, as established by binding
>>>> forms.
>>> 
>>> Well I suppose that that is a possible way to implement something, but I
>>> don't think that that ends up conforming to the definition of SPARQL.
>> 
>> that depends on your definition of sparql.
>> you propose one which extends beyond mine.
>> the described implementation conforms to the language definition with respect
>> to exists in so far as the test suite validates it.
> 
> If that is the bar that you think is sufficient to pass then sure, you pass
> the test suite.  Just that remember that a test suite is a form of
> debugging.  It can show that problems exist but not show that no problems exist.

a test suite expresses the behavior which the authors understood and believed significant for language conformance.
we disagree, as to whether the behaviour at issue is prescribed by the language.
in such a situation, it can be useful to take a test suite as the reference for the things which the authors thought the language prescribed.

you believe their definition prescribes additional behavior.
once you have identified cases which distinguish the behavior, you are free to refine and extend that knowledge.
until one provides new cases around which agreement develops about additional distinctions between conformant v/s non-conformant behavior, the suite stands where is.

> 
>> early on in this exchange, i suggested the step to formulate the tests which
>> demonstrate the significant issues and add them to the w3c [SPARQL] test
> suite in
>> order to set milestones.
>> once they exist, one can respond to your supposition.
> 
> How can one add tests to the W3C SPARQL test suite?

    https://github.com/w3c/rdf-tests/issues <https://github.com/w3c/rdf-tests/issues>

> 
> peter

---
james anderson | james@dydra.com | http://dydra.com