Problem Statement

Create an interpreter for a Markov Algorithm. Rules have the syntax: There is one rule per line. If there is a   .   (period)   present before the   ,   then this is a terminating rule in which case the interpreter must halt execution. A ruleset consists of a sequence of rules, with optional comments.

Rulesets Use the following tests on entries:

Sample text of: Should generate the output:

A test of the terminating rule Sample text of: Should generate:

This tests for correct substitution order and may trap simple regexp based replacement routines if special regexp characters are not escaped. Sample text of: Should generate:

This tests for correct order of scanning of rules, and may trap replacement routines that scan in the wrong order.   It implements a general unary multiplication engine.   (Note that the input expression must be placed within underscores in this implementation.) Sample text of: should generate the output:

A simple Turing machine, implementing a three-state busy beaver. The tape consists of 0s and 1s,   the states are A, B, C and H (for Halt), and the head position is indicated by writing the state letter before the character where the head is. All parts of the initial tape the machine operates on have to be given in the input. Besides demonstrating that the Markov algorithm is Turing-complete, it also made me catch a bug in the C++ implementation which wasn't caught by the first four rulesets. This ruleset should turn into

Let's start with the solution:

(remove-comments) text:
    ]
    for line in text:
        if and line not starts-with line "#":
            line
    [

(markov-parse) text:
    ]
    for line in text:
        local :index find line " -> "
        local :pat slice line 0 index
        local :rep slice line + index 4 len line
        local :term starts-with rep "."
        if term:
            set :rep slice rep 1 len rep
        & pat & term rep
    [

markov-parse:
    (markov-parse) (remove-comments) split !decode!utf-8 !read!stdin "\n"

(markov-tick) rules start:
    for rule in copy rules:
        local :pat &< rule
        local :rep &> dup &> rule
        local :term &<
        local :index find start pat
        if < -1 index:
            )
            slice start + index len pat len start
            rep
            slice start 0 index
            concat(
            return term
    true start

markov rules:
    true
    while:
        not (markov-tick) rules

!. markov markov-parse get-from !args 1