Prolog - Does this Prolog newbie getting it right?

Author

Does this Prolog newbie getting it right?

Emre Sevinc

2004-12-23, 4:07 pm

Hi,

Regular readers/posters may be used to my adventures
in Prologwonderland. Once again I want Prolog masters
to enlighten me and enhance my vision. This time a simple
code review (a code that works fine, I guess ;-) will
just do.

I keep on going along the Brakto's book. I've just finished
reading the chapter about non-deterministic finite automata.

He gives example code that can check if a string is acceptable
given a finite state automaton:

final(s3).

trans(s1, a, s1).
trans(s1, a, s2).
trans(s1, b, s1).
trans(s2, b, s3).
trans(s3, b, s4).

silent(s2, s4).
silent(s3, s1).

accepts(State, []) :- % Accept empty string if it is from Final state
final(State).

accepts(State, [X | Rest]) :-
trans(State, X, State1),
accepts(State1, Rest).

accepts(State, String, MaxMoves) :-
silent(State, State1),
accepts(State1, String).

And then he draws attention that the automaton graph can
include cyclic silent paths. If we simply add another transition:

silent(s1, s3).

we'll have a silent cyclic path which can lead to an infinite
loop in case we ask for ?- accepts(s1, [a]).
So Mr. Bratko asks how to handle that situation. My solution is as
follows, modifying the first two accept predicates:

accepts(State, [], MaxMoves) :- % Accept empty string if it is from Final state
final(State).

accepts(State, [X | Rest], MaxMoves) :-
MaxMoves >= 0,
MaxMoves1 is MaxMoves - 1,
trans(State, X, State1),
accepts(State1, Rest, MaxMoves1).

accepts(State, String, MaxMoves) :-
MaxMoves >= 0,
MaxMoves1 is MaxMoves - 1,
silent(State, State1),
accepts(State1, String, MaxMoves1).

I've tried it and it works, what I ask is I did
it fine, if I did The Right Thing. Can it be made
simpler, is it suitable with Prolog spirit, if not
how can it be done?

Thanks in advance.

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

vannoord@let.rug.nl

2004-12-23, 9:03 pm

Emre Sevinc <emres@bilgi.edu.tr> wrote:

> accepts(State, [], MaxMoves) :- % Accept empty string if it is from Final state
> final(State).

> accepts(State, [X | Rest], MaxMoves) :-
> MaxMoves >= 0,
> MaxMoves1 is MaxMoves - 1,
> trans(State, X, State1),
> accepts(State1, Rest, MaxMoves1).

> accepts(State, String, MaxMoves) :-
> MaxMoves >= 0,
> MaxMoves1 is MaxMoves - 1,
> silent(State, State1),
> accepts(State1, String, MaxMoves1).

> I've tried it and it works, what I ask is I did
> it fine, if I did The Right Thing. Can it be made
> simpler, is it suitable with Prolog spirit, if not
> how can it be done?

- you can never accept sentences that contain more symbols than
MaxMoves

so you cracked the nut with a sledgehammer.

A typical Prolog solution
that I'd require from my students would be a solution in which you
keep track of the states visited during a 'silent-only' walk, and then
check that you can't return to a state that you already visited before
without consuming a new symbol.

Gj

Emre Sevinc

2004-12-23, 9:03 pm

vannoord@let.rug.nl writes:

> Emre Sevinc <emres@bilgi.edu.tr> wrote:
>
>
>
>
>
> - you can never accept sentences that contain more symbols than
> MaxMoves
>
> so you cracked the nut with a sledgehammer.

Ooops! Once again! :(

Is my solution that bad? Do you mean I should check the
length of symbol list and if it is greater than MaxMoves,
tell that it is FALSE? But if the symbol list is shorter than
MaxMoves I still have the possibility of entering an infinite loop.
(yes I'm a little bit

).

> A typical Prolog solution
> that I'd require from my students would be a solution in which you
> keep track of the states visited during a 'silent-only' walk, and then
> check that you can't return to a state that you already visited before
> without consuming a new symbol.

Yes, I said I was

. :) Does your solution correspond to
the same problem? If so, is it easier, simpler? I couldn't understand
exactly the part about "keeping track during silent-only" walks.

Cheers,

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

tmp123

2004-12-23, 9:03 pm

>
> Yes, I said I was

. :) Does your solution correspond to
> the same problem? If so, is it easier, simpler? I couldn't understand
> exactly the part about "keeping track during silent-only" walks.
>
>

