Prolog - Re: Newbie in need of help

Author

Re: Newbie in need of help

Shmmeee

2004-04-22, 11:36 am

UPDATE

I've been playing around with the code and have got something that
gives no errors but returns "no" every time. Below is my latest code,
could someone please help me find out where I'm going wring?

TIA

Ean

PROLOG CODE
--------------------------------------------------------------------------------
bubblesort(List,Sorted, Goal) :-
swap(List,PartSorted, Goal),!,
bubblesort(PartSorted,Sorted, Goal).
bubblesort(L,L).

swap([X,Y|Rest],[Y,X|Rest], Goal):-
gt(X,Y, Goal),!.
swap([H|T],[H|Rest], Goal):-
swap(T,Rest, Goal).

gt(X,Y, Goal):-
mismatched(X,Goal,Count1, Count1),
mismatched(Y, Goal, Count2, Count3),
Count1 > Count3.

mismatched( [], [], Count, Count ).
mismatched( [H1|Chars0], [H1|Chars1], Count0, Count ):-
Count1 is Count0 + 1,
mismatched( Chars0, Chars1, Count1, Count ).
mismatched( [Char0|Chars0], [Char1|Chars1], Count0, Count ) :-
mismatched( Chars0, Chars1, Count0, Count ).

word_game(Start,Goal,Path) :-
best_first([[Start]],Goal,Path).

best_first([[Goal|Path]|_],Goal,[Goal|Path]).
best_first([& #91;Current|Trail]|OtherPaths],Goal,Path
) :-
findall(& #91;Next,Current|Trail],next_node(Curren
t,Next,Trail),NewPaths),
append(OtherPaths,NewPaths,AllPaths),
bubblesort(AllPaths,SortAllPaths),
best_first(SortAllPaths,Goal,Path).

next_node(Current, Next, Trail):-
one_off2(Current, Next, _),
not(member(Next, Path)).

findall(X,Goal,Xlist):-
(call(Goal),
assertz(queue(X)),
fail);
assertz(queue(bottom)),
collect(Xlist).

collect(L):-
retract(queue(X)),
!,
(X == bottom,!,L = []
; L = [X|Rest],collect(Rest)).

one_off(dark, park).
one_off(dark, lark).
one_off(dark, dart).
one_off(dark, mark).
one_off(park, lark).
one_off(park, perk).
one_off(park, part).
one_off(perk, pert).
one_off(perk, berk).

one_off2(X, Y, D):-
one_off(X, Y, D).
one_off2(X, Y, D):-
one_off(Y, X, D).
--------------------------------------------------------------------------------

bart demoen

2004-04-22, 12:40 pm

Shmmeee wrote:
> UPDATE
>
> I've been playing around with the code and have got something that
> gives no errors but returns "no" every time.

Could you please be so kind as to specify what causes "it" to return no
every time ?
Any particular query, or just any query ?
Maybe it is not the case here, but you know, there are queries that
return no for every Prolog program; that's the origin for my request.

Thanks in advance

Bart Demoen

Stefan Ljungstrand

2004-04-22, 2:48 pm

On Thu, 22 Apr 2004, Shmmeee wrote:

> UPDATE
>
> I've been playing around with the code and have got something that
> gives no errors but returns "no" every time. Below is my latest code,
> could someone please help me find out where I'm going wring?
>
> TIA
>
> Ean
>
> PROLOG CODE
> --------------------------------------------------------------------------------
> bubblesort(List,Sorted, Goal) :-
> swap(List,PartSorted, Goal),!,
> bubblesort(PartSorted,Sorted, Goal).
> bubblesort(L,L).

Should you really define two predicates above :
bubblesort/3 and bubblesort/2 ?

> swap([X,Y|Rest],[Y,X|Rest], Goal):-
> gt(X,Y, Goal),!.
> swap([H|T],[H|Rest], Goal):-
> swap(T,Rest, Goal).
>
> gt(X,Y, Goal):-
> mismatched(X,Goal,Count1, Count1),
> mismatched(Y, Goal, Count2, Count3),
> Count1 > Count3.

This seems a bit weird ! :)

If mismatched/4 is going to give the number of mismatched (see below (*))
characters between X and Goal as the difference between the fourth and
third arguments (as you seem to be using the accumulator technique below),
then why are you giving Count1 *both* as third *and* fourth argument in
the first call of mismatched/4 above ?

