Backtracking for SemActs

[ericprud]

SemActs are used both to reject data and to perform side-effects. This means that side-effects may happen even for patterns that will later be rejected. For instance, with a trivial validation algorithm, this validation results in an extraneous print of "bad 1":

PREFIX log: <http://shex.io/extensions/Test/>
<S> {
  (
    <p1> . %log:{ print("bad 1") %} ;
    <p2> . %log:{ print("bad 2") %} ;
  ) | {
    <p1> . %log:{ print("good 1") %} ;
  }
}

<s> <p1> 1 .

The SORBE algorithm avoid this for tripleExprs so we have to move the validation to a shapeExpr to get the pathological behavior:

PREFIX log: <http://shex.io/extensions/Test/>
<S> ({
    ex:p1 .  %log:{ print("bad 1", o) %}
  } AND {
    ex:p2 .  %log:{ print("bad 2", o) %}
}) OR {
  ex:p1 .  %log:{ print("good 1", o) %}
}

semact output:

"bad 1", "p1"
"good 1", "p1"

A Google search for "semantic actions in backtracking parsers" lead to some interesting leads:

1. Delayed semantic actions
2. reversible semantic actions
3. "removed while backtracking"

I didn't dig into #3 long enough to see if the removal was automatic or weather the SemAct handler got a notification like "you've been backtracked" and had to do it itself. To make this automatic in ShEx, I think we'd have to have the SemAct return some object that would be available to SemActs further up the tree; basically emulating the $$ and $<n> variables you see in yacc, as in the ubiquitous calc example:

expr '+' expr { $$.a = $1.a + $3.a; }

The results of SemActs from backtracked branches would just disappear and hopefully get garbage-collected. I suspect it gives the best user experience while steering users away from executing side-effects before they should, (This is a jena-shex design decision that could lead to some ShEx SemAct specs or conventions in the future.)