Prolog + clpfd: simple binary number parser with value
I am currently trying to understand DCG in the prologue.
Let's consider this example.
digit(0) --> "0".
digit(1) --> "1".
binaryNumber(Val) --> digit(Val).
binaryNumber(Next*2 + Cur) -->
%CurVal #= Cur + Next*2,
binaryNumber(Next),
digit(Cur).
This produces:
207 ?- binaryNumber(X, Y, []). X = 0, Y = [48] ; X = 1, Y = [49] ; X = 0*2+0, Y = [48, 48] ; X = 0*2+1, Y = [48, 49] ; X = 1*2+0, Y = [49, 48] ; X = 1*2+1, Y = [49, 49] ; X = (0*2+0)*2+0,
It's good.
However, if I want to "convert" a string to a value:
:- use_module(library(clpfd)).
digit(0) --> "0".
digit(1) --> "1".
binaryNumber(Val) --> digit(Val).
binaryNumber(CurVal) -->
CurVal #= Cur + Next*2,
binaryNumber(Next),
digit(Cur).
I get:
209 ?- binaryNumber(X, Y, []).
X = 0,
Y = [48] ;
X = 1,
Y = [49] ;
ERROR: binaryNumber/3: Undefined procedure: (#=)/4
ERROR: However, there are definitions for:
ERROR: (#=)/2
Exception: (7) #=(_G4807345, _G4807428+_G4807431*2, _G4807346, _G4807475) ?
...
Two questions:
- Why
binaryNumber
wants to#=
have "arity" of 4? - How to fix it?
source to share
You are very close!
Usually dcg is foo//n
not implemented "directly" but by translating the grammar foo//n
into the corresponding Prolog predicate foo//(n+2)
. This translation is done term_expansion/2
, a mechanism similar to macros in other languages. You usually don't need to think about it at all.
More about dcgread: (1) this DCG primer and (2) the question " Is there a way or algorithm to convert DCG to normal defined articles in Prolog? " and the answers to this question.
Coming back to the topic, I see two problems in dcg use:
-
If used in grammar rules, "normal" Prolog targets must be enclosed in curly braces
{}/1
, so they are skipped in the above grammar-to-predicate translation step. In your code, you don't want to use(#=)//2
(aka(#=)/4
), you want(#=)/2
! -
It is good practice not to use targets
foo/(n+2)
directly. Usephrase/2
orphrase/3
for this
So, edit the relevant code snippet:
binaryNumber(Next*10 + Cur) -->
{ CurVal #= Cur + Next*2 },
binaryNumber(Next),
digit(Cur).
Now submit your request!
?- phrase(binaryNumber(X),Ts). X = 0, Ts = [48] ; X = 1, Ts = [49] ; X = 0, Ts = [48,48] ; X = 1, Ts = [48,49] ; X = 2, Ts = [49,48] ; X = 3, Ts = [49,49] ...
source to share