You are effictively saying that the counter must not be incremented a
single time, in that call ! This is probably not what you intended/want.
(Also Count1 and Count2 are uninstantiated when calling mismatched/4
twice above, so 'Count1 is Count0 + 1' in mismatched/4 below is going
to give you a run-time instantiation error for those two calls.)
(Hint : Perhaps you've heard about 'initializing' an accumulator ?)

It might be nice to add a description such as that below to mismatched/4 :
(And corresponding ones to all or most of your other predicates also,
actually. This is more a style issue, though)

% mismatched( +Chars0, +Chars1, Count, NewCount )
% NewCount minus Count is the number of mismatching characters in
% corresponding places in the two character lists Char0 and Char1
% (which have the same length).

(But see below (*))

> mismatched( [], [], Count, Count ).
> mismatched( [H1|Chars0], [H1|Chars1], Count0, Count ):-
> Count1 is Count0 + 1,
> mismatched( Chars0, Chars1, Count1, Count ).
> mismatched( [Char0|Chars0], [Char1|Chars1], Count0, Count ) :-
> mismatched( Chars0, Chars1, Count0, Count ).

You need some way of ensuring that Char0 and Char1 are not the same
character in the third clause above, right ?
(Also, renaming a variable so it's first character is an underscore
usually stops common complaints about singleton variables.)

(*)
Hmm, from the name of the predicate one might think that it computes the
number of mismatching characters between it's first two arguments, while
what you actually do is count the number of *matching* characters, right ?
Probably it would be wise to change either the name or the implementation
of the predicate.

> word_game(Start,Goal,Path) :-
> best_first([[Start]],Goal,Path).
>
> best_first([[Goal|Path]|_],Goal,[Goal|Path]).
> best_first([& #91;Current|Trail]|OtherPaths],Goal,Path
) :-
> findall(& #91;Next,Current|Trail],next_node(Curren
t,Next,Trail),NewPaths),
> append(OtherPaths,NewPaths,AllPaths),

Hmm, maybe "append(NewPaths,OtherPaths,AllPaths)," would be slightly (?)
better here. (If NewPaths are generally shorter than OtherPaths, we won't
have to traverse and copy as many cons-cells.) Though we're sorting it
anyways next, so I'm not sure how big/noticable this effect would be ...

> bubblesort(AllPaths,SortAllPaths),
> best_first(SortAllPaths,Goal,Path).
>
> next_node(Current, Next, Trail):-
> one_off2(Current, Next, _),
> not(member(Next, Path)).

Trail and Path are both singleton variables here.

> findall(X,Goal,Xlist):-
> (call(Goal),
> assertz(queue(X)),
> fail);
> assertz(queue(bottom)),
> collect(Xlist).

It's customary to indent the disjunction like this :

findall(X,Goal,Xlist):-
( call(Goal),
assertz(queue(X)),
fail
; assertz(queue(bottom)),
collect(Xlist)
).

(Hmm, shouldn't you assert the marker before asserting the items ?
Not sure about this.)

Also, what happens if X is bottom ?
(Hint : Don't use a 'defaulty' datastructure to store the items collected
and the bottom-marker for them.)

>
> collect(L):-
> retract(queue(X)),
> !,
> (X == bottom,!,L = []
> ; L = [X|Rest],collect(Rest)).

(Ditto about bottom and indentation here.)

>
> one_off(dark, park).
> one_off(dark, lark).
> one_off(dark, dart).
> one_off(dark, mark).
> one_off(park, lark).
> one_off(park, perk).
> one_off(park, part).
> one_off(perk, pert).
> one_off(perk, berk).

Are atoms really character lists in your Prolog ?
If not, you might consider either changing those facts above to use
character lists (often known as strings), or, at some point between here
and mismatched/4, convert the atoms to character list. (There is probably
some built-in predicate, which does this. Consult your manual.)

> one_off2(X, Y, D):-
> one_off(X, Y, D).
> one_off2(X, Y, D):-
> one_off(Y, X, D).

I can't see any one_off/3 predicate. Perhaps you meant one_off/2 ?
Also, what good does the argument D of one_off2/3 do ?
Is it really needed ?

> --------------------------------------------------------------------------------
>

Ok, did you remember to change all places affected by some changes in your
program, and check that they all are consistent with each other ?

Hope this helped somewhat.

--
Stefan Lj
md9slj

The infinity that can be finitely expressed is not the true infinity

Sponsored Links