MarkovAlgorithm
// This source code is subject to the terms of the Mozilla Public License 2.0 at https://mozilla.org/MPL/2.0/
// © RicardoSantos

//@version=5

// @description Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of 
// 		symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a 
// 		general model of computation and can represent any mathematical expression from its simple notation. 
//		~ wikipedia
// .
// reference:
//		https://en.wikipedia.org/wiki/Markov_algorithm
//		https://rosettacode.org/wiki/Execute_a_Markov_algorithm#Nim
library(title = 'MarkovAlgorithm')

import RicardoSantos/DebugConsole/13 as console
console.Console logger = console.new()
logger.table.set_position(position.bottom_right)
logger.table.cell_set_width(0, 0, 95)

// rule {

// @type String pair that represents `pattern -> replace`, each rule may be ordinary or terminating.
// @field pattern     Pattern to replace.
// @field replacement Replacement patterns.
// @field termination Termination rule.
export type rule
	string pattern
	string replacement
	bool termination = false

// }
// parse () {

// @function Parse the rules provided, the rules should formatted in a `pattern -> replace` way and separated by a new line or provided separator.
// @param rules		`string`: Expression containing the rules.
// @param separator	`string`: Separator, default=`newline`.
// @returns
// - `array<rule> _rules`: List of rules.
// ---
// Usage:
// - `parse("|0 -> 0||\n1 -> 0|\n0 -> ")`
export parse (string rules, string separator='\n') =>
	array<string> _lines = str.split(rules, separator)
	array<rule> _rules = array.new<rule>(0)
	for _line in _lines
		if str.startswith(_line, '#')
			continue
		if str.replace_all(_line, ' ', '') == ''
			continue
		array<string> _t = str.split(_line, ' -> ')
		if array.size(_t) > 1
			rule _rule = rule.new(array.get(_t, 0), array.get(_t, 1))
			if str.startswith(_rule.replacement, '.')
				_rule.termination := true
				_rule.replacement := str.replace(_rule.replacement, '.', '', 0)
			array.push(_rules, _rule)
	_rules

// }
// apply () {

// @function Aplies rules to a expression.
// @param expression	`string`	 : Text expression to be formated by the rules.
// @param rules			`array<rule>`: Rules to apply to expression.
// @returns
// - `string _result`: Formated expression.
// ---
// Usage:
// - `apply("101", parse("|0 -> 0||\n1 -> 0|\n0 -> "))`
export apply (string expression, array<rule> rules) =>
	string _result = expression
	bool _changed = true
	while _changed
		_changed := false
		for _rule in rules
			if str.contains(_result, _rule.pattern)
				_result := str.replace_all(_result, _rule.pattern, _rule.replacement)
				if _rule.termination
					break
				_changed := true
				break
	_result

// @function Aplies rules to a expression.
// @param expression	`string`: Text expression to be formated by the rules.
// @param rules			`string`: Rules to apply to expression on a string format to be parsed.
// @returns
// - `string _result`: Formated expression.
// ---
// Usage:
// - `apply("101", parse("|0 -> 0||\n1 -> 0|\n0 -> "))`
export apply (string expression, string rules) =>
	apply(expression, parse(rules))

// }



//#region	-> Preview:

string ruleset1 = str.format('{0}\n{1}\n{2}\n{3}\n{4}\n{5}\n{6}\n{7}\n', 
 '# 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')

string ruleset2 = str.format('{0}\n{1}\n{2}\n{3}\n{4}\n{5}\n{6}\n', 
 '# Slightly modified from the rules on Wikipedia',
 'A -> apple',
 'B -> bag',
 'S -> .shop',
 'T -> the',
 'the shop -> my brother',
 'a never used -> .terminating rule')

