Here is a recursive tacit solution, again sans parsing.
x=. @[
y=. @]
pat=. 0&{::x
sub=. 1&{::x
term=.2&{::x
string=. 0&{::y
trash=. 1&{::y
EMPTY=. 0 3$a:
empty=. EMPTY"_
patin=. {.x (pat (1:e.E.) ]) string
firstmatch=. [:{.[:I. pat E.]
rplcfirst=. (]}.~firstmatc...@pat) ,~ sub ,~ firstmatch {. ]
patsub=. {.x ((pat;sub) rplcfirst ]) string
patterm=. {.x term ]
markov=. string`(((}.x)$:(string ; [:<trash,{.x)) `
((((trash,[)$:(patsub;empty)) ` patsub ) @. patterm ) @. patin ) @.
(*...@#x)
NB. RULES markov STRING;EMPTY
So others don't have to do the typing as well:
NB. RULE=. PAT;SUB;TERMINAL
RULES1=. do;._2 ] 0 : 0
'A';'apple';0
'B';'bag';0
'S';'shop';0
'T';'the';0
'the shop';'my brother';0
'a never used';'terminating rule';1
)
RULES2=. do;._2 ] 0 : 0
'A';'apple';0
'B';'bag';0
'S';'shop';1
'T';'the';0
'the shop';'my brother';0
'a never used';'terminating rule';1
)
RULES3=. do;._2 ] 0 : 0
'A';'apple';0
'WWWW';'with';0
'Bgage';'->.*';0
'B';'bag';0
'->.*';'money';0
'W';'WW';0
'S';'shop';1
'T';'the';0
'the shop';'my brother';0
'a never used';'terminating rule';1
)
RULES4=. do;._2 ] 0 : 0
'_+1' ; '_1+' ; 0
'1+1' ; '11+' ; 0
'1!' ; '!1' ; 0
',!' ; '!+' ; 0
'_!' ; '_' ; 0
'1*1' ; 'x,@y' ; 0
'1x' ; 'xX' ; 0
'X,' ; '1,1' ; 0
'X1' ; '1X' ; 0
'_x' ; '_X' ; 0
',x' ; ',X' ; 0
'y1' ; '1y' ; 0
'y_' ; '_' ; 0
'1...@1' ; 'x,@y' ; 0
'1...@_' ; '@_' ; 0
',@_' ; '!_' ; 0
'++' ; '+' ; 0
'_1' ; '1' ; 0
'1+_' ; '1' ; 0
'_+_' ; '' ; 0
)
RULES1 markov 'I bought a B of As from T S.';EMPTY
I bought a bag of apples from my brother.
RULES2 markov 'I bought a B of As from T S.';EMPTY
I bought a bag of apples from T shop.
RULES3 markov 'I bought a B of As W my Bgage from T S.';EMPTY
I bought a bag of apples with my money from T shop.
RULES4 markov '_1111*11111_';EMPTY
11111111111111111111
On Wed, Dec 16, 2009 at 8:45 PM, Viktor Cerovski
<[email protected]> wrote:
>
>
> Andrew Nikitin wrote:
>>
>>
>>> For those who want to train their tacit muscles, here's a challenge.
>>
>>> A Markov algorithm is a specialized term rewriter. It accepts ...
>>
>>
>>
>> I am not sure the problem can be handled by tacit expressions better than
>> with explicit expressions.
>>
>> Tacit way to implement 'while' is body^:predicate^:_
>>
>> In J as it is there is no information flow between body and predicate, but
>> for this problem there is a significant sharing of information. predicate
>> is true when a non-terminal rule was applied and body is the application
>> of this rule.
>>
>>
>>
>> Also, I belive, if you are demanding "tacit" solution, you should also use
>> only tacitly defined utilities. stringreplace (which seems to be the
>> cornerstone of the algorithm) is not.
>>
>>
>>
>> Anyway, here is my submission (sans parsing)
>>
>>
>>
>> NB. This rules file is extracted from Wikipedia:
>> NB. http://en.wikipedia.org/wiki/Markov_Algorithm
>> R1=:i.0 3
>> R1=:R1,'A';'apple';0
>> R1=:R1,'B';'bag';0
>> R1=:R1,'S';'shop';0
>> R1=:R1,'T';'the';0
>> R1=:R1,'the shop';'my brother';0
>> R1=:R1,'a never used';'terminating rule';1
>>
>> T1=:'I bought a B of As from T S.'
>>
>>
>>
>> mapply=: 4 : 0
>> ri=.0
>> while. ri<#x do.
>> z=.y E.~ p=.>{.r=.ri{x
>> ri=.1+ri
>> if. +./z do.
>> y=.((> 1 { r) , (#p) }. ])&.((z i. 1)&|.) y
>> ri=._*>{:r
>> end.
>> end.
>> y
>> )
>>
>> [...]
>>
>
> Slightly shorter/faster/neater:
>
> mapply1=: 4 : 0
> t=.ri=.0
> while. (-.t) *. ri<#x do.
> 'p s t'=.ri{x
> y=.(s , (#p) }. ])&.((z i. 1)&|.)^:(f=.+./z=.p E. y) y
> ri=.(-.f)*ri+1
> end.
> y
> )
>
> --
> View this message in context:
> http://old.nabble.com/Tacit-exercise-tp26818596s24193p26821788.html
> Sent from the J Programming mailing list archive at Nabble.com.
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
