Binary Digits to ASCII Characters

Question

I wrote this code, as a novice a to Prolog, for a challenge posted on /r/DailyProgrammer. The formal description of this challenge, as presented in the prompt reads:

Input description

On console input you will be given a variable number of 0's and 1's that correspond to letters in the alphabet [a-z] and whitespace ' '. These will be integers coming in, it's your job to cast them however you need.

Output description

The program should output the english translation (or other languages if you feel so inclined!) of the binary phrase

This is a fairly simple task so, even as a novice to Prolog, it didn't take me long to complete.

main(Words):-
    open('text.txt',read,Stream),
    readAll(Stream,Codes),
    close(Stream),
    atom_codes(Words,Codes).

readAll(Stream,[]):-
    at_end_of_stream(Stream).
readAll(Stream,Out):-
    readBinary(Stream,8,Out2),
    readAll(Stream,Out3),
    Out = .(Out2,Out3).

readBinary(_,0,0).
readBinary(Stream,Digits,Out):-
    get_code(Stream,A),
    B is (A-48) * 2 ^ (Digits-1),
    Digits2 is Digits - 1,
    readBinary(Stream,Digits2,Out2), 
    Out is B + Out2.

text.txt is a text file containing the flowing binary digits encoded as characters in UTF-8:

0100100001100101011011000110110001101111001000000101011101101111011100100110110001100100

Running the code results in the correct output:

Hello World

---

The code undoubtedly works, and I even find that I like how it looks. My greatest concern, however, is that this somehow does not maintain style and format standards of Prolog programs. Reading through the code, it reads as a completely imperative program, but I know that Prolog is built off the logic programming paradigm. Is this because of a fault in how I wrote the program, or is the problem that this challenge does not lend itself to logic programming? If the former is correct, how could this be written to better reflect the full capabilities of Prolog?

Answer 1

Your concerns about style and format are warranted, +1 for striving to make the code more elegant and declarative!

First of all, whatDoYouFindEasierToRead: mixed_caps_or_underscores?

For that reason, using underscores is the Prolog convention for naming predicates.

Second, Prolog is all about relations between things. You are using low-level moded arithmetic (is/2), which can only be used in one direction.

Instead, use constraints: They are completely general relations that can be used in all directions.

Third, since you are describing a list of bytes, consider using DCG notation. Do not use side-effects (opening a file etc.), because they prevent you from using your program in all directions. Instead, focus on a clear declarative description, and use pure features like library(pio) to apply a DCG to file contents.

All in all, consider the following program, tested with SWI-Prolog:

:- use_module(library(clpfd)).

:- set_prolog_flag(double_quotes, codes).

bytes([])     --> [].
bytes([B|Bs]) --> byte(B), bytes(Bs).

byte(Byte) -->
        [A,B,C,D,E,F,G,H],
        { foldl(pow, [A,B,C,D,E,F,G,H], 0-7, Byte-_) }.

pow(X0, Val0-Pow0, Val-Pow) :-
        X in 0..1,
        X #= X0 - 0'0,
        Val #= Val0 + X*2^Pow0,
        Pow #= Pow0 - 1.

Notice that I am not using any side-effects at all, and I don't have to, because I can do everything I need on the toplevel:

?- phrase(bytes(Bs), "0100100001100101011011000110110001101111001000000101011101101111011100100110110001100100"), maplist(char_code, Chars, Bs), maplist(write, Chars).
Hello World
Bs = [72, 101, 108, 108, 111, 32, 87, 111, 114|...],
Chars = ['H', e, l, l, o, ' ', 'W', o, r|...] .

And now the beauty of the declarative approach: In fact, the program is much more general than that, and I can also use it in the other direction:

?- phrase(bytes("Hello"), Codes), maplist(char_code, Chars, Codes), maplist(write, Chars).
0100100001100101011011000110110001101111
Codes = [48, 49, 48, 48, 49, 48, 48, 48, 48|...],
Chars = ['0', '1', '0', '0', '1', '0', '0', '0', '0'|...].

In fact, I can even leave everything unspecified and still obtain answers:

?- phrase(bytes(Bs), Codes).

Thus, the program is now much more general.

I would like to add that logic programming is very well suited for such kinds of problems. In fact, one of the very first applications of Prolog was concerned with language translation, and parsing a list of bytes like that was certainly part of that. Just stay in the pure and declarative part of Prolog (use constraints, pure input etc.), and you will obtain pretty nice programs.

EDIT: As requested, a few more comments about the code. The main part of the program, the grammar rule byte//1, is a declarative description of what we consider a byte in this notation. Now this is easily described: A byte in this particular notation is just a list of 8 bits [A,B,...,H]. And these bits are related to the byte B via the well-known relation B = A*2^7 + B*2^6 + ... + H*2^0. The pow/3 predicate defines this relation for each of the bits, using a running sum and position indicator as one of its arguments. Of course I have to subtract the ASCII code of 0 (Prolog: 0'0) from each of the given bits, because they are themselves specified in ASCII already, hence X #= X0 - 0'0 to obtain the "true" value of the bit X, 0 or 1.

Well and that's pretty much there is to it. A list of such bytes is readily described with DCG notation, and we use the phrase/2 interface to access DCGs.

I leave figuring out the rest as an easy exercise. Remember that you can always use the graphical tracer with ?- gtrace, your_goal., if you are interested in any particular execution details. In general though, I recommend you instead read the program declaratively and understand the relations that are being defined.