Thue (programming language)
- Thue (programming language)
Thue (pronEng|ˈtuːeɪ "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 (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."
Production Rules
A Thue program starts with substitution rules of the form:lhs ::= rhs
Successive rules can be added. 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 grammars.
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.
ample 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
External links
* [http://catseye.tc/projects/thue/ The Thue Programming Language]
* [http://catseye.tc/projects/thue/doc/thue.txt Thue FAQ]
* [http://esoteric.voxelperfect.net/wiki/Thue Thue at the Esolang wiki]
* [http://scienceblogs.com/goodmath/2006/08/friday_pathological_programmin_2.php Blog post on Thue]
Wikimedia Foundation.
2010.
Look at other dictionaries:
Esoteric programming language — An esoteric programming language (sometimes shortened to esolang) 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. There is usually no intention of the… … Wikipedia
Thue (langage) — Thue est un langage de programmation exotique inventé par John Colagioia au début des années 2000. Il s agit d un méta langage permettant la définition et la reconnaissance de langages de type 0 dans la hiérarchie de Chomsky. Thue est basé sur… … Wikipédia en Français
Axel Thue — Infobox Scientist name = Axel Thue image width = 250px caption = Axel Thue (1863 1922) birth date = birth date|1863|2|19|df=y birth place = Tönsberg, Norway residence = nationality = death date = death date and age|1922|3|7|1863|2|19|df=y death… … Wikipedia
L-system — An L system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar (a set of rules and symbols), most famously used to model the growth processes of plant development, but also able to model the morphology of a … Wikipedia
Formal grammar — In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language ndash; that is, of a set of strings over some alphabet. In other words, a grammar describes which… … Wikipedia
Turing tarpit — Turing tar pit is a general term for a programming language designed to be Turing complete while in some sense simplifying to the greatest extent possible both the syntax and the semantics of the language. Such a language gives up certain… … Wikipedia
Thoralf Skolem — Infobox Scientist name = Thoralf Skolem birth date = birth date|1887|5|23|mf=y birth place = Sandsvaer, Buskerud, Norway residence = nationality = death date = death date and age|1963|3|23|1887|5|23|mf=y death place = Oslo, Norway field =… … Wikipedia
Liste des langages de programmation — Le but de cette Liste des langages de programmation est d inclure tous les langages de programmation existants, qu ils soient actuellement utilisés ou historiques, par ordre alphabétique. Ne sont pas listés ici les langages informatiques de… … Wikipédia en Français
Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia
Post–Turing machine — The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines. A Post–Turing machine is a program formulation of an especially simple type of Turing machine, comprising a … Wikipedia
