# Markov algorithm simulator (Ocaml)

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

<<markov.ml>>=Markov

You will need to load the Str (regular expressions) library somehow, which is usually given as an option to the compiler. The following directive will load it while in the toplevel interpreter.

<<Markov>>=#load "str.cma";;openStr

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.

<<Markov>>=typeword = stringtyperule = word * word * booltypealgor = rule list

The successor algorithm is encoded as a list of rules.

<<Markov>>=letsuccessor =["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>>=letreccontains(s:string)(sub:string): bool =tryignore(search_forward(regexp_string sub)s 0); truewithNot_found -> false

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 *Not_found* is raised.

<<Markov>>=letfind_rule(a:algor)(w:word): rule = List.find(fun(l,_,_)-> contains w l)a

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>>=letapply_rule(l,r,_:rule)(s:word): word = replace_first(regexp_string l)r s

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. *Not_found* is raised if no rule matches.

<<Markov>>=letapply_alg(a:algor)(w:word): word * bool =let_,_,basr = find_rule a winapply_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>>=letrecrun(a:algor)(w:word): word list =tryletw', flg = apply_alg a winifnot flgthenw :: run a w' (* Normal rule was applied *)else[w; w'](* Halting rule was applied *)withNot_found ->[w](* No rule was applied *)

Example:

# run successor "L0LL";; - : word list = ["L0LL"; "aL0LL"; "La0LL"; "L0aLL"; "L0LaL"; "L0LLa"; "L0LLb"; "L0Lb0"; "L0b00"; "LL00"]

Download code |