Marthue

Marthue is a generalization of both semi-Thue systems and Markov algorithms, posted by Yoel Matveyev on Github in June 2020. The language includes basic input/output, forward, backward and random search for string replacement, conditional jumps, function calls and returns between the Thue or Markov blocks. It's implemented in Common Lisp; Marthue programs can be saved either as files in a specific format or written as Lisp arrays. The Lisp package also supports loading Thue language files and generic Markov algorithms.
Here is an example for a Marthue program, which asks for a binary number, decrements it by a Thue algorithm, and prints the result by a modified Markov algorithm:
 ON::->Input a binary number:
 ::
 IN::->
 ::
 N::->_
 B::
 N::->_
 T::
 0_->0--
 1_->0
 10--->01
 00--->0--1
 _1--->@
 _0--->1
 _0->
 ::
 _1->_*1
 _0->_*0
 O::*1->1
 O::*0->0
 _->
The same in the internal Lisp format:
 #(
 ((:M) #(("" "Input a binary number:" :O :N)))
 ((:M) #(("" "" :I :N)))
 ((:M) #(("" "_" :N)))
 ((:M :B) #(("" "_" :N)))
 ((:T) #(("0_" "0--") ("1_" "0") ("10--" "01") ("00--" "0--1") ("_1--" "@")("_0--" "1") ("_0" "")))
 ((:M) #(("_1" "_*1")("_0" "_*0")("*1" "1" :O) ("*0" "0" :O)("_" ""))))
All strings in Marthue programs that don't contain "::" or "->" are treated as comments. Additionally, comments may be added after "::" in block description lines.
The "::" indicates either a block description or, when followed by "->", a rule description with additional functionality. In both cases, the substring before "::" is treated as an opcode, optionally followed by a label. The opcode is a string made of same letters denoting the following:
*T for Thue vs. Markov
*M for Markov vs. Thue (unnecessary, useful only for readability, as the blocks are Markov algorithms by default)
*F - forward search by default
*B - backward search by default
*X - random search (also denoted by F and B)
*I for input
*O for output (When I and O are combined, the replacement string is printed and the left-side original string is replaced by the input)
*N for terminating the computation of the current block and going to the next block. If combined with a label, it means a jump without storing the previous block in the stack.
*R for returning from a function call. When used with a label, if attempts to return to the corresponding block, somewhat similar to Lisp's special operator return-from.
*C or whatever, just for the sake on convenience and readability, may denote a function call, although the presence of the label itself is sufficient and is interpreted by default as a function call.
The combination of R and T is reserved for possible future extensions and is currently interpreted as R.
The internal Lisp format uses the same letters as keys (e.g. (:T :X)).
Block termination may also be denoted as [original_string]->.[new_string], like in standard Markov algorithms. To use "->.", "::", "->" inside the rules, use backslashes. "\n" denotes a newline inside the rule.
Trying to jump to an non-existent label or trying to return to a label that is not in the stack causes the entire program to stop.
This program takes series of stars as input, converts them into Roman numerals by a Markov algorithm, prints the result and asks, whether to try another star sequence or not:
 ;; Convert series of stars to Roman numerals
 a::
 OC b::->Input series of stars like this: *** **** *****\n
 b::
 I::->._
 ;; Conversion algorithm
 ::
 *->I
 IIIII->V
 IIII->IV
 VV->X
 VIV->IX
 XXXXX->L
 XXXX->XL
 LL->C
 LXL->XC
 CCCCC->D
 CCCC->CD
 DD->M
 DCD->CM
 ->._
 ;; Printing the result
 ::
 _M->_*M
 _D->_*D
 _C->_*C
 _L->_*L
 _X->_*X
 _V->_*V
 _I->_*I
 _ ->_*
 O::*M->M
 O::*D->D
 O::*C->C
 O::*L->L
 O::*X->X
 O::*V->V
 O::*I->I
 ;; There should be a space on the right side below
 O::*-> 
 ::
 N::_->
 ::
 O::_->\nTry again? (y/n)
 ->._
 ::
 I::_->
 R a::y->
 R end::n->
==See also==
* Thue
==External resources==
* Yoel Matveyev's implementation of Marthue
* "Markov algorithm" on en.Wikipedia
Category:Languages
Category:String-rewriting paradigm
Category:Nondeterministic
Category:Turing complete
Category:Turing tarpits
Category:Implemented
Category:Low-level
Category:2020