Page Break
Iota
Lena Ebert, Keerthigah Poobalasingham
Talen en automaten 2011-12
Page Break
Beschrijving
Iota is een esoterisch programmeertaal die door Chris Barker ontworpen is. De naam van de taal komt van de Griekse letter iota. Dit is de kleinste letter van dat alfabet. Iota is ontworpen met het doel zo eenvoudig als mogelijk te zijn maar wel Turing-volledig en niet ambigu. De taal maakt gebruik van slechts twee symbolen(* en i) en is gebaseerd op combinatorische logica.
SKI - combinatorische calculus heeft slechts twee kanonische operatoren, de combinatoren S en K. Om het makkelijker te maken wordt er ook een I gebruikt, maar dit is ook uit te drukken in S en K. Iedere programma kan met SKI worden uitgedrukt.
Hierbij geldt:
1. S is de functie "λ x y z . x z (y z)".
2. K is de functie "λ x y . x"
3. I is de functie "λ x . x" (dit is ook te schijven als SSK)
Iota is nog eenvoudiger. Hier worden alleen de combinator i gebruikt en wordt * als functie applicatie gebruikt. De SKI combinatoren in Iota zijn:
1. S=*i*i*i*ii
2. K=*i*i*ii
3. I=*ii
Iota is een programmeertaal zonder output. Het programma zelf is zowel input als output. Er zijn interpreters zoals Lazy-K die Iota accepteren en dan output geven.
Voorbeelden
In Iota kunnen geen cijfers worden gebruikt. Hier zijn de Iota uitdrukkingen gegeven voor de cijfers 1, 2 en 3.
Om programma’s met Iota te kunnen bouwen moeten er ook statements mogelijk zijn. Er moet een if, een true en een false statement gedefinieerd zijn.
| Cijfer |
Lambda Syntax |
Iota
|
| 1 |
λ s z . s z. |
* i i
|
| 2 |
λ s z . s (s z) |
***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii
|
| 3 |
λ s z . s (s (sz)) |
***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii***i*i*i*ii***i*i*i*ii**i*i*ii*i*i*i*ii*i*i*ii*ii
|
| Statement |
Lambda Syntax |
Iota
|
| true |
λ x y . x |
* i * i * i i
|
| false |
λ x y . y |
* * i * i * i i * i i
|
| if |
c t f . ( c t f ) |
* i i
|
Regulier?
Om te bewijsen dat Iota niet regulier is wordt er gebruik gemaakt van het pomp lemma.
Dan is er een DFA M met L = L(M) en k toestanden en z ϵ L met lengte (z) ≥ k.
z is dan te schrijven als z = uvw met lengte (v) > 0 zodat 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 uv^iw}
ϵ L voor elke i ≥ 0, waarbij lengte (uv) ≤ k.
Aanname: Iota (L) is wel regulier.
Bekijk: 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 z= *^ki^{{(k+1)}}}
waarbij z ϵ L en lengte (z) ≥ 0
Volgens het pomplemma moet er z = uvw met lengte (uv) ≤ k 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 uv^iw}
ϵL voor alle i gelden.
Het aantal * in v is maximaal k, maar v bevat in iedere geval een *.
Zeg p = |v|, zodat 1 ≤ p ≤ k.
Voor i = 3 is dan:
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 uv^3w}
ϵ L
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-p+3p)}}i^{{(k-1)}}}
ϵ L
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+2p)}}i^{{(k+1)}}}
ϵ L
Omdat p ≥ 1 en het aantal 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+2p}
, maar 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+2p}
niet kleiner dan het aantal 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 i=k+1}
zit er een tegenspraak in. De aanname 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 L}
is regulier is dus fout 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 L}
is niet regulier.
Iota voldoet dus niet aan het pomplemma en is niet regulier.
Contextvrij?
Om aan te tonen dat Iota een contextvrije taal is wordt ere en een contextvrijde grammatica opgesteld die de taal herkent.
Een mogelijke contextvrije grammaitca ziet er als volgt uit:
S → i
S → *SS
Iota is dus een contextvije taal.
Bronnen
http://esolangs.org/wiki/Iota
http://esolangs.org/wiki/Jot
http://semarch.linguistics.fas.nyu.edu/barker/Iota/
http://en.wikipedia.org/wiki/Iota_and_Jot
