Thue ( / ˈt uːeɪ / ) er et esoterisk programmeringssprog udviklet af John Colagoyai begyndelsen af 2000. Det er et metasprog, der udviser en nultype i Chomsky-hierarkiet , altså en ubegrænset grammatik . Thue giver dig mulighed for at definere ethvert sprog og er Turing komplet.
Forfatteren beskriver det på denne måde: "Thue er den enkleste demonstration af begrænsningsprogrammering . Det er på grund af dette paradigme, at sproget ligner URISC- sprogene i imperativparadigmet. Med andre ord, det er et Turing-sump ."
Et Thue-program består af en tabel med regler og en begyndelsestilstand. Regeltabellen består af simple definitioner af formen
A ::= BA og B kan bestå af både individuelle bogstaver og symboler og deres grupper. Der kan være mange regler med samme A og forskellig B. Regeltabellen slutter med en tom regel:
::=Starttilstanden er en streng af tegn skrevet efter regeltabellen.
Programmets opgave er at finde de originale (venstre) tegn og erstatte dem med højre i overensstemmelse med reglen.
Jobbet afsluttes, når ingen regler kan anvendes på strengen.
Således ligner et Thue-program en Turing-maskine: Der er et bånd af symboler, og der er et sæt regler, som de erstattes med.
Et af sprogets nøgletræk er den ikke-deterministiske udvælgelsesrækkefølge.
Hvis der er flere tegn i strengen, som reglen kan anvendes på, så vil den blive anvendt på et tilfældigt valgt tegn.
Hvis der er defineret flere regler for det samme tegn, vil en tilfældigt valgt regel blive anvendt.
For at implementere input og output har sproget en særlig form for regler. Tilden bruges til at vise tegn:
En ::=~tegnstrengDenne regel fjerner A fra strengen og udsender alle tegn efter tilden.
Sådan indtaster du tre koloner:
A ::=:::Denne regel erstatter A med strengen læst fra input.
Hej Verden! på Thue:
a::=~Hej verden! ::= -enDer er ingen variable som begreber i sproget. Derfor er det for enhver beregning nødvendigt at indstille de tilsvarende regelsystemer. Det følgende program viser, hvordan man øger et binært tal (øger med én). Tallet er skrevet symbolsk og er markeret rundt om kanterne med en understregning:
1_::=1++ 0_::=1 01++::=10 11++::=1++0 _0::=_ _1++::=10 ::= _1111111111_Determinisme er tilvejebragt ved tilstedeværelsen af kun én regel og kun ét symbol, som den kan anvendes på på et bestemt tidspunkt.
Følgende program demonstrerer implementeringen af sløjfer og reglernes ikke-determinisme:
b::=~0 b::=~1 xx::=xbx ::= xbxDette program udsender en endeløs række af etere og nuller. Cyclicitet er tilvejebragt som følger: efter hvert output fjernes tegnet b fra strengen xbx, de resterende xx tegn erstattes af xbx, hvilket gengiver starttilstanden. Det er således muligt at oprette afgrænsede loops, hvis antal iterationer er givet af antallet af bestemte tegn eller sæt af tegn i strengen:
_x::=i_ i::=~test! ::= _xxxxxDette program vil udskrive strengtesten! 5 gange. Bemærk, at rækkefølgen i og _x erstattes i er udefineret. Det vil sige, at programmet under udførelsen både kan behandle i som de vises, og vælge alle x fra strengen på én gang.
| Programmeringssprog | |
|---|---|
| |