Write a function accepting wrapped constants, but only one level deep

Question

I want to write a function (apologies for probably not using the correct term here) wubble which is true for specific constants and true for those constants if wrapped into another constant, but only one layer deep! Examples:

% are supposed to be TRUE:
?- wubble(foo).
?- wubble(bar).
?- wubble(wrapper(foo)).
?- wubble(wrapper(bar)).

% are suppoed to be FALSE:
?- wubble(not_in_knowledge_base).
?- wubble(wrapper(wrapper(foo))).

The naive (at least in my brain) implementation looks like this:

wubble(foo).
wubble(bar).

wubble(wrapper(wrapper(_))) :- !, fail.
wubble(wrapper(X)) :- wubble(X).

And this works with the queries above. However, I can't enumerate all valid X for wubble with this implementation:

?- wubble(X).
X = foo
X = bar

So this is missing X = wrapper(foo) and X = wrapper(bar). Is it possible to fix my implementation somehow?

Answer 1

You could separate the facts from the rules:

wubble_(foo).
wubble_(bar).

wubble(X) :- wubble_(X).
wubble(wrapper(X)) :- wubble_(X).

Answer 2

One solution in this particular case, as the OP noted himself, is the following:

wubble(foo).
wubble(bar).

wubble(wrapper(X)) :- wubble(X), ((X = wrapper(_), !, fail); true).

Since he also asked for an explanation of this pattern, here is my best shot:

Given the above knowledge base, a query like wubble(X). looks through it from top to bottom for either facts or heads of rules that unify with the goal, wubble(X). If it finds a fact, like wubble(foo), the goal just succeeds, unifying X with the inner term of the fact, in this case foo. After that, we can tell Prolog to backtrack to the last choice point (a node in the depth first search tree that Prolog builds during this process), which in this case was given by the original goal wubble(X) and make it look for other solutions to that goal. If we do this here, we get the fact for the second constant wubble(bar) of course.

Now for the fun part. If we backtrack again, the only way left to satisfy the goal wubble(X) is by satisfying the antecedent of your rule. Now let's go through this mechanically. This might be surprising, but wubble(wrapper(X)) unifies with wubble(X); you have to think of these Xes as independent. Both in the case of the query wubble(X) and the rule definition wubble(wrapper(X)) :- ..., X is just a local name. Really, these two variables are independent, uninstantiated variables in this situation and since an uninstantiated variable unifies with basically everything, we have X = wrapper(X) and thus the head of the rule matches our query. Maybe we should call them X1 and X2 for the query and the rule respectively, for now.

Now the tail of the rule is a conjunction, so we first try to satisfy the first goal, wubble(X), which creates a new choice point. Now the process basically starts over: We search the knowledge base from top to bottom for stuff that unifies with that, which first finds wubble(foo). So X2 is now unified with foo and we check whether the second part of the conjunction, now with X2 = foo, succeeds, which it does, because foo \= wrapper(_). So because both goals of the conjunction succeeded with X2 = foo, our original goal succeeds as well with X1 = wrapper(X2) = wrapper(foo).

Backtracking from this basically brings us back to the second choice point, created by the first goal of the conjunction in the rule. Next, we find X2 = bar, which again checks out with the second part of the conjunction and our original goal succeeds with X1 = wrapper(bar).

Next, we get to the rule again; we unify X2 = wrapper(X3), our new goal is wubble(X3), creating a new choice point, and this succeeds with X3 = foo and the second part also checks out. So now we go one layer up and we have X2 = wrapper(foo). This does not satisfy the second part of the conjunction! It triggers the !, fail, so our original goal of wubble(X1), where we unified X1 = wrapper(X2) = wrapper(wrapper(foo)), fails this time. But not only that, we also cut, which eliminates the choice point of the first recursive kipple call and everything below it, so we don't even try X3 = bar or X3 = wrapper(X4) anymore.

So we go back further to our original choice point for the goal wubble(X1); but there are no further clauses in the database that match this, so we are done.

Now I get that this might be hard to follow in text form, so here is my attempt to visualize the search tree: