How to resolve the algorithm Execute a Markov algorithm step by step in the SETL programming language
How to resolve the algorithm Execute a Markov algorithm step by step in the SETL programming language
Table of Contents
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
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:
Step by Step solution about How to resolve the algorithm Execute a Markov algorithm step by step in the SETL programming language
Source code in the setl programming language
program markov_algorithm;
magic := false;
if command_line(1) = om then
print("error: no ruleset file given");
stop;
elseif command_line(2) = om then
print("error: no input string given");
stop;
end if;
rules := read_file(command_line(1));
input := command_line(2);
loop do
loop for [pat, repl, trm] in rules do
if pat in input then
input(pat) := repl;
if trm then
quit;
else
continue loop do;
end if;
end if;
end loop;
quit;
end loop;
print(input);
proc read_file(file_name);
if (rulefile := open(file_name, "r")) = om then
print("error: cannot open ruleset file");
stop;
end if;
rules := [];
loop doing
line := getline(rulefile);
while line /= om do
rule := parse_rule(line);
if rule /= om then rules with:= rule; end if;
end loop;
return rules;
end proc;
proc parse_rule(rule);
if rule(1) = "#" then return om; end if; $ comment
if " -> " notin rule then return om; end if; $ not a rule
[s, e] := mark(rule, " -> ");
pattern := rule(..s-1);
repl := rule(e+1..);
whitespace := "\t\r\n ";
span(pattern, whitespace);
rspan(pattern, whitespace);
span(repl, whitespace);
rspan(repl, whitespace);
trm := match(repl, ".") /= "";
return [pattern, repl, trm];
end proc;
end program;
You may also check:How to resolve the algorithm Even or odd step by step in the Pike programming language
You may also check:How to resolve the algorithm Greatest element of a list step by step in the Lua programming language
You may also check:How to resolve the algorithm Determine if only one instance is running step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the D programming language
You may also check:How to resolve the algorithm Delete a file step by step in the Ruby programming language