Thue ( / ˈt uːeɪ / ) este un limbaj de programare ezoteric dezvoltat de John Colagoyala începutul anului 2000. Este un meta-limbaj care prezintă un tip nul în ierarhia Chomsky , adică o gramatică nerestricționată . Thue vă permite să definiți orice limbă și Turing este complet.
Autorul o descrie astfel: „Thue este cea mai simplă demonstrație a programării cu constrângeri . Datorită acestei paradigme, limbajul este similar cu limbajele URISC ale paradigmei imperative. Cu alte cuvinte, este o mlaștină Turing .”
Un program Thue constă dintr-un tabel de reguli și o stare inițială. Tabelul de reguli constă din definiții simple ale formei
A ::= BA și B pot consta atât din litere și simboluri individuale, cât și din grupurile lor. Pot exista multe reguli cu același A și B diferit . Tabelul cu reguli se termină cu o regulă goală:
::=Starea inițială este un șir de caractere scris după tabelul de reguli.
Sarcina programului este să găsească caracterele originale (stânga) și să le înlocuiască cu cele din dreapta în conformitate cu regula.
Lucrarea se termină când nu pot fi aplicate reguli șirului.
Astfel, un program Thue este similar cu o mașină Turing: există o bandă de simboluri și există un set de reguli prin care acestea sunt înlocuite.
Una dintre caracteristicile cheie ale limbajului este ordinea de selecție nedeterministă.
Dacă există mai multe caractere în șir cărora li se poate aplica regula, atunci aceasta va fi aplicată unui caracter selectat aleatoriu.
Dacă sunt definite mai multe reguli pentru același caracter, atunci se va aplica o regulă selectată aleatoriu.
Pentru a implementa intrarea și ieșirea, limbajul are o formă specială de reguli. Tidul este folosit pentru a afișa caractere:
A ::=~șir de caractereAceastă regulă elimină A din șir și scoate toate caracterele după tilde.
Pentru a introduce trei două puncte:
A ::=:::Această regulă înlocuiește A cu șirul citit de la intrare.
Salut Lume! pe Thu:
a::=~Bună lume! ::= ANu există variabile ca concepte în limbaj. Prin urmare, pentru orice calcule, este necesar să se stabilească sistemele de reguli corespunzătoare. Următorul program demonstrează cum să crești un număr binar (incrementare cu unu). Numărul este scris simbolic și este marcat în jurul marginilor cu o liniuță:
1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 ::= _1111111111_Determinismul este asigurat de prezența unei singure reguli și a unui singur simbol căruia îi poate fi aplicat la un anumit moment de timp.
Următorul program demonstrează implementarea buclelor și nedeterminismul regulilor:
b::=~0 b::=~1 xx::=xbx ::= xbxAcest program produce un șir nesfârșit de unu și zerouri. Ciclicitatea este furnizată astfel: după fiecare ieșire, caracterul b este eliminat din șirul xbx, restul de caractere xx sunt înlocuite cu xbx, reproducând starea inițială. Astfel, este posibil să se creeze bucle mărginite, al căror număr de iterații este dat de numărul anumitor caractere sau seturi de caractere din șir:
_x::=i_ i::=~test! ::= _xxxxxAcest program va tipări testul șirurilor de 5 ori. Rețineți că ordinea în care i și _x sunt înlocuiți este nedefinită. Adică, în timpul execuției, programul poate atât procesa imediat i așa cum apar, cât și poate selecta toate x din șir deodată.
| Limbaje de programare | |
|---|---|
| |