Sugestion: Make a paralelism between this problem and the "rooms -
doors find path" problem. States are the rooms, silents the doors.

vannoord@let.rug.nl

2004-12-23, 9:03 pm

Emre Sevinc <emres@bilgi.edu.tr> wrote:
> vannoord@let.rug.nl writes:

[color=darkred]
> Ooops! Once again! :(

> Is my solution that bad? Do you mean I should check the
> length of symbol list and if it is greater than MaxMoves,
> tell that it is FALSE?

No.

> But if the symbol list is shorter than
> MaxMoves I still have the possibility of entering an infinite loop.
> (yes I'm a little bit

).

The idea to use a maximum numer of moves is not good, since you cannot
tell in advance what this maximum should be. For any maximum that you
suggest, I come up with a string for which this maximum does not work.

[color=darkred]
> Yes, I said I was

. :) Does your solution correspond to
> the same problem?

Yes. That's why I replied.

Yours is not a solution. It "solves" the problem by making it impossible
to recognize certain good strings.

> If so, is it easier, simpler? I couldn't understand
> exactly the part about "keeping track during silent-only" walks.

well. The problem is that you can enter an infinite loop by jumping
(taking a 'silent' move) around in cycles. So this is what your code
should prevent. Such a cycle consists of a series of silent moves from
state p to state p. You can prevent this by keeping track of all the
states that you have been in, since last consuming a symbol. You can
then forbid to jump to such a state. But as soon as you take a "real"
transition (consume a symbol), you can forget about all those states.
I don't know how to explain this any better.

Gj

--
Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl http://www.let.rug.nl/~vannoord

Emre Sevinc

2004-12-23, 9:03 pm

vannoord@let.rug.nl writes:

> Emre Sevinc <emres@bilgi.edu.tr> wrote:
>
[color=darkred]
>
>
> well. The problem is that you can enter an infinite loop by jumping
> (taking a 'silent' move) around in cycles. So this is what your code
> should prevent. Such a cycle consists of a series of silent moves from
> state p to state p. You can prevent this by keeping track of all the
> states that you have been in, since last consuming a symbol. You can
> then forbid to jump to such a state. But as soon as you take a "real"
> transition (consume a symbol), you can forget about all those states.
> I don't know how to explain this any better.
>
> Gj

Oh! Thanks a lot, now it is much more clear! Looks like I was rather
concentrated on Bratko's cue and this prevented me thinking about
the real nature of cyclicity problem.

By the way, a friend of mine suggested such a modification:
(even though I don't know what exactly \+ means...)

accepts(State,[]) :-
final(State).

accepts(State,[X|Rest]) :-
trans(State,X,State1),
sils(State1,State2,[]),
accepts(State2,Rest).

sils(StateI,StateI,_).
sils(StateI,StateF,Previous) :-
silent(StateI,StateN),
\+ member(StateN,Previous),
sils(StateN,StateF,[StateN|Previous]).

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

Bart Demoen

2004-12-24, 3:57 pm

Emre Sevinc wrote:

> (even though I don't know what exactly \+ means...)

\+ is "not provable" (by Prolog) - close to, and sometimes

with, negation.

But you question indicates that you urgently need to look at a manual, a
tutorial or a book on Prolog. The FAQ suggests some online tutorials.
You will find plenty about \+

Cheers

Bart Demoen

Emre Sevinc

2004-12-24, 8:56 pm

Bart Demoen <bmd@cs.kuleuven.ac.be> writes:

> Emre Sevinc wrote:
>
>
> \+ is "not provable" (by Prolog) - close to, and sometimes

> with, negation.
>
> But you question indicates that you urgently need to look at a manual, a
> tutorial or a book on Prolog. The FAQ suggests some online
> tutorials. You will find plenty about \+

Well, I'm following Bratko's text and I didn't meet it yet,
I've just looked at index and found that it is at the very
end of the book, p.648:

"In this book we use not Goal for negation as failure. Many Prologs
(and the standard) use the (somewhat less pretty) notation:

*\+ Goal*

to emphasize that this is not the proper logical negation, but
negation defined through failure. For compatibility with these
Prologs, 'not' should be replaced by '\+', or (with less work),
*not* introduced as a user-defined predicate (see Appendix B)."

Well I don't know if Bratko's style is good or bad. My SWI manual
tells me that it has *not* but *\+* must be used instead because
*not* is just retained for compatibility.

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

Sponsored Links