Does this Prolog newbie getting it right?

From: Emre Sevinc (emres_at_bilgi.edu.tr)
Date: 12/23/04

  • Next message: vannoord_at_let.rug.nl: "Re: Does this Prolog newbie getting it right?" 
    Date: Thu, 23 Dec 2004 21:08:23 +0200

    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
  • Next message: vannoord_at_let.rug.nl: "Re: Does this Prolog newbie getting it right?"

    Relevant Pages

    • Re: Possible to register a foreign function dynamically?
      ... anything, it just returns the pointer to the actual string, so I don't ... Actually it can also come along during the lifetime of the predicate ... Prolog threads active. ... If above is how Python programmers would like to see it, ...
      (comp.lang.prolog)
    • Re: Can I do this in prolog string to [s,t,r,i,n,g]
      ... >>How do I do this in ISO or SWI Prolog? ... >> string functions like those in visual prolog. ... For, if the input is an atom you can use sub_atom/5, for a string ...
      (comp.lang.prolog)
    • Re: String manipulation in Prolog
      ... > I'm exploring the use of Prolog in text/corpus processing. ... > can't find much in the way of string manipulation. ... > insert a substring into a string ...
      (comp.lang.prolog)
    • String manipulation in Prolog
      ... I'm exploring the use of Prolog in text/corpus processing. ... simple in other languages like Python and Ruby, ... can't find much in the way of string manipulation. ...
      (comp.lang.prolog)
    • Re: what does for _ in range() mean?
      ... > E.g. to declare that X is a parent if X is a father or mother: ... string that needs localization. ... in Prolog and the use of _ in Python; ... That's not true in Python, ...
      (comp.lang.python)