5.3.6 Occurs-Check

[Sidetrack]

There is one thing about Prolog we can learn using the previous DCG (dCG4Questions.pl ). If you feed this DCG to Prolog and play with it, you will see that it accepts sentences (questions) that should not be accepted:

2 ?- s(_,[who,likes],[]).
 
Yes

What happens here is that NPs can be empty that should not be allowed to. But our DCG is correct. So how can this be? The problem is an unwanted interaction between Prolog's unification mechanism and the way we represent empty difference lists. We write np(F-F) to make sure that the list containing the gaps of an NP is empty. But in fact, Prolog can unify such an NP with an NP having a gap:

?- np(F-F) = np([gap(np)|G]-G).
 
F = [gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(...)|...]
G = [gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(np), gap(...)|...]  
 
Yes

The reason lies in Prolog's standard unification mechanism. For reasons of efficiency, it leaves out the so-called Occurs-Check . This plays no role most of the time. But in some cases it does. Let's look at a canonical example to see what's going wrong:

?- A = f(A).
 
A = f(f(f(f(f(f(f(f(f(f(...))))))))))  
 
Yes

If you ask Prolog to unify a variable with a complex term, it does not check whether this variable occurs inside the term. Therefore you can unify the variable and the term in the example above resulting in an infinite structure. You can think of what is happening as follows: First, A on the left matches f(A) on the right and becomes f(A). At the same time, f(A) on the right becomes f(f(A)). This matches f(A) on the left again and becomes f(f((A))), and so on.

The simplest solution to this is not to use Prolog's standard unification. For example in SWI Prolog there is a special predicate unify_with_occurs_check/2:

?- unify_with_occurs_check(A,f(A)).
 
No.

Now that was the true story. It looks like we will have to use unification-with-occurs-check, instead of the standard built-in Prolog unification. Luckily, there's another, much simpler, solution in our case: Nothing hinges on how exactly we represent the empty difference list. We don't have to use variables for this purpose (in particular, we needn't be as unspecific as in the calls shown above, where we gave one anonymous variable _ for the whole difference list). Instead of using variables, we can also use a non-variable '-'-term, as long as we make sure that the difference between both sides of the '-' is the empty list. For instance, we can use the following to symbolize an empty difference list: []-[].

Indeed np([]-[]) and np([gap(np)|G]-G) don't unify, in contrast to np(F-F) and np([gap(np)|G]-G). So calling s([]-[],[who,likes],[]) instead of s(_,[who,likes],[]) should solve our problem - and so it does.