Hulp
Boekenmaker (uitschakelen)

Talen en automaten/2011-12/producten/Entropy

Uit Werkplaats
< Talen en automaten‎ | 2011-12‎ | producten
Versie door Erik Barendsen (overleg | bijdragen) op 24 jan 2012 om 10:52
(wijz) ← Oudere versie | Huidige versie (wijz) | Nieuwere versie → (wijz)
Ga naar: navigatie, zoeken
busy
Page Break




Algolfrag.jpg

Talen en automaten

Erik Barendsen

 © comments



Entropy

Thom Wiggers, Simon Brugman

2009-11-06-entropy.jpg


Talen en automaten 2011-12



14:10 A






Thom Wiggers Bachelor Informatica
 e-mail 

cursuspagina

Thom Wiggers.jpg

Simon Brugman
 e-mail 

cursuspagina

Bestand:Simon Brugman.jpg
Page Break





Beschrijving

Entropy is een esoterische programmeertaal waarbij er data vergaat. Na het gebruik van elke waarde wordt deze een klein beetje aangepast, en wordt daardoor minder precies. Het programma zelf wordt niet aangepast, waardoor na het herstarten het programma weer terug is in de oorspronkelijke toestand. Entropy is ontworpen door Daniel Temkin in 2010.[1]

De taal kan gebruikt worden op plaatsen waar willekeur nodig is en de integriteit van de gevens niet (erg) van belang is. De onderstaande voorbeelden zijn wat 'lollige' voorbeelden, maar er zijn wel degelijk wat serieuzere toepassingen te bedenken, zoals Glitch Art. Door het gebruiken van deze taal wordt de output van het programma altijd wat onverwacht, waardoor je 'bugs' of 'glitches' kunt nabootsen, dit kan op een afbeeldingen een mooi, vreemd of grappig effect hebben. Wanneer de integriteit van de gegevens wél belangrijk is, maar er een deel is dat willekeurig moet zijn, is het ook mogelijk om andere datatypes (uit bijvoorbeeld C#) te gebruiken, nadat Entropy is geconverteerd naar C# code. Hiervoor bestaat de volgende (.NET-)compiler.[2]

Structuur

Entropy is niet heel verschillend van andere talen als C#, toch zijn er een aantal zaken die verduidelijking nodig hebben.

Datatypes

De taal gebruikt een drietal verschillende datatypes. In het bijzonder bevat de taal geen integers.

Real

Een komma-getal (float), die bij elke keer dat deze wordt gelezen een klein beetje wordt aangepast. Hierdoor wordt het trouwens onmogelijk om te controleren of twee waardes gelijk zijn, maar kan dit alleen bij benadering gedaan worden via de kleiner- en groter-dan-operator.

Char

Dit is een (ASCII-)karakter, gebaseerd op een real en neemt de waarde die het dichts bij de huidige waarde ligt, waarvan deze het karakter teruggeeft. Wanneer een tekst bijvoorbeeld vaak wordt weergeven, kan deze zodanig veranderen dat de waarde een aantal van deze karakters bijvoorbeeld 7 is, wat zorgt voor wel bekende Systeem-beeps.

String

Een string is een array van chars. Hoewel dit hetzelfde is als in de meeste talen, heeft char hier een zodanige andere definitie, die ook de integriteit van de string aantast.

Notatie

Een script begint altijd met de code, waarbij de woorden tussen accolades vervangen dienen te worden: <source lang="vb">Program {namespaceNaam} {programmaNaam} [</source> En wordt afgesloten met <source lang="vb">]</source> Hier valt al op dat blokhaken worden gebruikt in plaats van accolades. Dit is ook zo bij loops, zoals de while-loop. Wat ook opvalt is dat er geen haakjes worden gebruikt (behalve bij berekeningen waarbij bepaalde bewerkingen eerst moeten worden gedaan), bij bijvoorbeeld de while-loop. Verder spreekt de notatie erg voor zich (zie volgende sectie: voorbeelden).

Voorbeelden

Hello, world!

De volgende code is een simpel "Hello world!" voorbeeld. De output zal niet zijn zoals gebruikelijk, maar met een kleine afwijking. Zo kan de output zijn "Hellp World!" of "Wello World!" etc.

<source lang="vb"> Program ExampleNamespace HelloWorld [ 

	print "Hello World!";
]</source>

Easy Lyrics

Het volgende programma is door ons geschreven als variatie op 99 Bottles Het ouput de lyrics van het nummer Satisfaction van Benny Benassi uit 2003, alleen elke keer wordt de songtekst iets aangepast, zodat het minder eentonig is.

<source lang="vb"> Program EasyLyricsNamespace Singitahunderdtimes [ 

	declare count real;
	let count = 99;
	
	while count > 0
	[
               declare scount real;
               let scount = 5;
               print "Push me\n";
               print "And then just touch me\n";
               print "Till I can get my\n";
               while scount > 0
               [
                     print "Satisfaction ";
                     if scount > 1
                     [
                           print ",";
                     ]  
                     let scount = scount - 1;
               ]
               print "\n\n";
		let count = count - 1;
	]
	
	print "\n\n\nI should drink less.";
]</source>[3]
Output

De eerste 3 loops:

Pu}h me

