Open bertram-gil opened 2 years ago
For this one, I have two comments after investigating the issue:
The demand("bf")
attribute will tell Scallop to compute fib
in an on-demand basis. Due to that a__
relation containing up-to 92
for the second element, Scallop needs to know the fib
relation up to the first element being 92
. This will in turn populate the whole fib
relation to contain all the x
from 0
to 92
, hence the long fib
relation you see from running the second program.
This is expected, as adding demand
will have side-effects on information propagation. Now a__
and fib
cannot be treated as two separated relations. There will be information passing between these two relations.
At the end, since fib
now contains all these tuples, it appears that (1, 1)
, (2, 2)
, and (3, 3)
are the three tuples that match the atom fib(a, a)
. Therefore by the rule
rel a__(a, a) = fib(a, a)
we will add these tuples into the a__
relation as well.
fib(92)
is a pretty large number, and this will cause integer overflow, hence the negative numbers you see in fib
. When compiling scli
, I have the runtime overflow check being disabled for performance. But using scli
with debug mode will actually throw error. A quick fix to this is setting the type of fib
and a__
to i128
(i64
is still not big enough). Otherwise, I'm thinking about a better way to raise the error to the user.Thanks for the explanation! :)
So then it seems that the first program is the buggy one? Tuples (2, 2)
and (3, 3)
are then missing from the result of the first program?
No. Again since we are touching the domain of magic-set transformation/demand transformation, things would start to get trickier and you wouldn't be able to tackle the problem using the old assumptions you have.
Here, we have defined fib
saying it should be demand transformed. Therefore we will only do computation if there is a demand on fib
with the pattern "bound-free" (bf
). In the first program, the rule a__(a, a) = fib(a, a)
does not populate a demand for fib
with the pattern "bound-free". At the end, there is no demand on fib
and so fib
won't be computed. Therefore only the base-cases will be populated (0, 1), (1, 1)
.
For example,
:- fib(3, a)
creates a demand on fib
with the "bound-free" pattern: the first argument is bounded and is 3
. :- d(a), fib(a, b)
creates a demand on fib
with the "bound-free" pattern: the first argument is bounded by any argument a
in the relation d
. :- fib(a, b)
the argument a
is not bounded by any.
Hi guys,
Consider the following program:
When I run this program with the latest Scallop commit (
778dfa126e98acb90a21dbececc825699f6688bd
), I get:If I add another rule (
rel a__(a, b) = a__(a, b), fib(b, b)
) for relationa__
to get the following new program:Now if I run this program, I get:
I get 2 extra tuples
(2, 2)
and(3, 3)
. However, adding this rule for relationa__
should not add these extra tuples fora__
.Also note that
fib
for the first program is:and for the second program:
Please let me know if you cannot reproduce this result or if I am doing something wrong.
My machine: