Thue ( / ˈt uːeɪ / ) je esoterický programovací jazyk vyvinutý Johnem Colagoyouna začátku roku 2000. Je to metajazyk, který v Chomského hierarchii vykazuje nulový typ , tedy neomezenou gramatiku . Thue vám umožňuje definovat jakýkoli jazyk a je Turing kompletní.
Autor to popisuje takto: „Thue je nejjednodušší ukázka programování s omezeními . Díky tomuto paradigmatu je jazyk podobný jazykům URISC imperativního paradigmatu. Jinými slovy, je to Turingova bažina ."
Program Thue se skládá z tabulky pravidel a počátečního stavu. Tabulka pravidel se skládá z jednoduchých definic formuláře
A ::= BA a B se mohou skládat jak z jednotlivých písmen a symbolů, tak z jejich skupin. Může existovat mnoho pravidel se stejným A a různým B . Tabulka pravidel končí prázdným pravidlem:
::=Počáteční stav je řetězec znaků zapsaných za tabulkou pravidel.
Úkolem programu je najít původní (levé) znaky a nahradit je pravými v souladu s pravidlem.
Úloha končí, když na řetězec nelze použít žádná pravidla.
Program Thue je tedy podobný Turingovu stroji: existuje páska symbolů a existuje soubor pravidel, kterými jsou nahrazeny.
Jedním z klíčových rysů jazyka je nedeterministické pořadí výběru.
Pokud je v řetězci několik znaků, na které lze pravidlo použít, bude aplikováno na náhodně vybraný znak.
Pokud je pro stejný znak definováno více pravidel, použije se náhodně vybrané pravidlo.
Pro implementaci vstupu a výstupu má jazyk speciální formu pravidel. Vlnovka se používá k zobrazení znaků:
A ::=~řetězec znakůToto pravidlo odstraní A z řetězce a vypíše všechny znaky za vlnovkou.
Chcete-li zadat tři dvojtečky:
A ::=:::Toto pravidlo nahradí A řetězcem přečteným ze vstupu.
Ahoj světe! ve čtvrtek:
a::=~Ahoj světe! ::= AV jazyce neexistují žádné proměnné jako pojmy. Proto je pro jakékoli výpočty nutné nastavit odpovídající systémy pravidel. Následující program ukazuje, jak zvýšit binární číslo (přírůstek o jednu). Číslo je napsáno symbolicky a po okrajích je označeno podtržítkem:
1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 ::= _1111111111_Determinismus je poskytován přítomností pouze jednoho pravidla a pouze jednoho symbolu, na který může být aplikován v kterémkoli konkrétním okamžiku.
Následující program demonstruje implementaci smyček a nedeterminismus pravidel:
b::=~0 b::=~1 xx::=xbx ::= xbxTento program vytváří nekonečný řetězec jedniček a nul. Cyklicita je zajištěna následovně: po každém výstupu je znak b odstraněn z řetězce xbx, zbývající znaky xx jsou nahrazeny xbx, čímž se reprodukuje počáteční stav. Je tedy možné vytvářet ohraničené smyčky, jejichž počet iterací je dán počtem určitých znaků nebo sad znaků v řetězci:
_x::=i_ i::=~testuji! ::= _xxxxxTento program vytiskne test řetězce 5krát. Všimněte si, že pořadí, ve kterém jsou i a _x nahrazeny, není definováno. To znamená, že během provádění může program okamžitě zpracovat i, jak se objeví, a vybrat všechna x z řetězce najednou.
| Programovací jazyky | |
|---|---|
| |