Main ArticleExamples TOC

Ancestors Datalog Example (long trace version)

The classic example to showcase Logic Programming, running on Takmela/Datalog! The query in this example leads to a long trace and a complicated graph.

All ancestors examples: Short / Medium / Longer trace. (Note that the fact set is slightly different in each example)

Program 
parent("a", "b").
parent("b", "c").
parent("a", "d").
parent("d", "e").

// All parents are ancestors
ancestor(X, Y):- parent(X, Y).

// An ancestor of an ancestor is also an ancestor
ancestor(X, Y):- ancestor(X, Z), ancestor(Z, Y).
Query 
ancestor(X, c)

Tracing this query leads to a rather complicated graph, which is why in the actual trace we use 'a' to mean ancestor and 'p' to mean parent.

Hint: Hovering over a graph expands it

Trace appears confusing? This might help

Call start rule
#0: Called a(?, c) at the top level (will process)
Processing a(?, c) codePos a(X, Y)→•p(X,Y|c)
Calling fact: p(?, c)
Found fact: p(?, c) → [b, c]
Processing a(?, c) codePos a(X, Y)→•a(X,Z), a(Z,Y|c)
Calling: a(?, ?) [will process]
Processing a(?, ?) codePos a(X, Y)→•p(X,Y)
Calling fact: p(?, ?)
Found fact: p(?, ?) → [a, b]
Found fact: p(?, ?) → [b, c]
Found fact: p(?, ?) → [a, d]
Found fact: p(?, ?) → [d, e]
Processing a(?, ?) codePos a(X, Y)→•a(X,Z), a(Z,Y)
Calling: a(?, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e]
Iteration 0
Worklist - successes
jS p(?, ?) → (a, b)
jS p(?, ?) → (b, c)
jS p(?, ?) → (d, e)
jS p(?, ?) → (a, d)
jS p(?, c) → (b, c)
Worklist - continuations
S⤚ p(?, ?) → a(X, Y)→p(X,Y)•
nJ a(?, ?) → a(X, Y)→a(X,Z)•a(Z,Y|c)
nJ a(?, ?) → a(X, Y)→a(X,Z)•a(Z,Y)
S⤚ p(?, c) → a(X, Y)→p(X,Y|c)•
#1: JoinS: p(?, ?) → [a, b] will resume cont: a(X, Y)→p(X,Y)•
newVars: {X=a, Y=b}
Processing a(?, ?) codePos a(X, Y)→p(X|a,Y|b)•
Reached end of rule, success! a(?, ?) → [a, b]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b]
#2: JoinS: p(?, ?) → [b, c] will resume cont: a(X, Y)→p(X,Y)•
newVars: {X=b, Y=c}
Processing a(?, ?) codePos a(X, Y)→p(X|b,Y|c)•
Reached end of rule, success! a(?, ?) → [b, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c]
#3: JoinS: p(?, ?) → [d, e] will resume cont: a(X, Y)→p(X,Y)•
newVars: {X=d, Y=e}
Processing a(?, ?) codePos a(X, Y)→p(X|d,Y|e)•
Reached end of rule, success! a(?, ?) → [d, e]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e]
#4: JoinS: p(?, ?) → [a, d] will resume cont: a(X, Y)→p(X,Y)•
newVars: {X=a, Y=d}
Processing a(?, ?) codePos a(X, Y)→p(X|a,Y|d)•
Reached end of rule, success! a(?, ?) → [a, d]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d]
#5: JoinS: p(?, c) → [b, c] will resume cont: a(X, Y)→p(X,Y|c)•
newVars: {X=b}
Processing a(?, c) codePos a(X, Y)→p(X|b,Y|c)•
Reached end of rule, success! a(?, c) → [b, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c]
Iteration 1
Worklist - successes
jS a(?, ?) → (a, b)
jS a(?, ?) → (b, c)
jS a(?, ?) → (d, e)
jS a(?, ?) → (a, d)
jS a(?, c) → (b, c)
Worklist - continuations
#6: JoinS: a(?, ?) → [a, b] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=a, Z=b}
Processing a(?, c) codePos a(X, Y)→a(X|a,Z|b)•a(Z|b,Y|c)
Calling: a(b, c) [will process]
Processing a(b, c) codePos a(X, Y)→•p(X|b,Y|c)
Calling fact: p(b, c)
Found fact: p(b, c) → [b, c]
Processing a(b, c) codePos a(X, Y)→•a(X|b,Z), a(Z,Y|c)
Calling: a(b, ?) [will process]
Processing a(b, ?) codePos a(X, Y)→•p(X|b,Y)
Calling fact: p(b, ?)
Found fact: p(b, ?) → [b, c]
Processing a(b, ?) codePos a(X, Y)→•a(X|b,Z), a(Z,Y)
Calling: a(b, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#7: JoinS: a(?, ?) → [a, b] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=a, Z=b}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|b)•a(Z|b,Y)
Calling: a(b, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#8: JoinS: a(?, ?) → [b, c] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=b, Z=c}
Processing a(?, c) codePos a(X, Y)→a(X|b,Z|c)•a(Z|c,Y|c)
Calling: a(c, c) [will process]
Processing a(c, c) codePos a(X, Y)→•p(X|c,Y|c)
Calling fact: p(c, c)
Processing a(c, c) codePos a(X, Y)→•a(X|c,Z), a(Z,Y|c)
Calling: a(c, ?) [will process]
Processing a(c, ?) codePos a(X, Y)→•p(X|c,Y)
Calling fact: p(c, ?)
Processing a(c, ?) codePos a(X, Y)→•a(X|c,Z), a(Z,Y)
Calling: a(c, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#9: JoinS: a(?, ?) → [b, c] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=b, Z=c}
Processing a(?, ?) codePos a(X, Y)→a(X|b,Z|c)•a(Z|c,Y)
Calling: a(c, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#10: JoinS: a(?, ?) → [d, e] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=d, Z=e}
Processing a(?, c) codePos a(X, Y)→a(X|d,Z|e)•a(Z|e,Y|c)
Calling: a(e, c) [will process]
Processing a(e, c) codePos a(X, Y)→•p(X|e,Y|c)
Calling fact: p(e, c)
Processing a(e, c) codePos a(X, Y)→•a(X|e,Z), a(Z,Y|c)
Calling: a(e, ?) [will process]
Processing a(e, ?) codePos a(X, Y)→•p(X|e,Y)
Calling fact: p(e, ?)
Processing a(e, ?) codePos a(X, Y)→•a(X|e,Z), a(Z,Y)
Calling: a(e, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#11: JoinS: a(?, ?) → [d, e] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=d, Z=e}
Processing a(?, ?) codePos a(X, Y)→a(X|d,Z|e)•a(Z|e,Y)
Calling: a(e, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c]
#12: JoinS: a(?, ?) → [a, d] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=a, Z=d}
Processing a(?, c) codePos a(X, Y)→a(X|a,Z|d)•a(Z|d,Y|c)
Calling: a(d, c) [will process]
Processing a(d, c) codePos a(X, Y)→•p(X|d,Y|c)
Calling fact: p(d, c)
Processing a(d, c) codePos a(X, Y)→•a(X|d,Z), a(Z,Y|c)
Calling: a(d, ?) [will process]
Processing a(d, ?) codePos a(X, Y)→•p(X|d,Y)
Calling fact: p(d, ?)
Found fact: p(d, ?) → [d, e]
Processing a(d, ?) codePos a(X, Y)→•a(X|d,Z), a(Z,Y)
Calling: a(d, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e]
#13: JoinS: a(?, ?) → [a, d] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=a, Z=d}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|d)•a(Z|d,Y)
Calling: a(d, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e]
#14: JoinS: a(?, c) → [b, c] will resume cont: Root(V0, "c")→a(V0,"c")•
newVars: {V0=b}
Processing Root() codePos Root(V0, "c")→a(V0|b,"c")•
Reached end of rule, success! Root() → [b, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓
Iteration 2
Worklist - successes
jS p(b, ?) → (b, c)
nJ Root() → (b, c)
jS p(d, ?) → (d, e)
jS p(b, c) → (b, c)
Worklist - continuations
nJ a(c, c) → a(X, Y)→a(X|b,Z|c), a(Z|c,Y|c)•
nJ a(b, c) → a(X, Y)→a(X|a,Z|b), a(Z|b,Y|c)•
nJ a(b, ?) → a(X, Y)→a(X|b,Z)•a(Z,Y|c)
nJ a(b, ?) → a(X, Y)→a(X|a,Z|b), a(Z|b,Y)•
nJ a(b, ?) → a(X, Y)→a(X|b,Z)•a(Z,Y)
nJ a(e, c) → a(X, Y)→a(X|d,Z|e), a(Z|e,Y|c)•
nJ a(d, c) → a(X, Y)→a(X|a,Z|d), a(Z|d,Y|c)•
nJ a(d, ?) → a(X, Y)→a(X|d,Z)•a(Z,Y|c)
nJ a(d, ?) → a(X, Y)→a(X|d,Z)•a(Z,Y)
nJ a(d, ?) → a(X, Y)→a(X|a,Z|d), a(Z|d,Y)•
nJ a(c, ?) → a(X, Y)→a(X|c,Z)•a(Z,Y|c)
nJ a(c, ?) → a(X, Y)→a(X|b,Z|c), a(Z|c,Y)•
nJ a(c, ?) → a(X, Y)→a(X|c,Z)•a(Z,Y)
nJ a(e, ?) → a(X, Y)→a(X|e,Z)•a(Z,Y|c)
nJ a(e, ?) → a(X, Y)→a(X|d,Z|e), a(Z|e,Y)•
nJ a(e, ?) → a(X, Y)→a(X|e,Z)•a(Z,Y)
S⤚ p(b, c) → a(X, Y)→p(X|b,Y|c)•
nJ p(d, c) → a(X, Y)→p(X|d,Y|c)•
nJ p(c, c) → a(X, Y)→p(X|c,Y|c)•
nJ p(c, ?) → a(X, Y)→p(X|c,Y)•
S⤚ p(b, ?) → a(X, Y)→p(X|b,Y)•
nJ p(e, c) → a(X, Y)→p(X|e,Y|c)•
nJ p(e, ?) → a(X, Y)→p(X|e,Y)•
S⤚ p(d, ?) → a(X, Y)→p(X|d,Y)•
#15: JoinS: p(b, ?) → [b, c] will resume cont: a(X, Y)→p(X|b,Y)•
newVars: {Y=c}
Processing a(b, ?) codePos a(X, Y)→p(X|b,Y|c)•
Reached end of rule, success! a(b, ?) → [b, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c]
#16: JoinS: p(d, ?) → [d, e] will resume cont: a(X, Y)→p(X|d,Y)•
newVars: {Y=e}
Processing a(d, ?) codePos a(X, Y)→p(X|d,Y|e)•
Reached end of rule, success! a(d, ?) → [d, e]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e]
#17: JoinS: p(b, c) → [b, c] will resume cont: a(X, Y)→p(X|b,Y|c)•
Processing a(b, c) codePos a(X, Y)→p(X|b,Y|c)•
Reached end of rule, success! a(b, c) → [b, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c]
Iteration 3
Worklist - successes
jS a(b, c) → (b, c)
jS a(b, ?) → (b, c)
jS a(d, ?) → (d, e)
Worklist - continuations
#18: JoinS: a(b, c) → [b, c] will resume cont: a(X, Y)→a(X|a,Z|b), a(Z|b,Y|c)•
Processing a(?, c) codePos a(X, Y)→a(X|a,Z|b), a(Z|b,Y|c)•
Reached end of rule, success! a(?, c) → [a, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c]
#19: JoinS: a(b, ?) → [b, c] will resume cont: a(X, Y)→a(X|b,Z)•a(Z,Y|c)
newVars: {Z=c}
Processing a(b, c) codePos a(X, Y)→a(X|b,Z|c)•a(Z|c,Y|c)
Calling: a(c, c) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c]
#20: JoinS: a(b, ?) → [b, c] will resume cont: a(X, Y)→a(X|a,Z|b), a(Z|b,Y)•
newVars: {Y=c}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|b), a(Z|b,Y|c)•
Reached end of rule, success! a(?, ?) → [a, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c]
#21: JoinS: a(b, ?) → [b, c] will resume cont: a(X, Y)→a(X|b,Z)•a(Z,Y)
newVars: {Z=c}
Processing a(b, ?) codePos a(X, Y)→a(X|b,Z|c)•a(Z|c,Y)
Calling: a(c, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c]
#22: JoinS: a(d, ?) → [d, e] will resume cont: a(X, Y)→a(X|d,Z)•a(Z,Y|c)
newVars: {Z=e}
Processing a(d, c) codePos a(X, Y)→a(X|d,Z|e)•a(Z|e,Y|c)
Calling: a(e, c) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c]
#23: JoinS: a(d, ?) → [d, e] will resume cont: a(X, Y)→a(X|d,Z)•a(Z,Y)
newVars: {Z=e}
Processing a(d, ?) codePos a(X, Y)→a(X|d,Z|e)•a(Z|e,Y)
Calling: a(e, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c]
#24: JoinS: a(d, ?) → [d, e] will resume cont: a(X, Y)→a(X|a,Z|d), a(Z|d,Y)•
newVars: {Y=e}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|d), a(Z|d,Y|e)•
Reached end of rule, success! a(?, ?) → [a, e]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e]
Iteration 4
Worklist - successes
jS a(?, ?) → (a, c)
jS a(?, ?) → (a, e)
jS a(?, c) → (a, c)
Worklist - continuations
nJ a(c, c) → a(X, Y)→a(X|b,Z|c), a(Z|c,Y|c)•
nJ a(e, c) → a(X, Y)→a(X|d,Z|e), a(Z|e,Y|c)•
nJ a(c, ?) → a(X, Y)→a(X|b,Z|c), a(Z|c,Y)•
nJ a(e, ?) → a(X, Y)→a(X|d,Z|e), a(Z|e,Y)•
#25: JoinS: a(?, ?) → [a, c] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=a, Z=c}
Processing a(?, c) codePos a(X, Y)→a(X|a,Z|c)•a(Z|c,Y|c)
Calling: a(c, c) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e]
#26: JoinS: a(?, ?) → [a, c] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=a, Z=c}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|c)•a(Z|c,Y)
Calling: a(c, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e]
#27: JoinS: a(?, ?) → [a, e] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y|c)
newVars: {X=a, Z=e}
Processing a(?, c) codePos a(X, Y)→a(X|a,Z|e)•a(Z|e,Y|c)
Calling: a(e, c) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e]
#28: JoinS: a(?, ?) → [a, e] will resume cont: a(X, Y)→a(X,Z)•a(Z,Y)
newVars: {X=a, Z=e}
Processing a(?, ?) codePos a(X, Y)→a(X|a,Z|e)•a(Z|e,Y)
Calling: a(e, ?) [already processed]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e]
#29: JoinS: a(?, c) → [a, c] will resume cont: Root(V0, "c")→a(V0,"c")•
newVars: {V0=a}
Processing Root() codePos Root(V0, "c")→a(V0|a,"c")•
Reached end of rule, success! Root() → [a, c]
p(?, c) → [b, c] p(?, ?) → [a, b] p(?, ?) → [b, c] p(?, ?) → [a, d] p(?, ?) → [d, e] a(?, ?) → [a, b] a(?, ?) → [b, c] a(?, ?) → [d, e] a(?, ?) → [a, d] a(?, c) → [b, c] p(b, c) → [b, c] p(b, ?) → [b, c] p(d, ?) → [d, e] Root() → [b, c]✓ a(b, ?) → [b, c] a(d, ?) → [d, e] a(b, c) → [b, c] a(?, c) → [a, c] a(?, ?) → [a, c] a(?, ?) → [a, e] Root() → [a, c]✓
Iteration 5
Worklist - successes
nJ Root() → (a, c)
Worklist - continuations
nJ a(c, c) → a(X, Y)→a(X|a,Z|c), a(Z|c,Y|c)•
nJ a(e, c) → a(X, Y)→a(X|a,Z|e), a(Z|e,Y|c)•
nJ a(c, ?) → a(X, Y)→a(X|a,Z|c), a(Z|c,Y)•
nJ a(e, ?) → a(X, Y)→a(X|a,Z|e), a(Z|e,Y)•
(No new calls or successes that can be further processed)
Iteration 6 [Fixed point reached]