Thue ( / ˈt uːeɪ / ) es un lenguaje de programación esotérico desarrollado por John Colagoyaa principios de 2000. Es un metalenguaje que exhibe un tipo nulo en la jerarquía de Chomsky , es decir, una gramática sin restricciones . Thue le permite definir cualquier idioma y es Turing completo.
El autor lo describe de esta manera: “Thue es la demostración más simple de programación con restricciones . Es debido a este paradigma que el lenguaje es similar a los lenguajes URISC del paradigma imperativo. En otras palabras, es un atolladero de Turing ".
Un programa Thue consta de una tabla de reglas y un estado inicial. La tabla de reglas consta de definiciones simples de la forma
A ::= BA y B pueden constar de letras y símbolos individuales y sus grupos. Puede haber muchas reglas con la misma A y diferente B. La tabla de reglas termina con una regla vacía:
::=El estado inicial es una cadena de caracteres escrita después de la tabla de reglas.
El trabajo del programa es encontrar los caracteres originales (izquierdos) y reemplazarlos por los correctos de acuerdo con la regla.
El trabajo finaliza cuando no se pueden aplicar reglas a la cadena.
Así, un programa de Thue es similar a una máquina de Turing: hay una cinta de símbolos y hay un conjunto de reglas por las que se reemplazan.
Una de las características clave del lenguaje es el orden de selección no determinista.
Si hay varios caracteres en la cadena a los que se puede aplicar la regla, se aplicará a un carácter seleccionado al azar.
Si se definen varias reglas para el mismo personaje, se aplicará una regla seleccionada al azar.
Para implementar la entrada y la salida, el lenguaje tiene una forma especial de reglas. La tilde se usa para mostrar caracteres:
Una cadena de caracteres ::=~Esta regla elimina A de la cadena y genera todos los caracteres después de la tilde.
Para ingresar tres dos puntos:
A ::=:::Esta regla reemplaza A con la cadena leída de la entrada.
Hola Mundo! el jueves:
a::=~¡Hola mundo! ::= aNo hay variables como conceptos en el lenguaje. Por lo tanto, para cualquier cálculo, es necesario establecer los sistemas de reglas correspondientes. El siguiente programa demuestra cómo incrementar un número binario (incrementar en uno). El número está escrito simbólicamente y está marcado alrededor de los bordes con un guión bajo:
1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 ::= _1111111111_El determinismo lo proporciona la presencia de una sola regla y un solo símbolo al que se puede aplicar en cualquier momento particular.
El siguiente programa demuestra la implementación de bucles y el no determinismo de las reglas:
b::=~0 b::=~1 xx::=xbx ::= xboxEste programa genera una cadena interminable de unos y ceros. La ciclicidad se proporciona de la siguiente manera: después de cada salida, el carácter b se elimina de la cadena xbx, los xx caracteres restantes se reemplazan por xbx, reproduciendo el estado inicial. Por lo tanto, es posible crear bucles acotados, cuyo número de iteraciones viene dado por el número de ciertos caracteres o conjuntos de caracteres en la cadena:
_x::=i_ yo::=~prueba! ::= _xxxxxEste programa imprimirá la prueba de cuerdas 5 veces. Tenga en cuenta que el orden en que se reemplazan i y _x no está definido. Es decir, durante la ejecución, el programa puede procesar inmediatamente las i tal como aparecen y seleccionar todas las x de la cadena a la vez.
| Lenguajes de programación | |
|---|---|
| |