View source for Iota and Jot

{{Short description|Esoteric programming languages}}
{{Infobox programming language
| name = Iota, Jot, Zot
| logo = <!-- (filename) -->
| logo caption = 
| screenshot = <!-- (filename) -->
| screenshot caption = 
| paradigms = [[Formal language]], [[Turing tarpit]], [[esoteric programming language|esoteric]]
| family =  
| designer = [[Chris Barker (linguist)|Chris Barker]]
| developer = Chris Barker
| released = {{Start date and age|2001}}
| latest release version = 2001
| latest release date = {{Start date and age|2001}}
| typing = 
| scope = 
| programming language = [[Scheme (programming language)|Scheme]], [[JavaScript]]
| discontinued = Y
| platform = Scheme interpreter, [[Web browser]] (JavaScript)
| operating system = 
| license = [[Public domain]]
| file ext = 
| file format = 
| website = {{URL|https://web.archive.org/web/20181024173237/http://www.nyu.edu/projects/barker/Iota/}}
| implementations = 
| dialects = 
| influenced by = 
| influenced = [[#Zot|Zot]]
}}
In [[formal language]] theory and [[computer science]], '''Iota''' and '''Jot''' (from [[Greek language|Greek]] [[iota]] ι, [[Hebrew]] [[yodh]] י, the smallest letters in those two alphabets) are languages, extremely minimalist [[formal system]]s, designed to be even simpler than other more popular alternatives, such as  [[lambda calculus]] and [[SKI combinator calculus]]. Thus, they can also be considered minimalist computer [[programming language]]s, or [[Turing tarpit]]s, [[esoteric programming language]]s designed to be as small as possible but still [[Turing-complete]]. Both systems use only two symbols and involve only two operations. Both were created by professor of linguistics [[Chris Barker (linguist)|Chris Barker]] in 2001. '''Zot''' (2002) is a successor to Iota that supports input and output.<ref>{{cite web|url=https://www.nyu.edu/projects/barker/Iota/zot.html |title=Zot |last=Barker |first=Chris |website=The Esoteric Programming Languages Webring |archive-url=https://web.archive.org/web/20160312050150/http://semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html |archive-date=12 March 2016 |access-date=4 October 2016 |url-status=dead }}</ref>

Note that this article uses [[Backus-Naur form]] to describe syntax.

==Universal iota==
Chris Barker's universal iota combinator {{mvar|ι}} has the very simple λf.fSK structure defined here, using [[denotational semantics]] in terms of the [[lambda calculus]],

{{NumBlk|:|<math>\iota := \lambda f.((fS)K) := \lambda f.((f\lambda a.\lambda b.\lambda c.((ac)(bc)))\lambda d.\lambda e.d) </math>|{{EquationRef|1}}}}

From this, one can recover the usual [[SKI combinator calculus#SKI expressions|SKI expressions]], thus:

{{NumBlk|:|<math>I\, =\, (\iota \iota),\; K\, =\, (\iota(\iota(\iota\iota))), \;S\, =\, (\iota(\iota(\iota(\iota\iota))))</math>|{{EquationRef|2}}}}

Because of its minimalism, it has influenced research concerning [[Chaitin's constant]].<ref>{{cite journal|last=Stay|first=Michael|date=August 2005|title=Very Simple Chaitin Machines for Concrete AIT|url=http://content.iospress.com/articles/fundamenta-informaticae/fi68-3-03|journal=Fundamenta Informaticae|publisher=IOS Press|volume=68|issue=3|pages=231–247|doi=10.3233/FUN-2005-68303 |arxiv=cs/0508056|bibcode=2005cs........8056S|access-date=20 February 2011}}</ref>

==Iota==
Iota is the [[LL parser|LL(1)]] language that [[Polish notation|prefix orders]] trees of the aforementioned [[#Universal iota|Universal iota]] {{mvar|ι}} combinator leafs, [[cons]]ed by [[function application]] {{mvar|ε}},

<syntaxhighlight lang="ebnf">iota = "1" | "0" iota iota</syntaxhighlight>

so that for example {{val|0011011|fmt=none}} denotes <math>((\iota\iota)(\iota\iota))</math>, whereas {{val|0101011|fmt=none}} denotes <math>(\iota(\iota(\iota\iota)))</math>.

==Jot==
Jot is the [[regular language]] consisting of all sequences of 0 and 1,

<syntaxhighlight lang="ebnf">jot = "" | jot "0" | jot "1"</syntaxhighlight>

The semantics is given by translation to SKI expressions.
The empty string denotes <math>I</math>,
<math>w0</math> denotes <math>(([w]S)K)</math>,
where <math>[w]</math> is the translation of <math>w</math>,
and <math>w1</math> denotes <math>(S(K[w]))</math>.

The point of the <math>w1</math> case is that the translation satisfies <math>(([w1]A)B) = ([w](A B))</math> for arbitrary SKI terms <math>A</math> and <math>B</math>.
For example,
<math display="block">[w11100] = (([w1110]S)K) = (((([w111]S)K)S)K) = ((([w11](SK))S)K) = (([w1]((SK)S))K) = ([w](((SK)S)K)) = ([w]K)</math>
holds for arbitrary strings <math>w</math>.
Similarly,
<math display="block">[w11111000] = (((((([w11111]S)K)S)K)S)K) = ([w](((((SK)S)K)S)K)) = ([w]S)</math>
holds as well.
These two examples are the base cases of the translation of arbitrary SKI terms to Jot given by Barker,
making Jot a natural [[Gödel numbering]] of all [[algorithm]]s.

Jot is connected to Iota by the fact that <math>[w0] = (\iota[w])</math> and by using the same identities on SKI terms for obtaining the basic combinators <math>K</math> and <math>S</math>.

==Zot==
The Zot and Positive Zot languages command [[#Iota|Iota]] [[computation]]s, from [[Input (computer science)|input]]s to [[Input/output|output]]s by [[continuation-passing style]], in [[syntax]] resembling  [[#Jot|Jot]],

<syntaxhighlight lang="ebnf">
zot = pot | ""
pot = iot | pot iot
iot = "0" | "1"</syntaxhighlight>

where {{val|1}} produces the continuation <math>\lambda cL.L(\lambda lR.R(\lambda r.c(lr)))</math>,
and {{val|0}} produces the continuation <math>\lambda c.c\iota</math>,
and {{mvar|wi}} consumes the final input digit {{mvar|i}} by continuing through the continuation {{mvar|w}}.

==See also==
*[[Lambda calculus]]
*[[Combinatory logic]]
*[[Binary combinatory logic]]
*[[SKI calculus|SKI combinator calculus]]

==References==
{{Reflist}}

==External links==
* {{Official website|www.nyu.edu/projects/barker}}
* {{cite web|url=https://www.nyu.edu/projects/barker/Iota/ |title=Iota and Jot: the simplest languages? |last=Barker |first=Chris |website=The Esoteric Programming Languages Webring |archive-url=https://web.archive.org/web/20160823182917/http://semarch.linguistics.fas.nyu.edu/barker/Iota |archive-date=23 August 2016 |access-date=13 August 2004 |url-status=dead }}
* https://esolangs.org/wiki/Iota
* https://esolangs.org/wiki/Jot
* https://esolangs.org/wiki/Zot

{{DEFAULTSORT:Iota and Jot}}
[[Category:Esoteric programming languages]]
[[Category:Combinatory logic]]
[[Category:Algorithmic information theory]]
{{Esoteric programming languages}}