Thue (programming language)
Encyclopedia
Thue is an esoteric programming 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
. Because it is able to define languages of such complexity, it is also Turing-complete
itself. Thue is based on a nondeterministic
string rewriting system called semi-Thue grammar, which itself is named after (and possibly created by) the Norwegian
mathematician
Axel Thue
; inspiration is also taken from the grue
. 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
are to the imperative paradigm; in other words, it's a tar pit
."
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.
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.
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
::=
_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
Esoteric programming language
An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...
invented by John Colagioia
John Colagioia
John Colagioia is a software engineer in Long Island, New York. He received his Masters of Science Degree in Computer Science from Polytechnic University in 1996, and is an adjunct professor of Computer Science...
in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy
Chomsky hierarchy
Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
. Because it is able to define languages of such complexity, it is also Turing-complete
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
itself. Thue is based on a nondeterministic
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...
string rewriting system called semi-Thue grammar, which itself is named after (and possibly created by) the Norwegian
Norway
Norway , officially the Kingdom of Norway, is a Nordic unitary constitutional monarchy whose territory comprises the western portion of the Scandinavian Peninsula, Jan Mayen, and the Arctic archipelago of Svalbard and Bouvet Island. Norway has a total area of and a population of about 4.9 million...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Axel Thue
Axel Thue
Axel Thue was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics....
; inspiration is also taken from the grue
Grue (monster)
A grue is a fictional predator that dwells in the dark. The word was first used in modern times as a fictional predator in Jack Vance's Dying Earthuniverse ....
. The author describes it as follows: "Thue represents one of the simplest possible ways to construe constraint-based programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
. It is to the constraint-based paradigm what languages like OISC
One instruction set computer
A one instruction set computer , sometimes called an ultimate reduced instruction set computer , is an abstract machine that uses only one instruction – obviating the need for a machine language opcode...
are to the imperative paradigm; in other words, it's a tar pit
Turing tarpit
A Turing tarpit is any programming language or computer interface that allows for a great deal of flexibility in function but is difficult to learn and use because it offers little or no support for common tasks...
."
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.
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's 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
::=
_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