Markov algorithm simulator (Python)

From LiteratePrograms

Other implementations: Haskell | Ocaml | Python

The following is an implementation of a Markov Algorithm system written in Python.

<<markov.py>>=
Markov

A Markov algorithm is a string rewriting system consisting of rewrite rules. Each rule is a triple consisting of the word to match, the word to use as a replacement and a boolean flag. If the flag is true then the rule is a halting rule.

The successor algorithm is encoded as a list of rules.

<<Markov>>=
successor = [("aL", "La", False),
             ("a0", "0a", False),
             ("a" , "b" , False),
             ("Lb", "b0", False),
             ("0b", "L" , True ),
             ("b" , "L" , True ),
             (""  , "a" , False)]

The contains function returns true if the second argument is a substring of the first argument.

<<Markov>>=
def contains(s, sub):
    return s.find(sub) != -1

The find_rule function takes a list of rules and a word and returns the first rule that matches. The contains function defined above is used to test for the match. If no matching rule is found then the exception ValueError is raised.

<<Markov>>=
def find_rule(a, w):
    for l,r,b in a:
        if contains(w, l):
            return l,r,b
    raise ValueError, "not found"

The apply_rule function applies a single rule to a word. This function searches the word until it matches the left side of the rule. Once the match is found the text is replaced with the right side of the rule and the resulting word is returned.

<<Markov>>=
def apply_rule((l,r,b), s):
    return s.replace(l, r, 1)

The apply_alg function takes a list of rules and a word and applies the first matching rule. The find_rule function is used to find the first matching rule then the apply_rule function is used to apply the rule. A pair is returned containing the resulting word and a bool flag, the flag is true if the rule that was applied was a halting rule. ValueError is raised if no rule matches.

  
<<Markov>>=
def apply_alg(a, w):
    _,_,b = r = find_rule(a, w)
    return apply_rule(r, w), b

The run function applies the Markov algorithm continuously until either a halting rule is matched or no rule is matched. The word sequence that results from applying the algorithm is returned. This function calls itself recursively with the result of the previous call to apply_alg.

       
<<Markov>>=
def run(a, w):
    result = []
    flag = False                      # whether Halting rule was applied
    try:
        while not flag:               # Normal rule was applied
            result.append(w)
            w, flag = apply_alg(a, w) # apply a rule
        result.append(w)
    except ValueError:                # No rule was applied
        pass
    return result

Some test code:

<<Markov>>=
if __name__ == "__main__":
    print run(successor, "L0LL")

Output:

['L0LL', 'aL0LL', 'La0LL', 'L0aLL', 'L0LaL', 'L0LLa', 'L0LLb', 'L0Lb0', 'L0b00', 'LL00']

Download code