Markov algorithm simulator (Python)
- Other implementations: Ocaml | Python
The following is an implementation of a Markov Algorithm system written in Python.
We will be using functions from the string module:
<<Markov>>= import string
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): try: return filter(lambda (l,r,b): contains(w, l), a) except IndexError: 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): l,r,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
>>> run(successor, "L0LL") ['L0LL', 'aL0LL', 'La0LL', 'L0aLL', 'L0LaL', 'L0LLa', 'L0LLb', 'L0Lb0', 'L0b00', 'LL00']