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
External resources
- [https://github.com/yoelmatveyev/marthue Yoel Matveyev's implementation of Marthue
- "Thue (programming language)" on en.Wikipedia
- "Markov algorithm" on en.Wikipedia