Return from Prolog predicate

Question

I have a predicate, which is true, if passed such list of pairs, for instance:

translatable([(dog,perro)], [(perro,hund)], [(dog,hund)])

Means - if "dog" translates to "perro", and "perro" translates to "hund", then it is true that "dog" translates to "hund".

Here follows full code. Returns/suggests first member of pair - given ((a, b), a) returns true, given ((a, b), X) returns X = a:

first((First, _), First).

Similar to "first", but for second pair member:

second((_, Second), Second).

This returns true if translatable word exists in list of tuples, and saves translation to Translation: (dog, Translation, [(bed,cama),(dog,perro)]

translation_exists(Word, Translation, [H|T]) :-
    first(H, Word), second(H, Translation), !;
    translation_exists(Word, Translation, T).

And resulting:

translatable(EnglishSpanish, SpanishGerman, EnglishGerman) :-
forall(member(Pair, EnglishGerman), (
    first(Pair, Word),
    second(Pair, ResultTranslation),
    translation_exists(Word, Translation, EnglishSpanish),
    translation_exists(Translation, ResultTranslation, SpanishGerman)
)).

This code returns true/false correctly. But why, given translatable([(dog,perro)], [(perro,hund)], X).

It does not returns X = [(dog,hund)]?

EDIT To be more specific, actual goal is: to find out if LAST dictionary has translatable pairs (and them only). Daniel, thanks a lot, I have adopted your suggested member function - great simplification, thank you! This is all the code I have now:

lastIsTranslatable(_, _, []).

lastIsTranslatable(EngSpan, SpanGerm, [(Eng, Germ) | T]) :-
    member((Eng, Span), EngSpan),
    member((Span, Germ), SpanGerm),

    % this is to protect endless [(dog,hund), (dog, hund), ...]
    not(member((Eng, Germ), T)),

    lastIsTranslatable(EngSpan, SpanGerm, T),
    !.

And still, this works great finding True & False:

lastIsTranslatable([(a,b)], [(b,c)], [(a,c)]).
lastIsTranslatable([(a,b)], [(b,c)], [(a,no)]).

But for

lastIsTranslatable([(a,b)], [(b,c)], X).

result is X= [], then, after hitting ";" - false. Why? Well, running with trace option, I see execution is failing on

not(member((Eng, Germ), T))

But otherwise resulting X will be endlessly filled with (a,c), (a,c)... Maybe there is better way to protect from duplicates?

To represent pairs, do not use comma like (A,B). Instead, use a different functor like A-B. — repeat

Daniel Lyons Daniel Lyons · Accepted Answer · 2016-01-13T17:33:33

The reason, basically, is that because EnglishGerman is uninstantiated, member/2 is free to come up with possible lists for it:

?- member((perro,X), List).
member((perro,X), List).
List = [ (perro, X)|_G18493911] ;
List = [_G18493910, (perro, X)|_G18493914] ;
List = [_G18493910, _G18493913, (perro, X)|_G18493917] ;
List = [_G18493910, _G18493913, _G18493916, (perro, X)|_G18493920] 
...

This is the most direct issue, but even if you change the flow of data I think you'll still have problems:

translatable1(EnglishSpanish, SpanishGerman, EnglishGerman) :-
    member((English,Spanish), EnglishSpanish),
    member((Spanish,German),  SpanishGerman),
    member((English,German),  EnglishGerman).

Note that I have foregone your first/2 and second/2 predicates in favor of pattern matching; I think this reads more clearly.

Aside: If you know your list is concrete and you don't want to generate multiple solutions, you can use memberchk/2 to verify that an element exists instead of member/2; it's cheaper and deterministic.

This works better (you get solutions, anyway) but still you get a lot more solutions than you need:

?- translatable1([(dog,perro)], [(perro,hund)], X).
X = [ (dog, hund)|_G18493925] ;
X = [_G18493924, (dog, hund)|_G18493928] ;
X = [_G18493924, _G18493927, (dog, hund)|_G18493931] a

Something which we know that our code does not know is that the cardinality of the result set should be less than or equal to the lowest cardinality of our inputs; if I have fifteen English-Spanish words and twelve Spanish-German words, I can't have more than twelve words in my English-German result. The reason our code doesn't know that is because it is trying to behave like math: our code is basically saying "for every element of English-Spanish, if there exists a matching element of Spanish-German, that is also an element of English-German." This does not tell us how to construct English-German! It only tells us a fact about English-German that we can verify with English-Spanish and Spanish-German! So it's cool, but it isn't quite enough to compute English-German.

Aside: it's conventional in Prolog to use a-b instead of (a,b); it's too easy to lull yourself into believing that Prolog has tuples when it doesn't and the operator precedence can get confusing.

So, how do we tell Prolog how to compute English-German? There are probably lots of ways but I would prefer to use select/3 because our set cardinality constraints (as well as a general sense that it will converge/halt) will emerge naturally from a computation that "uses up" the input sets as it goes.

translatable2([], _, []).
translatable2(_, [], []).
translatable2([Eng-Span|EngSpanRem], SpanGerm, EngGerm) :-
    (select(Span-Germ, SpanGerm, SpanGermRem) ->
         translatable2(EngSpanRem, SpanGermRem, EngGermRem),
         EngGerm = [Eng-Germ|EngGermRem]
     ;
         translatable2(EngSpanRem, SpanGerm, EngGerm)
    ).

The base cases should be obvious; if we are out of English-Spanish or Spanish-German, there's nothing left to compute. Then the inductive case peels the first item off the English-Spanish list and searches for a Spanish-German translation that matches. If it finds one, it uses it to build the result; otherwise, it just recurs on the remaining English-Spanish list. This way, on each iteration we at least discard an English-Spanish translation from that list, and we discard Spanish-German translations as they are used. So it seems intuitively likely that this will work and terminate without producing a bunch of extra choice points.

It seems to do the trick:

?- translatable2([dog-perro], [perro-hund], X).
X = [dog-hund] ;
X = [dog-hund].

The extra result there is because we hit both terminal cases because both lists became []; this isn't attractive but it isn't anything to worry about really either.

Now one thing that sucks about this solution is that it treats the first two parameters as in-parameters and the last one as an out-parameter and there isn't really anything you can do about this. I don't know if this is an issue for you; translatable/1 should not have this limitation, but because member((Spanish,German), SpanishGerman) happens before member((English,German), EnglishGerman) it winds up generating an infinitely large list, searching in effect for the missing Spanish-German translation.

Still, it feels like it should be possible to come up with a general purpose predicate that works as long as you supply any two of these inputs. I can do that if I know that all three lists are complete and in the same order:

translatable3([], [], []).
translatable3([X-Y|XYs], [Y-Z|YZs], [X-Z|XZs]) :-
    translatable3(XYs, YZs, XZs).

And you can see it work like so:

?- translatable3([dog-perro], [perro-hund], X).
X = [dog-hund].

?- translatable3([dog-perro], X, [dog-hund]).
X = [perro-hund].

?- translatable3(X, [perro-hund], [dog-hund]).
X = [dog-perro].

But I don't know enough about your constraints to know if that could be a legitimate answer. My suspicion is no, because languages don't work that way, but who knows?

Anyway, that's three different approaches; I hope one of them is helpful to you!

Return from Prolog predicate

1 Answers