string ruleset3 = '' +
 '# BNF Syntax testing rules' + '\n' +
 'A -> apple'                 + '\n' +
 'WWWW -> with'               + '\n' +
 'Bgage -> ->.*'              + '\n' +
 'B -> bag'                   + '\n' +
 '->.* -> money'              + '\n' +
 'W -> WW'                    + '\n' +
 'S -> .shop'                 + '\n' +
 'T -> the'                   + '\n' +
 'the shop -> my brother'     + '\n' +
 'a never used -> .terminating rule'

string ruleset4 = '' +
 '### Unary Multiplication Engine, for testing Markov Algorithm implementations' + '\n' +
 '### By Donal Fellows.'                                                         + '\n' +
 '# Unary addition engine'                                                       + '\n' +
 '_+1 -> _1+'                                                                    + '\n' +
 '1+1 -> 11+'                                                                    + '\n' +
 '# Pass for converting from the splitting of multiplication into ordinary'      + '\n' +
 '# addition'                                                                    + '\n' +
 '1! -> !1'                                                                      + '\n' +
 ',! -> !+'                                                                      + '\n' +
 '_! -> _'                                                                       + '\n' +
 '# Unary multiplication by duplicating left side, right side times'             + '\n' +
 '1*1 -> x,@y'                                                                   + '\n' +
 '1x -> xX'                                                                      + '\n' +
 'X, -> 1,1'                                                                     + '\n' +
 'X1 -> 1X'                                                                      + '\n' +
 '_x -> _X'                                                                      + '\n' +
 ',x -> ,X'                                                                      + '\n' +
 'y1 -> 1y'                                                                      + '\n' +
 'y_ -> _'                                                                       + '\n' +
 '# Next phase of applying'                                                      + '\n' +
 '1@1 -> x,@y'                                                                   + '\n' +
 '1@_ -> @_'                                                                     + '\n' +
 ',@_ -> !_'                                                                     + '\n' +
 '++ -> +'                                                                       + '\n' +
 '# Termination cleanup for addition'                                            + '\n' +
 '_1 -> 1'                                                                       + '\n' +
 '1+_ -> 1'                                                                      + '\n' +
 '_+_ -> '

string ruleset5 = '' +
 '# Turing machine: three-state busy beaver'               + '\n' +
 '#'                                                       + '\n' +
 '# state A, symbol 0 => write 1, move right, new state B' + '\n' +
 'A0 -> 1B'                                                + '\n' +
 '# state A, symbol 1 => write 1, move left, new state C'  + '\n' +
 '0A1 -> C01'                                              + '\n' +
 '1A1 -> C11'                                              + '\n' +
 '# state B, symbol 0 => write 1, move left, new state A'  + '\n' +
 '0B0 -> A01'                                              + '\n' +
 '1B0 -> A11'                                              + '\n' +
 '# state B, symbol 1 => write 1, move right, new state B' + '\n' +
 'B1 -> 1B'                                                + '\n' +
 '# state C, symbol 0 => write 1, move left, new state B'  + '\n' +
 '0C0 -> B01'                                              + '\n' +
 '1C0 -> B11'                                              + '\n' +
 '# state C, symbol 1 => write 1, move left, halt'         + '\n' +
 '0C1 -> H01'                                              + '\n' +
 '1C1 -> H11'

string phrase1 = 'I bought a B of As from T S.'
string phrase2 = 'I bought a B of As from T S.'
string phrase3 = 'I bought a B of As W my Bgage from T S.'
string phrase4 = '_1111*11111_'
string phrase5 = '000000A000000'

test_set = input.int(1, options=[1, 2, 3, 4, 5])
if barstate.islast
	switch test_set
		1 => logger.queue_one(apply(phrase1, parse(ruleset1)))
		2 => logger.queue_one(apply(phrase2, parse(ruleset2)))
		3 => logger.queue_one(apply(phrase3, parse(ruleset3)))
		4 => logger.queue_one(apply(phrase4, parse(ruleset4)))
		5 => logger.queue_one(apply(phrase5, parse(ruleset5)))
		
logger.update()

//#endregion