Thue
Thue é uma linguagem de programação esotérica inventada por John Colagioia no início de 2000. É uma meta-linguagem que pode ser usada para definir ou reconhecer linguagens do tipo 0 da hierarquia de Chomsky. Porque ela é capaz de definir linguagens de tal complexidade, é também Turing completa ela mesma. Thue é baseado em um sistema de reescrita de strings não determinístico chamado gramática Thue-semi, que por sua vez é nomeado após (e, possivelmente, criado pelo) matemático norueguês Axel Thue; inspiração também é tirada do grue. O autor descreve-o como segue: "Thue representa uma das maneiras mais simples possíveis de interpretar programação baseada em restrições. São para o paradigma baseado em restrições que linguagens como a OISC são para o imperativo paradigma, em outras palavras, é uma tar pit. "
Regras de produção editar
Um programa Thue começa com uma regra base, que é uma série de regras de substituição, cada uma das seguinte forma:
lhs ::= rhs
A regra base termina com um símbolo de produção solitário em uma linha:
::=
O estado inicial é uma série de símbolos que se seguem a regra base.
Thue consome os símbolos iniciais e substitui o resultado das regras de cada um dos símbolos de estado inicial.
Thue termina quando lhs não pode ser encontrado em um estado resultante.
Notas editar
- ::= é pronunciado pode ser.
- lhs é "lado esquerdo(left hand side)".
- rhs é "lado direito (right hand side)".
- "::=" não pode nunca ser lhs.
- ":::" é um fluxo de entrada.
- "~" é um fluxo de saída.
- Sistemas semi-Thue são isomórficos a gramáticas irrestritas.
Chamando Thue editar
Quando chamado com 'd' (debug), imprime o estado. Quando chamado com 'l' (lado esquerdo), aplica as regras da esquerda para a direita. Quando chamado com 'r' (lado direito), aplica as regras da direita para a esquerda. O último 'l' ou 'r' substitui as opções anteriores.
Programas de Exemplo editar
Aqui está o tradicional "Olá Mundo!" em Thue:
a::=~Hello World! ::= a
O programa Thue a seguir executa um incremento de um número binário introduzido como o estado inicial cercado por caracteres "_", neste caso, o número 1111111111:
1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 ::= _1111111111_
O programa de exemplo a seguir é para demonstrar o não-determinismo de Thue (e para mostrar um exemplo de um loop infinito, além). O programa gera saídas de bits em uma seqüência indefinida (e possivelmente aleatória).
b::=~0 b::=~1 ac::=abc ::= abc