And then just touch me
Till I can�get my
Satisfaction ,Satisfacthon ,Satisgacthon ,Satisgacthon ,Satisgacthon

Pu}h me
And then jutt touch me
Till I can�get my
Satisgacthon ,S`tisgacthon ,S`tisfacthon ,S`tisfacthon ,S`tisfacthon

Pu}h me
And then jutt touch me
Till I can�get my

Sbtisfacthon ,Sbtisfacthon ,Sbtisfacthon ,Sbthsfacthon ,Sbthsfactgon

Er is duidelijk te zien dat de tekst steeds verder aftakelt. De laatste paar executies ziet er al zo uit:

�Pu|l�i_�Anf uheo$http"uokec td Vjml�G�lbl�bf{�ox�UZoiqa^ii`wU�5UZoiqa^ii`wU�5UZoiqa^iiVwU�5VZoiqa^iiVvU�5VZoiqa^iiVvU�

�Pu|l�i_�Anf uheo$http"uokec�td Vjml�G�lbl�bf{�ox�VZoiqa^iiVvU�5VZoiqa^iiVvU�5VZoiqa^iiVvU�5VZoiqa^iiVvU�5VZoiqa^iiVvU�VZohqa^iiVvU�
�Pu|l�i_�Anf uhco$http"uokec�td Vjml�G�lbl�bf{�ox�VZohqa^iiVvU�+VZohqa^iiVwU�+VZohra^iiVwU�+VZohra^iiVwU�+VZogra^ihVmU�
�Pu}l�i_�Anf uhco$http"uokec�td Vtml�=�lbl�bf{�ox�VZogra^ihVmU�+VZogra^ihVmU�+VZogra^ihVmU�+VZogra^ihVmU�+VZogqa^ihVmU�+
�Pu}l�i_�Anf uhco$http"uokec�td Vtml�=�lbl�df{�ox�VZogqa^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�
�Pt}l�i_�Anf uhco$http"uokec td Vtml�=�lbl�df{�ox�VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+VZogqb^ihVmU�+
�Pt}l�i_�Anf uhco$http"uokec td Vtmm�=�lbl�df{�ox�VZogqb^ihVmU�+VZogqb_ihVmU�+VZogqb_ihVmS�+VZogqb_lhVmS�+VZogrb_lhVmS�+
�Pt}l�i_�Anf uhco$http"uokec td Vtmm�=�lbl�df{�ox�VZogrb_lhVmS�+VZogrb_lhVmS�+VZogrb_lhVmS�+VZrgrb_lhVmS�+VZrgrb_lhVmS�+VZrhrb_lhVmS�
�


