Prolog homework: how to parse a list of 'bits' representing a numeric value into a decimal representation?

Question

Okay, so I have another question on a prolog homework problem I am struggling with. The problem goes as follows:

Write a Prolog program that will take a list representing the bits of a binary number, and return the decimal value of the integer that the list represents.

Example: valueof([1,1,0,1],X). X = 13

So here's what I have so far:

valueOf(List, X) :- setup(List, [], X).
setup([H|T], [Y|H], X) :- setup(T,Y,X).
setup([], Y, X) :- count(Y, X, 0).
count([], _, _).
count([H|T], X, Count) :- NewCount is Count + 1, NewX is X + (H*2^Count),
                          count(T,NewX,NewCount).

Once again, I appreciate any help at all, I really seem to be struggling with this prolog stuff. Thanks.

Answer 1

Your algorithm looks far too complicated; try something along these lines:

• base case: one digit list, return the digit
• recursive case: return the last digit plus 2 times the result of the list with the last digit removed.

Since it's homework, I'll leave the implementation details up to you.

Answer 2

I would say that I disagree with Carl's choice of base case. We must handle the case of empty list, and it is better not to have multiple types of "base cases." The analogy of "base" case is the case at the "bottom" of the recursion and we all know things have only one bottom, or base.

So I would suggest:

• base case:
  • empty list, which has the value of "zero" (0)
  • this case concludes the recursion and so must copy any accumulated value into the output parameter.
• initial case: having not yet accumulated any digits, the accumulator variable will be zero (0).
• recursive case: the digit examined in each recursion is accumulated into the accumulator

The prolog code will look like this:

% Initial value of accumulator is zero (0).
valueOf( L, X) :- value_of_accumulation( L, 0, X).

% Base case:
% When there are no more digits to process, the output value (3rd param)
% is unified with the accumulator (2nd param)
value_of_accumulation( [], A, A).

% The recursive step.  There is a digit (B) to process here.  T is a temporary
% which holds the value of the accumulator "passed down" to the next case
% and, ultimately, to the base case after possible more accumulations.  A holds
% the previously-accumulated value derived from more-significant bits, already
% processed in previous recursions.  This clause is invoked once for each bit.
% Implicitly, the invocations of this clause generate a "count" but there is no
% actual use of the count when accumulating the bits.  Each bit is accumulated
% without knowledge of whether subsequent bits follow.
value_of_accumulation( [B | L], A, X) :-
    B >= 0,
    B =< 1,
    T is % fill this in with math, a function of bit B and previously-accumulated bits A,
    value_of_accumulation( L, %fill this in with prolog understanding.