Prolog - Non-recursive mod problem.

Author

Non-recursive mod problem.

charlie

2006-01-10, 4:10 am

Hi,
I'm quite new to prolog and I'm working my way through The Art of
Prolog. All was going well until I got to the mod function. I think
I've got everything as it should be but the non-recursive mod just
doesn't seem to want to terminate for anything other than:
mod(X,s(0),Mod)
where X is any number in the sn(0) format.
I suspect that there may be problem that mod has discovered in the
other predicates but I can't track it down and I don't have the
experience to be able to just see it. I've done some testing and all
the other preds seem to work well but maybe there's a case I haven't
found. Code posted at the end.

Thanks,
Charlie

%% -*- Mode: Prolog -*-

natural_number(0).
natural_number(s(X)) :-
natural_number(X).

lt(0,s(Y)) :- natural_number(Y).
lt(s(X),s(Y)) :- lt(X,Y).

lt_et(0,Y) :- natural_number(Y).
lt_et(s(X),s(Y)) :- lt_et(X,Y).

gt(s(X),0) :- natural_number(X).
gt(s(X),s(Y)) :- gt(X,Y).

gt_et(X,0) :- natural_number(X).
gt_et(s(X),s(Y)) :- gt_et(X,Y).

plus(0,X,X) :- natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).

times(0,X,0) :- natural_number(X).
times(s(X),Y,Z) :- times(X,Y,XY), plus(XY,Y,Z).

exp(0,X,0) :- natural_number(X).
exp(s(N),X,Y) :- exp(N,X,Z), times(Z,X,Y).

factorial(0,s(0)).
factorial(s(N),F) :- factorial(N,F1), times(s(N),F1,F).

mod(X,Y,Mod) :- lt(Mod,Y), times(Y,Q,QY), plus(QY,Mod,X).

%%mod(X,Y,X) :- gt(Y,X).
%%mod(X,Y,Mod) :- plus(X1,Y,X), mod(X1,Y,Mod).

Bart Demoen

2006-01-10, 4:10 am

charlie wrote:
> Hi,
> I'm quite new to prolog and I'm working my way through The Art of
> Prolog. All was going well until I got to the mod function. I think
> I've got everything as it should be but the non-recursive mod just
> doesn't seem to want to terminate for anything other than:
> mod(X,s(0),Mod)
> where X is any number in the sn(0) format.
> I suspect that there may be problem that mod has discovered in the
> other predicates but I can't track it down and I don't have the
> experience to be able to just see it. I've done some testing and all
> the other preds seem to work well but maybe there's a case I haven't
> found. Code posted at the end.
[...]
>
> mod(X,Y,Mod) :- lt(Mod,Y), times(Y,Q,QY), plus(QY,Mod,X).

Declaratively ok.

Procedurally, it says

for each Mod smaller than Y do (by backtracking)
for each QY that is a multiple of Y do
check whether QY+Mod == X

if for the first Mod smaller than Y there does not exist a QY such that
.... the inner for keeps on generating QYs and the check fails forever.

Put the lt goal at the end and convince yourself that this gives
solutions (and why). Also convince yourself that there is something
needed to stop the backtracking :-)

Cheers

Bart Demoen

charlie

2006-01-10, 4:10 am

Ok so what's happened is that I caught prolog in a loop because it was
trying to find a number that it had already passed and there was no way
for it to know that it had passed it already.

mod(X,Y,Mod) :- lt(Mod,Y), times(Y,Q,QY), plus(QY,Mod,X).

The only thing I want to ask now is why prolog chooses to increment Q
rather than Mod when it's bactracking. I would guess that by the time
it gets to the plus goal Mod is already bound because it's in the lt
goal so the last variable bound is Q (ignoring QY) so that's what gets
changed. Moving the lt to the end removes this binding so it can get
changed.

Cheers,
Charlie

Bart Demoen

2006-01-10, 4:10 am

charlie wrote:

> mod(X,Y,Mod) :- lt(Mod,Y), times(Y,Q,QY), plus(QY,Mod,X).
>
> The only thing I want to ask now is why prolog chooses to increment Q
> rather than Mod when it's bactracking.

Because Q gets bindings from a goal more to the right (in the clause)
than the goal that binds Mod.

Prolog implements chronological backtracking, i.e. the most recently
activated goal (with untried alternatives) is selected for backtracking.
And since Prolog activates goals from left to right in a clause ...

Cheers

Bart Demoen

charlie

2006-01-10, 4:10 am

That would make sense. Thanks for he help.

Cheers,
Charlie

Sponsored Links