Execute a Markov algorithm: Difference between revisions
Content added Content deleted
(Added F# version) |
|||
Line 2,535: | Line 2,535: | ||
say run(:$ruleset, :$start_value, :$verbose).perl; |
say run(:$ruleset, :$start_value, :$verbose).perl; |
||
}</lang> |
}</lang> |
||
=={{header|Phix}}== |
|||
<lang Phix>procedure markov(string rules, input, expected) |
|||
sequence subs = {}, reps = {} |
|||
sequence lines = split(substitute(rules,"\t"," "),'\n') |
|||
for i=1 to length(lines) do |
|||
string li = lines[i] |
|||
if length(li) and li[1]!='#' then |
|||
integer k = match(" -> ",li) |
|||
if k then |
|||
subs = append(subs,trim(li[1..k-1])) |
|||
reps = append(reps,trim(li[k+4..$])) |
|||
end if |
|||
end if |
|||
end for |
|||
string res = input |
|||
bool term = false |
|||
while 1 do |
|||
bool found = false |
|||
for i=1 to length(subs) do |
|||
string sub = subs[i] |
|||
integer k = match(sub,res) |
|||
if k then |
|||
found = true |
|||
string rep = reps[i] |
|||
if length(rep) and rep[1]='.' then |
|||
rep = rep[2..$] |
|||
term = true |
|||
end if |
|||
res[k..k+length(sub)-1] = rep |
|||
exit |
|||
end if |
|||
if term then exit end if |
|||
end for |
|||
if term or not found then exit end if |
|||
end while |
|||
?{input,res,iff(res=expected?"ok":"**ERROR**")} |
|||
end procedure |
|||
constant ruleset1 = """ |
|||
# This rules file is extracted from Wikipedia: |
|||
# http://en.wikipedia.org/wiki/Markov_Algorithm |
|||
A -> apple |
|||
B -> bag |
|||
S -> shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""" |
|||
markov(ruleset1,"I bought a B of As from T S.","I bought a bag of apples from my brother.") |
|||
constant ruleset2 = """ |
|||
# Slightly modified from the rules on Wikipedia |
|||
A -> apple |
|||
B -> bag |
|||
S -> .shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""" |
|||
markov(ruleset2,"I bought a B of As from T S.","I bought a bag of apples from T shop.") |
|||
constant ruleset3 = """ |
|||
# BNF Syntax testing rules |
|||
A -> apple |
|||
WWWW -> with |
|||
Bgage -> ->.* |
|||
B -> bag |
|||
->.* -> money |
|||
W -> WW |
|||
S -> .shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""" |
|||
markov(ruleset3,"I bought a B of As W my Bgage from T S.","I bought a bag of apples with my money from T shop.") |
|||
constant ruleset4 = """ |
|||
### Unary Multiplication Engine, for testing Markov Algorithm implementations |
|||
### By Donal Fellows. |
|||
# Unary addition engine |
|||
_+1 -> _1+ |
|||
1+1 -> 11+ |
|||
# Pass for converting from the splitting of multiplication into ordinary |
|||
# addition |
|||
1! -> !1 |
|||
,! -> !+ |
|||
_! -> _ |
|||
# Unary multiplication by duplicating left side, right side times |
|||
1*1 -> x,@y |
|||
1x -> xX |
|||
X, -> 1,1 |
|||
X1 -> 1X |
|||
_x -> _X |
|||
,x -> ,X |
|||
y1 -> 1y |
|||
y_ -> _ |
|||
# Next phase of applying |
|||
1@1 -> x,@y |
|||
1@_ -> @_ |
|||
,@_ -> !_ |
|||
++ -> + |
|||
# Termination cleanup for addition |
|||
_1 -> 1 |
|||
1+_ -> 1 |
|||
_+_ -> |
|||
""" |
|||
markov(ruleset4,"_1111*11111_","11111111111111111111") |
|||
constant ruleset5 = """ |
|||
# Turing machine: three-state busy beaver |
|||
# |
|||
# state A, symbol 0 => write 1, move right, new state B |
|||
A0 -> 1B |
|||
# state A, symbol 1 => write 1, move left, new state C |
|||
0A1 -> C01 |
|||
1A1 -> C11 |
|||
# state B, symbol 0 => write 1, move left, new state A |
|||
0B0 -> A01 |
|||
1B0 -> A11 |
|||
# state B, symbol 1 => write 1, move right, new state B |
|||
B1 -> 1B |
|||
# state C, symbol 0 => write 1, move left, new state B |
|||
0C0 -> B01 |
|||
1C0 -> B11 |
|||
# state C, symbol 1 => write 1, move left, halt |
|||
0C1 -> H01 |
|||
1C1 -> H11 |
|||
""" |
|||
markov(ruleset5,"000000A000000","00011H1111000")</lang> |
|||
{{out}} |
|||
<pre> |
|||
{"I bought a B of As from T S.","I bought a bag of apples from my brother.","ok"} |
|||
{"I bought a B of As from T S.","I bought a bag of apples from T shop.","ok"} |
|||
{"I bought a B of As W my Bgage from T S.","I bought a bag of apples with my money from T shop.","ok"} |
|||
{"_1111*11111_","11111111111111111111","ok"} |
|||
{"000000A000000","00011H1111000","ok"} |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Line 2,571: | Line 2,706: | ||
: (markov "r5" "000000A000000") |
: (markov "r5" "000000A000000") |
||
-> "00011H1111000"</pre> |
-> "00011H1111000"</pre> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Works with SWI-Prolog and module(library(lambda)).<br> |
Works with SWI-Prolog and module(library(lambda)).<br> |