Thue (programming language)
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
Thue (// TOO-ay) 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 the Norwegian mathematician Axel Thue. 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."
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.
- ::= 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 grammars.
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.
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
- The Thue Programming Language
- Thue at the Esolang wiki
- Blog post on Thue