binaryintegerprologswi-prolog# Binary to Integer in Prolog

Ok so. Still learning the basics in prolog and was given the bonus question on an assignment of converting a binary number into an integer based on the following definition for a binary num:

```
bin(bin(X),bin(Y,Z)):-
bin(X),
bin(Y,Z).
bin(bin(X),bin(Y)):-
bin(X),
bin(Y).
bin(zero).
bin(one).
% So for example, 10010 becomes:
% bin(bin(one),bin(bin(zero),bin(bin(zero),bin(bin(one),bin(zero)))))
```

Now I'll admit, I haven't haven't even begun to approach this one. It feels very daunting given my limited understanding of the language, and so I've only got the current base cases:

```
bin_int(bin(zero),0).
bin_int(bin(one),1).
bin_int(bin(B),X):-bin_int(B,X).
```

Like I said, limited understanding.

It's obviously gonna be recursive but I'm absolutely on how to go about it.

I'll post updates as work on it but for now it's just pseudocode so bear with me.

So, until B is 'one' or 'zero' it is going to have to be two bins and I'm already stuck.

Like how do I write that B must be a bin() tuple and how do I handle the second bin in the tuple having a tuple in itself or not?

Anybody got any as to how to go about this one I'd greatly appreciate some help. Thanks!

Solution

There are two types of `bin`

data given in the exercise: One type is something like `bin(D)`

representing a single digit, the other is `bin(D, Rest)`

representing a *sequence* of a digit followed by a rest (another digit or sequence).

Here's the code renamed and rearranged:

```
digit(zero).
digit(one).
sequence(digit(X),digit(Y)):-
digit(X),
digit(Y).
sequence(digit(X),sequence(Y,Z)):-
digit(X),
sequence(Y,Z).
binary(digit(Binary)) :-
digit(Binary).
binary(sequence(A, B)) :-
sequence(A, B).
```

Isn't this much clearer already? Thanks to the slightly rearranged code (non-recursive rules before recursive ones), we can ask Prolog to enumerate some solutions for us to explore how this behaves:

```
?- binary(B).
B = digit(zero) ;
B = digit(one) ;
B = sequence(digit(zero), digit(zero)) ;
B = sequence(digit(zero), digit(one)) ;
B = sequence(digit(one), digit(zero)) ;
B = sequence(digit(one), digit(one)) ;
B = sequence(digit(zero), sequence(digit(zero), digit(zero))) ;
B = sequence(digit(zero), sequence(digit(zero), digit(one))) ;
B = sequence(digit(zero), sequence(digit(one), digit(zero))) ;
B = sequence(digit(zero), sequence(digit(one), digit(one))) ;
B = sequence(digit(zero), sequence(digit(zero), sequence(digit(zero), digit(zero)))) ;
B = sequence(digit(zero), sequence(digit(zero), sequence(digit(zero), digit(one)))) ;
B = sequence(digit(zero), sequence(digit(zero), sequence(digit(one), digit(zero)))) . % etc.
```

Note that the enumeration isn't fair: Nested sequences with a leading `digit(one)`

will never be enumerated.

Now for your questions:

Like how do I write that B must be a bin() tuple

Exactly like you did. In Prolog, you describe what is true. Everything you don't describe is not true. You do not need to describe what is not true. If you define a predicate like

```
binary_integer(digit(zero), 0).
binary_integer(digit(one), 1).
binary_integer(sequence(Digit, Rest), ...) :- ...
```

then any call where the first argument is not unifiable with `digit(X)`

or `sequence(X, Y)`

will fail. You do not need to do anything special for non-binary cases.

and how do I handle the second bin in the tuple having a tuple in itself or not?

Recursively. If you have a recursive rule to handle `sequence(Digit, Rest)`

, and the `Rest`

is itself a `sequence(Digit2, Rest2)`

, then it will be handled.

Basically you want to write (in addition to the two rules for digits `zero`

and `one`

) a rule like:

```
binary_integer(sequence(Digit, Rest), N) :-
"Length is the number of binary digits in Rest",
Base is Digit << Length,
binary_integer(Rest, RestValue),
N is Base + RestValue.
```

The `"Length is the number of binary digits in Rest"`

is left as an exercise.

- How to remove trailing zeros from a binary number
- Count ones in a segment (binary)
- Correct use of getUint16()
- Converting from an integer to its binary representation
- inserting in binary tree doesn't work using java
- python: c# binary datetime encoding
- How to get only the first ten bytes of a binary file
- Difference between machine language, binary code and a binary file
- Why does Git treat this text file as a binary file?
- Override git's choice of binary file to text
- Distributing a statically linked ELF 32bit Binary - Will it run on all platforms?
- Statically Linked ELF 32 bit Binary - Distro Specific
- Translation from Binary to Decimal
- Calculating the total number of possibilities in binary?
- Regular Expression for Binary Numbers Divisible by 5
- How to check code generated by C++ compiler?
- What is the algorithm of Skeleton
- Setting all bits before first '1'
- Bitmasking conversion of CPU ids with Go
- Custom decode binary data in polars
- Why console.log shows only part of the number resulting from 0.1+0.2=0.30000000000000004
- Unable to properly return python data in function
- Word to represent 5 bits of data?
- How to convert text to binary code in JavaScript?
- Can I use a binary literal in C or C++?
- Reading integers from binary file in Python
- Way to add leading zeroes to binary string in JavaScript
- base conversion in c programming language
- How to detect if a binary number has a 0 in Decimal
- How can I read a binary file in C