Saltar para o conteúdo

Thue

Origem: Wikipédia, a enciclopédia livre.

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 | editar código-fonte]

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.

  • ::= é 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.

Chamando Thue

[editar | editar código-fonte]

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 | editar código-fonte]

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

Ligações externas

[editar | editar código-fonte]