While working on a PR for #212, I notice that the notion of an expression and the evaluation of such expressions is not really defined in the spec.

What is an expression?

Section 17 Expressions and Testing Values mentions "the expression" in the second sentence without saying what kind of expression this refers to.

A few paragraphs later, we have the following:

SPARQL expressions are constructed according to the grammar and provide access to functions [...]

Assuming that "SPARQL expression" and "expression" are the same concept, my takeaway from this sentence is that a (SPARQL) expression is a string admitted by some particular production of the SPARQL grammar. Okay, that's fine. Or, is it actually meant to be an AST obtained by parsing a such string based on the grammar??

In any case, it would be useful to make this an explicit definition, and also to say explicitly which production of the SPARQL grammar is the one that is meant here (is it Expression as used in, e.g., Bind or is it Constraint as used in Filter?)

How is the evaluation of an expression defined?

Now, this one is a bit more tricky. There is Section 17.2 Filter Evaluation, which has informal text that covers various cases but there is nothing that explicitly says something like: "Given an expression expr, the result of evaluating expr is ..." In other words, we are missing something akin to the eval function but for expressions.

Another aspect of the evaluation of expressions that is not mentioned at all in Section 17.2 Filter Evaluation is that an expression is not evaluated per se, but with respect to a solution mapping (and, in fact, also with respect to a dataset with an active graph, if we want to be able to properly define the semantics of expressions with EXISTS). The only part of Section 17 Expressions and Testing Values related to the fact that solution mappings are considered for the evaluation of expressions is the second sentence, which says that

[...] FILTERs eliminate any solutions that, when substituted into the expression, either result in [...].

Yet, what it means for a solution (mapping) to be "substituted into the expression," is not explicitly defined anywhere.

Ill-defined algebra operators with expression

The lack of a clear definition of the evaluation of expressions makes the definitions of corresponding algebra operators (Filter, Diff, and Extend) ill-defined as well.

For instance, the definition of Filter says that:

[...] and expr(μ) is an expression that has an effective boolean value of true }

While the notion of the "effective boolean value" of an expression is defined in Section 17.2.2 Effective Boolean Value (EBV), it is not clear what exactly "expr(μ)" means. Apparently, it also "is an expression." Then, by considering the aforementioned statement about "substituted into the expression," I assume that "expr(μ)" is meant to denote the expression that one obtains by applying the solution mapping μ to the variables in expr.

Yet, if "expr(μ)" is meant to denote an expression, then it cannot be used as currently done in the definition of Extend:

Extend(μ, var, expr) = μ ∪ { (var, value) | var not in dom(μ) and value = expr(μ) }

... because here it seems to be used to denote the "value" (an RDF term!) obtained by the evaluation of expr with respect to μ.

How to move forward?

At the very minimum, we need to specify what "expr(μ)" means in the definitions of Filter, Diff, and Extend, respectively.

A slightly better option is to, additionally, extend the formulas in these three definitions in some way that makes it clear that the dataset D with active graph G is also an input to the evaluation of the given expression. (again, this is needed to be able to properly define the semantics of EXISTS, no matter what exactly this semantics will be)

An ideal option is to introduce a function that explicitly defines the evaluation of an expression (with respect to both a solution mapping and a dataset with an active graph) and, then, use this function in the definitions of Filter, Diff, and Extend.