For those who want to train their tacit muscles, here's a challenge. A Markov algorithm is a specialized term rewriter. It accepts a list of rules (denoting substitutions) and a target string to evaluate. See http://rosettacode.org/wiki/Markov_Algorithm for a more detailed description, examples, and some implementations (ignore the J implementation for now; it is incorrect).
However, the Markov engine has a very strict order of evaluation. At each step, it evaluates the current rule; if the rule matches, it makes one and only one substitution (to the leftmost match), and then it starts over from the beginning (i.e. at rule 0, as opposed to looking for more matches for this rule or moving on to the next rule). Once all the rules have been applied and no more matches occur, the (now stable) result is the output of the Markov engine. The engine may also termination early, before the result stabilizes; a rule may be marked as a "terminator", and if such a rule matches, it makes one and only one substitution (to the leftmost match) and the result is the output of the Markov engine. Below is a model in explicit J. Can you rewrite it tacitly? Now, the challenge is more than just a tacit rewrite (though that can be a fun exercise in itself, especially for those new to tacit J). Any stateless explicit code can be rewritten tacitly (Pepe proved this), through a fairly mechanical translation procedure. But the results are often ugly and inferior (longer, harder to read, more redundant) than the original explicit model. For an example, see http://rosettacode.org/wiki/Talk:Markov_Algorithm#explicit_vs_tacit . The challenge truly is: can you write an elegant tacit Markov algorithm? -Dan ------------------ markovLexer =: verb define rules =. LF cut TAB&=`(,:&' ')}y rules =. a: -.~ (dltb@:{.~ i:&'#')&.> rules rules =. 0 _1 {"1 '\s+->\s+' (rxmatch rxcut ])S:0 rules NB. Determine which rules are terminating (,. ] (}.&.>~ ,. ]) ('.'={.)&.>)/ |: rules ) replace =: dyad define 'index patternLength replacement'=. x 'head tail' =. index split y head, replacement, patternLength }. tail ) matches =: E. i. 1: markovStrict =: dyad define rules =. markovLexer x ruleIdx =. 0 while. ruleIdx < #rules do. 'pattern replacement terminating' =. ruleIdx { rules if. (#y) > index =. pattern matches y do. y =. (index ; (#pattern) ; replacement) replace y if. terminating do. NB. If terminating rule, just return current string ruleIdx =. #rules else. NB. Else reevaluate from the beginning after every match ruleIdx =. 0 end. else. ruleIdx =. 1 + ruleIdx end. end. y ) ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
