Execute a Markov algorithm: Difference between revisions
Add Refal
Not a robot (talk | contribs) (Add Refal) |
|||
(11 intermediate revisions by 6 users not shown) | |||
Line 153:
{{trans|Nim}}
<
String pattern
String replacement
Line 282:
L(ruleset) RuleSets
V rules = parse(ruleset)
print(apply(SampleTexts[L.index], rules))</
{{out}}
Line 295:
=={{header|Ada}}==
markov.ads:
<
package Markov is
Line 320:
Entries : Entry_Array (1 .. Length);
end record;
end Markov;</
markov.adb:
<
function Parse (S : String_Array) return Ruleset is
Line 403:
end Apply;
end Markov;</
test_markov.adb:
<
with Ada.Text_IO.Unbounded_IO;
with Ada.Strings.Unbounded;
Line 453:
end;
end;
end Test_Markov;</
Output (rulesX contains the ruleset of above examples and testX the example text):
Line 469:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
trim←{(~(∧\∨⌽∘(∧\)∘⌽)⍵∊⎕UCS 9 32)/⍵}
rules←(~rules∊⎕UCS 10 13)⊆rules←80 ¯1 ⎕MAP ⍺
Line 488:
}
rules apply ⍵
}</
{{out}}
<pre> 'f:\ruleset1.mkv' markov 'I bought a B of As from T S.'
Line 502:
=={{header|AutoHotkey}}==
<
; Markov Algorithm.ahk
; by wolf_II
Line 855:
;---------- end of file ----------------------------------------------------</
=={{header|BBC BASIC}}==
<
PRINT FNmarkov("ruleset2.txt", "I bought a B of As from T S.")
PRINT FNmarkov("ruleset3.txt", "I bought a B of As W my Bgage from T S.")
Line 892:
UNTIL EOF#rules% OR done%
CLOSE #rules%
= text$</
'''Output:'''
<pre>
Line 904:
=={{header|Bracmat}}==
Save the following text to a file "markov.bra":
<
markov=
{
Line 1,119:
& ok
| failure;
</syntaxhighlight>
Test:
Line 1,138:
=={{header|C}}==
<
#include <stdlib.h>
#include <string.h>
Line 1,340:
return 0;
}</
text: I bought a B of As from T S.
markoved: I bought a bag of apples from my brother.
Line 1,359:
text: 000000A000000
markoved: 00011H1111000
</syntaxhighlight>
=={{header|C++}}==
Note: Non-use of <code>iswhite</code> is intentional, since depending on the locale, other chars besides space and tab might be detected by that function.
<
#include <cstdlib>
#include <iostream>
Line 1,476:
std::cout << output << "\n";
}</
=={{header|CLU}}==
<
rule = struct[from, to: string, term: bool]
rep = array[rule]
Line 1,578:
when invalid(s: string): stream$putl(eo, "Parse error: " || s)
end
end start_up</
{{out}}
<pre>$ ./markov ruleset1.mkv "I bought a B of As from T S."
Line 1,597:
=={{header|Common Lisp}}==
I should mention that this uses the regular expression machinery present in Allegro Lisp but not Common Lisp generally (though there are public domain Lisp libraries).
<
(defclass markov ()
((rules :initarg :rules :initform nil :accessor rules)))
Line 1,664:
(setf ret (adjust rule-info ret))
(if (terminal (car rule-info)) (return ret))
(setf rule-info (get-rule markov ret)))))</
Testing:
<syntaxhighlight lang="text">(defparameter
*rules1*
"# This rules file is extracted from Wikipedia:
Line 1,693:
00011H1111000
NIL
</syntaxhighlight>
=={{header|Cowgol}}==
<
include "strings.coh";
include "malloc.coh";
Line 1,892:
print(ApplyRules(ReadFile(fname), &patbuf[0]));
print_nl();</
{{out}}
<pre>$ ./markov.386 ruleset1.mkv "I bought a B of As from T S."
Line 1,907:
=={{header|D}}==
{{trans|Perl}}
<
import std.stdio, std.file, std.regex, std.string, std.range,
std.functional;
Line 1,939:
writefln("%s\n%s\n", origTest, test);
}
}</
{{out}}
<pre>I bought a B of As from T S.
Line 1,958:
=={{header|Déjà Vu}}==
This implementation expect the initial text on the command line and the ruleset on STDIN.
<
]
for line in text:
Line 2,000:
not (markov-tick) rules
!. markov markov-parse get-from !args 1</
=={{header|EchoLisp}}==
<
;; rule := (pattern replacement [#t terminal])
Line 2,037:
(define (task i-string RS)
(markov i-string (parse-rules RS)))
</syntaxhighlight>
{{out}}
<pre>
Line 2,074:
=={{header|F_Sharp|F#}}==
<p>Using Partial Active Pattern to simplify pattern matching.</p>
<
open System.IO
open System.Text.RegularExpressions
Line 2,126:
|> run
|> printfn "%s"
0</
{{out}}
<pre>H:\RosettaCode\ExecMarkovAlgo>echo I bought a B of As from T S. | Fsharp\RosettaCode\bin\Debug\RosettaCode.exe m1
Line 2,144:
=={{header|Go}}==
<
import (
Line 2,319:
`00011H1111000`,
},
}</
{{out}}
<pre>
Line 2,327:
=={{header|Groovy}}==
<
def ruleMap = [:]
rules.eachLine { line ->
Line 2,351:
text
}]
}</
The test code is below (with the markov rulesets 2..5 elided):
<
[withInput: { text ->
[hasOutput: { expected ->
Line 2,385:
def ruleset5 = markovInterpreterFor("""...""")
verify ruleset5 withInput '000000A000000' hasOutput '00011H1111000'</
{{out}}
<pre>
Line 2,399:
This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.
<
import Data.Maybe (catMaybes)
import Control.Monad
Line 2,441:
then let new = reverse before ++ to ++ drop (length from) ahead
in if terminating then new else f rules new
else g (a : before) as</
=={{header|Icon}} and {{header|Unicon}}==
<
rules := loadRules(open(A[1],"r"))
every write(line := !&input, " -> ",apply(rules, line))
Line 2,466:
if (s == line) | \r.term then return s else line := s
}
end</
Sample runs using above rule sets and test strings:
Line 2,488:
=={{header|J}}==
'''Solution''':<
markovLexer =: verb define
Line 2,517:
end.
y
)</
'''Example''':<
# This rules file is extracted from Wikipedia:
# http://en.wikipedia.org/wiki/Markov_Algorithm
Line 2,532:
m1 markov 'I bought a B of As from T S.'
I bought a bag of apples from my brother.
</syntaxhighlight>
'''Discussion''': The J implementation correctly processes all the rulesets. More details are available on the [[Talk:Markov Algorithm#explicit_vs_tacit|the talk page]].
Line 2,538:
{{trans|D}}
{{works with|Java|7}}
<
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
Line 2,600:
return rules;
}
}</
Output:
Line 2,620:
=={{header|JavaScript}}==
<
* Take a ruleset and return a function which takes a string to which the rules
* should be applied.
Line 2,779:
console.log(markov(ruleset3)('I bought a B of As W my Bgage from T S.'));
console.log(markov(ruleset4)('_1111*11111_'));
console.log(markov(ruleset5)('000000A000000'));</
Output:
<pre>I bought a bag of apples from my brother.
Line 2,802:
'''Preliminaries'''
<
def deregex:
reduce ("\\\\", "\\*", "\\^", "\\?", "\\+", "\\.", "\\!", "\\{", "\\}", "\\[", "\\]", "\\$", "\\|",
Line 2,828:
def rules: $markov_rules | readRules;
def tests: readTests;</
<
"^ *(?<period>[.]?) *(?<rule>.*)" as $pattern
| reduce $rules[] as $rule ([];
Line 2,839:
end );
# applyRules applies $rules to . recursively,
# where $rules is the set of applicable rules in the form of an array-of-triples.
# Input and output: a string
def applyRules($rules):
# The inner function has arity-0 for efficiency
def apply:
| first(
| if $c[1] ==
then (apply | .
{stop: false, string: .} | apply
def proceed:
Line 2,866 ⟶ 2,865:
| tests as $tests
| range(0; $tests|length) as $ix
| $tests[$ix]
| " \(.)\n=>\(applyRules( parseRules( $rules[$ix] )
proceed</
{{out}}
Line 2,890 ⟶ 2,887:
=>00011H1111000
</pre>
=={{header|Julia}}==
Line 2,896 ⟶ 2,892:
'''Module''':
<
struct MarkovRule{F,T}
Line 2,943 ⟶ 2,939:
end
end # module MarkovAlgos</
'''Main''':
<
let rulesets = @.("data/markovrules0" * string(1:5) * ".txt"),
Line 2,956 ⟶ 2,952:
println("Transformed:\n", MarkovAlgos.apply(ruletest[i], rules))
end
end</
{{out}}
Line 2,996 ⟶ 2,992:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.io.File
Line 3,039 ⟶ 3,035:
println("$origTest\n$test\n")
}
}</
{{out}}
Line 3,060 ⟶ 3,056:
=={{header|Lua}}==
<
function normalize(str)
local result = str:gsub("(%p)", "%%%1")
Line 3,244 ⟶ 3,240:
do_markov(grammar3, text2, 'I bought a bag of apples with my money from T shop.')
do_markov(grammar4, text3, '11111111111111111111')
do_markov(grammar5, text4, '00011H1111000')</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Module[{terminating = False, output = text,
rules = StringCases[
Line 3,258 ⟶ 3,254:
output = StringReplace[output, rule[[1]] -> rule[[2]]];
If[! rule[[3]], terminating = False]; Break[]], {rule, rules}]];
output];</
Example:
<
#
# state A, symbol 0 => write 1, move right, new state B
Line 3,277 ⟶ 3,273:
# state C, symbol 1 => write 1, move left, halt
0C1 -> H01
1C1 -> H11", "000000A000000"]</
Output:
<pre>"00011H1111000"</pre>
=={{header|МК-61/52}}==
<syntaxhighlight lang="text"> 9 П4
КИП4 [x] П7 Вx {x} П8
ИП8 ИПE * П8 {x} x=0 08
Line 3,302 ⟶ 3,298:
ИП3 ИПE / [x] П3
x=0 22
ИП4 ИП0 - 9 - x=0 02 С/П</
Under the rules of left 4 registers, under the word has 8 character cells, the alphabet of the digits from 1 to 8. Rules are placed in "123,456", where "123" is a fragment, and "456" is to be replaced, in the registers of the РA to РD. The number of rules is stored in Р0, the initial word is in Р9. Number triggered rule is the last digit registration Р4 (0 to 3), if no rule did not work, the indicator 0, otherwise the current word to be processed. In РE is stored 10.
=={{header|Nim}}==
<
type Rule = object
Line 3,459 ⟶ 3,455:
for n, ruleset in RuleSets:
let rules = ruleset.parse()
echo SampleTexts[n].apply(rules)</
{{out}}
Line 3,472 ⟶ 3,468:
I'm not familiar with string processing, or parsing, so there are probably better ways to express this in OCaml. One might be with the mikmatch library which allows pattern-matching with regexps. Here I've only used the OCaml stdlib...
<
let try_finally x f g =
try let res = f x in g x; res
Line 3,519 ⟶ 3,515:
print_endline (run rules (input_line stdin));
translate ()
in try translate () with End_of_file -> ()</
With the above compiled to an executable 'markov', and the five rule-sets in files, strings are accepted on stdin for translation:
Line 3,542 ⟶ 3,538:
000000A000000
00011H1111000
</pre>
=={{header|Pascal}}==
{{works with|FPC}}
<syntaxhighlight lang="pascal">
program InterpretMA;
{$mode objfpc}{$h+}{$j-}{$b-}
uses
SysUtils;
type
TRule = record
Pattern, Replacement: string;
Terminating: Boolean;
end;
function ParseMA(const aScheme: string; out aRules: specialize TArray<TRule>): Boolean;
function ParseLine(const s: string; out r: TRule): Boolean;
var
Terms: TStringArray;
begin
Terms := s.Split([' -> ']);
if Length(Terms) <> 2 then exit(False);
r.Pattern := Terms[0].Trim;
r.Replacement := Terms[1].Trim;
r.Terminating := False;
if (r.Replacement <> '') and (r.Replacement[1] = '.') then begin
r.Terminating := True;
Delete(r.Replacement, 1, 1);
end;
Result := True;
end;
var
Lines: TStringArray;
s: string;
I: Integer;
begin
aRules := nil;
if aScheme = '' then exit(False);
Lines := aScheme.Split([LineEnding], TStringSplitOptions.ExcludeEmpty);
if Lines = nil then exit(False);
SetLength(aRules, Length(Lines));
I := 0;
for s in Lines do begin
if s[1] = '#' then continue;
if not ParseLine(s, aRules[I]) then exit(False);
Inc(I);
end;
SetLength(aRules, I);
Result := True;
end;
function ExecuteMA(const aScheme, aInput: string): string;
var
Rules: array of TRule;
r: TRule;
Applied: Boolean;
begin
if not ParseMA(aScheme.Replace(#9, ' ', [rfReplaceAll]), Rules) then
exit('Error while parsing MA scheme');
Result := aInput;
repeat
Applied := False;
for r in Rules do begin
if r.Pattern = '' then begin
Result := r.Replacement + Result;
Applied := True;
end else begin
Applied := Result.IndexOf(r.Pattern) >= 0;
if Applied then
Result := Result.Replace(r.Pattern, r.Replacement);
end;
if Applied then begin
if r.Terminating then exit;
break;
end;
end;
until not Applied;
end;
type
TTestEntry = record
Scheme, Input, Output: string;
end;
const
LE = LineEnding;
TestSet: array[1..5] of TTestEntry = (
(Scheme:
'# This rules file is extracted from Wikipedia: ' +LE+
'# http://en.wikipedia.org/wiki/Markov_Algorithm' +LE+
'A -> apple' +LE+
'B -> bag' +LE+
'S -> shop' +LE+
'T -> the' +LE+
'the shop -> my brother' +LE+
'a never used -> .terminating rule';
Input: 'I bought a B of As from T S.'; Output: 'I bought a bag of apples from my brother.'),
(Scheme:
'# Slightly modified from the rules on Wikipedia' +LE+
'A -> apple' +LE+
'B -> bag' +LE+
'S -> .shop' +LE+
'T -> the' +LE+
'the shop -> my brother' +LE+
'a never used -> .terminating rule';
Input: 'I bought a B of As from T S.'; Output: 'I bought a bag of apples from T shop.'),
(Scheme:
'# BNF Syntax testing rules' +LE+
'A -> apple' +LE+
'WWWW -> with' +LE+
'Bgage -> ->.*' +LE+
'B -> bag' +LE+
'->.* -> money' +LE+
'W -> WW' +LE+
'S -> .shop' +LE+
'T -> the' +LE+
'the shop -> my brother' +LE+
'a never used -> .terminating rule';
Input: 'I bought a B of As W my Bgage from T S.'; Output: 'I bought a bag of apples with my money from T shop.'),
(Scheme:
'### Unary Multiplication Engine, for testing Markov Algorithm implementations' +LE+
'### By Donal Fellows.' +LE+
'# Unary addition engine' +LE+
'_+1 -> _1+' +LE+
'1+1 -> 11+' +LE+
'# Pass for converting from the splitting of multiplication into ordinary' +LE+
'# addition' +LE+
'1! -> !1' +LE+
',! -> !+' +LE+
'_! -> _' +LE+
'# Unary multiplication by duplicating left side, right side times' +LE+
'1*1 -> x,@y' +LE+
'1x -> xX' +LE+
'X, -> 1,1' +LE+
'X1 -> 1X' +LE+
'_x -> _X' +LE+
',x -> ,X' +LE+
'y1 -> 1y' +LE+
'y_ -> _' +LE+
'# Next phase of applying' +LE+
'1@1 -> x,@y' +LE+
'1@_ -> @_' +LE+
',@_ -> !_' +LE+
'++ -> +' +LE+
'# Termination cleanup for addition' +LE+
'_1 -> 1' +LE+
'1+_ -> 1' +LE+
'_+_ -> ';
Input: '_1111*11111_'; Output: '11111111111111111111'),
(Scheme:
'# Turing machine: three-state busy beaver' +LE+
'#' +LE+
'# state A, symbol 0 => write 1, move right, new state B' +LE+
'A0 -> 1B' +LE+
'# state A, symbol 1 => write 1, move left, new state C' +LE+
'0A1 -> C01' +LE+
'1A1 -> C11' +LE+
'# state B, symbol 0 => write 1, move left, new state A' +LE+
'0B0 -> A01' +LE+
'1B0 -> A11' +LE+
'# state B, symbol 1 => write 1, move right, new state B' +LE+
'B1 -> 1B' +LE+
'# state C, symbol 0 => write 1, move left, new state B' +LE+
'0C0 -> B01' +LE+
'1C0 -> B11' +LE+
'# state C, symbol 1 => write 1, move left, halt' +LE+
'0C1 -> H01' +LE+
'1C1 -> H11';
Input: '000000A000000'; Output: '00011H1111000')
);
E_FMT = 'test #%d: expected "%s", but got "%s"';
var
e: TTestEntry;
Result: string;
I: Integer = 1;
Failed: Integer = 0;
begin
for e in TestSet do begin
Result := ExecuteMA(e.Scheme, e.Input);
if Result <> e.Output then begin
WriteLn(Format(E_FMT, [I, e.Output, Result]));
Inc(Failed);
end;
Inc(I);
end;
WriteLn('tests completed: ', Length(TestSet), ', failed: ', Failed);
end.
</syntaxhighlight>
{{out}}
<pre>
tests completed: 5, failed: 0
</pre>
Line 3,547 ⟶ 3,735:
This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.
<
open my $source, '<', $ARGV[0] or die "I couldn't open \"$ARGV[0]\" for reading. ($!.)\n";
my @rules;
Line 3,564 ⟶ 3,752:
and ($terminating ? last OUTER : redo OUTER);}}
print $input;</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">procedure</span> <span style="color: #000000;">markov</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">subs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">reps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
Line 3,693 ⟶ 3,881:
"""</span>
<span style="color: #000000;">markov</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ruleset5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"000000A000000"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"00011H1111000"</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 3,705 ⟶ 3,893:
=={{header|PHP}}==
<
function markov($text, $ruleset) {
Line 3,851 ⟶ 4,039:
foreach ($conf AS $id => $rule) {
echo 'Ruleset ', $id, ' : ', markov($rule['text'], $rule['rule']), PHP_EOL;
}</
{{out}}
Line 3,862 ⟶ 4,050:
=={{header|PicoLisp}}==
<
(use (@A @Z R)
(let Rules
Line 3,880 ⟶ 4,068:
(T (= "." (cadr (setq R @)))
(append @A (cddr R) @Z) )
(setq Text (append @A (cdr R) @Z)) ) ) ) ) )</
Output:
<pre>: (markov "r1" "I bought a B of As from T S.")
Line 3,901 ⟶ 4,089:
Module lambda can be found there : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl
<
:- use_module(library(lambda)).
Line 3,989 ⟶ 4,177:
replacement([X | R]) --> [X], {X \= '\n'}, replacement(R).
replacement([]) --> [].
</syntaxhighlight>
Code to test :
<
:- use_module(library(lambda)).
Line 4,108 ⟶ 4,296:
writeln(B),
writeln(R).
</syntaxhighlight>
Output :
<pre> ?- markov.
Line 4,136 ⟶ 4,324:
=={{header|PureBasic}}==
The GUI used here allows a ruleset to be loaded from a text file or manually added one rule at a time. Symbol input can be tested anytime by selecting 'Interpret'.
<
pattern.s
replacement.s
Line 4,249 ⟶ 4,437:
EndSelect
Until isDone
</syntaxhighlight>
Sample output from loading Ruleset 1 and interpreting a symbol:
<pre>Comment: "# This rules file is extracted from Wikipedia:"
Line 4,268 ⟶ 4,456:
The example gains flexibility by not being tied to specific files. The functions may be imported into other programs which then can provide textual input from their sources without the need to pass 'file handles' around.
<
def extractreplacements(grammar):
Line 4,401 ⟶ 4,589:
== '11111111111111111111'
assert replace(text4, extractreplacements(grammar5)) \
== '00011H1111000'</
=={{header|Racket}}==
Line 4,409 ⟶ 4,597:
The <tt>Markov-algorithm</tt> for a set of rules returns a function which maps from a string to string and can be used as a first-class object. Rules are represented by abstract data structures.
<
#lang racket
Line 4,438 ⟶ 4,626:
(let loop ([x x0] [fx (f x0)])
(if (equal? x fx) fx (loop fx (f fx)))))
</syntaxhighlight>
Example of use:
<
> (define MA
(Markov-algorithm
Line 4,454 ⟶ 4,642:
> (MA "I bought a B of As from T S.")
"I bought a bag of apples from T shop."
</syntaxhighlight>
===The source reader===
Line 4,460 ⟶ 4,648:
To read from a file just replace <tt>with-input-from-string</tt> ==> <tt>with-input-from-file</tt>.
<
;; the reader
(define (read-rules source)
Line 4,483 ⟶ 4,671:
(define (read-Markov-algorithm source)
(apply Markov-algorithm (read-rules source)))
</syntaxhighlight>
Examples:
<
(define R3 (read-Markov-algorithm "
# BNF Syntax testing rules
Line 4,552 ⟶ 4,740:
0C1 -> H01
1C1 -> H11"))
</syntaxhighlight>
<
> (R3 "I bought a B of As W my Bgage from T S.")
"I bought a bag of apples with my money from T shop."
Line 4,563 ⟶ 4,751:
> (R5 "000000A000000")
"00011H1111000"
</syntaxhighlight>
=={{header|Raku}}==
Line 4,573 ⟶ 4,761:
Add --verbose to see the replacements step-by-step.
<syntaxhighlight lang="raku"
token TOP {
^ [^^ [<rule> | <comment>] $$ [\n|$]]* $
Line 4,637 ⟶ 4,825:
say "starting with: $start_value";
say run(:$ruleset, :$start_value, :$verbose);
}</
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, <Arg 1>: e.File
, <Arg 2>: e.Input
, <ReadLines 1 e.File>: e.Lines
, <Each ParseRule e.Lines>: e.Rules
, <Apply (e.Rules) e.Input>: e.Result
= <Prout e.Result>;
};
Each {
s.F = ;
s.F (e.I) e.R = <Mu s.F e.I> <Each s.F e.R>;
};
ReadLines {
s.Chan e.File = <Open 'r' s.Chan e.File>
<ReadLines (s.Chan)>;
(s.Chan), <Get s.Chan>: {
0 = <Close s.Chan>;
e.Line = (e.Line) <ReadLines (s.Chan)>;
};
};
ParseRule {
= (Empty);
'#' e.X = (Empty);
e.Pat ' -> ' e.Rep,
<Trim e.Pat>: e.TrPat,
<Trim e.Rep>: e.TrRep,
e.TrRep: {
'.' e.R = (Term (e.Pat) (e.R));
e.R = (Nonterm (e.Pat) (e.R));
};
};
ApplyRule {
(s.Type (e.Pat) (e.Rep)) e.Subj,
e.Subj: e.X e.Pat e.Y = s.Type e.X e.Rep e.Y;
t.Rule e.Subj = NoMatch e.Subj;
};
Apply {
(e.Rules) () e.Subj = e.Subj;
(e.Rules) (t.Rule e.Rest) e.Subj,
<ApplyRule t.Rule e.Subj>: {
NoMatch e.Subj = <Apply (e.Rules) (e.Rest) e.Subj>;
Term e.Res = e.Res;
Nonterm e.Res = <Apply (e.Rules) e.Res>;
};
(e.Rules) e.Subj = <Apply (e.Rules) (e.Rules) e.Subj>;
};
Trim {
' ' e.X = <Trim e.X>;
e.X ' ' = <Trim e.X>;
e.X = e.X;
};</syntaxhighlight>
{{out}}
<pre>$ refgo markov ruleset1.mkv 'I bought a B of As from T S.'
I bought a bag of apples from my brother.
$ refgo markov ruleset2.mkv 'I bought a B of As from T S.'
I bought a bag of apples from T shop.
$ refgo markov ruleset3.mkv 'I bought a B of As W my Bgage from T S.'
I bought a bag of apples with my money from T shop.
$ refgo markov ruleset4.mkv '_111*11111_'
111111111111111
$ refgo markov ruleset5.mkv '000000A000000'
00011H1111000</pre>
=={{header|REXX}}==
Code was added to the REXX example to optionally list the contents of the ruleset and/or the Markov entries.
<br>Also, blank lines in the ruleset were treated as comments.
<
parse arg low high . /*allows which ruleset to process. */
if low=='' | low=="," then low=1 /*Not specified? Then use the default.*/
Line 4,683 ⟶ 4,941:
@.r=linein(rFID); if tellR then say 'ruleSet' ?"."left(r,4) '───►' @.r
end /*r*/ /* [↑] read and maybe echo the rule. */
return</
Some older REXXes don't have a '''changestr''' BIF, so one is included here ──► [[CHANGESTR.REX]].
<br><br>
Line 4,706 ⟶ 4,964:
=={{header|Ruby}}==
{{works with|Ruby|
<
ruleset.each_line.inject([]) do |rules, line|
if line =~ /^\s*#/
Line 4,719 ⟶ 4,977:
end
def
rules = setup(ruleset)
while (matched = rules.find { |match, replace, term|
Line 4,726 ⟶ 4,984:
end
input_data
end</
'''Test:'''
<
# This rules file is extracted from Wikipedia:
# http://en.wikipedia.org/wiki/Markov_Algorithm
Line 4,740 ⟶ 4,998:
EOS
puts
ruleset2 = <<EOS
Line 4,752 ⟶ 5,010:
EOS
puts
ruleset3 = <<EOS
Line 4,768 ⟶ 5,026:
EOS
puts
ruleset4 = <<EOS
Line 4,801 ⟶ 5,059:
EOS
puts
ruleset5 = <<EOS
Line 4,824 ⟶ 5,082:
EOS
puts
{{out}}
Line 4,834 ⟶ 5,092:
00011H1111000
</pre>
=={{header|Rust}}==
<
#[derive(Clone, Debug)]
Line 5,068 ⟶ 5,325:
}
}
</syntaxhighlight>
=={{header|Scala}}==
{{works with|Scala|2.8}}
<
object MarkovAlgorithm {
Line 5,101 ⟶ 5,358:
println(algorithm(args(1)))
}
}</
Script-style, and more concise:
<
if (argv.size != 2 ) error("Syntax: MarkovAlgorithm inputFile inputPattern")
Line 5,120 ⟶ 5,377:
println(argv(1))
println(algorithm(argv(1)))</
Sample outputs:
Line 5,148 ⟶ 5,405:
The following implementation uses several string-related procedures provided by SRFI-13 [http://srfi.schemers.org/srfi-13/srfi-13.html].
<
(define split-into-lines
(lambda (str)
Line 5,196 ⟶ 5,453:
rules))
(loop (cdr remaining) result)))))))
</syntaxhighlight>
=={{header|SequenceL}}==
<syntaxhighlight lang="sequencel">
import <Utilities/Sequence.sl>;
Line 5,249 ⟶ 5,506:
replaceSubString(str, original, new, n + 1);
</syntaxhighlight>
=={{header|SETL}}==
<syntaxhighlight lang="setl">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;</syntaxhighlight>
{{out}}
<pre>$ setl markov.setl ruleset1.mkv "I bought a B of As from T S."
I bought a bag of apples from my brother.
$ setl markov.setl ruleset2.mkv "I bought a B of As from T S."
I bought a bag of apples from T shop.
$ setl markov.setl ruleset3.mkv "I bought a B of As W my Bgage from T S."
I bought a bag of apples with my money from T shop.
$ setl markov.setl ruleset4.mkv "_1111*11111_"
11111111111111111111
$ setl markov.setl ruleset5.mkv "000000A000000"
00011H1111000</pre>
=={{header|SNOBOL4}}==
Note that the run-time data is immediately after the "end" label. This works with CSNOBOL4, on a Unix (or Unix-like) platform.
The Markov rules are actually compiled into the program after parsing, and are then directly executed (self-modifying code).
<syntaxhighlight lang="snobol4">
#!/bin/sh
exec "snobol4" "-r" "$0" "$@"
Line 5,383 ⟶ 5,715:
000000A000000
END
</syntaxhighlight>
=={{header|Swift}}==
{{trans|Ruby}}
<
func setup(ruleset: String) -> [(String, String, Bool)] {
Line 5,432 ⟶ 5,764:
}
</syntaxhighlight>
{{out}}
<pre>
Line 5,444 ⟶ 5,776:
=={{header|Tcl}}==
{{works with|Tcl|8.5}}
<
if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}
lassign $argv ruleFile inputFile outputFile
Line 5,484 ⟶ 5,816:
puts $out $line
}
close $out</
In the case where there are no terminating rules and no overlapping issues, the following is an alternative:
<
if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}
lassign $argv ruleFile inputFile outputFile
Line 5,513 ⟶ 5,845:
}
puts $out $data
close $out</
=={{header|VBScript}}==
====Implementation====
<syntaxhighlight lang="vb">
class markovparser
Line 5,591 ⟶ 5,923:
end function
end class
</syntaxhighlight>
=====Invocation=====
<syntaxhighlight lang="vb">
dim m1
set m1 = new markovparser
Line 5,655 ⟶ 5,987:
m5.ruleset = fso.opentextfile("busybeaver.tur").readall
wscript.echo m5.apply("000000A000000")
</syntaxhighlight>
=====Output=====
<syntaxhighlight lang="vb">
I bought a bag of apples from my brother.
I bought a bag of apples from T shop.
Line 5,664 ⟶ 5,996:
11111111111111111111
00011H1111000
</syntaxhighlight>
=={{header|Wren}}==
Line 5,670 ⟶ 6,002:
{{libheader|Wren-ioutil}}
{{libheader|wren-pattern}}
<
import "./pattern" for Pattern
var lb = FileUtil.lineBreak
Line 5,711 ⟶ 6,043:
System.print("%(origTest)\n%(test)\n")
ix = ix + 1
}</
{{out}}
Line 5,732 ⟶ 6,064:
=={{header|zkl}}==
<
if(vm.numArgs>1) lines=vm.arglist; // lines or object
ks:=L(); vs:=L();
Line 5,757 ⟶ 6,089:
}while(go);
text
}</
<
"# http://en.wikipedia.org/wiki/Markov_Algorithm",
"A\t->\tapple", "B -> bag", "S -> shop", "T -> the",
"the shop -> my brother", "a never used -> .terminating rule");
ruleSet.println();
markov("I bought a B of As from T S.",ruleSet).println();</
{{out}}
<pre>
Line 5,769 ⟶ 6,101:
I bought a bag of apples from my brother.
</pre>
<
T("# Slightly modified from the rules on Wikipedia",
"A -> apple", "B -> bag", "S -> .shop", "T -> the",
Line 5,779 ⟶ 6,111:
"W -> WW", "S -> .shop", "T -> the",
"the shop -> my brother", "a never used -> .terminating rule") :
markov("I bought a B of As W my Bgage from T S.",_).println();</
{{out}}
<pre>
Line 5,786 ⟶ 6,118:
</pre>
For the next two tasks, read the rule set from a file.
<
parseRuleSet(File("ruleSet5")) : markov("000000A000000",_).println();</
{{out}}
<pre>
|