GNU Prolog - Recursion issue (easy?)

Tag: recursion , prolog Author: yifan34 Date: 2010-10-01

Ok, so i have this

edu_less(hs,college).
edu_less(college,masters).
edu_less(masters,phd).

I need to write a function to tell if something is less than the other. The predicate is

edu_le.

So if i put edu_le(hs,phd). it should return yes. I came up with this.

edu_le(A,B) :- A = B.
edu_le(A,B) :- edu_less(A,B).
edu_le(A,B) :- edu_less(A,C), edu_le(C,B).

I really don't want it to go through everything and return multiple answers.

Is it possible to only return yes or no if it finds that it is in fact less than or equal to the 2nd argument?

So basically if i use the example edu_le(hs,phd) again, then because hs is less than college, and college is than masters, and masters is less than phd, then hs must be less than phd and it would say yes.

Sorry, really new to prolog, still trying to get the hang of this.

Best Answer

The most practical way to write predicates like that is to use the cut (!). The cut causes further clauses not to be considered when backtracking. You would write your predicate as following:

edu_le(A,B) :- A = B, !.
edu_le(A,B) :- edu_less(A,B), !.
edu_le(A,B) :- edu_less(A,C), edu_le(C,B).

The last clause does not need a cut because there are no further clauses to consider anyway. The cut is placed after any tests to determine whether the clause should succeed.

Logic programming purists disapprove of the cut, because it makes the meaning of a predicate depend on the ordering of the clauses, which is unlike logic in mathematics.

comments:

AHHHHHHHH (like a holy ahhh). Thank you. Thank god im not a purists then right?

Other Answer1

In the predicate definition

edu_le(A,B) :- A = B.
edu_le(A,B) :- edu_less(A,B).
edu_le(A,B) :- edu_less(A,C), edu_le(C,B).

the second clause is superfluous and causes repeated generation of answers. Use

edu_le(A,B) :- A = B.
edu_le(A,B) :- edu_less(A,C), edu_le(C,B).

This gives you one true answer, then no more answers (false) on backtracking. You can use a cut in the first clause, but then generating won't work anymore.

?- edu_le(hs,X).
X = hs ;
X = college ;
X = masters ;
X = phd ;
false.

becomes incomplete:

?- edu_le(hs,X).
X = hs.

As mat suggested, use once/1 instead. In a good Prolog implementation, this predicate works as if your program had cuts in strategic places, speeding up your program without disturbing its logical semantics.

Other Answer2

!/0 also makes this program incomplete, consider for example the most general query with both versions:

?- edu_le(X, Y).

It is often better to use once/1 if you only want a single proof of a particular goal:

?- once(edu_le(hs, phd)).

Other Answer3

I would suggest you NOT to follow the path proposed by Juho Östman and keep purity - otherwise, why should you use Prolog in first instance? If you are too lenient with sticking to the logical paradigm you obtain some unpleasing results. In this case, Juho's predicate is definitely different from yours, and I'll show you why.

First, just drop the useless edu_le(A,B) :- edu_less(A,B). rule, as larsmans suggests. You will obtain a less redundant version of your original predicate:

edu_le1(A, A).
edu_le1(A, B) :- edu_less(A, C), edu_le1(C, B).

It just behaves as edu_le, meaning: given an arbitrary query, it produces exactly the same answer, except for duplicates (edu_le1 has less). You may just be happy with it, but it still has some redundant answers that you may not like; e.g, under SWI:

?- edu_le1(hs, hs)
true ;
false.

Now you may say you do not like it because it still has the redundant false, but if you use Juho's predicate instead (without the useless rule):

edu_le2(A, A) :- !.
edu_le2(A, B) :- edu_less(A, C), edu_le2(C, B).

it's true that you eliminate the useless final false:

?- edu_le2(hs, hs)
true.

?-

but you lose more than that: You lose, as mat remarks, the possibility of generating all the solutions when one variable is not instantiated:

?- edu_le1(hs, B) %same, with more copies, for edu_le
B = hs ;
B = college ;
B = masters ;
B = phd ;
false.

?- edu_le2(hs, B)
B = hs.           %bad!

?-

In other words, the latter predicate is NOT equivalent to the former: edu_le and edu_le1 have type edu_le(?A, ?B), while instead edu_le2 has type edu_le2(+A, +B) (see [1] for the meaning). Be sure: edu_le2 is less useful because it does less things, and thus can be reused in less contexts. This because the cut in edu_le2 is a red cut, i.e., a cut that changes the meaning of the predicate where it is introduced. You may nevertheless be content with it, given that you understand the difference between the two. It all depends on what you want to do with it.

If you want to get the best of the two worlds, you need to introduce in edu_le1 a proper green cut that lowers the redundancy when A and B are completely instantiated to terms. At the purpose, you must check that A and B are instantiated to the same term before cutting. You cannot do it with =, because = does not check, but unifies. The right operator is ==:

edu_le3(A, B) :- (A == B -> ! ; true), A = B.
edu_le3(A, B) :- edu_less(A, C), edu_le3(C, B).

Note that the additional cut in the first rule is active only when A and B happen to be the same term. Now that the cut is a proper green cut, the predicate works also in the most general cases as your original one:

?- edu_le3(A, A).
true.

?- edu_le3(A, B).  %note that A and B are not the same term
A = B ;
A = hs,
B = college ;
A = hs,
B = masters ;
A = hs,
B = phd ;
A = college,
B = masters ;
A = college,
B = phd ;
A = masters,
B = phd ;
false.

?-

with Prolog backtracking through all the solutions.

I don't think there is some way to eliminate the last false without introducing too strong dependency on edu_lt. This because we must keep open the possibility that there is another edu_lt to explore, in the case you decide later to enrich it with more ground facts. So, in my opinion, this is the best you can have.

[1] SWI Prolog reference manual, section 4.1.