Takmela: Ancestors Datalog Example (medium-length trace version)

The classic example to showcase Logic Programming, running on Takmela/Datalog! This example has a relatively straighforward query with a medium-length trace.

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

parent("a", "b").
parent("b", "c").
parent("c", "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).

ancestor(b, X)

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