Thue ( ) is an
esoteric programming language
An esoteric programming language (sometimes shortened to esolang) is a programming language designed to test the boundaries of computer programming language design, as a proof of concept, as software art, as a hacking interface to another language ...
invented by John Colagioia in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the
Chomsky hierarchy
In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
This hierarchy of grammars was described by ...
. Because it is able to define languages of such complexity, it is also
Turing-complete
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tur ...
itself. Thue is based on a
nondeterministic string rewriting system
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ov ...
called
semi-Thue grammar
In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi- Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation R between fixed strings ...
, which itself is named after the
Norwegian
Norwegian, Norwayan, or Norsk may refer to:
*Something of, from, or related to Norway, a country in northwestern Europe
* Norwegians, both a nation and an ethnic group native to Norway
* Demographics of Norway
*The Norwegian language, including ...
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Axel Thue
Axel Thue (; 19 February 1863 – 7 March 1922) was a Norwegian mathematician, known for his original work in diophantine approximation and combinatorics.
Work
Thue published his first important paper in 1909.
He stated in 1914 the so-calle ...
. The author describes it as follows: "Thue represents one of the simplest possible ways to construe
constraint-based programming. It is to the constraint-based paradigm what languages like
OISC
Oisc (also Æsc or Esc, pronounced “oish” or “ash”) was an early king of Kent who — according to the Anglo-Saxon Chronicle — ruled from 488-512CE. He seems to be the same person as Ansehis (or Anschis) who is described as a leader o ...
are to the imperative paradigm; in other words, it's a
tar pit
Tar pits, sometimes referred to as asphalt pits, are large asphalt deposits. They form in the presence of oil, which is created when decayed organic matter is subjected to pressure underground. If this crude oil seeps upward via fractures, co ...
."
Production rules
A Thue program starts with a rulebase, which is a series of substitution rules, each of this form:
''lhs'' ::= ''rhs''
The rulebase terminates with a lone production symbol on a line:
::=
The initial state is a series of symbols which follow the rulebase.
Thue consumes the initial symbols and substitutes the result of the rules for each of the initial state's symbols.
Thue terminates when lhs cannot be found in a resultant state.
Notes
*''::='' is pronounced ''can be''.
*''lhs'' is "left hand side".
*''rhs'' is "right hand side".
*"''::=''" can never be the lhs.
*":::" is an input stream.
*"~" is the output stream.
* Semi-Thue systems are isomorphic to
unrestricted grammar In automata theory, the class of unrestricted grammars (also called semi-Thue, type-0 or phrase structure grammars) is the most general class of grammars in the Chomsky hierarchy. No restrictions are made on the productions of an unrestricted gramma ...
s.
Calling Thue
When invoked with 'd' (debug), print the state.
When invoked with 'l' (left side), apply the rules left-to-right.
When invoked with 'r' (right side),
apply the rules right-to-left.
The last 'l' or 'r' overrides the previous switches.
Sample programs
Here is the traditional "Hello World!" in Thue:
a::=~Hello World!
::=
a
The following Thue program performs an increment of a binary number entered as the initial state surrounded by "_" characters, in this case the number 1111111111:
1_::=1++
0_::=1
01++::=10
11++::=1++0
_0::=_
_1++::=10
__::=1
::=
_1111111111_
The following sample program is to demonstrate Thue's nondeterminism (and to show an example of an infinite loop, besides). The program outputs bits in an undefined (and quite possibly random) sequence.
b::=~0
b::=~1
ac::=abc
::=
abc
See also
*
Markov algorithm
In theoretical computer science, a 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 gener ...
External links
The Thue Programming LanguageThue at the Esolang wikiBlog post on Thue
Esoteric programming languages
Programming languages created in 2000
{{compu-lang-stub