PROLAN/M
PROLAN/M is the language described in one of the problems of the 2nd International Olympiad in Infomatics in 1990. Its programs are essentially sequential substitution systems, a string-rewriting paradigm.
The language is much like Thue. The code consists of a list of substitution rules of the form
(<original string>,<replacement string>)
which is terminated with
(,)
PROLAN/M programs are run as follows. First, the input string is retrieved, perhaps from the user or another program. Second, each of the substitution rules is tried from top to bottom until one matches, in which case the substitution is made, or all rules are exhausted. This second step is repeated as long as at least one rule matches. When no more rules match, the string in its final form is printed out, and the program terminates.
Only one substitution is made at a time. That is, if the substitution
(e,o)
is run on the string "beet pies", the result is "boet pies", not "boot pios".
Note that PROLAN/M has no input or output instructions. Instead, it simply operates on a single string, which at the beginning of the program is input, and at the end of the program is output.
Computational class
Because PROLAN/M is almost equivalent to Thue, we can show that it is Turing-complete.
External resources
Note that the example in the problem description below has a typo. The string would be rewritten from "aad" to "bd", not "aad" to "db", but the output of the example program is still "finish".
- 2nd International Olympiad in Informatics Problems
- A solution to the sum problem
- Interpreter in Javascript (from the Wayback Machine; retrieved on 17 May 2006)
- Interpreter in C
- Sequential substitution systems at Mathworld.