Takmela: Self-matching variable Datalog Example

Every new Datalog interpreter should be tested with a program that contains an atom like p(X, X, Y) where a variable occurs more than once, thus having to match an earlier occurrence of itself.

buys("a", "a", "noodles").
buys("a", "b", "watch").

buys("b", "a", "socks").
buys("b", "c", "gloves").

buys("c", "c", "suit").


selfBuys(X):- buys(X, X, Something).

likes(X, Y):- buys(X, Y, Something).

selfLikes(X):- likes(X, X).

selfLikes(X)

Hint: Hovering over a graph expands it

Call start rule
	#0: Called selfLikes(?) at the top level (will process) Processing selfLikes(?) codePos selfLikes(X)→•likes(X,X) Calling: likes(?, ?) [will process] Processing likes(?, ?) codePos likes(X, Y)→•buys(X,Y,Something) Calling fact: buys(?, ?, ?) Found fact: buys(?, ?, ?) → [a, a, noodles] Found fact: buys(?, ?, ?) → [a, b, watch] Found fact: buys(?, ?, ?) → [b, a, socks] Found fact: buys(?, ?, ?) → [b, c, gloves] Found fact: buys(?, ?, ?) → [c, c, suit]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit]
Iteration 0
Worklist - successes jS buys(?, ?, ?) → (a, b, watch) jS buys(?, ?, ?) → (b, c, gloves) jS buys(?, ?, ?) → (b, a, socks) jS buys(?, ?, ?) → (a, a, noodles) jS buys(?, ?, ?) → (c, c, suit) Worklist - continuations S⤚ buys(?, ?, ?) → likes(X, Y)→buys(X,Y,Something)• nJ likes(?, ?) → selfLikes(X)→likes(X,X)•
	#1: JoinS: buys(?, ?, ?) → [a, b, watch] will resume cont: likes(X, Y)→buys(X,Y,Something)• newVars: {X=a, Y=b, Something=watch} Processing likes(?, ?) codePos likes(X, Y)→buys(X|a,Y|b,Something|watch)• Reached end of rule, success! likes(?, ?) → [a, b]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b]
	#2: JoinS: buys(?, ?, ?) → [b, c, gloves] will resume cont: likes(X, Y)→buys(X,Y,Something)• newVars: {X=b, Y=c, Something=gloves} Processing likes(?, ?) codePos likes(X, Y)→buys(X|b,Y|c,Something|gloves)• Reached end of rule, success! likes(?, ?) → [b, c]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c]
	#3: JoinS: buys(?, ?, ?) → [b, a, socks] will resume cont: likes(X, Y)→buys(X,Y,Something)• newVars: {X=b, Y=a, Something=socks} Processing likes(?, ?) codePos likes(X, Y)→buys(X|b,Y|a,Something|socks)• Reached end of rule, success! likes(?, ?) → [b, a]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a]
	#4: JoinS: buys(?, ?, ?) → [a, a, noodles] will resume cont: likes(X, Y)→buys(X,Y,Something)• newVars: {X=a, Y=a, Something=noodles} Processing likes(?, ?) codePos likes(X, Y)→buys(X|a,Y|a,Something|noodles)• Reached end of rule, success! likes(?, ?) → [a, a]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a]
	#5: JoinS: buys(?, ?, ?) → [c, c, suit] will resume cont: likes(X, Y)→buys(X,Y,Something)• newVars: {X=c, Y=c, Something=suit} Processing likes(?, ?) codePos likes(X, Y)→buys(X|c,Y|c,Something|suit)• Reached end of rule, success! likes(?, ?) → [c, c]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c]
Iteration 1
Worklist - successes F likes(?, ?) → (b, a) jS likes(?, ?) → (a, a) jS likes(?, ?) → (c, c) F likes(?, ?) → (a, b) F likes(?, ?) → (b, c) Worklist - continuations
	#6: JoinS: likes(?, ?) → [b, a] and cont: selfLikes(X)→likes(X,X)• failed to bind variables
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c]
	#7: JoinS: likes(?, ?) → [a, a] will resume cont: selfLikes(X)→likes(X,X)• newVars: {X=a} Processing selfLikes(?) codePos selfLikes(X)→likes(X|a,X|a)• Reached end of rule, success! selfLikes(?) → [a]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a]
	#8: JoinS: likes(?, ?) → [c, c] will resume cont: selfLikes(X)→likes(X,X)• newVars: {X=c} Processing selfLikes(?) codePos selfLikes(X)→likes(X|c,X|c)• Reached end of rule, success! selfLikes(?) → [c]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a] selfLikes(?) → [c]
	#9: JoinS: likes(?, ?) → [a, b] and cont: selfLikes(X)→likes(X,X)• failed to bind variables
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a] selfLikes(?) → [c]
	#10: JoinS: likes(?, ?) → [b, c] and cont: selfLikes(X)→likes(X,X)• failed to bind variables
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a] selfLikes(?) → [c]
Iteration 2
Worklist - successes jS selfLikes(?) → (a) jS selfLikes(?) → (c) Worklist - continuations
	#11: JoinS: selfLikes(?) → [a] will resume cont: Root(V0)→selfLikes(V0)• newVars: {V0=a} Processing Root() codePos Root(V0)→selfLikes(V0|a)• Reached end of rule, success! Root() → [a]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a] selfLikes(?) → [c] Root() → [a]✓
	#12: JoinS: selfLikes(?) → [c] will resume cont: Root(V0)→selfLikes(V0)• newVars: {V0=c} Processing Root() codePos Root(V0)→selfLikes(V0|c)• Reached end of rule, success! Root() → [c]
buys(?, ?, ?) → [a, a, noodles] buys(?, ?, ?) → [a, b, watch] buys(?, ?, ?) → [b, a, socks] buys(?, ?, ?) → [b, c, gloves] buys(?, ?, ?) → [c, c, suit] likes(?, ?) → [a, b] likes(?, ?) → [b, c] likes(?, ?) → [b, a] likes(?, ?) → [a, a] likes(?, ?) → [c, c] selfLikes(?) → [a] selfLikes(?) → [c] Root() → [a]✓ Root() → [c]✓
Iteration 3
Worklist - successes nJ Root() → (a) nJ Root() → (c) Worklist - continuations
(No new calls or successes that can be further processed)
Iteration 4 [Fixed point reached]