I should drink less.

Wat niet goed weer te geven is in dit document zijn de grote hoeveelheid controletekens die ook door de mutaties ontstaan.

Regulier?

Entropy is geen reguliere taal. Dit kunnen we bewijzen door middel van de Pompstelling voor reguliere talen. Deze stelt dat voor elke reguliere taal woorden Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w\,} met Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |w| \ge n} kunnen worden opgedeeld in drie delen, namelijk Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle xyz\,} . Hierbij staat Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n\,} voor een constant getal, wat aangeeft hoeveel tekens er maximaal kunnen zijn voordat er een herhaling moet optreden (namelijk, het aantal toestanden van de bijbehorende eindige automaat, die weer voor elke reguliere taal gemaakt kan worden).

Voor deze drie delen geldt:

  1. Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |y| > 0\,}
  2. Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |x| + |y| \leq n}
  3. Voor alle Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k \geq 0} , Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle xy^kz\,} behoort tot Entropy

Dit wil eigenlijk zeggen dat wanneer een woord lang genoeg is (Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |w| \le n} ) het woord een deel bevat (Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |y| > 0 \,} ), wat kan worden weggelaten of eindeloos kan worden herhaald.

Om nu te bewijzen dat Entropy niet regulier is, moeten we een woord kiezen, die lang genoeg is, maar niet pompbaar is. Neem de volgende code: <source lang="vb"> Program Namespace Programma[ 

    while 1
    [
          while 1
          [
                 ...
          ]
    ]

] </source> In dit voorbeeld staat ... gelijk aan een while-loop met daarin weer ..., zodat voordat de eerste eind-blokhaak wordt geschreven, er minstens Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n\,} tekens zijn geweest. Als Entropy regulier zou zijn, moet er in dit eerste stuk een deel zijn dat herhaald is. Dit is er niet (door het gebruikt van deze blokhaken) en dat maakt Entropy niet-regulier.

Contextvrij?

Wij gaan hier proberen te bewijzen dat Entropy een context-vrije taal is door een context-vrije grammatica voor (een deel van) de taal te maken. Een context-vrije grammatica[4] is een vier-tupel Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left( V, \Sigma, P, S\right)} waar Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle V\,} een eindige set variabelen is, Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma\,} een eindig alfabet bestaande uit terminale symbolen, Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P\,} een verzameling productieregels van de vorm Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \to w \,} waar Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \in V\,} en Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w \in \left(V \cup \Sigma\right)^*\,} . Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S\,} is het startsymbool.

Het alfabet van de taal Entropy bestaat voornamelijk uit controlestructuren, functies, operatoren en labels. Labels worden bijvoorbeeld gebruikt in functienamen, namespaces en variabelenamen.

