How to change iteration order of results?

Help!
1

I’m using: SWI-Prolog version (threaded, 64 bits, version 9.2.8)

My problem:
Based on exercise 4.5 of this tutorial I have implemented the listtrans(G, E) predicate which translates a list of German words to a list of English words.

My solution works fine for translations from G to E or vice versa, but does not give me the answer I want when I query G and E at the same time.

What I’m getting is:

?- listtran(G, E).
G = E, E = [] ;
G = [eins],
E = [one] ;
G = [eins, eins],
E = [one, one] ;
G = [eins, eins, eins],
E = [one, one, one] ;
G = [eins, eins, eins, eins],
E = [one, one, one, one]

Of course this is not wrong, but I would like to have something like

?- listtran(G, E).
G = E, E = [] ;
G = [eins],
E = [one];
G = [zwei],
E = [two];
...
G = [eins, eins],
E = [two, two];

and so on.

My code looks like this:

tran(eins,one).
tran(zwei,two).
tran(drei,three).
tran(vier,four).
tran(fuenf,five).
tran(sechs,six).
tran(sieben,seven).
tran(acht,eight).
tran(neun,nine).

listtran([], []).
listtran([X|R1], [Y|R2]) :- tran(X, Y), listtran(R1, R2).

My question:
How do I have to modify listtran, in order to get the desired behavior?

What I tried:
Currently I can modify my query using a helper predicate

samelen([], []).
samelen([_|R1], [_|R2]) :- samelen(R1, R2).

Now when I do the following query, I get the desired result:

?- samelen(X, Y), listtran(X, Y).

But, if possible, I would prefer to find a solution which does not need this helper in the query.

2

Could use instead:

listtran([X], [Y]) :- tran(X, Y).
listtran([X|R1], [Y|R2]) :- tran(X, Y), listtran(R1, R2).

Results:

?- listtran(G, E).
G = [eins],
E = [one] ;
G = [zwei],
E = [two] ;
G = [drei],
E = [three] ;
...
G = [neun],
E = [nine] ;
G = [eins, eins],
E = [one, one] ;
G = [eins, zwei],
E = [one, two] ;
...
3

This is actually a very common ‘‘problem’’ (in quotes because it’s not really a problem when you think about it) when using lists in prolog.

The ordering you see in your first query comes from the ordering of non-deterministic predicates in your code.
The question you need to ask yourself is: Which predicate has created the last choicepoint ?
In your case, it is the listtrans/2 predicate that created the last choicepoint when stopping on the first clause listtrans([], [])., the second clause is still possible.

If I reformulate your question, it would something like this: How can I make trans/2 be the predicate that create the last choicepoint, so that I can first iterate all possibilities of trans/2 and then explore other list lengths ?

The solution you found with your helper predicate samelen/2 only hints at the real solution: If you don’t want listtrans/2 to be the predicate that create the last choicepoint, you need to make it deterministic.
The non-deterministic nature of listtrans/2 comes from not knowing the list length. Therefore, if you fix the list length before entering listtrans/2, listtrans/2 will be deterministic.

The common solution to this problem in prolog is just to stick a call to the standard predicate length/2 before the call to your predicate, like this:

?- length(G, _), listtrans(G, E).

In this mode, length/2 create lists of differente lengths, starting from 0 to infinity.
Now, it is length/2 that makes the choicepoint of iterating on differente list lengths, and listtrans/2 only jobs is to evaluate different trans/2 solutions.

NB1: you can see which clause has created the last choicepoint from the graphical debugger. Try the query: ?- gtrace, listtrans(G, E).

NB2: I have used some prolog specific vocabulary like “determinism”, “mode” or “choicepoints”. If you don’t know them, make sure to understand them as it is essential to understand prolog.

NB3: your helper predicate samelen/2 actually already exists and is called same_length/2.

NB4: To answer literally your question: you need to make an auxiliary predicate for listtrans/2 that willl himself call length/2:

listtrans(L1, L2) :-
    length(L1, _),
    listtrans_(L1, L2).
listtran_([], []).
listtran_([X|R1], [Y|R2]) :- tran(X, Y), listtran_(R1, R2).
1 Like
4

Thank you very much for this detailed answer! I will have to think about it a bit, but I think I get the main idea.