Prolog How to get uninstantiated variables to yield output

Question

I have a predicate that receives a binary number in the form of an atom, and returns a list of hexadecimal codes.

?- binaryHex('11111111',X).
X = [f, f].

When I try to go from hexadecimal to binary, I get this error:

?- binaryHex(X,[f,f]).
ERROR: atom_codes/2: Arguments are not sufficiently instantiated

I want both variables to produce the correct output. Here is the code.

hex('0000',0). hex('0001',1). hex('0010',2). hex('0011',3).
hex('0100',4). hex('0101',5). hex('0110',6). hex('0111',7).
hex('1000',8). hex('1001',9). hex('1010',a). hex('1011',b).
hex('1100',c). hex('1101',d). hex('1110',e). hex('1111',f).

binaryHex(X,Y) :-
    atom_codes(X,A),
    binaryList(A,B),
    binaryHex_(B,Y).

binaryList([],[]).
binaryList([A,B,C,D|Ds],[Y|Ys]) :-
    atom_codes(Y,[A,B,C,D]),
    binaryList(Ds,Ys).

binaryHex_([],[]).
binaryHex_([B|Bs],[H|Hs]) :-
    hex(B,H),
    binaryHex_(Bs,Hs).

The variables in the predicates binaryHex_/2 and binaryList/2 work both ways. The program breaks down because of the order of instantiation in the original binaryHex/2: binaryList/2 must come before binaryHex_/2 in order for the original task of binary to hex to work.

I imagine that this problem will be compounded if I convert the hexadecimal list to an atom. What are some strategies to cope with this situation so that as I continue to program I do not run into instantiation errors? Any comments/answers as to when this is not achievable are also encouraged.

Answer 1

Your problem is that you are using the wrong representation. Prolog can handle what you want very easily without any extra effort when using lists. That is, lists of characters (= atoms of length 1). Also, it is much more natural to use a dcg. Ah, and 0 alone is an integer, '0' is the corresponding character!

:- set_prolog_flag(double_quotes, chars). % More about double quotes

hexdigit('0') --> "0000".
hexdigit('1') --> "0001".
hexdigit('2') --> "0010".
hexdigit('3') --> "0011".
hexdigit('4') --> "0100".
hexdigit('5') --> "0101".
hexdigit('6') --> "0110".
hexdigit('7') --> "0111".
hexdigit('8') --> "1000".
hexdigit('9') --> "1001".
hexdigit( a ) --> "1010".
hexdigit( b ) --> "1011".
hexdigit( c ) --> "1100".
hexdigit( d ) --> "1101".
hexdigit( e ) --> "1110".
hexdigit( f ) --> "1111".

hexnum([]) -->
   [].
hexnum([D|Ds]) -->
   hexdigit(D),
   hexnum(Ds).

binaryHex(Bin, Hex) :-
   phrase(hexnum(Hex), Bin).

And now some sample usage:

?- binaryHex("11111111",X).
   X = [f,f]
;  false.
?- binaryHex(H,"ff").
   H = ['1', '1', '1', '1', '1', '1', '1', '1'].
?- use_module(double_quotes).
% double_quotes compiled into double_quotes 0.00 sec, 12 clauses
   true.
?- binaryHex(H,"ff").
   H = "11111111".

So you get "bidirectionality" simply by using lists. Coroutining is really overkill here. Worse, your original representation using atoms cannot cope with situations as generating all bitstrings of length 8:

?- length(L,8), binaryHex(L,Hex).
   L = "00000000", Hex = "00"
;  L = "00000001", Hex = "01"
;  L = "00000010", Hex = "02"
;  L = "00000011", Hex = "03"
; ... .

Proving that there are no bitstrings of length 7:

?- length(L,7), binaryHex(L,Hex).
   false.

And proving that bitstrings starting with 10 cannot correspond to a hex number starting with f.

?- binaryHex(['1','0'|L],[f|_]).
   false.

You cannot do all these with atoms and when/2 declarations.

Answer 2

I think that what you're asking for is not achievable - generally - in Prolog. But since I answered a similar question, I would suggest to try

binaryHex(X,Y) :-
    when_2(atom_codes(X,A)),
    when_2(binaryList(A,B)),
    binaryHex_(B,Y).

binaryList([],[]).
binaryList([A,B,C,D|Ds],[Y|Ys]) :-
    when_2(atom_codes(Y,[A,B,C,D])),
    binaryList(Ds,Ys).

:- meta_predicate when_2(0).
when_2(P) :-
    strip_module(P,_,Q),
    Q =.. [_,A0,A1],
    when((ground(A0);ground(A1)), P).

Of course, when/2 must be provided by your system.