Elementen van Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle V\,} zijn hier cursief gedrukt en beginnen met een hoofdletter. Woorden in de taal zijn afgedrukt als rechtopstaande letters. Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} Programma &\to \mbox{Program } Namespace \ Functienaam \ Commandoblok \\ Namespace &\to Label\\ Functienaam &\to Label \\ Commandoblok &\to [ Commandos ] \ \\ Commandos &\to Commando \ | \ Commando \ Commandos \\ Commando &\to ConditioneleOperatie \ | \ Instructie \ | \ \lambda \\ Instructie &\to VariableDeclaratie \ \mbox{;} | \ FunctieAanroep \ \mbox{;} \, | Rekenoperatie \mbox{;}\\ Rekenoperatie &\to Nummerwaarde \ | \ Rekenoperator \ Nummerwaarde \ | \ Nummerwaarde \ Rekenoperator \ Rekenoperatie \ | \ Rekenoperatie \ Rekenoperator \ Nummerwaarde \\ VariabeleDeclaratie &\to RealDeclaratie \ | \ StringDeclaratie \\ StringDeclaratie &\to \mbox{let } VariabeleNaam \mbox{ = } String \\ RealDeclaratie &\to \mbox{let } VariabeleNaam \mbox{ = } Cijfer \\ FunctieAanroep &\to Functies \ ParameterLijst\\ ConditieOperatie &\to ConditieSoort \ Conditie \ Conditiebody \ | \ IfElse \\ ConditieBody &\to Commandoblok \ | \ Instructie\\ IfElse &\to \mbox{if} \ Conditie \ ConditieBody \ \mbox{else} \ ConditieBody \ | \ \mbox{if} \ Conditie \ ConditieBody \ \mbox{else} \ IfElse \\ Conditie &\to Waarde \ Vergelijker \ Waarde \\ ConditieSoort &\to \mbox{if} \ | \ \mbox{while}\\ ParameterLijst &\to Parameter \ | Parameter, \ ParameterLijst \ | \ \lambda\\ Parameter &\to Waarde\\ Waarde &\to String \ | \ KommaCijfer \ | \ VariabeleNaam \\ NummerWaarde &\to KommaCijfer \ | \ VariabeleNaam \\ VariabeleNaam &\to Label\\ Functies &\to \mbox{print} \ | \ FunctieNaam \\ Label &\to \mbox{a}|\mbox{b}|\mbox{c}|\mbox{d}|\mbox{e}|\mbox{f}|\mbox{g}|\mbox{h}|\mbox{i}|\mbox{j}|\mbox{k}|{l}|\mbox{m}|\mbox{n}|\mbox{o}|\mbox{p}|\mbox{q}|\mbox{r}|\mbox{s}|\mbox{t}|\mbox{u}|\mbox{v}|\mbox{w}|\mbox{x}|\mbox{y}|\mbox{z}|\mbox{A}|\mbox{B}|\mbox{C}|\mbox{D}|\mbox{E}|\mbox{F}|\mbox{G}|\mbox{H}|\mbox{I}|\mbox{J}|\mbox{K}|\mbox{L}|\mbox{M}|\mbox{N}|\mbox{O}|\mbox{P}|\mbox{Q}|\mbox{R}|\mbox{S}|\mbox{T}|\mbox{U}|\mbox{V}|\mbox{W}|\mbox{X}|\mbox{Y}|\mbox{Z} | \ Label \ Label \\ KommaCijfer &\to Cijfer \ | \ Cijfer \mbox{ . } Cijfer \\ Cijfer &\to \mbox{0}\ |\ \mbox{1}\ |\ \mbox{2}\ |\ \mbox{3}\ |\ \mbox{4}\ |\ \mbox{5}\ |\ \mbox{6}\ |\ \mbox{7}\ |\ \mbox{8}\ |\ \mbox{9}\ | \ Cijfer \ Cijfer \ \\ String &\to ''stringcontents''\\ Vergelijker &\to > | < \\ Rekenoperator &\to - \ + \ * \ / \ \% \end{align}}

Er is dus een grammatica voor deze taal te maken, en deze is dus contextvrij.

Externe links

De externe pagina's zijn verdeeld in twee categorieën, namelijk "Meer informatie", dit zijn pagina's die wel interessant zijn, maar niet of maar weinig zijn gebruikt voor de tekst op deze pagina, en "Bronnen", wat directe referenties zijn naar pagina's die zijn gebruikt voor een deel van de tekst.

Meer informatie

Bronnen

  1. ↑ Website van ontwerper Daniel Temkin over Entropy
  2. ↑ Website van ontwerper Daniel Temkin over Entropy
  3. ↑ http://esolangs.org/wiki/Entropy#99_Bottles 99 Bottles
  4. ↑ Languages and Machines, Third edition, Thomas A. Sudkamp
Overgenomen van "https://lab.cs.ru.nl/algemeen/index.php?title=Talen_en_automaten/2011-12/producten/Entropy&oldid=177210"